Runaway Robot Puzzle

[Captain Segfault]

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.

[ShardFire]

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.

[Captain Segfault]

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.

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.

[Stormx]

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.

[Captain Segfault]

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.

What's causing your speed cap is your algorithm. Implementing it in hand optimized assembler isn't going to get you *that* much further. You can probably hit 513 with a better algorithm in your language; assuming PHP-cli is within a factor of 10 of Perl, my algorithm ported to it would finish runaway within a day or two.

[hackapple]

I began to feel or interesting, and slowly continue to play, I feel it will be difficult to move with the brain.
Carefully look at, no clue. Many thought, but also want to point out things.

[alina]

I began to feel or interesting, and slowly continue to play, I feel it will be difficult to move with the brain.
Carefully look at, no clue. Many thought, but also want to point out things.

i found it the same ..it is quite nice..

[gfoot]

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

It's an interesting problem, because you can get to various stages with progressively more scalable algorithms, and it's not always a matter of starting from scratch - in some cases the tweaks were relatively minor.

I'm now in a position where I can solve any puzzle in under 1.5 seconds. Only three of the 513 levels take longer that 1 second, and I can solve all of them (from predownloaded copies) in under a minute. It's a shame the server can't produce bigger boards - I'm wondering how far my algorithm actually would scale now.

Interestingly, I got to level 511 on an NP algorithm (refactored on level 98, and optimised to reduce memory usage by level 200) - some levels took a while, though (e.g. 5/20/40 minutes). Level 511, however, took over a day and still didn't get a solution - something about that one was particularly stressing my algorithm's lack of scalability.

It was only a relatively simple change to one of the lower level routines to get it to the point it's at now. I think that's what's interesting here - relatively simple tweaks to the algorithm can have such dramatic (and visible) effects.

Level 504 came about 15th for me, in terms of time taken, and 512/513 are the top two. It's interesting if different "good" algorithms have trouble on different levels - I guess it could be down to either randomization of generated levels, or fairly arbitrary preferences in the algorithms (e.g. prefer longer or shorter solutions, prefer horizontal before vertical moves).

In case it's of any interest, my solver is written in Python (which I'm not very experienced with), with a shell script harness to fetch pages and submit the solutions the script works out. Python's not the fastest language in the world, but I agree with points others have made - it's mostly about the algorithm, not the language. However, bad use of any language can cause terrible performance - especially when it comes to data structures.

[Captain Segfault]

Interestingly, I got to level 511 on an NP algorithm

Nitpick: algorithms aren't NP. Languages/problems are NP. NP does not mean "non polynomial".

[falcon2424]

I'm kind of curious how other people solved this and got their algorithms to be so fast.

I know that some of the key components of mine were a bit of pre-processing on the entire board to identify unreachable squares. Then I 'collapsed' the board for each of the possible legal ending points of a single iteration of a solution.

Did everyone else use something like this, too?

[gfoot]

I didn't bother identifying unreachable areas - it was no gain for me. My algorithm would have given up before looking at them anyway.

I think you're already doing roughly the same things as me. The operations are all pretty cheap, and it scales well. I'd be interested to hear if anyone has anything better. In practice I think board size doesn't bother it much, but sequence length ends up most significant.

[edit: cut out specific solution information]

[Conkers_bfd]

Got to 100 by hand, and now it doesnt let me see the board?

[V4hn]

GOTCHA!

Quite optimized C++ with an bash-interface for down-/uploading

I started using a simple recursive BF 'till Level 100.
Optimized it by implementing BF iterative and adding preprocessing of the map 'till Level 161
Then made up a completely new - iterative - algorithm - just reused the preprocessing of the map
and implemented some more small improvements..
If the number of levels in here will go beyond 700, I may think about some other improvements,
which will start to be useful by that level . But 'till then,

go on playing with your code

V4hn

remark _for_ the moderators: i think this thread gives away too much information
on the well-scaling algorithms, even when i read it after coding mine...
may someone removes at least some of the information given?
After all it takes a lot of fun out of the coding, if you know exactly what to do..

[<<D.A.>>]

Code: Select all

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

i have a little problem with logging in... there are special symbols in my username, < and >, which result in incorrect username... is there any solution to such a problem??

[Allosentient]

Hello,

Replace < with %3C
Replace > with %3E

If there is a way to fix it on your end, that is what will work.

You can find a complete chart here:
http://www.ascii.cl/htmlcodes.htm

Best of luck!