Ilmari Heikkinen wrote:
> #
> # 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
> #

Ilmari, I tried to replicate your solution, before seeing it, and 
strangely run into exactly the same behaviour. The code is not complete, 
but the idea is to go downwards to 1 with both numbers. I'm using the 
complement of +2, -2 for the target number.

      t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
                  -->  -->  --v
                  <--  <--  <--
    t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

Having these two sequences, I find the largest common number, in this 
case 512. This gives me the non optimal solution [255,510,512,514,257], 
which is exactly the same as yours. I'm not sure if identifying 
shortcuts afterwards, will find the shortest path, though, in all cases. 
(Finding 255 + 2 = 257, is easy, but what about finding 255 -> 259 if 
257 is missing.)

I tried the six digit subproblem of your big problem, and it worked out 
perfectly optimal. So I was surprised 255 -> 257 behaved so bad.

Christer


def down(x)
  return [] if x==0
  return [1] if x==1
  return [2,1] if x==2
  return [x] + down(x*2) if x.modulo(2)==1
  return [x] + down(x/2) if x.modulo(4)==0
  [x] + down(x-2)
end

def up(x)
  return [] if x==0
  return [1] if x==1
  return [2,1] if x==2
  return [x] + up(x*2) if x.modulo(2)==1
  return [x] + up(x/2) if x.modulo(4)==0
  [x] + up(x+2)
end

require 'test/unit'
class TestIlmari < Test::Unit::TestCase
  def t (actual, expect)
    assert_equal expect, actual
  end
  def test_all
    t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
    t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
    #t up(72), [72,36,18,20,10,12,6,8,4,2,1]
    #t down(28), [28,14,12,6,4,2,1]
    #t up(150128850109293).size,82
    #t down(8591982807778218492).size, 100
  end
end

-- 
Posted via http://www.ruby-forum.com/.