Best algorithms?

DaymItzJack · Post by **DaymItzJack** » Mon Jul 18, 2011 6:45 am

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.

gfoot · Post by **gfoot** » Mon Jul 18, 2011 10:59 am

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

megabreit · Post by **megabreit** » Mon Jul 18, 2011 11:07 am

My nearly none optimized perl script takes 231s for level 513... 100s took the "pre-optimization": probably the worst code I ever wrote

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

CodeX · Post by **CodeX** » Mon Jul 18, 2011 4:18 pm

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 100°C

DaymItzJack · Post by **DaymItzJack** » Mon Jul 18, 2011 5:51 pm

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.

tune2fs · Post by **tune2fs** » Tue Jul 26, 2011 7:22 pm

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.

tiwe · Post by **tiwe** » Tue Oct 11, 2011 3:37 pm

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.

da_hunta · Post by **da_hunta** » Mon Feb 20, 2012 1:12 pm

tried the hillclimbing algo optimizing the number of crashes ... works well till level 100 then it sucks^^

Allosentient · Post by **Allosentient** » Wed Feb 22, 2012 4:54 am

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

100°C? That seems a bit hot

CodeX · Post by **CodeX** » Wed Feb 22, 2012 10:38 am

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 100°C
100°C? That seems a bit hot

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 20°C

Besere · Post by **Besere** » Sat Mar 03, 2012 7:36 am

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.

irgangla · Post by **irgangla** » Thu Aug 23, 2012 8:19 pm

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

Hippo · Post by **Hippo** » Sat Oct 25, 2014 12:34 pm

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

.

go.to.hell · Post by **go.to.hell** » Tue Jun 30, 2015 9:57 pm

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

Wed Sep 23, 2015 6:13 pm

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

I thought it does not go beyond level 512, which when you have solved it shows as 513 in your profile. Is that correct?

hacker.org

Best algorithms?

Best algorithms?

Fun Fun Fun

A few results