Brute-force Pathfinder (converted from python)

pathfinder.rb

require 'term/ansicolor'

SMALL_MAZE = """
|||||||||
|S      |
| ||| |||
|       |
| || || |
|       |
| || ||||
|      E|
|||||||||
"""

LARGE_MAZE = """
|||||||||||||||||||||||||
|S     ||     ||||||    |
| ||||    ||| |||||  || |
|    | ||||||       ||| |
| || |   |||| |||  || | |
|||| |||      ||||    | |
||   |||| || ||| |||||| |
|| |      || | |        |
|| || |||||| | | ||| ||||
|  || |||||| | | |      |
|| || ||     | | | ||||||
|| || || ||||| | |     ||
|| ||    ||    | | ||| ||
|| |||| ||| |||| |   | ||
||   |           ||| | ||
|| | | ||||||||||| | | ||
|  | | ||      |   | | ||
| |||| || |||| | | | ||||
| |   ||    || | ||| ||||
| | |||||||||  | ||  ||||
| | ||        || ||     |
| |    ||||||||| |||||| |
| ||||||||||      ||||| |
|            ||||      E|
|||||||||||||||||||||||||
"""

class Maze

  attr_reader :solutions

  def initialize(pic=nil)
    @solutions = []
    @grid = grid_from_pic(pic)
  end

  def height
    @grid.size
  end

  def width
    @grid[0].size
  end

  def grid_from_pic(pic=nil)
    grid = (pic || SMALL_MAZE).split("\n").inject([]) do |arr, line|
      chars = line.chars
      row = chars.each_with_index.map do |char, x|
        y = arr.length
        cell = Cell.new(self, x, y, char)
        @starting_point = cell if char == 'S'
        cell
      end
      arr << row
    end
    # grid[1..-2]
    grid
  end

  def print_grid(path=nil)
    # prints a pretty representation of the grid to stdout
    puts
    @grid.each do |row|
      row.each do |cell|
        if path && path.include?(cell)
          print Term::ANSIColor.red('.')
        else
          cell.print_char
        end
      end
      print("\n")
    end
    puts
  end

  def cell_at(x, y)
    @grid[y][x]
  rescue
    nil
  end

  def solve
    @starting_point.pathfind([])
  end

end

class Coord < Struct.new(:x, :y)
  def to_s
    "(#{self.x}, #{self.y})"
  end

  def +(other)
    if other.is_a? Coord
      Coord.new *[self.x, self.y].zip([other.x, other.y]).map{|a,b| a+b}
    end
  end
end

class Cell

  TYPE_MAP = {
    ' ' => :space,
    '|' => :wall,
    'S' => :start,
    'E' => :end
  }

  COLORS = {
    'S' => :green,
    'E' => :red
  }

  DIRECTIONS = [
    Coord.new( 0, -1), #up
    Coord.new( 0,  1), #down
    Coord.new(-1,  0), #left
    Coord.new( 1,  0)  #right
  ]

  def initialize(maze, x, y, char)
    @maze = maze
    @coords = Coord.new(x,y)
    @char = char
  end

  def type
    TYPE_MAP[@char]
  end

  def is_wall?
    type == :wall
  end

  def to_s
    "Cell #{@coords}: #{type}"
  end

  def color
    COLORS[@char] || :white
  end

  def print_char
    print Term::ANSIColor.send(color) { @char }
  end

  def pathfind(path)
    branches = neighbors.compact.reject{|n| n.is_wall? || path.include?(n)}

    branches.each do |branch|
      if branch.is_ending_point
        @maze.solutions.push(path + [self])
      else
        branch.pathfind(path + [self])
      end
    end
  end

  def is_ending_point
    @char == 'E'
  end

  def neighbors
    # returns a list of (x, y) tuples for each cell adjacent up, down, left, and right
    cells = DIRECTIONS.inject([]) do |cells, dir|
      cells << @maze.cell_at(*(dir + @coords))
      cells
    end
  end

end

def run
  # consumes an ASCII grid representation and creates a 2D matrix.
  # finds the start (sp) and end (ep) points and finds shortest path.
  maze = Maze.new
  maze.print_grid()
  maze.solve()
  solutions = maze.solutions
  solutions.each do |solution|
    # puts solution
    maze.print_grid(solution)
    puts
  end
  shortest = solutions.sort_by(&:length).first

  puts "Found %s solutions." % solutions.length
  # puts "Shortest path (%s steps):" % shortest.length
  puts "Shortest path:"
  maze.print_grid(shortest)
end

run()