RPCFN: Mazes (#5) Solution + Specs + Fixtures
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 # | |
##### | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
=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