secret
Created — forked from rfelix/fixtures.rb

  • 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
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
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
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
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
=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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.