From: "J. Ryan Sobol" <ryansobol@...>
Date: 2006-01-02T16:25:08+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)

Here's my (first) solution (ever) for quiz #60.

I also choose a breadth-first search algorithm because I'm probably  
going to need a decent searching algorithm in the near future.  To  
maximize reusability, I implemented 6 methods in the Integer class  
that abstract the problem-specific logic out of the searching  
algorithm.  When I use a different 'node' class, I will also need to  
include the Comparable mix-in and define the <=> method for the  
Array.max method on line #40.

The running time for the algorithm is O(N), where N is the number of  
integers the algorithm 'visits'.  To limit the number of visited  
integers, I added a few of the clever optimizations already  
mentioned: removing consecutive double/halves and removing adjacent  
values greater than a maximum.

$ time ./quiz.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, 199992, 199994,  
99997, 99999]

real    0m2.098s
user    0m1.868s
sys     0m0.091s

Not faster than Dominik's, but still pretty fast.  Perhaps my 1.33  
Ghz G4 and 768 MB of RAM is holding my back?  :)

Although this is one of many BFS algorithms posted, I'd really  
appreciate some feedback on my implementation.  Especially in regards  
to potential speed ups, missed opportunities for ruby idioms, and  
additional optimizations to the adjacency_list method.

~ ryan ~

#!/usr/bin/env ruby

class Integer
   attr_reader :distance, :discovered

   def odd?
     self % 2 != 0
   end

   # optimized to remove consecutive double/halves and remove  
adjacent values greater than a maximum
   def adjacency_list(maximum = Infinity)
     list = []
     list << self * 2 unless @parent == self * 2  or self * 2 > maximum
     list << self / 2 unless self.odd? or @parent == self / 2
     list << self + 2 unless self + 2 > maximum
     list || []
   end

   def visit!(parent = nil)
     @discovered = true
     @parent = parent
     @distance = parent ? parent.distance + 1 : 0
   end

   def path_from(start)
     if self == start
       [start]
     else
       if @parent == nil
         raise "no path from #{start} to #{self} exists"
       else
         @parent.path_from(start) << self
       end
     end
   end
end

def solve(start, target)
   return [start] if start == target
   roof = [start, target].max * 2 + 2
   start.visit!
   queue = [start]
   queue.each do |vertex|
     vertex.adjacency_list(roof).each do |child|
       unless child.discovered
         child.visit!(vertex)
         return target.path_from(start) if target == child
         queue.push(child)
       end
     end
   end
end

# Run this code only when the file is the main program
if $0 == __FILE__
   # Parse arguments (authored by James Edward Gray II)
   unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ }
     puts "Usage:  #{File.basename($0)} START_NUMBER FINISH_NUMBER"
     puts "  Both number arguments must be positive integers."
     exit
   end
   start, finish = ARGV.map { |n| Integer(n) }

   p solve(start, finish)
end