ferencd@0: #---
ferencd@0: # Excerpted from "Mazes for Programmers",
ferencd@0: # published by The Pragmatic Bookshelf.
ferencd@0: # Copyrights apply to this code. It may not be used to create training material, 
ferencd@0: # courses, books, articles, and the like. Contact us if you are in doubt.
ferencd@0: # We make no guarantees that this code is fit for any purpose. 
ferencd@0: # Visit http://www.pragmaticprogrammer.com/titles/jbmaze for more book information.
ferencd@0: #---
ferencd@0: class Distances
ferencd@0:   def initialize(root)
ferencd@0:     @root = root
ferencd@0:     @cells = {}
ferencd@0:     @cells[@root] = 0
ferencd@0:   end
ferencd@0: 
ferencd@0:   def [](cell)
ferencd@0:     @cells[cell]
ferencd@0:   end
ferencd@0: 
ferencd@0:   def []=(cell, distance)
ferencd@0:     @cells[cell] = distance
ferencd@0:   end
ferencd@0: 
ferencd@0:   def cells
ferencd@0:     @cells.keys
ferencd@0:   end
ferencd@0: 
ferencd@0:   def path_to(goal)
ferencd@0:     current = goal 
ferencd@0: 
ferencd@0:     breadcrumbs = Distances.new(@root) 
ferencd@0:     breadcrumbs[current] = @cells[current]
ferencd@0: 
ferencd@0:     until current == @root 
ferencd@0:       current.links.each do |neighbor| 
ferencd@0:         if @cells[neighbor] < @cells[current] 
ferencd@0:           breadcrumbs[neighbor] = @cells[neighbor] 
ferencd@0:           current = neighbor
ferencd@0:           break
ferencd@0:         end
ferencd@0:       end
ferencd@0:     end
ferencd@0: 
ferencd@0:     breadcrumbs
ferencd@0:   end
ferencd@0: 
ferencd@0:   def max
ferencd@0:     max_distance = 0
ferencd@0:     max_cell = @root
ferencd@0: 
ferencd@0:     @cells.each do |cell, distance|
ferencd@0:       if distance > max_distance
ferencd@0:         max_cell = cell
ferencd@0:         max_distance = distance
ferencd@0:       end
ferencd@0:     end
ferencd@0: 
ferencd@0:     [max_cell, max_distance]
ferencd@0:   end
ferencd@0: end