public
Created — forked from jbgutierrez/maze.rb

  • Download Gist
maze.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
class String
alias_method :is_a, :==
alias_method :is_an, :==
end
 
class Maze
NAVIGABLE = ' '
WALL = '#'
POINT_A = 'A'
POINT_B = 'B'
def initialize(input)
# builds a multidimensional representation of the input string
@labyrinth = input.split("\n").map { |line| line.scan(/./) }
 
# finds the POINT_A coordinates
line = @labyrinth.detect { |l| l.include?(POINT_A)}
y = @labyrinth.index(line)
x = line.index(POINT_A)
@start_point = [y, x]
end
def solvable?(position = init_steps_taken_and_return_first, &block)
# checks wheter we found the target position
if at(position).is_an(POINT_B)
# avoids unnecesary iterations when we only want to know if a maze is solvable
return true unless block_given?
#yields the amount of steps for this particular solution
steps_amount = caller.grep(/solvable/).length / 2
yield steps_amount
end
# "Steps"
# can only be taken up, down, left or right
# cannot be taken throught walls :-)
# shouldn't be taken more than once
y, x = *position
steps_available = [ [y - 1, x],
[ y, x - 1], [ y, x + 1],
[y + 1, x] ]
steps_available.reject! do |p|
at(p).is_a(WALL) || @steps_taken.include?(p)
end
@steps_taken.concat(steps_available)
# recursively looks for the POINT_B from each step available
steps_available.any? { |step| solvable?(step, &block) }
end
def steps
amounts = []
solvable? do |amount|
amounts << amount
end
amounts.min || 0
end
private
def at(position)
y, x = *position
@labyrinth[y][x]
end
def init_steps_taken_and_return_first
@steps_taken = [ @start_point ]
@start_point
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
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
 
class MazeTest < Test::Unit::TestCase
def test_good_mazes
assert_equal true, Maze.new(MAZE1).solvable?
assert_equal true, Maze.new(MAZE2).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
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.