public
Last active — forked from jurgens/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 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
#
# Copyright (c) Yuri Omelchuk <jurgen@upscript.com>
#
# January 8, 2009
#
# Maze class written for RubyLearning contest
# http://rubylearning.com/blog/2009/12/27/rpcfn-mazes-5/
#
# solution is based on find shortest path algorithm
#
 
class Maze
 
WALL = '#'
SPACE = ' '
START = 'A'
FINISH = 'B'
 
def initialize(structure)
 
# build a maze map
@map = []
structure.split("\n").each_with_index do |line, i|
@map[i] = []
line.each_char do |c|
@map[i] << c
end
end
 
solve # use a find shortest path method to solve a maze
end
 
def solvable?
(n, m) = find_start
for (a, b) in neighbor_cells(n, m)
return true if is_number?(a, b)
end
 
false
end
 
def steps
s = []
(n, m) = find_start
 
# find possible multiple solutions and select minimal number of steps
for (a, b) in neighbor_cells(n, m)
if is_number?(a, b)
s << @map[a][b]
end
end
 
return s.empty? ? 0 : s.min + 1 # add 1 for very last step
end
 
def display
for n in (0..@map.size - 1) do
puts @map[n].map{|e| e.to_s.center(3)}.join(' ')
end
end
 
protected
 
def solve
#start from finish
@queue = []
@queue << find_finish
step = 1
 
while !@queue.empty? do
@queue = round(@queue, step)
step += 1
end
end
 
# perform a round in finding shortest path algorithm
def round(queue, step)
next_round = []
while !queue.empty? do
(n, m) = queue.shift
for (a, b) in neighbor_cells(n, m)
if space?(a, b)
@map[a][b] = step
next_round << [a, b]
end
end
end
next_round
end
 
# check if cell is empty
def space?(n, m)
@map[n][m] == SPACE
end
 
# check if cell contains a number (which means a step number)
def is_number?(n, m)
is_int(@map[n][m])
end
 
# return array of neighbor cells coordinates
def neighbor_cells(n, m)
cells = []
cells << [n-1, m] if n > 0
cells << [n+1, m] if n < height
cells << [n, m-1] if m > 0
cells << [n, m+1] if m < width
return cells
end
 
# check if variable contains integer value
def is_int(value)
true if Integer(value) rescue false
end
 
# get width of the maze
def width
@map[0].size
end
 
# get height of the maze
def height
@map.size
end
 
# find a cell marked as start
def find_start
find_cell(START)
end
 
# find a cell marked as finish
def find_finish
find_cell(FINISH)
end
 
# find a cell coordinates by cell value
def find_cell(key)
for n in (0..@map.size - 1)
for m in (0..@map[n].size - 1)
if @map[n][m] == key
return [n, m]
end
end
end
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
require 'test/unit'
require 'maze'
 
MAZE1 = %{#####################################
# # # #A # # #
# # # # # # ####### # ### # ####### #
# # # # # # # # #
# ##### # ################# # #######
# # # # # # # # #
##### ##### ### ### # ### # # # # # #
# # # # # # B# # # # # #
# # ##### ##### # # ### # # ####### #
# # # # # # # # # # # #
# ### ### # # # # ##### # # # ##### #
# # # # # # #
#####################################}
 
MAZE2 = %{#####################################
# # # # # #
# ### ### # ########### ### # ##### #
# # # # # # # # # #
# # ###A##### # # # # ### ###########
# # # # # # # # #
####### # ### ####### # ### ####### #
# # # # # # # #
# ####### # # # ####### # ##### # # #
# # # # # # # # # # #
# ##### # # ##### ######### # ### # #
# # # # #B#
#####################################}
 
 
MAZE3 = %{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
 
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.