On 12/30/05, Ruby Quiz <james / grayproductions.net> wrote:> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=>> by Christer Nilsson>> You have a starting point and a target, say 2 and 9.>> You have a set of three operations:>>         double>         halve    (Odd numbers cannot be halved.)>         add_two>> Problem: Move from the starting point to the target, minimizing the number of> operations.>>         Examples:>>         solve(2,9)  # => [2,4,8,16,18,9]>         solve(9,2)  # => [9,18,20,10,12,6,8,4,2]>>
# The problem can be thought of in binary.# (Which also happens to make solving by hand easy.)## i * 2 = i << 1# i / 2 = i >> 1, only applicable if i[0] == 0# i + 2 = i + 0b10## Let's solve 22 -> 99.# Mark the numbers in binary: 22 = 10110, 99 = 1100011## Now start making the binary digits of 22 into 99's,# progress one digit at a time:## 10110# first 1 matches but second 0 should be 1, let's add 2# 10110 + 10 => 11000# ok, first five match (11000, 1100011)# shift so that we can turn the sixth into 1# 11000 << 1 => 110000# 110000 << 1 => 1100000# now add two to make 6th digit match# 1100000 + 10 => 1100010# shift and add to make 7th digit match# 1100010 << 1 => 11000100# 11000100 + 10 => 11000110# ok, all first digits match, divide to make length right# 11000110 >> 1 => 1100011## Problems appear when trying to make 255 into 257:# 11111111 -> 100000001## The shortest way is by adding 2.# But the algorithm below fails at that and goes the long way:# 11111111 << 1# 111111110 + 2# 1000000000 + 2# 1000000010 >> 1# 100000001#def nsrch(s,g)  orig_s = s  ss = s.to_s 2  gs = g.to_s 2  ops = []  bits = gs.split(//)  i = 0  # Go through all bits of g.  # If there are ones in the trailing part of ss, we  # must get rid of them (Otherwise: 1001 -> 100, all digits match,  # jump out of loop, make length equal by >>. Oops, it was an odd  # number we just halved. So must check for ones.)  while i < bits.size or ss[bits.size..-1].include? ?1    b = bits[i]    op = nil    n = 0    while ss[i,1] != b      # Add zeroes to right to make length right and      # to get the rightmost bit into an editable state.      if ss.size < i+2 or s[0] == 1        op = :*      # Delete zeroes from right to make length right.      elsif ss.size > i+2 and (s[0] == 0 and s[1] == 0)        op = :/      # Add 2 if length is ok and there are no zeroes to take out.      # We are here because the second right-most bit is wrong.      # Adding 2 flips it. It may also flip every bit we've just      # went through, invalidating the invariant and thus we reset      # the bit counter.      else        op = :+        i = 0      end      ops << op      s = case op          when :+            s + 2          when :*            s << 1          when :/            s >> 1          end      ss = s.to_s 2      break if op == :+ # invariant may be bad,                        # must check before continuing    end    i += 1 unless op == :+  end  # take out extra zeroes on right  r = s >> (ss.size-gs.size)  ops.push *[:/]*(ss.size-gs.size)  # and collect middle states using done ops  a = [orig_s]  ops.each{|op|    a << case op    when :*      a.last * 2    when :/      a.last / 2    when :+      a.last + 2    end  }  aend
if __FILE__ == $0  p(nsrch(*ARGV.map{|n| n.to_i}))end