public
Created — forked from alg/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
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
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
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.