secret
Last active

RPCFN: Mazes (#5) Solution + Specs + Fixtures

  • Download Gist
fixtures.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
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 #
#####
}
maze_private_spec.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
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
maze_spec.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
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
raoulfelix.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
=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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.