From: Zed Lopez <rubyforum.20.zed2323@...>
Date: 2006-01-03T07:01:02+09:00
Subject: Re: Numeric Maze (#60)

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 
Word Ladder:

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 
for already existing values.

~ (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/.