Runaway Robot Puzzle

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:
	http://www.hacker.org/runaway/index.php?name=<username>&password=<password>&path=DRR

Last edited by adum on Mon May 07, 2007 8:55 pm; edited 1 time in total

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.)

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

	Code:
	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!

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.

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

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.)

	snarkophilus wrote:
	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.

	snarkophilus wrote:
	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. Smile

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.

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.

damn ... i dont understand...

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). Wink

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:

	Quote:
	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).

	ShardFire wrote:
	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.

There is a fairly straightforward polynomial time algorithm for this problem. With maybe the exception of mortalcoil, the others are NP hard.

Also, I'd expect VB.net to have decent performance. I would be surprised if you gained more than a factor of two just by switching languages, and a factor of two isn't even a level in any of the others.

Sorry, but could you explain how you came to the conclusion that the others are NP hard? Well, the modulo puzzle seems NP to me, not sure about the others.

	ShardFire wrote:
	Sorry, but could you explain how you came to the conclusion that the others are NP hard? Well, the modulo puzzle seems NP to me, not sure about the others.

They're all NP (="easily verified"), of course; unless you can generate boards with known unique solutions the problems all need to be easily verified. Smile

I haven't actually constructed a proof for Modulo, but I think you can easily reduce SAT to it by building some sort of circuit widget.

Bricolage is a variant of clickomania/same game. Demaine (the young master of proving games are hard) et al showed it was NP hard in nontrivial cases a few years ago; see http://theory.csail.mit.edu/~edemaine/clickomania/. Reducing clickomania to bricolage is straightforward and left as an exercise to the reader.

Mortalcoil is the only one I'm not convinced of. I'd be surprised if it weren't, but I don't have any proof, just a few ideas as to how one might start such a proof.

I wrote what I considered to be a fairly good method - first remove all impossible areas of the map, then loop through possible scenarios, building up an array of non-rubbish paths. I initially built a non-learning app which got me to lvl 70 after a couple of hours.

Issue is that I built it in PHP-cli, which is what is causing the speed cap on mine. I might learn perl to see if I can get it up to speed.