maze.rb

# Peter Cooper's initial Maze solution

class Maze
  START_CHARACTER = 'A'
  END_CHARACTER = 'B'
  WALL_CHARACTER = '#'
  
  def initialize(maze)
    # Get the height and width of the maze
    @maze_width = maze[/^.*?\n/].length - 1
    @maze_height = maze.split(/\n/).length
    
    # Store the maze as a string without any newlines
    @maze = maze.gsub(/\n/, '')

    # Get co-ordinates of the start and end points
    @start_x, @start_y = position_to_coords(@maze.index(START_CHARACTER))
    @end_x, @end_y = position_to_coords(@maze.index(END_CHARACTER))
    @routes = []
  end
  
  # Returns true if the maze is solvable, false if not.
  def solvable?
    old_maze = @maze.dup
    flood_fill(@start_x, @start_y)
    possible = !@maze.index(END_CHARACTER)
    @maze = old_maze
    possible
  end
  
  # Returns how many steps are necessary to get from the start to the end of the maze
  def steps
    @steps = []
    old_maze = @maze.dup
    walk_maze(@start_x, @start_y)
    possible = !@maze.index(END_CHARACTER)
    @maze = old_maze
    @steps.min
  end
  
  private
  # Convert a literal position within the maze string to X/Y co-ordinates
  def position_to_coords(pos)
    [pos % @maze_width, pos / @maze_width]
  end
  
  # Convert X/Y co-ordinates into a literal position within the maze string
  def coords_to_position(x, y)
    y * @maze_width + x
  end
  
  # Flood fill non wall areas of the maze
  def flood_fill(x, y)
    unless [WALL_CHARACTER, '.'].include?(@maze[coords_to_position(x, y)].chr)
      @maze[coords_to_position(x, y)] = '.'
      flood_fill(x - 1, y)
      flood_fill(x + 1, y)
      flood_fill(x, y - 1)
      flood_fill(x, y + 1)
    end
  end
  
  # Flood fill but track steps involved to an end point
  # A horribly lazy way to solve the "steps" issue
  def walk_maze(x, y, steps = 0)
    unless [WALL_CHARACTER, '.'].include?(@maze[coords_to_position(x, y)].chr)
      if x == @end_x && y == @end_y
        @steps << steps
        return
      end
      @i ||= 0
      @i += 1

      if defined?(DEBUG)
        sleep 0.05
        print "\e[2J\e[f"
        puts @maze.scan(/.{37}/)
      end

      @maze[coords_to_position(x, y)] = '.'
      walk_maze(x - 1, y, steps + 1) if neighbors(x - 1, y) == 1
      walk_maze(x + 1, y, steps + 1) if neighbors(x + 1, y) == 1
      walk_maze(x, y - 1, steps + 1) if neighbors(x, y - 1) == 1
      walk_maze(x, y + 1, steps + 1) if neighbors(x, y + 1) == 1
      @maze[coords_to_position(x, y)] = ' '
    end
  end
  
  # Return how many neighboring dots there are at a certain location
  def neighbors(x, y)
    neighbors = 0
    neighbors += 1 if x - 1 >= 0 && @maze[coords_to_position(x - 1, y)].chr == '.'
    neighbors += 1 if x + 1 < @maze_width && @maze[coords_to_position(x + 1, y)].chr == '.'
    neighbors += 1 if y - 1 >= 0 && @maze[coords_to_position(x, y - 1)].chr == '.'
    neighbors += 1 if y + 1 < @maze_height && @maze[coords_to_position(x, y + 1)].chr == '.'
    neighbors
  end
end

if $0 == __FILE__
MAZE1 = %{#####################################
# #   #     #         #     #       #
# # # # # # ####### # ### # ####### #
# # #   # #         #     # #       #
# ##### # ################# # #######
#    A# #       #   #     # #   #   #
##### ##### ### ### # ### # # # # # #
#   #     #   # #   #  B# # # #   # #
# # ##### ##### # # ### # # ####### #
# #     # #   # # #   # # # #       #
# ### ### # # # # ##### # # # ##### #
#   #       #   #       #     #     #
#####################################}

a = Maze.new(MAZE1)
puts a.solvable?
puts a.steps
end