```I took a look into bi-directional search, and it's really a rewarding
technique. I predicted a 16-fold performance increase, but it was 12.
I'm storing the result of both searches in a common array. To keep the
two solutions separated I use the sign. When the other side, there is a
connection, between the two growing trees.

I really tried to find something more clever than Simon's solutions, but
had to give up. Kudos to Simon!

Thanks to everybody, it's been really nice to follow everybody's
efforts!

Christer

Timings:

t solve(      2,      9).size, 6    #1
t solve(     22,     99).size, 8    #2
t solve(    222,    999).size, 16   #3
t solve(   2222,   9999).size, 25   #4
t solve(  22222,  99999).size, 36   #5
t solve( 222222, 999999).size, 47   #6
t solve(2222222,9999999).size, 58   #7
t solve(9999999,2222222).size, 61   #7
t solve( 999999, 222222).size, 51   #6
t solve(  99999,  22222).size, 42   #5
t solve(   9999,   2222).size, 33   #4
t solve(    999,    222).size, 23   #3
t solve(     99,     22).size, 13   #2
t solve(      9,      2).size, 9    #1

Each test consists of two problems.

Test 7:
Simon     1.833 secs
Christer  3.425 secs

Test 6:
Simon     0.321 secs
Christer  0.551 secs
Ryan     37     secs

Test 5:
Simon     0.11  secs
Christer  0.15  secs
Ryan      4.597 secs
Tristan   7.18  secs
Kenneth  13.93  secs
Zed      14.241 secs
Kero     70.6   secs

Test 4:
Chris     2.614 secs

Test 2:
James     0.12  secs

def solve start, target
return [start] if start == target
@max = 2 + 2 * [start,target].max
@back = []
@back[start] = start
@back[target] = -target
q1 = [start]
q2 = [target]
loop do
q1 = solve_level(q1, 1)
q2 = solve_level(q2, -1)
end
end

def path(number)
nr = abs(@back[number])
[number] + (nr == number ? [] : path(nr))
end

def solve_level(queue, sign)
@queue = []
@sign = sign
queue.each do |number|
store number, number * 2
store number, number + 2 * sign
store number, number / 2 if number[0] == 0
end
@queue
end

def store number, result
return if result > @max
return if result <= 0
if @back[result].nil? then
@queue.unshift result
@back[result] = number * @sign
else
if sign(@back[result]) == -@sign then