Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Solution for the Rubylearning Challenge #5 (http://tinyurl.com/yf8lxch)

View maze.rb
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 array representation from 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 if 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
View maze.rb
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
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.