On Sun, Jan 01, 2006 at 06:23:08PM +0900, Ilmari Heikkinen wrote: } On 1/1/06, Dominik Bathon <dbatml / gmx.de> wrote: } > } > $ time ruby num_maze.rb 22222 99999 } > [22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87, 89, } > 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496, 12498, } > 24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999] } > } > real 0m1.768s } > user 0m1.725s } > sys 0m0.022s } > } > ;-) } } I wrote a heuristic solver by abusing the properties of the } mathematical problem. It doesn't find the shortest transformation } sequence but runs pretty fast. } } $ time ruby numpuz.rb 150128850109293 8591982807778218492 [...] } real 0m0.037s } user 0m0.029s } sys 0m0.008s } } Anyone want to provide the shortest solution to that? ;-) Whatever you're doing, I'm doing much the same thing. I get the identical solution in almost identically the same time (note: Dual G4 800): real 0m0.037s user 0m0.028s sys 0m0.009s I wouldn't call my solver heuristic, though. There is exactly one heuristic optimization. Other than that it is pretty much a straight analysis of the problem, with a nasty cleanup at the end to remove path loops. By the way, I can't get to http://swaits.com/articles/2005/12/31/ruby-quiz-60-test-cases at the moment. It seems to be down. Would anyone like to post some canonical test cases to the list? --Greg