Ilmari Heikkinen wrote: > 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 > > [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.037s > user 0m0.029s > sys 0m0.008s > > Anyone want to provide the shortest solution to that? ;-) Beautiful! So many bignums, so few cycles... Would be interesting to see your heuristic solution applied to something human, like 222->999. I think we have to rephrase > Anyone want to provide the shortest solution to that? ;-) to Anyone want to provide a shorter solution to that? Christer -- Posted via http://www.ruby-forum.com/.