-
-
Save IndianGuru/349d7ec9de274c37b161 to your computer and use it in GitHub Desktop.
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 ## | |
####### | |
} |
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 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 |
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 | |
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