Mercurial > maze-src
annotate distances.rb @ 0:1eef88068f9f tip
initial commit of maze game source
| author | ferencd |
|---|---|
| date | Sun, 15 Sep 2019 11:46:47 +0200 |
| parents | |
| children |
| rev | line source |
|---|---|
| ferencd@0 | 1 #--- |
| ferencd@0 | 2 # Excerpted from "Mazes for Programmers", |
| ferencd@0 | 3 # published by The Pragmatic Bookshelf. |
| ferencd@0 | 4 # Copyrights apply to this code. It may not be used to create training material, |
| ferencd@0 | 5 # courses, books, articles, and the like. Contact us if you are in doubt. |
| ferencd@0 | 6 # We make no guarantees that this code is fit for any purpose. |
| ferencd@0 | 7 # Visit http://www.pragmaticprogrammer.com/titles/jbmaze for more book information. |
| ferencd@0 | 8 #--- |
| ferencd@0 | 9 class Distances |
| ferencd@0 | 10 def initialize(root) |
| ferencd@0 | 11 @root = root |
| ferencd@0 | 12 @cells = {} |
| ferencd@0 | 13 @cells[@root] = 0 |
| ferencd@0 | 14 end |
| ferencd@0 | 15 |
| ferencd@0 | 16 def [](cell) |
| ferencd@0 | 17 @cells[cell] |
| ferencd@0 | 18 end |
| ferencd@0 | 19 |
| ferencd@0 | 20 def []=(cell, distance) |
| ferencd@0 | 21 @cells[cell] = distance |
| ferencd@0 | 22 end |
| ferencd@0 | 23 |
| ferencd@0 | 24 def cells |
| ferencd@0 | 25 @cells.keys |
| ferencd@0 | 26 end |
| ferencd@0 | 27 |
| ferencd@0 | 28 def path_to(goal) |
| ferencd@0 | 29 current = goal |
| ferencd@0 | 30 |
| ferencd@0 | 31 breadcrumbs = Distances.new(@root) |
| ferencd@0 | 32 breadcrumbs[current] = @cells[current] |
| ferencd@0 | 33 |
| ferencd@0 | 34 until current == @root |
| ferencd@0 | 35 current.links.each do |neighbor| |
| ferencd@0 | 36 if @cells[neighbor] < @cells[current] |
| ferencd@0 | 37 breadcrumbs[neighbor] = @cells[neighbor] |
| ferencd@0 | 38 current = neighbor |
| ferencd@0 | 39 break |
| ferencd@0 | 40 end |
| ferencd@0 | 41 end |
| ferencd@0 | 42 end |
| ferencd@0 | 43 |
| ferencd@0 | 44 breadcrumbs |
| ferencd@0 | 45 end |
| ferencd@0 | 46 |
| ferencd@0 | 47 def max |
| ferencd@0 | 48 max_distance = 0 |
| ferencd@0 | 49 max_cell = @root |
| ferencd@0 | 50 |
| ferencd@0 | 51 @cells.each do |cell, distance| |
| ferencd@0 | 52 if distance > max_distance |
| ferencd@0 | 53 max_cell = cell |
| ferencd@0 | 54 max_distance = distance |
| ferencd@0 | 55 end |
| ferencd@0 | 56 end |
| ferencd@0 | 57 |
| ferencd@0 | 58 [max_cell, max_distance] |
| ferencd@0 | 59 end |
| ferencd@0 | 60 end |