Skip to content

Instantly share code, notes, and snippets.

@leobessa
Created January 14, 2010 18:48
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save leobessa/c430ff419e2e795a72c4 to your computer and use it in GitHub Desktop.
class Maze
attr_reader :start_point, :end_point
def initialize map
@cell_map = map.lines.map { |b| b.scan(/./)}
map.lines.each_with_index do |line,line_index|
@start_point ||= [line_index,line.index('A')] if line.include?('A')
@end_point ||= [line_index,line.index('B')] if line.include?('B')
break if @start_point and @end_point
end
end
def solvable?
@steps = 1
origins = [start_point]
until origins.empty?
selected_neighbors = []
origins.each do |(x,y)|
neighbors = [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]
return true if neighbors.include? @end_point
selected_neighbors += neighbors.find_all do |(a,b)|
@cell_map[a][b] = @steps if @cell_map[a][b] == " "
end
end
origins = selected_neighbors
@steps += 1
end
false
end
def steps
solvable? ? @steps : 0
end
end
require 'test/unit'
require 'leonardobessa'
MAZE1 = %{#####################################
# # # #A # # #
# # # # # # ####### # ### # ####### #
# # # # # # # # #
# ##### # ################# # #######
# # # # # # # # #
##### ##### ### ### # ### # # # # # #
# # # # # # B# # # # # #
# # ##### ##### # # ### # # ####### #
# # # # # # # # # # # #
# ### ### # # # # ##### # # # ##### #
# # # # # # #
#####################################}
# Maze 1 should SUCCEED
MAZE2 = %{#####################################
# # # # # #
# ### ### # ########### ### # ##### #
# # # # # # # # # #
# # ###A##### # # # # ### ###########
# # # # # # # # #
####### # ### ####### # ### ####### #
# # # # # # # #
# ####### # # # ####### # ##### # # #
# # # # # # # # # # #
# ##### # # ##### ######### # ### # #
# # # # #B#
#####################################}
# Maze 2 should SUCCEED
MAZE3 = %{#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################}
# Maze 3 should FAIL
SIMPLE_MAZE = %{#####
# #
# A #
# #
#####%}
class MazeTest < Test::Unit::TestCase
def test_start_point
assert_equal [2,2],Maze.new(SIMPLE_MAZE).start_point
end
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