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