From: Steven Aerts <steven.aerts@...>
Date: 2006-01-02T07:20:18+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)

Hi all,

hereby my first solution for the ruby quiz and my first real world ruby 
program. :-)

So all comments about my ruby-coding-style are very welcome(especially how 
you think about using the throw catch statement).

The program itself runs two depth first searches in parallel one from the 
start number and one from the end number looking for the middle number in the 
end-result.  
When found, the two paths to get to this middle number form the end-result.  

It is possible to use the same method to calculate both pathways by using 
negative numbers for the path from the end-point.
-- 
Hope you like it,

	Steven  <steven.aerts@gmail.com>

--
class NumericMaze
	def solve (from, to)
		return [from] if from == to
		
		@done = {from => :from, -to => :to}
		@todo = [from, -to]
		
		catch :found do
			while true
				t = @todo.shift
				
				addEdge(2*t, t)
				addEdge(t+2, t) if (t <- 2) || (0 <= t)
				addEdge(t/2,t) if t.modulo(2) == 0
			end
		end
		return @result
	end
	
	def addEdge(new, from)
		return if @done[new] != nil
	 
		@done[new] = from
		
		if @done[-new] then #path found
			@result = calcPath(new.abs)
			throw :found
		end
		
		@todo.push new
	end
	
	def calcPath(middle)
		pathway = [middle]
	
		t = middle
		pathway.unshift(t) until (t = @done[t]) == :from
		
		t = -middle
		pathway.push(-t) until (t = @done[t]) == :to

		return pathway
	end
end