hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Runaway Robot Puzzle
Goto page Previous  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
Captain Segfault



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

Post Re: Languages? Reply with quote
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.
Wed Jun 27, 2007 9:07 am View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
hackapple



Joined: 20 Aug 2007
Posts: 1

Post Hard game Reply with quote
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.
Mon Aug 20, 2007 2:13 am View user's profile Send private message
alina



Joined: 25 Aug 2007
Posts: 242
Location: DarkNet

Post Re: Hard game Reply with quote
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
Sat Aug 25, 2007 5:53 pm View user's profile Send private message Send e-mail MSN Messenger
gfoot



Joined: 05 Sep 2007
Posts: 269
Location: Brighton, UK

Post Reply with quote
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.
Fri Sep 07, 2007 11:28 pm View user's profile Send private message
Captain Segfault



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

Post Reply with quote
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
Sat Sep 08, 2007 8:02 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
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?
Sun Sep 23, 2007 5:18 pm View user's profile Send private message
gfoot



Joined: 05 Sep 2007
Posts: 269
Location: Brighton, UK

Post Reply with quote
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
Tue Oct 09, 2007 7:59 pm View user's profile Send private message
Conkers_bfd



Joined: 12 Nov 2007
Posts: 1

Post Reply with quote
Got to 100 by hand, and now it doesnt let me see the board?
Tue Nov 13, 2007 2:49 am View user's profile Send private message
V4hn



Joined: 27 Nov 2007
Posts: 14

Post Reply with quote
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..

_________________
Wed Feb 13, 2008 9:04 pm View user's profile Send private message Visit poster's website
<<D.A.>>



Joined: 15 Aug 2007
Posts: 647
Location: nowhere

Post Re: Runaway Robot Puzzle Reply with quote
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??
Thu May 15, 2008 8:47 pm View user's profile Send private message Send e-mail AIM Address
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
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!
Thu May 15, 2008 10:04 pm View user's profile Send private message
Hephaestus



Joined: 17 May 2008
Posts: 5

Post Reply with quote
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?
Thu May 29, 2008 9:28 am View user's profile Send private message
The_Dark_Avenger



Joined: 11 Jun 2008
Posts: 115

Post Reply with quote
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
Wed Jun 11, 2008 11:54 pm View user's profile Send private message
s_e_m_u_d



Joined: 25 Nov 2008
Posts: 3
Location: jakarta-batam.indonesia

Post Reply with quote
eza wrote:
damn ... i dont understand...



idem za... Surprised Laughing

_________________
SEMUD HAS ENTERED
Tue Nov 25, 2008 6:15 am View user's profile Send private message Send e-mail Visit poster's website AIM Address Yahoo Messenger MSN Messenger
osterlaus



Joined: 02 Nov 2008
Posts: 20

Post Reply with quote
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...
Wed Dec 31, 2008 10:57 am View user's profile Send private message ICQ Number
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle All times are GMT
Goto page Previous  1, 2, 3, 4  Next
Page 2 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.