```There is a small time fraction possible to squeeze out from Simon's
solution.
These lines, by Simon, are trying to detect if contact has been made, in
the bi-directional search:

forward.each {|n|return pathf, pathb, n if pathb[n] != ?X}
backward.each {|n|return pathf, pathb, n if pathf[n] != ?X}

If pathf and pathb are merged into one string, this check be done
without iteration. To be able to do that we must distinguish between
numbers reached by going forward and numbers reached by going backwards.
This can be done by using lower and upper case letters:

Forward character set:
?f starting number
?a add 2
?d divide
?m multiply

Backward character set:
?F target number
?S subtract 2
?D divide
?M multiply

?X unreached number

Result:

t solve(22222222,99999999).size, 58   #8
t solve(99999999,22222222).size, 61   #8
Christer   5.108 secs
Simon      6.175 secs

The code is ugly, please turn down the light:

# store operations instead.
# one common string
# use letters for operations

def solve start, target
return [start] if start == target
@MAX = 1 + 2 + 2 * [start,target].max

op = ''.ljust(@MAX, 'X')
op[start] = ?f
op[target] = ?F

@ready = nil
q1 = [start]
q2 = [target]
loop do
q1 = solve1(q1,op)
break if @ready
q2 = solve2(q2,op)
break if @ready
end
path(@ready[0],op).reverse + path(@ready[1],op)
end

def path(n,op)
case op[n]
when ?A,?a: [n] + path(n-2,op)
when ?D,?d: [n] + path(n*2,op)
when ?S,?s: [n] + path(n+2,op)
when ?M,?m: [n] + path(n/2,op)
when ?F,?f: [n]
end
end

def solve1(queue,op)
q = []
queue.each do |n|

#   store1 ?m, n, n * 2 if n+n<=@MAX
result = n + n
if result <= @MAX then
if op[result]==?X then
q.push result
op[result] = ?m
else
@ready = n, result if op[result] < ?a
end
end

#   store1 ?a, n, n + 2 if n+2<=@MAX
result = n + 2
if result <= @MAX then
if op[result]==?X then
q.push result
op[result] = ?a
else
@ready = n, result if op[result] < ?a
end
end

#   store1 ?d, n, n / 2 if n.modulo(2) == 0
if n.modulo(2) == 0 then
result = n / 2
if op[result]==?X then
q.push result
op[result] = ?d
else
@ready = n, result if op[result] < ?a
end
end

break if @ready
end
q
end

def solve2(queue,op)
q = []
queue.each do |n|

#   store2 ?M, n, n * 2 if n+n<=@MAX
result = n + n
if result <= @MAX then
if op[result]==?X then
q.push result
op[result] = ?M
else
@ready = n, result if op[result] >= ?a
end
end

#   store2 ?S, n, n - 2 if n>2
result = n - 2
if result >= 1 then
if op[result]==?X then
q.push result
op[result] = ?S
else
@ready = n, result if op[result] >= ?a
end
end

#   store2 ?D, n, n / 2 if n.modulo(2) == 0
if n.modulo(2) == 0 then
result = n / 2
if op[result]==?X then
q.push result
op[result] = ?D
else
@ready = n, result if op[result] >= ?a
end
end

break if @ready
end
q
end

#def store1 op, number, result
#if result.op.nil? then
#@queue.push result
#result.op = op
#else
#@ready = number, result if result.op < ?a
#end
#end

#def store2 op, number, result
#if result.op.nil? then
#@queue.push result
#result.op = op
#else
#@ready = result, number if result.op >= ?a
#end
#end

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

```