the way a couple players have blown this puzzle away, it's pretty clear that there's no point going past 1000. (level 1000 took segfault 10 seconds or so.) so level 1000 is the end. congrats to captain segfault for getting there first!
adum
Puzzle ends at 1000
-
Captain Segfault
- Posts: 67
- Joined: Sat May 05, 2007 6:11 pm
- Location: San Carlos, CA
- Contact:
Re: Puzzle ends at 1000
Actually, it took the solver only 0.3313 seconds, although there was at least one level that took over 20.adum wrote: (level 1000 took segfault 10 seconds or so.)
Unlike runaway I'm absolutely certain that this problem is (in general) NP-hard. However, I suspect the expected running time of my solver against a random generated instance is a small polynomial.
There are a number of results (see eg http://citeseer.ist.psu.edu/broder91finding.html, which uses a much more complicated algorithm than mine) suggesting that writing a good generator for this problem is hard.
I still would not be surprised if my algorithm got stuck somewhere before 2000; the hard levels may be getting exponentially harder.
Woah, I posted a reply in the general puzzles forum (about the average case difficulty of Hamiltonian path finding being polynomial) not having checked this forum or the high scores. I knew my solver was very badly optimized, and it doesn't use all the possible tricks, but I'm still surprised by that speed - congrats Segfault.
Spoiler (select text to see):
I thought about Roy-Floyd for solving this, but after reading your post I started thinking... then I realized that Hamilton is brute force in graph-theorem, so it can't be polynomial at all. I'll stay with Roy Floyd or Kruskal in finding the longest road within a graph, until the length is n*n, meaning that every vertex was visited.
I thought about Roy-Floyd for solving this, but after reading your post I started thinking... then I realized that Hamilton is brute force in graph-theorem, so it can't be polynomial at all. I'll stay with Roy Floyd or Kruskal in finding the longest road within a graph, until the length is n*n, meaning that every vertex was visited.
Sry, I have several mistakes in my previous post. Thanks for a no-name user for telling me, that he couldn't get anywhere with that written there. Select text to read:
It's not Kruskal, it's Dijkstra with the shortest ways. And Roy-Floyd can't be used for negative cycles, thus no good for longest ways. So, use Dijkstra.
I wont edit my old post because it's too old for others notice the changes.
It's not Kruskal, it's Dijkstra with the shortest ways. And Roy-Floyd can't be used for negative cycles, thus no good for longest ways. So, use Dijkstra.
I wont edit my old post because it's too old for others notice the changes.
My algorithm just traverses a well chosen path and than I try simple path improvements without big bruteforce (for kxk square it finds path of length roughly k^2 in O(k^4) worst case). Adding some randomness to tie breaking and restarting when not successfull, the code went to level 448 overnight. Only levels ending on digit 8 were causing problems.
(Actually I bet the time is better than O(k^3) in most cases).
I am planning to extend the path improvements set a bit for the next try. (I think the running time for one try will remain O(k^4).)
I still do not filter edges.
(Actually I bet the time is better than O(k^3) in most cases).
I am planning to extend the path improvements set a bit for the next try. (I think the running time for one try will remain O(k^4).)
I still do not filter edges.
OK it's difficult to bound well the worst case running time of one my attempt, upper bound for nxn board is O(n^{12}). I tooks 2-10 minutes on levels near 650 ending 8. The attempt fails on thesse levels by about 10 squares. (One of about 10 attempts wents through).
... but the probability going through decreases. For other levels the attempts fail very rarely (3 times alltogether for *7 levels till 677, never for other than *7,*8 levels).
I could decrease the upper bound by chosing better data structure, let us see it will be needed ...
OK
removing logging reduced the attempt time to about 1s 
so ...
... I had to increase the stack size for 898 level ...
On levels above 900, fails are by about 40 squares so several hundred attempts are required ...
Level 978 requires more than 10000 attempts ... I wish I have codded it better considering garbage collector requirements ... let us see the level 1000 would be beated overnight (or 2) before I would have time to improve it... (I have one other cheap improvement on mind).
After finishing the level 1000, I have removed all the debug logging and run it once again from level 0. I have mesured time starting after parsing the html, but before the graph is created, I have counted number of required tries.
first level requiring more than 1s (1329ms) was 124, next (1466ms) was 138.
Levels till 200 were getting slower but required less than 3s.
Starting from level 200 times were near 20ms.
First level requiring more than 1 try was 337 requiring 2 tries with solution time 31ms, that repeated on 348. Third level requiring more than 1 try was 398 with 9 tries and solution time 46ms.
First level above 200 requiring more than 1s (1170ms) was level 788 with 60 tries.
Next was 798 with (6084ms) and 227 tries.
Next was 818 with (35365ms) and 491 tries.
828 required (2309ms) and 75 tries.
838 required (2075ms) and 93 tries.
848 required (3276ms) and 133 tries.
858 required (2714ms) and 133 tries.
868 required (5039ms) and 172 tries.
878 required (22922ms) and 436 tries.
888 required (13932ms) and 527 tries.
898 required (430922ms) and 935 tries.
908 required (5026ms) and 185 tries.
918 required (139012ms) and 3807 tries.
928 required (171813ms) and 3030 tries.
938 required (297257ms) and 2553 tries.
948 required (378847ms) and 12224 tries.
968 required (785543ms) and 15395 tries.
978 required (12457897ms) and 88439 tries!!!
988 required (15865ms) and 335 tries.
998 required (1687545ms) and 38999tries.
So for me 978 looked most difficult with 998 close to it.
On first run ...
998 required 13452 tries,
988 required 5806 tries,
978 required 76706 tries,
968 required 3995 tries.
what looks like confirmation of it.
Of course other algorithms could have problems with other graph features ...
... but the probability going through decreases. For other levels the attempts fail very rarely (3 times alltogether for *7 levels till 677, never for other than *7,*8 levels).
I could decrease the upper bound by chosing better data structure, let us see it will be needed ...
OK
removing logging reduced the attempt time to about 1s so ...... I had to increase the stack size for 898 level ...
On levels above 900, fails are by about 40 squares so several hundred attempts are required ...
Level 978 requires more than 10000 attempts ... I wish I have codded it better considering garbage collector requirements ... let us see the level 1000 would be beated overnight (or 2) before I would have time to improve it... (I have one other cheap improvement on mind).
After finishing the level 1000, I have removed all the debug logging and run it once again from level 0. I have mesured time starting after parsing the html, but before the graph is created, I have counted number of required tries.
first level requiring more than 1s (1329ms) was 124, next (1466ms) was 138.
Levels till 200 were getting slower but required less than 3s.
Starting from level 200 times were near 20ms.
First level requiring more than 1 try was 337 requiring 2 tries with solution time 31ms, that repeated on 348. Third level requiring more than 1 try was 398 with 9 tries and solution time 46ms.
First level above 200 requiring more than 1s (1170ms) was level 788 with 60 tries.
Next was 798 with (6084ms) and 227 tries.
Next was 818 with (35365ms) and 491 tries.
828 required (2309ms) and 75 tries.
838 required (2075ms) and 93 tries.
848 required (3276ms) and 133 tries.
858 required (2714ms) and 133 tries.
868 required (5039ms) and 172 tries.
878 required (22922ms) and 436 tries.
888 required (13932ms) and 527 tries.
898 required (430922ms) and 935 tries.
908 required (5026ms) and 185 tries.
918 required (139012ms) and 3807 tries.
928 required (171813ms) and 3030 tries.
938 required (297257ms) and 2553 tries.
948 required (378847ms) and 12224 tries.
968 required (785543ms) and 15395 tries.
978 required (12457897ms) and 88439 tries!!!
988 required (15865ms) and 335 tries.
998 required (1687545ms) and 38999tries.
So for me 978 looked most difficult with 998 close to it.
On first run ...
998 required 13452 tries,
988 required 5806 tries,
978 required 76706 tries,
968 required 3995 tries.
what looks like confirmation of it.
Of course other algorithms could have problems with other graph features ...
I am just doing this challenge now and I too noticed that level ending with 8 cause problems and take way longer (before I added randomness to my code, I couldn't even solve levels ending with 8, starting from 368).
Also I still have a graphic representation of the level in my terminal and the levels ending on 8 look distinctly different from all other levels. If I can find out what that distinction is, I might be able to improve my code for it though.
Also I still have a graphic representation of the level in my terminal and the levels ending on 8 look distinctly different from all other levels. If I can find out what that distinction is, I might be able to improve my code for it though.