Create a gist now

Instantly share code, notes, and snippets.

# Peter Cooper's initial Maze solution
class Maze
START_CHARACTER = 'A'
END_CHARACTER = 'B'
WALL_CHARACTER = '#'
def initialize(maze)
# Get the height and width of the maze
@maze_width = maze[/^.*?\n/].length - 1
@maze_height = maze.split(/\n/).length
# Store the maze as a string without any newlines
@maze = maze.gsub(/\n/, '')
# Get co-ordinates of the start and end points
@start_x, @start_y = position_to_coords(@maze.index(START_CHARACTER))
@end_x, @end_y = position_to_coords(@maze.index(END_CHARACTER))
@routes = []
end
# Returns true if the maze is solvable, false if not.
def solvable?
old_maze = @maze.dup
flood_fill(@start_x, @start_y)
possible = !@maze.index(END_CHARACTER)
@maze = old_maze
possible
end
# Returns how many steps are necessary to get from the start to the end of the maze
def steps
@steps = []
old_maze = @maze.dup
walk_maze(@start_x, @start_y)
possible = !@maze.index(END_CHARACTER)
@maze = old_maze
@steps.min
end
private
# Convert a literal position within the maze string to X/Y co-ordinates
def position_to_coords(pos)
[pos % @maze_width, pos / @maze_width]
end
# Convert X/Y co-ordinates into a literal position within the maze string
def coords_to_position(x, y)
y * @maze_width + x
end
# Flood fill non wall areas of the maze
def flood_fill(x, y)
unless [WALL_CHARACTER, '.'].include?(@maze[coords_to_position(x, y)].chr)
@maze[coords_to_position(x, y)] = '.'
flood_fill(x - 1, y)
flood_fill(x + 1, y)
flood_fill(x, y - 1)
flood_fill(x, y + 1)
end
end
# Flood fill but track steps involved to an end point
# A horribly lazy way to solve the "steps" issue
def walk_maze(x, y, steps = 0)
unless [WALL_CHARACTER, '.'].include?(@maze[coords_to_position(x, y)].chr)
if x == @end_x && y == @end_y
@steps << steps
return
end
@i ||= 0
@i += 1
if defined?(DEBUG)
sleep 0.05
print "\e[2J\e[f"
puts @maze.scan(/.{37}/)
end
@maze[coords_to_position(x, y)] = '.'
walk_maze(x - 1, y, steps + 1) if neighbors(x - 1, y) == 1
walk_maze(x + 1, y, steps + 1) if neighbors(x + 1, y) == 1
walk_maze(x, y - 1, steps + 1) if neighbors(x, y - 1) == 1
walk_maze(x, y + 1, steps + 1) if neighbors(x, y + 1) == 1
@maze[coords_to_position(x, y)] = ' '
end
end
# Return how many neighboring dots there are at a certain location
def neighbors(x, y)
neighbors = 0
neighbors += 1 if x - 1 >= 0 && @maze[coords_to_position(x - 1, y)].chr == '.'
neighbors += 1 if x + 1 < @maze_width && @maze[coords_to_position(x + 1, y)].chr == '.'
neighbors += 1 if y - 1 >= 0 && @maze[coords_to_position(x, y - 1)].chr == '.'
neighbors += 1 if y + 1 < @maze_height && @maze[coords_to_position(x, y + 1)].chr == '.'
neighbors
end
end
if $0 == __FILE__
MAZE1 = %{#####################################
# # # # # # #
# # # # # # ####### # ### # ####### #
# # # # # # # # #
# ##### # ################# # #######
# A# # # # # # # #
##### ##### ### ### # ### # # # # # #
# # # # # # B# # # # # #
# # ##### ##### # # ### # # ####### #
# # # # # # # # # # # #
# ### ### # # # # ##### # # # ##### #
# # # # # # #
#####################################}
a = Maze.new(MAZE1)
puts a.solvable?
puts a.steps
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment