```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-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]

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]

real	0m0.022s
user	0m0.015s
sys	0m0.007s

% ruby test60.rb 32 48
[32, 16, 18, 20, 22, 24, 48]

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]

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]

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

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

@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

double
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
end
@result.halve
elsif dist_from_top == 4
if shift > 0
try_to_halve(@result.cur)
else
end
elsif dist_from_top == 3
if shift > 0
try_to_halve(@result.cur)
else
end
elsif dist_from_top == 2
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
elsif ((cur&2) != 0)
# won't be able to halve again
else
@result.halve
end
end

end

end

# vim:ts=2 sw=2 expandtab foldmethod=syntax foldcolumn=5
################################################################################

} Reinder
--Greg

```