hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Runaway Robot Puzzle
Goto page 1, 2, 3, 4  Next
 
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle View previous topic
View next topic
Runaway Robot Puzzle
Author Message
adum



Joined: 19 Apr 2007
Posts: 390

Post Runaway Robot Puzzle Reply with quote
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
Fri May 04, 2007 6:38 pm View user's profile Send private message Visit poster's website
falcon2424



Joined: 30 Apr 2007
Posts: 30

Post Reply with quote
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.)
Fri May 04, 2007 11:48 pm View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
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!
Sat May 05, 2007 12:46 am View user's profile Send private message Visit poster's website
falcon2424



Joined: 30 Apr 2007
Posts: 30

Post Reply with quote
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.
Sat May 05, 2007 5:38 pm View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
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
Mon May 07, 2007 6:16 pm View user's profile Send private message Visit poster's website
falcon2424



Joined: 30 Apr 2007
Posts: 30

Post Reply with quote
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.)
Wed May 09, 2007 7:37 pm View user's profile Send private message
Captain Segfault



Joined: 05 May 2007
Posts: 67
Location: San Carlos, CA

Post Reply with quote
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.
Thu May 10, 2007 5:16 am View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
Captain Segfault



Joined: 05 May 2007
Posts: 67
Location: San Carlos, CA

Post Reply with quote
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.
Thu May 10, 2007 2:45 pm View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
falcon2424



Joined: 30 Apr 2007
Posts: 30

Post Reply with quote
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.
Thu May 10, 2007 7:25 pm View user's profile Send private message
eza



Joined: 21 May 2007
Posts: 1

Post Reply with quote
damn ... i dont understand...
Mon May 21, 2007 8:24 pm View user's profile Send private message AIM Address Yahoo Messenger ICQ Number
ShardFire



Joined: 30 May 2007
Posts: 26
Location: United Kingdom

Post Reply with quote
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).
Mon Jun 04, 2007 11:47 pm View user's profile Send private message
Captain Segfault



Joined: 05 May 2007
Posts: 67
Location: San Carlos, CA

Post Reply with quote
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.
Wed Jun 06, 2007 3:36 am View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
ShardFire



Joined: 30 May 2007
Posts: 26
Location: United Kingdom

Post Reply with quote
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.
Thu Jun 07, 2007 6:12 pm View user's profile Send private message
Captain Segfault



Joined: 05 May 2007
Posts: 67
Location: San Carlos, CA

Post Reply with quote
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.
Fri Jun 08, 2007 2:50 am View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
Stormx



Joined: 04 Jun 2007
Posts: 1

Post Languages? Reply with quote
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.
Tue Jun 26, 2007 8:08 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle All times are GMT
Goto page 1, 2, 3, 4  Next
Page 1 of 4

 
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.