secret
Created — forked from mminneman1/marcminneman.rb

  • Download Gist
marcminneman.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
=begin
Introduction
 
Mazes are known to have challenged humans from as far back as the 5th century
BC. There are many types of maze, but typically you need to find your way from
a start point to an end point.
 
In this Ruby challenge, you will need to develop a class that can be used to
solve mazes. Mazes will be provided as a string showing a graphical
representation of the maze’s layout. Spaces are navigable, while # (pound)
symbols are used to denote walls. In this challenge the letter "A" is used to
mark the start point, and "B" the end point. Here’s an example of a maze
contained within a string:
 
MAZE1 = %{#####################################
# # # #A # # #
# # # # # # ####### # ### # ####### #
# # # # # # # # #
# ##### # ################# # #######
# # # # # # # # #
##### ##### ### ### # ### # # # # # #
# # # # # # B# # # # # #
# # ##### ##### # # ### # # ####### #
# # # # # # # # # # # #
# ### ### # # # # ##### # # # ##### #
# # # # # # #
#####################################}
 
The prior maze would be loaded into a Maze object like so:
 
Maze.new(MAZE1)
 
The Challenge
 
There are two parts to the challenge: you can choose to do one or both,
depending on your skill level or how much time you have available.
 
1. Implement a Maze#solvable? method that returns true/false depending on
whether it’s possible to navigate the maze from point A to point B.
2. Implement a Maze#steps method that returns an integer of the least number
of "steps" one would have to take within the maze to get from point A to
point B. "Steps" can only be taken up, down, left or right. No diagonals.
 
There are a number of ways to "solve" mazes but there’s a wide scope for you to
be as straightforward or as clever as you like with this challenge (tip: I’d
love to see some clever/silly solutions!). Your "solvable?" and "steps" methods
could share algorithms or you might come up with alternate ways to be more
efficient in each case. Good luck!
=end
 
class Array
# locate given element in 2D array and return coordinates
def coordinates_2d(element)
self.each_with_index do |subarray, i|
raise ArgumentError, 'receiver object must be a 2d array' unless subarray.is_a? Array
j = subarray.index(element)
return i, j if j
end
nil
end
end
 
class Maze
 
def initialize(maze)
raise ArgumentError, "Maze contains an illegal character. Use only ['#',' ','A','B']." if maze.match(/[^#\sAB]/) #precondition
raise ArgumentError, "Maze must include exactly one starting point (A) and one finishing point (B)." unless maze.match(/^[^A]*A[^A]*$/) && maze.match(/^[^B]*B[^B]*$/) #precondition
@maze = maze.lines.map{|l| l.tr("\n",'').chars.to_a} # encode maze as 2D array
raise ArgumentError, "Maze must have a walled(#) border." unless [@maze[0], @maze[-1]].inject(true) {|r,l| r&&=!l.join.match(/[^#]/)} && @maze[1..-2].inject(true) {|r,l| r&&=l[0]=='#'&&l[-1]=='#'} #precondition
@queue = [@maze.coordinates_2d('A') << 0] # enqueue root coordinate along with distance for bfsearch
end
 
def solvable?
@solvable ||= bfsearch # results are cached to minimize cost in "steps" method
end
 
def steps
self.solvable? ? @steps : 0
end
 
private
 
def bfsearch
# search method that implements a Breadth-First Search Algorithm
#
# A maze can be viewed as a finite graph and "bfsearch" will find the
# shortest path from A to B.
#
# For more details see:
#
# http://en.wikipedia.org/wiki/Breadth-first_search
#
r,c,@steps = @queue.shift # dequeue a coordinate and distance from root
return true if [r,c]== @finish ||= @maze.coordinates_2d('B') # if the finish coordinate is found, quit the search and return a positive result
(@examined ||=[]) << [r,c] # ensure that each coordinate is examined only once
# enqueue all successor coordinates and new distance from root coordinate
# successor coordinates are found above [r+1,c+0], below [r-1,c+0], left [r+0,r-1], and right [r+0,r+1] of current coordinate
[[1,0],[-1,0],[0,-1],[0,1]].each do |x, y|
new_r, new_c, distance = r+x, c+y, @steps+1
@queue << [new_r,new_c,distance] if !@examined.index([new_r,new_c]) && @maze[new_r][new_c].match(/[\sB]/)
end
return false if @queue.empty? # If the queue is empty, every reachable coordinate in the maze has been examined, return a negative result
bfsearch # recursively repeat search until a result a result is achieved
end
 
end
maze_test.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
require 'test/unit'
require 'maze'
 
MAZE1 = %{#####################################
# # # #A # # #
# # # # # # ####### # ### # ####### #
# # # # # # # # #
# ##### # ################# # #######
# # # # # # # # #
##### ##### ### ### # ### # # # # # #
# # # # # # B# # # # # #
# # ##### ##### # # ### # # ####### #
# # # # # # # # # # # #
# ### ### # # # # ##### # # # ##### #
# # # # # # #
#####################################}
# Maze 1 should SUCCEED
 
MAZE2 = %{#####################################
# # # # # #
# ### ### # ########### ### # ##### #
# # # # # # # # # #
# # ###A##### # # # # ### ###########
# # # # # # # # #
####### # ### ####### # ### ####### #
# # # # # # # #
# ####### # # # ####### # ##### # # #
# # # # # # # # # # #
# ##### # # ##### ######### # ### # #
# # # # #B#
#####################################}
# Maze 2 should SUCCEED
 
MAZE3 = %{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 3 should FAIL
 
MAZE4 = %{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # AB # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # # # # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 4 shoud SUCCEED (trivial)
 
MAZE5 = %{#####################################
# # # # #
# ### # ####### # # # ############# #
# # #X # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 5 should FAIL precondition check (illegal character)
 
MAZE6 =%{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 6 should FAIL precondition check (missing start coordinate)
 
MAZE7 =%{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # # # # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 7 should FAIL precondition check (missing finish coordinate)
 
MAZE8 =%{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#################### ################}
# Maze 8 should FAIL precondition check (missing horizontal border wall)
 
MAZE9 =%{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 9 should FAIL precondition check (missing vertical border wall)
 
class MazeTest < Test::Unit::TestCase
def test_good_mazes
assert_equal true, Maze.new(MAZE1).solvable?
assert_equal true, Maze.new(MAZE2).solvable?
assert_equal true, Maze.new(MAZE4).solvable?
end
 
def test_bad_mazes
assert_equal false, Maze.new(MAZE3).solvable?
end
 
def test_maze_steps
assert_equal 44, Maze.new(MAZE1).steps
assert_equal 75, Maze.new(MAZE2).steps
assert_equal 0, Maze.new(MAZE3).steps
assert_equal 1, Maze.new(MAZE4).steps
end
 
def test_error_illegal_character
e = assert_raise(ArgumentError) { Maze.new(MAZE5) }
assert_match(/Maze contains an illegal character/, e.message)
end
 
def test_error_missing_start
e = assert_raise(ArgumentError) { Maze.new(MAZE6) }
assert_match(/Maze must include exactly one starting point/, e.message)
end
 
def test_error_missing_finish
e = assert_raise(ArgumentError) { Maze.new(MAZE7) }
assert_match(/Maze must include exactly.+ one finishing point/, e.message)
end
 
def test_error_missing_horiz_border
e = assert_raise(ArgumentError) { Maze.new(MAZE8) }
assert_match(/Maze must have a walled\(#\) border/, e.message)
end
 
def test_error_missing_vert_border
e = assert_raise(ArgumentError) { Maze.new(MAZE9) }
assert_match(/Maze must have a walled\(#\) border/, e.message)
end
 
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.