hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Best algorithms?
Goto page 1, 2  Next
 
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle View previous topic
View next topic
Best algorithms?
Author Message
DaymItzJack



Joined: 29 Oct 2009
Posts: 106

Post Best algorithms? Reply with quote
For the people who have reached 513, how long did it take your program to run the actual solving code? (Ignoring web requests)

I just wrote one in C# today and with minimal effort of efficiency, my program took roughly 30 seconds for all the solving.
Mon Jul 18, 2011 6:45 am View user's profile Send private message
gfoot



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

Post Reply with quote
Is that for all the levels, or just level 513? My final algorithm, implemented in Python, solved all the levels in under two seconds each, and took about a minute to solve them all in sequence (without redownloading them).
Mon Jul 18, 2011 10:59 am View user's profile Send private message
megabreit



Joined: 03 Jan 2009
Posts: 141

Post Reply with quote
My nearly none optimized perl script takes 231s for level 513... 100s took the "pre-optimization": probably the worst code I ever wrote Smile But I never changed it because it was "fast enough for the job".
Hardware is Intel i750 with 2.6GHz. The damn thing was slower when I solved it 2 years ago...
Mon Jul 18, 2011 11:07 am View user's profile Send private message
CodeX



Joined: 17 Oct 2008
Posts: 350

Post Reply with quote
I think mine took about 0.08 seconds and was written in C that could have been improved by using a generator that would make the most likely to succeed maps first instead of going from one extremity to the other for each possible length. The code itself was actually quite simple and didn't employ anything fancy for threading or GPU use. Ran with Vista32 on a Core 2 Duo running at 2.1GHz on each core that happen to run at just 100C
Mon Jul 18, 2011 4:18 pm View user's profile Send private message
DaymItzJack



Joined: 29 Oct 2009
Posts: 106

Post Reply with quote
Roughly 30 seconds was for all 513 puzzles in a row. Mine also had no threading or gui, I did however try to reduce the number of prints (to 0) but that's no way cheating.
Mon Jul 18, 2011 5:51 pm View user's profile Send private message
tune2fs



Joined: 05 Mar 2009
Posts: 1

Post Reply with quote
My Algorithm in Python needed about 0.5 sec for solving a Level. For two it took him about 12 sec, I am not sure why.
With downloading the Levels it took him about 15min from Level 140 to 513.
Tue Jul 26, 2011 7:22 pm View user's profile Send private message
tiwe



Joined: 05 Mar 2009
Posts: 3

Post Reply with quote
I used a shell script for submitting results, downloading the next level and extracting the parameters.
The actual solving is done in single-threaded C.
Total CPU time (shell+C) for all levels is 30s in a 2.0GHz Core2. Most levels were solved in under 10ms, longest single-level runtime was 6.49s for 511.

The algorithm was developed after solving levels ~15-~40 with screen shots and GIMP.
Tue Oct 11, 2011 3:37 pm View user's profile Send private message
da_hunta



Joined: 08 Oct 2011
Posts: 2

Post Fun Fun Fun Reply with quote
Very Happy tried the hillclimbing algo optimizing the number of crashes ... works well till level 100 then it sucks^^
Mon Feb 20, 2012 1:12 pm View user's profile Send private message
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
CodeX wrote:
Ran with Vista32 on a Core 2 Duo running at 2.1GHz on each core that happen to run at just 100C


100C? That seems a bit hot Smile
Wed Feb 22, 2012 4:54 am View user's profile Send private message
CodeX



Joined: 17 Oct 2008
Posts: 350

Post Reply with quote
Allosentient wrote:
CodeX wrote:
Ran with Vista32 on a Core 2 Duo running at 2.1GHz on each core that happen to run at just 100C


100C? That seems a bit hot Smile
Sure is, the CPU heatsink is poorly attached using 4 push/twist locks (one of which broke). After putting on a load more thermal paste and laying the tower horizontal so gravity keeps it attached the temperature has dropped at least 20C
Wed Feb 22, 2012 10:38 am View user's profile Send private message
Besere



Joined: 12 Mar 2011
Posts: 12

Post Reply with quote
Mine solved each lvl under 2 seconds or less.

Can someone send me their algorithm? or code?
I'm not trying to cheat or anything, I beat all 513 levels. You can check my profile.

Someone mentioned a polynomial time algorithm to solve this and I really want to know what that algorithm looks like.
Sat Mar 03, 2012 7:36 am View user's profile Send private message
irgangla



Joined: 11 Sep 2009
Posts: 3

Post A few results Reply with quote
Finally I reached level 513 with some luck. I have a bug somewhere into my algorithm which I can not figure out at the moment, so I'm not able to solve the levels above 503 each time, but it seems there is some randomization into the levels so requesting a new version of the level helps sometime. This is the data from a run from level 1 to 503 a few minutes ago:

Download duration: 40.53 seconds
Maximum download duration: 40.53, average download duration: 5.218

Solving time for level 503: 0.774 seconds
Maximum solving duration: 6.057, average solving duration: 0.068
Thu Aug 23, 2012 8:19 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Reply with quote
My solving times are about 300ms (till level 505), except level 448 they were under 1s. Level 448 needed 2082ms.

I have searched for all program paths with the same endpoint at once, using "dynamic programming".
The puzzle is so easy and levels small that doing more tricks would be waste of time.

--- edit ---
now around 510 there is a bit slowdown. Solution for 513 needed 8419ms and solution for 514 took 8199ms Smile.
Sat Oct 25, 2014 12:34 pm View user's profile Send private message
go.to.hell



Joined: 25 Dec 2009
Posts: 5

Post Reply with quote
The average solution time with my Java program (690 lines, 141 for the solver) is 16 ms, 513 takes 779ms and 514 required with 1948ms nearly a quarter of the total time (8234ms).
Tue Jun 30, 2015 9:57 pm View user's profile Send private message
AMindForeverVoyaging
Forum Admin


Joined: 28 May 2011
Posts: 473
Location: Germany

Post Reply with quote
Hippo wrote:

--- edit ---
now around 510 there is a bit slowdown. Solution for 513 needed 8419ms and solution for 514 took 8199ms Smile.


I thought it does not go beyond level 512, which when you have solved it shows as 513 in your profile. Is that correct?
Wed Sep 23, 2015 6:13 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  Next
Page 1 of 2

 
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.