hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
I Will Be Execute
Goto page 1, 2  Next
 
Reply to topic    hacker.org Forum Index » Challenges View previous topic
View next topic
I Will Be Execute
Author Message
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post I Will Be Execute Reply with quote
This seems to cause an infinite loop no matter what I try. The "g" causes the program to restart and then ends up at the "g" again. I tried it both on my C# implementation and the javascript and got the same output
Sat Jun 07, 2008 6:28 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
well, you're getting into the slightly harder challenges now. it would be too trivial if you could just copy and paste into the javascript =)

adum
Sat Jun 07, 2008 6:56 am View user's profile Send private message Visit poster's website
bok
Site Admin


Joined: 30 Jan 2007
Posts: 24

Post Reply with quote
Nice to see that you have a C# implementation of the VM. Maybe you can post it to share with others?
Sun Jun 08, 2008 11:40 am View user's profile Send private message Send e-mail
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
I have only tested it with a few of the challenges so I can't say for sure if it works perfectly yet, but here is the file. I don't see any way to attach it so I will post the code here and see if someone can host it. Looks kind of messy here but if you copy and paste it into visual studio everything will format itself.

(in case you are wondering why I have a separate function for all 10 push1, push2, etc, it is to keep things simpler for the dictionary/delegate objects, since a delegate has to have the same signature)

Code:

using System;
using System.Collections.Generic;

namespace HOrgChallenges
{
    public delegate void FuncDelegate();

    public class HVM
    {
        static int MAX_CYCLES = 10000;
        static long MIN_INT = int.MinValue;
        static long MAX_INT = int.MaxValue;
       
        long[] memory = new long[16384];
        Stack<long> callStack = new Stack<long>();
        Stack<long> operandStack = new Stack<long>();
        long programCounter = 0;
        long cycleCounter = 0;
        string code;
       
       
        Dictionary<char, FuncDelegate> OPS;

        public HVM()
        {
            OPS = new Dictionary<char, FuncDelegate>();
            OPS.Add(' ', DoNothing);
            OPS.Add('p', DoPrintInt);
            OPS.Add('P', DoPrintChar);
            OPS.Add('0', Push0);
            OPS.Add('1', Push1);
            OPS.Add('2', Push2);
            OPS.Add('3', Push3);
            OPS.Add('4', Push4);
            OPS.Add('5', Push5);
            OPS.Add('6', Push6);
            OPS.Add('7', Push7);
            OPS.Add('8', Push8);
            OPS.Add('9', Push9);
            OPS.Add('+', DoAdd);
            OPS.Add('-', DoSub);
            OPS.Add('*', DoMul);
            OPS.Add('/', DoDiv);
            OPS.Add(':', DoCmp);
            OPS.Add('g', DoGoto);
            OPS.Add('?', DoGotoIfZero);
            OPS.Add('c', DoCall);
            OPS.Add('$', DoReturn);
            OPS.Add('<', DoPeek);
            OPS.Add('>', DoPoke);
            OPS.Add('^', DoPick);
            OPS.Add('v', DoRoll);
            OPS.Add('d', DoDrop);
            OPS.Add('!', DoEnd);
        }

        public void Push1()
        {
            Push(1);
        }
        public void Push2()
        {
            Push(2);
        }
        public void Push3()
        {
            Push(3);
        }
        public void Push4()
        {
            Push(4);
        }
        public void Push5()
        {
            Push(5);
        }
        public void Push6()
        {
            Push(6);
        }
        public void Push7()
        {
            Push(7);
        }
        public void Push8()
        {
            Push(8);
        }
        public void Push9()
        {
            Push(9);
        }
        public void Push0()
        {
            Push(0);
        }
        public void Push(long v)
        {
            if (v < MIN_INT || v > MAX_INT)
                throw new InvalidOperationException("Integer overflow");
            operandStack.Push(v);
        }
        public long Pop()
        {
            if (operandStack.Count == 0)
                throw new InvalidOperationException("Stack underflow");
            return operandStack.Pop();
        }
        public void DoPrintChar()
        {
            System.Console.Write((char)(Pop() & 0x7F));
        }
        public void DoPrintInt()
        {
            System.Console.Write(Pop().ToString());
        }
        public void DoAdd()
        {
            Push(Pop() + Pop());
        }
        public void DoSub()
        {
            long a = Pop();
            long b = Pop();
            Push(b - a);
        }
        public void DoMul()
        {
            Push(Pop() * Pop());
        }
        public void DoDiv()
        {
            long a = Pop();
            long b = Pop();
            Push(b / a);
        }
        private long cmp(long a, long b)
        {
            if (a < b)
                return -1;
            if (a > b)
                return 1;
            return 0;
        }
        public void DoCmp()
        {
            long a = Pop();
            long b = Pop();
            Push(cmp(b, a));
        }
        public void DoGoto()
        {
            programCounter += Pop();
        }
        public void DoGotoIfZero()
        {
            long offset = Pop();
            if (Pop() == 0)
                programCounter += offset;
        }
        public void DoCall()
        {
            callStack.Push(programCounter);
            programCounter = Pop();
        }
        public void DoReturn()
        {
            if((callStack.Count == 0))
                throw new AccessViolationException("Call Stack Underflow");
            programCounter = callStack.Pop();
        }
        public void DoPeek()
        {
            long addr = Pop();
            if (addr < 0 || addr >= memory.Length)
                throw new AccessViolationException("Memory read access violation @" + addr.ToString());
            Push(memory[addr]);
        }
        public void DoPoke()
        {
            int addr = (int)Pop();
            if(addr < 0 || addr >= memory.Length)
                throw new AccessViolationException("Memory read access violation @" + addr.ToString());
            memory[addr] = Pop();
        }
        public void DoPick()
        {
            long where = Pop();
            if (where < 0 || where >= operandStack.Count)
                throw new AccessViolationException("Out of stack bounds @" + where.ToString());
            Push(new Stack<long>(operandStack.ToArray()).ToArray()[(operandStack.Count-1-where)]);
            //Push(operandStack.ToArray()[-(1 - where)]);
           // Push(operandStack.ToArray()[operandStack.Count-1 - where]);
        }
        private void del(ref long[] array, long index)
        {
            for (long i = index; i < array.Length - 1; i++)
            {
                array[index] = array[index + 1];
            }
            array[array.Length - 1] = 0;
        }
        public void DoRoll()
        {
            long where = Pop();
            if (where < 0 || where >= operandStack.Count)
                throw new AccessViolationException("Out of stack bounds @" + where.ToString());
           
            long[] stack = new Stack<long>(operandStack.ToArray()).ToArray();
            //long v = stack[-(1 - where)];
            long v = stack[operandStack.Count - 1 - where];
            del(ref stack, (operandStack.Count - 1 - where));
            operandStack = new Stack<long>(stack);
            Push(v);
        }
        public void DoDrop()
        {
            Pop();
        }
        public void DoEnd()
        {
            programCounter = code.Length;
        }
        public void DoNothing()
        {
        }

        void LoadMemory(List<string> memList)
        {
            for (int i = 0; i < memList.Count; i++)
            {
                memory[i] = Int64.Parse(memList[i]);
            }
        }

        public void Run(string code, string mem, bool traceArg)
        {
            this.code = code;
            programCounter = 0;
            cycleCounter = 0;
            List<string> memList = new List<string>();
            if(mem.Length > 0)
                memList = Crypto.GetAllWords(mem);

            bool trace = traceArg;

            if (memList.Count > 0)
                LoadMemory(memList);

            char op_code = (char)0;
            try
            {
               
                while (programCounter != code.Length)
                {
                    op_code = code[(int)programCounter];
                    if (trace)
                    {
                        Console.Write("@" + programCounter.ToString() + " " + op_code.ToString() + " ");
                    }
                    programCounter++;
                    cycleCounter++;
                    if (cycleCounter > MAX_CYCLES)
                        throw new InvalidOperationException("Too many cycles");
                    OPS[op_code]();
                    if (programCounter < 0 || programCounter > code.Length)
                        throw new InvalidOperationException("Out of code bounds");
                    if (trace)
                    {
                        long[] operands = new Stack<long>(operandStack.ToArray()).ToArray();
                        System.Console.Write(" [");
                        for (int i = 0; i < operands.Length - 1; i++)
                        {
                            System.Console.Write(operands[i].ToString() + ",");
                        }
                        if (operands.Length > 0)
                            System.Console.Write(operands[operands.Length - 1].ToString() + "]\n");
                        else
                            System.Console.Write("]\n");
                    }

                }
            }
            catch (Exception e)
            {
                System.Console.Write("!Error: exception while executing I=" + op_code.ToString() + " PC=" +
                    (programCounter - 1).ToString() + " STACK_SIZE" +
                    (operandStack.Count).ToString() + "\n");

            }
        }
    }
}


[/code]
Sun Jun 08, 2008 4:49 pm View user's profile Send private message
abc



Joined: 02 Nov 2008
Posts: 12

Post Uncompleted?!! Reply with quote
Hi!
I just tried to solve the Challenge "I Will Be Execute".

First I copy and paste the complete Line:
79+3>111++<9+3>0<1+0>999**0<:6?084*-g1111++*<p

Result: !ERROR: illegal value

The Error happens after:
79+3>111++<9+3>0<

Ok - there's nothing in the Memory Stack.
Let's initialize the Memory Stack with some Value.
0-0,1-0

Then the program run to:
79+3>111++<9+3>0<1+0>999**0<:6?084*-
Then g adds S0 (Value: [-32]) to the program counter.
After that the rest fo the code: 1111++*<p

If I run the program with g it never ends.
If I delete g the result is: 25 (false answer)

Then I thought that the Programm Counter should be added +1;
The result will be that the program runs 32x.
Then it prints:
33x 25 (false answer)

At this time I think this program doesn't work...
So - what exactly shall I do in this challenge / I don't have a crystal ball...

abc
Fri Dec 05, 2008 7:24 pm View user's profile Send private message
MerickOWA



Joined: 07 Apr 2008
Posts: 182
Location: HkRkoz al KuwaiT 2019 HaCkEr 101

Post Reply with quote
Yea i also worked up a C# implementation of HVM because (at the time) I hadn't gotten python installed.

Very very similar to Allosentient, a bit more C# 3.0 features (just cause i'm trying to learn them).

Code:

    const int MAX_CYCLES = 10000;

    static int[] Memory = new int[16384];
    static Stack<int> CallStack = new Stack<int>();
    static List<int> OperandStack = new List<int>();
    static string Code = "";
    static int ProgramCounter = 0;
    static int CycleCounter = 0;

    static int Pop() {
      if ( Memory.Length == 0 ) throw new Exception( "stack underflow" );

      int indexLast = OperandStack.Count - 1;
      var item = OperandStack[indexLast];

      OperandStack.RemoveAt( indexLast );
      return item;
      }

    static void Push( int v ) {
      OperandStack.Add( v );
      }

    static void DoNothing() {
      }

    static void DoPrintInt() {
      Console.Write( Pop() );
      }

    static void DoPrintChar() {
      Console.Write( (char)(Pop() & 0x7F) );
      }

    static void DoAdd() {
      Push( Pop() + Pop() );
      }

    static void DoSub() {
      var a = Pop();
      var b = Pop();
      Push( b - a );
      }

    static void DoMul() {
      Push( Pop() * Pop() );
      }

    static void DoDiv() {
      var a = Pop();
      var b = Pop();
      Push( b / a );
      }

    static void DoCmp() {
      var a = Pop();
      var b = Pop();
      Push( (b < a ? -1 : (b > a ? 1 : 0)) );
      }

    static void DoGoto() {
      ProgramCounter += Pop();
      }

    static void DoGotoIfZero() {
      var offset = Pop();
      if ( Pop() == 0 ) ProgramCounter += offset;
      }

    static void DoCall() {
      CallStack.Push( ProgramCounter );
      ProgramCounter = Pop();
      }

    static void DoReturn() {
      ProgramCounter = CallStack.Pop();
      }

    static void DoPeek() {
      var addr = Pop();
      if ( addr < 0 || addr >= Memory.Length ) throw new Exception( "memory read access violation @" + addr );
      Push( Memory[addr] );
      }

    static void DoPoke() {
      var addr = Pop();
      if ( addr < 0 || addr >= Memory.Length ) throw new Exception( "memory write access violation @" + addr );
      Memory[addr] = Pop();
      }

    static void DoPick() {
      var where = Pop();
      if ( where < 0 || where >= OperandStack.Count ) throw new Exception( "out of stack bounds @" + where );
      var index = OperandStack.Count-1-where;
      Push( OperandStack[index] );
      }

    static void DoRoll() {
      var where = Pop();
      if ( where < 0 || where >= OperandStack.Count ) throw new Exception( "out of stack bounds @" + where );
      var index = OperandStack.Count-1-where;
      var v = OperandStack[index];
      OperandStack.RemoveAt( index );
      Push( v );
      }

    static void DoDrop() {
      Pop();
      }

    static void DoEnd() {
      ProgramCounter = Code.Length;
      }

    delegate void Operation();
    static Dictionary<char, Operation> OPS = new Dictionary<char, Operation> {
            {' ',  DoNothing },
            {'\r', DoNothing },
            {'\n', DoNothing },
            {'p',  DoPrintInt },
            {'P',  DoPrintChar },
            {'0',  () => Push(0) },
            {'1',  () => Push(1) },
            {'2',  () => Push(2) },
            {'3',  () => Push(3) },
            {'4',  () => Push(4) },
            {'5',  () => Push(5) },
            {'6',  () => Push(6) },
            {'7',  () => Push(7) },
            {'8',  () => Push(8) },
            {'9',  () => Push(9) },
            {'+',  DoAdd },
            {'-',  DoSub },
            {'*',  DoMul },
            {'/',  DoDiv },
            {':',  DoCmp },
            {'g',  DoGoto },
            {'?',  DoGotoIfZero },
            {'c',  DoCall },
            {'$',  DoReturn },
            {'<',  DoPeek },
            {'>',  DoPoke },
            {'^',  DoPick },
            {'v',  DoRoll },
            {'d',  DoDrop },
            {'!',  DoEnd }
            };

    static string ToPretty<T>( List<T> list ) {

      var sb = new StringBuilder();

      sb.Append( "[" );
      if ( list.Count > 0 ) {
        sb.Append( list[0] );
        foreach ( var i in list.Skip( 1 ) ) {
          sb.Append( ',' );
          sb.Append( i );
          }
        }
      sb.Append( "]" );

      return sb.ToString();
      }

    static void Main( string[] args ) {

      if ( args.Length < 2 ) {
        Console.WriteLine( "hvm [--init <init-mem-filename>] [--trace] <code-filename>\nThe format for the initial memory file is: cell0,cell1,..." );
        return;
        }

      bool trace = false;
      int arg = 0;
      while ( arg < args.Length ) {

        switch ( args[arg] ) {

          case "--init":
            ++arg;

            string data = File.ReadAllText( args[arg] );
            ++arg;

            var initial_memory = (
                from o in data.Split( ',' )
                select int.Parse( o )).ToArray();

            initial_memory.CopyTo( Memory, 0 );

            break;

          case "--trace":
            ++arg;
            trace = true;
            break;

          default:
            Code = File.ReadAllText( args[arg] );
            ++arg;
            break;
          }
        }

      char op_code = ' ';
      try {

        while ( ProgramCounter != Code.Length ) {
          op_code = Code[ProgramCounter];
          if ( trace ) Console.Error.Write( "@{0} {1} ", ProgramCounter, op_code );
          ++ProgramCounter;
          ++CycleCounter;
          if ( CycleCounter > MAX_CYCLES ) throw new Exception( "too many cycles" );

          OPS[op_code]();

          if ( ProgramCounter < 0 || ProgramCounter > Code.Length ) throw new Exception( "out of code bounds" );
          if ( trace ) Console.Error.WriteLine( ToPretty( OperandStack ) );
          }
        }
      catch ( Exception ) {
        Console.Error.WriteLine( "!ERROR: exception while executing I={0} PC={1} STACK_SIZE={2}", op_code, ProgramCounter-1, OperandStack.Count );
        }
      }

    bool Execute( string Code, int[] initialmemory, bool trace ) {

      bool retval = true;

      initialmemory.CopyTo( Memory, 0 );

      char op_code = ' ';

      try {
        ProgramCounter = 0;
        while ( ProgramCounter != Code.Length ) {
          op_code = Code[ProgramCounter];
          if ( trace ) Console.Error.Write( "@{0} {1} ", ProgramCounter, op_code );
          ++ProgramCounter;
          ++CycleCounter;
          if ( CycleCounter > MAX_CYCLES ) throw new Exception( "too many cycles" );

          OPS[op_code]();

          if ( ProgramCounter < 0 || ProgramCounter > Code.Length ) throw new Exception( "out of code bounds" );
          if ( trace ) Console.Error.WriteLine( ToPretty( OperandStack ) );
          }
        }
      catch ( Exception ) {
        retval = false;
        }

      return retval;
      }

Fri Dec 05, 2008 10:38 pm View user's profile Send private message
Belriel



Joined: 20 Dec 2008
Posts: 16

Post Reply with quote
Hm I don't get this challenge ... the output of this program depends on the initialization of the memory, there are 312 values that do not cause a "too many cycles" error, I have tried the minimum, maximum and some in between, but I don't believe I have to test all possible values. I built a loop to sum all output values for all input values that do not cause error, but nothing Sad. Can anyone give me a hint into the right direction?
Thu Jan 08, 2009 8:25 pm View user's profile Send private message
megabreit



Joined: 03 Jan 2009
Posts: 141

Post Reply with quote
Unfortunately I'm stuck here too for quite some time.
It's quite easy to find out what is done and in what input range.
But what to do with this bunch of numbers?
Is the result a word instead of a number describing the row.. or something?
Wed Jan 28, 2009 7:31 pm View user's profile Send private message
PeterS



Joined: 05 Mar 2009
Posts: 24

Post Reply with quote
seems like the challenges are getting easier Wink
it's a matter of seconds if you use the python implementation *hint hint*
Sun Mar 15, 2009 10:51 am View user's profile Send private message
megabreit



Joined: 03 Jan 2009
Posts: 141

Post Reply with quote
You're right, I found that out some weeks ago... My problem was, that at some occasions it was said, that the Javascript implementation should work for the challenges, but the Python implementation should be used for more serious approaches. This was enough for me to decide to stay with the Javascript thingy.
This was a false decision because this statement is simply wrong.
I don't want to say that the Javascript implementation sux, but it's pretty close to this Mad

Later this challenge I noticed that there is another reason to not use the Javascript hackvm:
endless loops are no fun if you need to kill/restart your browser again and again.

Conclusion: Don't use the Javascript hackvm for serious work like solving challenges Laughing
Sun Mar 15, 2009 2:35 pm View user's profile Send private message
ffaadd



Joined: 24 Feb 2009
Posts: 4

Post Reply with quote
i've managed to get all results for the different inputs, but i dont know how i have to submit them. Have someone a hint for me without given the answer?

ciao,
ffaadd
Sun Mar 15, 2009 3:38 pm View user's profile Send private message
PeterS



Joined: 05 Mar 2009
Posts: 24

Post Reply with quote
What inputs are you talking about? There is no input for this one, so there is only one correct result.
Mon Mar 16, 2009 9:25 am View user's profile Send private message
ffaadd



Joined: 24 Feb 2009
Posts: 4

Post Reply with quote
thank you peter!
i stuck on the idea that i have to init the script...
Mon Mar 16, 2009 10:58 am View user's profile Send private message
jonik555



Joined: 31 Aug 2009
Posts: 43
Location: Prague

Post Reply with quote
dont code anythink just interpret the program in your head it is obvious then what you have to do. Very Happy
Mon Mar 08, 2010 7:55 pm View user's profile Send private message
kaio



Joined: 23 Aug 2010
Posts: 3

Post Reply with quote
I just override the inital-memory with zeros and changed the loop counter to a value within the allowed cycles. The loop increments the result in a linear way, so you can simply calculate the result yourself. No code required here Smile
Mon Sep 20, 2010 12:59 am View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Challenges All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.