Runaway Robot Puzzle

[adum]

This puzzle challenges you to free your robot from a deadly maze. He starts in the upper-left corner, and has to escape to any of the green squares. You must program his path with the arrows before he starts moving. You hit the Go button and the robot then executes the instructions repeatedly, looping around when he reaches the end of what you programmed. Hopefully he makes it out alive!

In each puzzle there's a minimum number of instructions you need to give the robot. They are marked with dots in the squares. You'll know you have enough when the GO! button appears.

You may find that after a certain level, this puzzle gets a little hard to solve by hand! That is where a computer program may help you. You'll find the input and output parameters are easily parsed and generated.

Submit a Solution via an HTTP GET:
The URL for the puzzle is http://www.hacker.org/runaway/index.php
The URL will accept parameters in the query part of the URL that correspond to your registered account:
name=<username>
password=<password>

To submit a solution, use the following parameter:
path=<moves>
where the moves are a list of 'D' or 'R' for down or right.
For example, to submit a solution where your robot's instructions are {down, right, right}, you would do an HTTP GET on the following URL:

Code: Select all

http://www.hacker.org/runaway/index.php?name=<username>&password=<password>&path=DRR

[falcon2424]

That game looks great, graphically and I'm going to see what I can hack together tonight.

Is there an easy way to automate importing the map? (I'm not sure what I should be feeding into my parser.)

[adum]

hey falcon, importing the map should be pretty easy. look for the part:

Code: Select all

FVterrainString=.....X.

in the html. you also need FVboardX, FVboardY, FVinsMin, and FVinsMax.
the terrainString is the map, where an X is a blocked spot and a dot is an empty one. it's all one string, but you can break it up knowing boardX. (the first boardX characters make the first row, etc.)

submitting is a sequence of R for right, D for down.

good luck!

[falcon2424]

I can't believe I didn't notice that. Thanks for the tip. It's amazingly hypnotic to watch that little robot go across the board, especially when the board gets really big.

I guess the next step would be using some perl to automate the extraction of the map and parameters.

[adum]

hey snark, glad you like the problem solving idea! we have more puzzles on the way. some will be in similar formats, and some will be new types.

1) always just R and D. (we're thinking about a separate puzzle with U and L too, but that would be a different game)

2) they're related to the board size in general, but there's no hard and fast rule.

3) we won't guarantee any format will remain constant between games, but at the least things will be pretty similar =)

cheers,
adum

[falcon2424]

This puzzle is fascinating. I keep coming up with what looks like a decent method only to realize that there are massive possible improvements to my search algorithms.

So, great design job, there's a lot more to it than there seems.

(Hint to the people considering it, brute force solutions work great up until about level 100.)

[Captain Segfault]

I think you can tell what kind of algorithm a person is using by what level has been achieved. The people below about 30 are doing it by hand. Around 100-150 are using a brute force method of some sort, with the higher end maybe optimizing by using modularity. I suspect that all the people around 500 are doing something recursive.

Recursion doesn't really help you here. My brute force algorithm was more recursive than my 513 one.

On the other hand, recursion is a special case of a more general concept "reduce the problem to something you know how to solve" which is often just as useful for solving weird problems.

[Captain Segfault]

I do have an explicitly recursive routine which got me up to 503. Got too hard for it after that because of the overhead of making those calls, so I collapsed it into a single function call, which made it more efficient.

The overhead of making the calls would not make a big difference, unless you were doing something crazy like building a new board every call. As long as you spend O(1) on the function call itself, it isn't going to make a huge difference.

If we go beyond 513 I might rework my solution for some efficiency and/or some parallelism; it takes my Perl script about 9 minutes to solve 513.

[falcon2424]

It really seemed like my solution hit a wall at about level 500, too.

If I needed to go beyond level 513, I think I'd probably do more pre-processing of the map, as I think the bit that I already do got me a decent improvement in speed at relatively little cost.

----
Is there any chance that we could have a thread to talk about this from the perspective of people who've beaten the puzzle? I don't want to post spoilers, but I'm curious about what other people did.

[eza]

damn ... i dont understand...

[ShardFire]

Well I did all levels 41-513 in under an hour, and that was including several network problems I was having during that time with it disconnecting for no reason. Anyway, my algorithm was interesting in that it never used any kind of searching for paths, instead working on eliminating impossible paths as quickly as possible and what was left was a possible route. And the only data types I used were 2 arrays of bytes, a lot of integers and a few strings as well of course. My calculations appear to show that the last 100 levels or so were taking on average 8 seconds each, but I guess most of that time was spent downloading them. 99% of the time it seemed to be downloading on the earlier levels. Anyway, I programmed it just today and yesterday in VB.NET 2003 (and that should explain a lot of the speed problems that might exist).

Edit: I decided to run the program again without interruptions from 0-513, and it took 11 minutes and 50 seconds to get to this stage:

An unhandled exception of type 'System.Net.WebException' occurred in system.dll

Additional information: The remote server returned an error: (500) Internal Server Error.

It seemed to hang for quite a while (maybe 10 seconds) on lvl504 for some reason. Must have been a particularly difficult one. 513 however was solved in about a second (after it had been downloaded).