```Kinda ugly, but pretty fast. Breadth first search alternating from each
end. It's the same basic algorithm I used for a Perl Quiz of the Week

http://perl.plover.com/~alias/list.cgi?mss:99:200409:dlfkjbmmdljnajmfagki

Instead of CPAN's Tree::Simple, I'm using unidirectional (nodes can find
their parents, but not their children) n-ary trees implemented in
hashes. I don't explicitly implement the don't-double-then-halve
optimization, but I get it as a side-effect of my use of node_index to
index all values already in the tree so I can avoid creating new nodes

~ (300) time ./numeric_maze5.rb 8740 7630
[8740, 4370, 4372, 2186, 2188, 1094, 1096, 548, 274, 276, 138, 140, 70,
72, 36, 38, 19, 21, 23, 25, 27, 29, 58, 116, 118, 236, 238, 476, 952,
1904, 1906, 3812, 3814, 7628, 7630]

real    0m2.280s
user    0m2.105s
sys     0m0.017s
~ (301) time ./numeric_maze5.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87,
89, 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496,
12498, 24996, 24998, 49996, 49998, 99996, 99998, 199996, 199998, 99999]

real    0m2.966s
user    0m2.796s
sys     0m0.016s

def success(x, node1, node2)
node1, node2 = node2, node1 unless x.zero?
p chain(node1).reverse + chain(node2)
exit
end

def chain(node)
(result ||= []) << node[:num] and node = node[:parent] until node.nil?
result
end

tree = []
node_index = []
ARGV.each { |x|
root = {:num => x.to_i, :parent => nil}
tree << [root]
node_index << { root[:num] => root }
}

x = 1
while x = 1 - x: # cycle between 0 and 1 in infinite loop
next_nodes = []
tree[x].each {|node| # for each node in current level
[node[:num]*2,
node[:num]%2 == 0 ? node[:num]/2 : 0,
x.zero? ? node[:num] + 2 : node[:num] - 2].uniq.select {|n|
n > 0 and !node_index[x].key?(n)}.each {|newnum|
# if we have a path to this result in the other tree, we're done
success(x, node, node_index[1-x][newnum]) if
node_index[1-x].key?(newnum) # only way out of the loop
next_nodes << node_index[x][newnum] = { :num => newnum, :parent
=> node } # build the next level
}
}
tree[x] = next_nodes
end

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

```