Exclusive Or (HVM Coding Challenge)

Post Reply
theStack
Posts: 72
Joined: Sun Nov 02, 2008 12:46 am

Exclusive Or (HVM Coding Challenge)

Post by theStack »

Hi folks,

I just finished my HVM code for evaluating the bitwise XOR between two operands.
However I got an Integer overflow as server response because I used 2^31 in my code which is of course simply too large when the 32-bit integer is signed.
So my question is: can I always surely assume that the MSB (Bit 31) of the two operands in all the tests I have to pass is zero, which means that the integer is positive?
The questions says
You have to XOR two positive integers placed in memory locations 0 and 1.
so I assumed the MSB is always zero, but maybe this sentence means those two operands are seen as unsigned integers and it could be that the MSB is set? :roll:

Greetings,
theStack
tails
Posts: 191
Joined: Tue Jun 10, 2008 7:51 pm
Location: Tokyo

Re: Exclusive Or (HVM Coding Challenge)

Post by tails »

Hi,

You can treat those integers as signed and positive.
theStack
Posts: 72
Joined: Sun Nov 02, 2008 12:46 am

Post by theStack »

Okay thanks, challenge solved.

But one thing, in my opinion the server output could be improved;
why? Well, after seeing that 2^31 is too large and changing the code to ignore the MSB I tested
it again on my local computer and it worked fine.

However, the server told me "2 test(s) passed", which was obviously not enough.
So after getting this message you think that the _semantics_ of the code is wrong and there must be an error somewhere in your algorithm which performs the XOR operation.
But there wasn't, the problem was that my code took too many cycles (because of my intensive use of the space operator, or NOP operator or however you call it)!

That was just a guess from me, the server didn't tell me that, so I removed some spaces and voila, it worked.

So, the problem is that the server obviously prints out detailled error messages (such as INTEGER OVERFLOW, TOO MANY CYCLES...) only during in the first test, assuming that in later tests it won't come up again anyway.

But the number of cycles does of course depend on the input!

So that could be fixed.

But anyway, nice challenge, was very fun to code :D
so1us
Posts: 4
Joined: Wed Sep 01, 2010 5:30 pm

Post by so1us »

I am also having difficulties with the Exclusive Or Challenge. I wrote the code, and did not bother about how much cycles it takes.. my solution is now about 3300 characters long, and it works fine on my computer.

But when i enter my solution and click "submit", i am downloading the chal.php file instead ^^ (which is saved as an empty file)

maybe i will try again with a shorter solution
pSub
Posts: 3
Joined: Tue May 26, 2009 11:28 am
Location: ZZZZZZZZ

Post by pSub »

so1us wrote: my solution is now about 3300 characters long, and it works fine on my computer.
I hope you didn't coded this solution by hand, because I find my 105 character (including with spaces) solution quit confusing and write-only.
I dont't know why you're downloading the chal.php file, the challenge works with my solution.

Good luck and maybe take paper and pencil to find a shorter solution :)
so1us
Posts: 4
Joined: Wed Sep 01, 2010 5:30 pm

Post by so1us »

got it now, shorter program is accepted... though it looks awful :D
think i also forgot to delete the comments, since the original HVM just throws "invalid instruction" when encountering comments
Karian
Posts: 75
Joined: Wed Jan 09, 2008 10:21 am

Post by Karian »

so1us wrote:got it now, shorter program is accepted... though it looks awful :D
think i also forgot to delete the comments, since the original HVM just throws "invalid instruction" when encountering comments
there exists no such thing as comments in HVM. Everything is considered code, so if the character isn't in the list of possible codes, when it is encountered, it is seen as an invalid character.
so1us
Posts: 4
Joined: Wed Sep 01, 2010 5:30 pm

Post by so1us »

Karin wrote:there exists no such thing as comments in HVM
true, but then the code isnt readable after a few lines...
its easy to change the python file to accept comments, e.g. i added

Code: Select all

def Comment():
    global ProgramCounter
    while Code[ProgramCounter] != '\n': ProgramCounter += 1
    ProgramCounter += 1
to the definitions, and then something like
'#': Comment
to where the commands are specified

im sure some people here had the same idea, because it makes work so much easier
Karian
Posts: 75
Joined: Wed Jan 09, 2008 10:21 am

Post by Karian »

There you did it again, you modified the programming language. HVM only has one line of code, so there are no problems with readability :)

Adding comments like that can indeed work for the simpler problems, but it will probably get you into trouble when you start using the 'c'/'$' operations. Replacing them with spaces usually isn't a good idea if you want to keep your program small to fit in the maximum number of cycles.

If you would change something, I would create a tool that strips out all comments (and maybe help you doing some other things) so that it transforms your (pseudo) code with comments in a real HVM program, keep the HVM implementation as is and check if it runs correctly.
Post Reply