From: Matthew D Moss <matthew.moss@...>
Date: 2006-01-04T07:57:58+09:00
Subject: Re: Numeric Maze (#60)

Here is my solution, very much a derivative of my solution to the
Knight's Travails quiz (#27). It will return a shortest solution
(chosen at random if there are more than one). It will always find a
shortest solution, though not necessarily fast. (I haven't tried timing
this.)



# Helper methods
class Integer
   def even?
      self & 1 == 0
   end

   def maze_adj
      if even?
         [self + 2, self * 2, self / 2]
      else
         [self + 2, self * 2]
      end
   end
end


def solve(a, b)
   i = 0
   steps = [[a]]

   # steps[i] contains all the numbers reachable in i steps
   until steps[i].include?(b)
      i += 1
      steps[i] = []
      steps[i-1].each do |x|
         steps[i].concat x.maze_adj
      end
   end

   # path is built in reverse order, finding a legal previous
   # number according to "adjacency" rules
   i -= 1
   path = [b]
   i.downto(0) do |k|
      s = steps[k].find_all { |x| x.maze_adj.include? path.last }
      path << s.sort_by { rand }.first
   end

   # path was built in reverse order, so reverse to get the final path
   path.reverse
end


# Examples
p solve(2, 9)
p solve(9, 2)