Skip to content

Instantly share code, notes, and snippets.

@rfelix
Created January 12, 2010 00:13
  • Star 0 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save rfelix/89e456ff8097cb08f8fb to your computer and use it in GitHub Desktop.
RPCFN: Mazes (#5) Solution + Specs + Fixtures
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 ##
#######
}
EDGE1= %{#####
# A #
# # #
# B #
#####
}
require 'raoulfelix'
require 'fixtures'
class Maze
# Gain access to the private methods
public *self.private_instance_methods
end
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
require 'raoulfelix'
require 'fixtures'
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
it "should say maze edge 1 is solvable" do
Maze.new(EDGE1).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
it "should say maze edge 1 needs 4 steps" do
Maze.new(EDGE1).steps.should == 4
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
=begin
Title: Ruby Challenge #5
Program Description: Maze solving
Submitted By: Raoul Felix
=end
require 'set'
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
private ### 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
# Position of A in the Maze map
#
def start_position
@start_finish_positions ||= find_start_and_finish
@start_finish_positions[0]
end
# Position of B in the Maze map
#
def finish_position
start_position
@start_finish_positions[1]
end
# The approach used here is a breadth-first search. Basically, the algorithm will start
# with the position of the starting point A. It will then expand all the possible moves
# that can be made from that position. Then, for each one of those calculated positions,
# a new set of possible moves will once again be calculated. This process repeats until
# there are either no possible moves left, meaning the maze is unsolvable; or until the
# final position (B) appears in the set of possible moves.
#
# Intuitively, one can think of this process in the following way: for each possible
# path that can be taken from the starting position, a new thread will be created in
# order to explore that path, thus all paths will be explored in parallel. Some will
# reach a deadend, but the first to find the "finish line" will be detected. So even with
# multiple paths to the final point, the shortest will be found first. The only problem
# here is the memory used to store all the possible moves for each step of the process.
#
# This algorithm uses a stack of Sets to find the solution. A Set is used to keep all the
# possible moves without duplicates, saving a bit of memory and CPU effort. It starts off
# with the position of A in the map. The algorithm then calculates a Set of possible moves
# that can be made from the start. This Set is then pushed on the stack.
# In the next loop iteration, the Set of moves on top of the stack will be analyzed and
# for each position a new Set of possible moves will be calculated. All those resulting
# positions are stores in the same Set and is once again pushed onto the stack.
# The loop will continue until:
# (a) There are no more possible moves, which means there's no solution. This is detected
# when the Set of moves on top of the stack is empty;
# (b) Or, when the Set on top of the stack contains the finish_position
# The only thing left to do is calculate the actual path that was taken and return a list
# of positions from point A to point B.
#
def solve
stack = [Set.new([start_position])]
visited = Set.new
while (!stack.last.include?(finish_position) && !stack.last.empty?) do
new_moves = Set.new
stack.last.each do |current_pos|
visited << current_pos
moves = possible_moves(current_pos).to_set
moves -= visited # Remove the moves that we've already made
unless moves.empty?
new_moves += moves
end
end
stack << new_moves
end
extract_path(stack)
end
# Because each level of the stack contains all the possible moves that can be made at
# that step, we need to traceback from the final position. Therefore, we start from the
# finish_position and calculate all the possible moves that can be made. We then
# calculate the intersection of that Set of moves with the ones in the stack, leaving
# behind the position for that step. We continue for all levels in the stack, which will
# then result in the starting position, and thus producing the shorted path.
#
def extract_path(stack)
return [] unless stack.last.include?(finish_position)
current_pos = finish_position
path = [finish_position]
(stack.length-2).downto(0) do |i|
moves_set = stack[i]
moves = possible_moves(current_pos).to_set
backtracked_move = moves_set & moves
backtracked_move.each { |m| current_pos = m }
path.unshift(current_pos)
end
path
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment