fixtures.rb

MAZE1 = %{#####################################
# #   #     #A        #     #       #
# # # # # # ####### # ### # ####### #
# # #   # #         #     # #       #
# ##### # ################# # #######
#     # #       #   #     # #   #   #
##### ##### ### ### # ### # # # # # #
#   #     #   # #   #  B# # # #   # #
# # ##### ##### # # ### # # ####### #
# #     # #   # # #   # # # #       #
# ### ### # # # # ##### # # # ##### #
#   #       #   #       #     #     #
#####################################}
# Maze 1 should SUCCEED

MAZE2 = %{#####################################
# #       #             #     #     #
# ### ### # ########### ### # ##### #
# #   # #   #   #   #   #   #       #
# # ###A##### # # # # ### ###########
#   #   #     #   # # #   #         #
####### # ### ####### # ### ####### #
#       # #   #       # #       #   #
# ####### # # # ####### # ##### # # #
#       # # # #   #       #   # # # #
# ##### # # ##### ######### # ### # #
#     #   #                 #     #B#
#####################################}
# Maze 2 should SUCCEED

MAZE3 = %{#####################################
# #   #           #                 #
# ### # ####### # # # ############# #
#   #   #     # #   # #     #     # #
### ##### ### ####### # ##### ### # #
# #       # #  A  #   #       #   # #
# ######### ##### # ####### ### ### #
#               ###       # # # #   #
# ### ### ####### ####### # # # # ###
# # # #   #     #B#   #   # # #   # #
# # # ##### ### # # # # ### # ##### #
#   #         #     #   #           #
#####################################}

SIMPLE1 = %{######
#A   #
#### #
#B   #
######
}

SOLVED_SIMPLE1 = %{######
#A...#
####.#
#B...#
######
}

SIMPLE2 = %{######
#A   #
######
#B   #
######
}

SIMPLE3 = %{#######
#A# ###
# #   #
#   # #
####  #
#B   ##
#######
}

maze_spec.rb

require File.join(File.expand_path(File.dirname(__FILE__)), "spec_helper.rb")
require 'fixtures'

describe Maze do
  context "#deconstruct_maze" do
    it "should return a bidimensional array" do
      map = "###\n# #\n###"
      maze = Maze.new(map)
      deconstructed_maze = [['#', '#', '#'], ['#', ' ', '#'], ['#', '#', '#']]
      maze.deconstruct_maze.should == deconstructed_maze
    end
  end
  
  context "#find_start_and_finish" do
    it "should find A as start and B as finish" do
      maze = Maze.new(SIMPLE1)
      maze.find_start_and_finish.should == [[1,1], [1,3]]
    end
    
    it "should raise an error when there are problems with start and finish" do
      lambda { Maze.new('###').find_start_and_finish }.should raise_error
      lambda { Maze.new('A').find_start_and_finish }.should raise_error
      lambda { Maze.new('B').find_start_and_finish }.should raise_error
      lambda { Maze.new('').find_start_and_finish }.should raise_error
    end
  end
  
  context "#possible_moves" do
    before(:each) do
      @maze = Maze.new(SIMPLE1)
    end

    it "should find no possible moves" do
      pos = [0,0]
      @maze.possible_moves(pos).should == []
      pos = [5,0]
      @maze.possible_moves(pos).should == []
    end
    
    it "should find 1 possible move" do
      pos = [1,1]
      @maze.possible_moves(pos).should == [[2,1]]
      pos = [5,1]
      @maze.possible_moves(pos).should == [[4,1]]
    end
    
    it "should find 2 possible moves" do
      pos = [2,1]
      @maze.possible_moves(pos).should == [[3,1], [1,1]]
      pos = [4,1]
      @maze.possible_moves(pos).should == [[4,2], [3,1]]
      pos = [4,2]
      @maze.possible_moves(pos).should == [[4,1], [4,3]]
    end
    
  end

  context "#solve" do
    it "should find a path for SIMPLE1" do
      Maze.new(SIMPLE1).solve.should == [
        [1,1], [2,1], [3,1], [4,1],
        [4,2],
        [4,3], [3,3], [2,3], [1,3]
      ]
    end
    
    it "should not find a path for SIMPLE2" do
      Maze.new(SIMPLE2).solve.should == []
    end
  end
  
  context "#solved_map" do
    it "should print the path taken in simple maze 1" do
      Maze.new(SIMPLE1).solved_map.should == SOLVED_SIMPLE1
    end
  end
end

describe Maze, "#solvable?" do
  context "solvable mazes" do
    it "should say simple maze 1 is solvable" do
      Maze.new(SIMPLE1).solvable?.should be_true
    end
    it "should say maze 1 is solvable" do
      Maze.new(MAZE1).solvable?.should be_true
    end
    it "should say maze 2 is solvable" do
      Maze.new(MAZE2).solvable?.should be_true
    end
  end
  
  context "unsolvable mazes" do
    it "should say simple maze 2 is not solvable" do
      Maze.new(SIMPLE2).solvable?.should be_false
    end    
    it "should say maze 3 is not solvable" do
      Maze.new(MAZE3).solvable?.should be_false
    end
  end
end

describe Maze, "#steps" do
  context "solvable mazes" do
    it "should say simple maze 1 needs 8 steps" do
      Maze.new(SIMPLE1).steps.should == 8
    end
    it "should say simple maze 3 needs 14 steps" do
      Maze.new(SIMPLE3).steps.should == 14
    end    
    it "should say maze 1 needs 44 steps" do
      maze = Maze.new(MAZE1)
      maze.steps.should == 44
    end
    it "should say maze 2 needs 75 steps" do
      Maze.new(MAZE2).steps.should == 75
    end
  end
  
  context "unsolvable mazes" do
    it "should say simple maze 2 needs 0 steps" do
      Maze.new(SIMPLE2).steps.should == 0
    end
    it "should say maze 3 needs 0 steps" do
      Maze.new(MAZE3).steps.should == 0
    end
  end  
end

raoulfelix.rb

=begin
Title:               Ruby Challenge #5
Program Description: Maze solving
Submitted By:        Raoul Felix
=end

class Maze
  # Initialize the Maze with a string containing the map
  # 
  def initialize(map)
    @map = map
  end
  
  # Returns +true+ if a solution was found for the maze and false otherwise
  #
  def solvable?
    !solution.empty?
  end
  
  # Returns the number of steps from point A to point B
  #
  def steps
    return 0 if solution.empty?
    # We have to subtract 1 because the starting position is in solution
    # e.g. Path 1,2,3,4 has 4 positions but only 3 steps: 1 to 2, 2 to 3, 3 to 4
    solution.length - 1
  end
  
  ### Additional Methods
  
  # Return an array of positions that go from A to B
  #
  def solution
    # The maze can't be changed, so it only needs to be solved once (lazy evaluation)
    @solution ||= solve
  end
  
  # Returns a string, just like the one passed to the Maze constructor, but has
  # the path from A to B filled with dots (.) to show the path that was taken.
  # Useful for debugging and visualization.
  #
  def solved_map
    str  = ""
    # Because Array#delete is destructive, we need to duplicate the solution array.
    # As the solution uses lazy evalutation and is only computed once, if we don't
    # duplicate the array and remove objects from the actual +solution+ then all
    # calls that rely on +solution+ after this will produce different and erroneous results.
    # Side-effects are bad!
    path = solution.dup
    maze.each_with_index do |row, y|
      row.each_with_index do |e, x|
        if path.delete([x,y]) && e != 'A' && e != 'B'
          str += "."
        else
          str += e
        end
      end
      str += "\n"
    end
    str
  end
  
  ### Helper Methods
  
  # Returns a bidimensional array of characters based on the maze string passed 
  # to the Maze constructor
  #
  def maze
    # Only deconstruct maze once
    @maze ||= deconstruct_maze
  end  
  
  # This solving methods uses a breadth-first search with a stack instead of 
  # recursion so it's not too slow.
  #
  def solve
    start, finish = find_start_and_finish
    stack         = [start]
    visited       = []
    while (stack.last != finish && !stack.empty?) do
      current_pos = stack.last
      moves       = possible_moves(current_pos)
      moves      -= stack # Remove any moves we've already taken
      moves      -= visited # Remove the moves that resulted in a dead-end
      if moves.empty?
        # Reached a dead-end, make sure we don't come here again
        visited << stack.pop
      else
        # Try the first move in the possible moves list
        stack << moves.first
      end
    end
    stack
  end
  
  # Transform the maze given as a string to the Maze constructor into a
  # bidimensional array of characters so it's easier to navigate through
  # 
  def deconstruct_maze
    @map.split("\n").map { |line| line.scan(/./) }
  end
  
  # Returns an array with two positions:
  #  - First is the start position (where A is)
  #  - Second is the finish position (where B is)
  # Positions are just arrays of length 2 that correspond to [x,y]
  # 
  def find_start_and_finish
    start, finish = nil, nil
    maze.each_with_index do |row,y|      
      row.each_with_index do |col,x|
        start = [x,y] if col == 'A'
        finish = [x,y] if col == 'B'
        return [start,finish] if start && finish
      end
    end
    raise "Start/Finish not properly specified"
  end
  
  # Returns an array with all positions that the algorithm can take given
  # the +pos+ passed as an argument. This method takes into account wall 
  # boundries and only navigates to positions where there is either one of 
  # these characters: ' ', A, and B.
  # Only top, right, bottom, and left moves are permitted.
  # 
  def possible_moves(pos)
    x,y       = pos
    width     = maze[0].length
    height    = maze.length
    positions = [
      [x  , y-1], # Top
      [x+1, y  ], # Right
      [x  , y+1], # Bottom
      [x-1, y  ]  # Left
    ].select do |x,y|
      x >= 0 && y >= 0 && x < width && y < height && [' ','A','B'].include?(maze[y][x])
    end
  end
end