secret
Created

  • Download Gist
stu_henry.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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.