Skip to content

@RLGGHC /maze.rb forked from alg/maze.rb
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
class Maze
WALL = '#'
EMPTY = ' '
attr_reader :steps
def initialize(spec)
@spec = spec.split("\n").map { |line| line.split('') }
solve
end
def solvable?
steps > 0
end
private
# Fill all dead ends with walls until there are none.
# If there are empty areas -- it's our path, so count steps
# and add one for the final step over 'B'.
def solve
begin
has_updates, @steps = false, 0
@spec.each_with_index do |row, y|
row.each_with_index do |cell, x|
if cell == EMPTY && deadend?(x, y)
row[x] = WALL
has_updates = true
end
@steps += 1 if row[x] == EMPTY
end
end
end while has_updates
@steps += 1 if @steps > 0
end
# If more than 2 walls around, it's dead end
def deadend?(x, y)
[ [0, -1], [1, 0], [0, 1], [-1, 0] ].inject(0) do |memo, delta|
memo + (@spec[y + delta[1]][x + delta[0]] == WALL ? 1 : 0)
end > 2
end
end
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 solvable?(MAZE1)
assert solvable?(MAZE2)
end
def test_bad_mazes
assert !solvable?(MAZE3)
end
def test_maze_steps
assert_steps 44, MAZE1
assert_steps 75, MAZE2
assert_steps 0, MAZE3
end
def assert_steps(steps, spec)
assert_equal steps, Maze.new(spec).steps
end
def solvable?(spec)
Maze.new(spec).solvable?
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.