Skip to content

@IndianGuru /fixtures.rb secret forked from rfelix/fixtures.rb
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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 ##
#######
}
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
=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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.