Runaway Robot Puzzle

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

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.

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

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

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

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?

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]

Last edited by gfoot on Mon Nov 03, 2008 11:38 pm; edited 1 time in total

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

GOTCHA!

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

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 Wink

. But 'till then,

go on playing with your code Cool

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

_________________

adum wrote:

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

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!

I havent actually quite finished all the levels just yet - chuggin away around 470 right now - but i think itll make it sometime today. I used a similar solution to gfoot and falcon2424 (preprocess board and then make small compressed boards from various possible instruction lengths). But I have this weird problem - some take about 16 milliseconds not counting download, and most are under a second, but some random ones take upwards of 10-20 mins for no apparent reason. Did anyone else get that or is it some obscure bug in my code?

	Allosentient wrote:
	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!

well, for forums it works, but here doesn't... had to use ultimate solution Very Happy

	eza wrote:
	damn ... i dont understand...

idem za... Surprised

_________________
SEMUD HAS ENTERED

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

I agree to you: Here are some hints given. But I'd like to discuss alternative solving strategies with you as I had come to level 166 with my algorithm - but it's getting very slow now and having found a solution for the last levels seems to contain some luck...