Create a gist now

Instantly share code, notes, and snippets.

@shenry /stu_henry.rb Secret
Created Dec 28, 2009

class Maze
# Will solve text mazes for food.
#
# This solution will find the most direct route form point A to point B.
#
# For grins, this maze will also display the solution to the maze with Maze#show_solution...
#
# #####################################
# # # .................# # #
# # ### #.# # ###########.### # ##### #
# # # #.# # # # ... # #
# # # ###A##### # # # # ###.###########
# # # # # # # # ... #
# ####### # ### ####### # ###.####### #
# # # # # # # .........#
# # ####### # # # ####### # ##### # #.#
# # # # # # # # # # #.#
# # ##### # # ##### ######### # ### #.#
# # # # # #B#
# #####################################
def initialize(maze)
# Convert maze string into an array for traversing
create_maze_array(maze)
# Get the height and width of the array, minus one for array index comparison
@width = maze.index("\n") - 1
@height = @maze_array.size - 1
# Setting the value of the target to be the height * width of the maze.
# This target will decrement by one for each adjacent space, allowing us to
# calculate the steps to the endpoint and also map the solution.
@b_value = @height * @width
# Creates a hash of all the spaces in the map.
# Hash keys are the address (row, column) of the space.
map_spaces(@maze_array)
# Stores the location of the start points and end points
@end = @spaces_hash.index("B")
@start = @spaces_hash.index("A")
# Starting from the end point, create a ToDo array of adjacent spaces
# to assign decrementing values.
create_todo_array(@spaces_hash)
until @todo_list.empty?
# Assign decrementing values to adjacent spaces
fill_maze(@todo_list)
end
end
def solvable?
@spaces_hash[@start].to_i > 0
end
def steps
if solvable?
@spaces_hash[@end] - @spaces_hash[@start]
else
return 0
end
end
def create_maze_array(maze)
@maze_array = maze.split("\n")
@maze_array.each_with_index do |s, i|
@maze_array[i] = s.split(//)
end
end
def map_spaces(maze_array)
@spaces_hash = Hash.new
maze_array.each_with_index do |array, row|
array.each_with_index do |element, column|
unless element == "#"
key = Array[row, column]
@spaces_hash[key] = element
end
end
end
end
def create_todo_array(spaces_hash)
@todo_list = []
# We're starting from the endpoint 'B'
start = spaces_hash.index("B")
spaces_hash[start] = @b_value
@todo_list << start
end
def fill_maze(todo_list)
todo_list.each do |address|
# Retrieve the current value of the space in the ToDo list, decrement by one.
value = get_value(address) - 1
get_adjacent_addresses(address)
fill_adjacent_addresses(address, value)
# Remove this element from the to-do list
@todo_list.delete(address)
end
end
def get_adjacent_addresses(address)
up = Array[ address[0] + 1, address[1] ]
down = Array[ address[0] - 1, address[1] ]
left = Array[ address[0], address[1] - 1 ]
right = Array[ address[0], address[1] + 1 ]
@neighbors = Array[ up, down, left, right ]
end
def fill_adjacent_addresses(address, value)
row = address[0]
column = address = [1]
@neighbors.each do |addr|
apply_value_to_space(addr, value)
end
end
def get_value(address)
# Gets the value of the current location.
# If the current location is 'B', the value is @target_value (the max value for the maze).
@spaces_hash[address] == "B" ? @b_value : @spaces_hash[address]
end
def apply_value_to_space(address, value)
# Check if location is valid
if @spaces_hash.has_key?(address)
# Make sure we don't over-write a larger value
if @spaces_hash[address].to_i < value
@spaces_hash[address] = value
# Add this location to the ToDo list
@todo_list << address
end
end
end
def show_solution
if solvable?
create_solution
@spaces_hash.each do |k, v|
if v == "."
row = k[0]
column = k[1]
@maze_array[row][column] = v
end
end
solution_string = ""
@maze_array.each do |array|
solution_string << array.to_s
solution_string << "\n"
end
puts solution_string
else
return "No solution to show, maze is unsolvable."
end
end
def solution_step(address)
@active_value = @spaces_hash[address]
@active_address = address
@spaces_hash[address] = "."
end
def create_solution
starting_value = @spaces_hash[@start]
@active_address = @start
@active_value = @spaces_hash[@start]
@spaces_hash[@start] = "A"
@spaces_hash[@end] = "B"
while @active_value < @b_value - 1
active_row = @active_address[0]
active_column = @active_address[1]
get_adjacent_addresses(@active_address)
@neighbors.each do |address|
if @spaces_hash.has_key?(address) && @spaces_hash[address].to_i > @active_value
solution_step(address)
end
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment