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