From: Gregory Seidman Date: 2006-01-02T09:09:26+09:00 Subject: Re: [SOLUTION] Numeric Maze (#60) This is my first Ruby quiz. I was hoping to have the whole thing done by the end of the first 48 hours, but I kept getting hung up on edge cases. I did figure out the binary approach on my own, though. On Mon, Jan 02, 2006 at 08:42:56AM +0900, Reinder Verlinde wrote: [...] } I think one should look at the mathematical side of the problem first. } Here are some starting ideas: } } - write both the starting and the target number in binary } - notice that the three operators do the following: } - add a zero to the right = left shift the number one position } - remove a zero from the right = right shift the number one position } - flip a bit in the one-but-rightmost position, possibly changing } consecutive ones to zeroes to the left of this bit [...] } I think logic like this will lead to a better understanding of the } problem, and possibly to more efficient solutions. This is exactly what I started from. My solution involves no search algorithm. It is entirely rule-based, including two optimization rules which could be called heuristic. (My code is at the end of this message.) The optimization rules are that two adds are cheaper than (and equal to) half-add-double, and four adds are cheaper than (and equal to) half-half-add-double-double. I'm pretty sure the results are guaranteed to be optimal, too. } For instance: I would guess that many of the optimal solutions are } rather dull, ending in a series of ('*2') or ('+2', '*2') operations to } shift in zero and one bits, followed by a single '/2' if the target } value is odd (WARNING: this is just a hunch; I may be completely wrong } here) Yeah, that's what I'm seeing. Take a look at some results (code below the line of ####): % ruby test60.rb 2 9 [2, 4, 8, 16, 18, 9] Ops = 5: dddah real 0m0.022s user 0m0.017s sys 0m0.006s % ruby test60.rb 9 2 [9, 18, 20, 10, 12, 6, 8, 4, 2] Ops = 8: dahahahh real 0m0.023s user 0m0.017s sys 0m0.008s % ruby test60.rb 999 222 [999, 1998, 2000, 1000, 500, 250, 252, 126, 63, 65, 67, 69, 71, 142, 144, 72, 36, 38, 19, 21, 23, 25, 27, 54, 108, 110, 220, 222] Ops = 27: dahhhahhaaaadahhahaaaaddada real 0m0.023s user 0m0.018s sys 0m0.005s % ruby test60.rb 222 999 [222, 224, 112, 114, 116, 118, 120, 122, 124, 248, 496, 498, 996, 998, 1996, 1998, 999] Ops = 16: ahaaaaaaddadadah real 0m0.022s user 0m0.015s sys 0m0.007s % ruby test60.rb 32 48 [32, 16, 18, 20, 22, 24, 48] Ops = 6: haaaad real 0m0.021s user 0m0.013s sys 0m0.008s % ruby test60.rb 48 32 [48, 24, 26, 28, 30, 32] Ops = 5: haaaa real 0m0.022s user 0m0.014s sys 0m0.008s % ruby test60.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, 22, 24, 26, 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] Ops = 171: dahahhhahhhahhhahahahahahahahahahhahahhhahahahhhahahhahhahhahahahhahahahhaaaaadadadadddadadadadddadaddadaddaddadaddaddadadaddadadddaddadadadaddddadddaddaddddadadadadadadad real 0m0.039s user 0m0.032s sys 0m0.007s % ruby test60.rb 8591982807778218492 150128850109293 [8591982807778218492, 4295991403889109246, 4295991403889109248, 2147995701944554624, 1073997850972277312, 536998925486138656, 268499462743069328, 134249731371534664, 67124865685767332, 33562432842883666, 33562432842883668, 16781216421441834, 16781216421441836, 8390608210720918, 8390608210720920, 4195304105360460, 2097652052680230, 2097652052680232, 1048826026340116, 524413013170058, 524413013170060, 262206506585030, 262206506585032, 131103253292516, 65551626646258, 65551626646260, 32775813323130, 32775813323132, 16387906661566, 16387906661568, 8193953330784, 4096976665392, 2048488332696, 1024244166348, 512122083174, 512122083176, 256061041588, 128030520794, 128030520796, 64015260398, 64015260400, 32007630200, 16003815100, 8001907550, 8001907552, 4000953776, 2000476888, 1000238444, 500119222, 500119224, 250059612, 125029806, 125029808, 62514904, 31257452, 15628726, 15628728, 7814364, 3907182, 3907184, 1953592, 976796, 488398, 488400, 244200, 122100, 61050, 61052, 30526, 30528, 15264, 7632, 3816, 1908, 954, 956, 478, 480, 240, 120, 60, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 25, 27, 29, 31, 33, 66, 68, 136, 272, 544, 546, 1092, 2184, 4368, 8736, 8738, 17476, 34952, 34954, 69908, 139816, 139818, 279636, 559272, 1118544, 1118546, 2237092, 2237094, 4474188, 8948376, 17896752, 35793504, 35793506, 71587012, 71587014, 143174028, 286348056, 572696112, 572696114, 1145392228, 2290784456, 4581568912, 9163137824, 18326275648, 36652551296, 73305102592, 146610205184, 293220410368, 586440820736, 586440820738, 1172881641476, 1172881641478, 2345763282956, 4691526565912, 4691526565914, 9383053131828, 9383053131830, 18766106263660, 37532212527320, 37532212527322, 75064425054644, 75064425054646, 150128850109292, 300257700218584, 300257700218586, 150128850109293] Ops = 157: hahhhhhhhahahahhahhahahhahahahhhhhahhahahhhahhhhahhahhhahhahhhahhhahahhhhhahahhhhaaaaaaaaaahaaaadadddaddddaddaddadddadaddddadadddaddddddddddadaddadaddadaddah real 0m0.039s user 0m0.030s sys 0m0.010s (All times on a dual G4 800.) ##### test60.rb ################################################################ require '60' include NumericMazeSolver src = ARGV[0].to_i dst = ARGV[1].to_i solution, ops = Solver.new(src, dst).solve p solution puts "\nOps = #{solution.length-1}: #{ops}" ##### 60.rb #################################################################### module NumericMazeSolver module BitHelpers def bit_len(num) return num.to_s(2).length end end class NumericPath attr_reader :result, :ops def initialize(s) @result = [s] @ops = '' end def reset(s = nil) @result.slice!(1, @result.length) @result[0] = s if s @ops = '' end def cur @result.last end def src @result.first end def add_two @result << (cur + 2) @ops << 'a' #p @result end def double @result << (cur << 1) @ops << 'd' #p @result end def halve c = cur fail "Trying to halve an odd number: #{c}" unless (c % 2) == 0 c >>= 1 @result << c @ops << 'h' #p @result end def add_one double add_two halve end end class Solver include BitHelpers def validate(src, dst) fail "We only deal with integers." unless (dst.kind_of? Integer) && (src.kind_of? Integer) fail "Not dealing with negative numbers" if (dst<0) || (src<0) fail "Can't get to zero from a positive number." if (dst==0) && (src>0) end def initialize(src, dst) validate(src, dst) @dst = dst @dst_bit_len = bit_len(@dst) @result = NumericPath.new(src) end def shifted_diff tmpsrc = @result.cur tmpdst = @dst src_bit_len = bit_len(tmpsrc) shift = src_bit_len - @dst_bit_len if shift < 0 tmpsrc >>= shift #really a left shift, since shift is negative else tmpdst <<= shift end xor_not_sub = tmpdst < tmpsrc diff = xor_not_sub ? (tmpdst ^ tmpsrc) : (tmpdst - tmpsrc) top_matched = bit_len(tmpdst) - bit_len(diff) return [ diff, shift, top_matched, src_bit_len ] end def solve @result.reset while @result.cur != @dst diff, shift, top_matched, src_bit_len = shifted_diff dist_from_top = src_bit_len - top_matched # p @result.result # puts "src = #{@result.cur.to_s(2)}" # puts "dst = #{@dst.to_s(2)}" # puts "diff = #{diff.to_s(2)}\n" # puts "dist = #{dist_from_top}\n" if diff==0 while shift > 0 @result.halve shift -= 1 end while shift < 0 @result.double shift += 1 end elsif dist_from_top > 5 # getting there try_to_halve(@result.cur) elsif dist_from_top == 5 # one away! # do this now in case we'd have to double-add-halve # unnecessarily later bit = 1 << (2 + shift + top_matched) if (diff&bit) != 0 @result.add_two end @result.halve elsif dist_from_top == 4 if shift > 0 try_to_halve(@result.cur) else 4.times { @result.add_two } end elsif dist_from_top == 3 if shift > 0 try_to_halve(@result.cur) else 2.times { @result.add_two } end elsif dist_from_top == 2 @result.add_two else @result.double end end return [ @result.result, @result.ops ] end private def try_to_halve(cur) if ((cur&1) != 0) # odd, so we can't halve yet @result.double @result.add_two elsif ((cur&2) != 0) # won't be able to halve again @result.add_two else @result.halve end end end end # vim:ts=2 sw=2 expandtab foldmethod=syntax foldcolumn=5 ################################################################################ } Reinder --Greg