```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/.

```