From: Ilmari Heikkinen Date: 2006-01-01T18:23:08+09:00 Subject: Re: [QUIZ] Numeric Maze (#60) On 1/1/06, Dominik Bathon 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 themathematical problem. It doesn't find the shortest transformationsequence but runs pretty fast. $ time ruby numpuz.rb 150128850109293 8591982807778218492 [150128850109293, 300257700218586, 300257700218588, 150128850109294,150128850109296, 75064425054648, 37532212527324, 18766106263662,18766106263664, 9383053131832, 4691526565916, 2345763282958,2345763282960, 1172881641480, 586440820740, 293220410370,293220410372, 146610205186, 146610205188, 73305102594, 73305102596,36652551298, 36652551300, 18326275650, 18326275652, 9163137826,9163137828, 4581568914, 4581568916, 2290784458, 2290784460,1145392230, 1145392232, 572696116, 286348058, 286348060, 143174030,143174032, 71587016, 35793508, 17896754, 17896756, 8948378, 8948380,4474190, 4474192, 2237096, 1118548, 559274, 559276, 279638, 279640,139820, 69910, 69912, 34956, 17478, 17480, 8740, 4370, 4372, 2186,2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,7628, 7630, 15260, 15262, 30524, 61048, 122096, 122098, 244196,244198, 488396, 976792, 976794, 1953588, 1953590, 3907180, 7814360,7814362, 15628724, 31257448, 31257450, 62514900, 62514902, 125029804,250059608, 250059610, 500119220, 1000238440, 1000238442, 2000476884,2000476886, 4000953772, 4000953774, 8001907548, 16003815096,16003815098, 32007630196, 32007630198, 64015260396, 128030520792,256061041584, 256061041586, 512122083172, 1024244166344,1024244166346, 2048488332692, 2048488332694, 4096976665388,4096976665390, 8193953330780, 8193953330782, 16387906661564,32775813323128, 65551626646256, 131103253292512, 131103253292514,262206506585028, 524413013170056, 1048826026340112, 1048826026340114,2097652052680228, 4195304105360456, 4195304105360458,8390608210720916, 16781216421441832, 33562432842883664,67124865685767328, 67124865685767330, 134249731371534660,134249731371534662, 268499462743069324, 268499462743069326,536998925486138652, 536998925486138654, 1073997850972277308,1073997850972277310, 2147995701944554620, 2147995701944554622,4295991403889109244, 4295991403889109246, 8591982807778218492] real 0m0.037suser 0m0.029ssys 0m0.008s Anyone want to provide the shortest solution to that? ;-)