Create a gist now

Instantly share code, notes, and snippets.

=begin
Title: Ruby Challenge #5
Program Description: Maze Solver
Submitted By: Jean-Christophe Cyr
=end
class Maze
MAZE_START = 'A'
MAZE_END = 'B'
NAVIGABLE_SPACE = ' '
Coordinates = Struct.new("Coordinates", :col, :row)
def initialize(maze)
@maze = []
maze.each_line { | s |
current_line = s.split('')
@maze << current_line
start_column = current_line.index(MAZE_START)
@start_cell = Coordinates.new(start_column, @maze.size-1) unless start_column.nil?
end_column = current_line.index(MAZE_END)
@end_cell = Coordinates.new(end_column, @maze.size-1) unless end_column.nil?
}
end
#
# Returns true if the maze can be solved
#
def solvable?
find_solution > 0
end
#
# Find the minimum number of steps to solve the maze
#
def steps
find_solution
end
private
#
# Find the number of steps using shortest path algorithm
#
def find_solution
open = [{:cell => @start_cell, :parent => nil, :distance => 0}]
closed = []
while !open.empty?
# Find the lowest movement cost
current_node = open.min{ |a,b| a[:distance] <=> b[:distance]}
# Check if we reached the end cell
if is_end?(current_node[:cell])
return current_node[:distance]
end
# Find immediate neighbors
current_neighbors = find_neighbors(current_node[:cell])
current_neighbors.each { | neighbor |
if closed.find { | node | node[:cell].eql?(neighbor[:cell])}.nil?
# Find if the cell is already in the open list
existing_open = open.find { |node | node[:cell].eql?(neighbor[:cell])}
if existing_open
# Find the shorter distance to the cell
current_distance = existing_open[:distance]
new_distance = current_node[:distance] + neighbor[:distance]
existing_opened[:distance] = new_distance if current_distance > new_distance
else
# Add the new visited cell to the open list
neighbor[:distance] = neighbor[:distance] + current_node[:distance]
open << neighbor
end
end
}
closed << current_node
open.delete(current_node)
end
0
end
#
# Find ajacent intersections of the cell
#
def find_neighbors(cell)
neighbors = []
neighbors << find_top_path(cell)
neighbors << find_right_path(cell)
neighbors << find_bottom_path(cell)
neighbors << find_left_path(cell)
# Return all the neighbors with the parent cell and the distance between them
neighbors.compact.collect { |current_cell| {:cell => current_cell, :parent => cell, :distance => find_distance_between(current_cell, cell)}}
end
#
# Finds the intersection at the top of the cell
#
def find_top_path(cell)
find_path(cell) { | cell | top_cell(cell) }
end
#
# Finds the intersection at the right of the cell
#
def find_right_path(cell)
find_path(cell) { | cell | right_cell(cell) }
end
#
# Finds the intersection at the bottom of the cell
#
def find_bottom_path(cell)
find_path(cell) { | cell | bottom_cell(cell) }
end
#
# Finds the intersectionat the left of the cell
#
def find_left_path(cell)
find_path(cell) { | cell | left_cell(cell) }
end
#
# Finds the intersection ajacent to the cell
#
def find_path(cell, &block)
current_cell = cell
begin
current_cell = yield(current_cell)
return current_cell if is_intersection?(current_cell)
end while is_navigable_space?(current_cell)
nil
end
#
# Returns the distance between two cells that are
# on the same row or same column
#
def find_distance_between(cell1, cell2)
if cell1.nil? || cell2.nil?
return 0
end
if cell1.col == cell2.col || cell1.row == cell2.row
return ((cell1.row - cell2.row) + (cell1.col - cell2.col)).abs
end
0
end
#
# Returns true if the cell is the start cell
#
def is_start?(cell)
@start_cell.eql?(cell)
end
#
# Returns true if the cell is the end cell
#
def is_end?(cell)
@end_cell.eql?(cell)
end
#
# Returns true if the cell is navigable
#
def is_navigable_space?(cell)
return false if cell.nil?
return false unless is_valid_cell?(cell)
value = @maze[cell.row][cell.col]
NAVIGABLE_SPACE.eql?(value) || is_start?(cell) || is_end?(cell)
end
#
# Returns true if the cell is an intersection, the start cell or the end cell
#
def is_intersection?(cell)
return false unless is_navigable_space?(cell)
return true if is_start?(cell) || is_end?(cell)
navigable_top_cell = is_navigable_space?(top_cell(cell))
navigable_bottom_cell = is_navigable_space?(bottom_cell(cell))
navigable_left_cell = is_navigable_space?(left_cell(cell))
navigable_right_cell = is_navigable_space?(right_cell(cell))
if ((navigable_top_cell || navigable_bottom_cell) && (navigable_left_cell || navigable_right_cell))
return true
end
return false
end
#
# Get the cell at the top
#
def top_cell(cell)
get_next_cell(cell) { | cell | Coordinates.new(cell.col, cell.row-1)}
end
#
# Get the cell at the bottom
#
def bottom_cell(cell)
get_next_cell(cell) { | cell | Coordinates.new(cell.col, cell.row+1)}
end
#
# Get the cell at the left
#
def left_cell(cell)
get_next_cell(cell) { | cell | Coordinates.new(cell.col-1, cell.row)}
end
#
# Get the cell at the right
#
def right_cell(cell)
get_next_cell(cell) { | cell | Coordinates.new(cell.col+1, cell.row)}
end
#
# Get a cell that is ajacent to a cell
#
def get_next_cell(cell, &block)
return nil if cell.nil?
next_cell = yield(cell)
return next_cell if is_valid_cell?(next_cell)
nil
end
#
# Check is a given cell is out of bounds
#
def is_valid_cell?(cell)
if cell.nil?
return false
end
if cell.col < 0 || cell.row < 0
return false
end
if cell.row < @maze.size && cell.col < @maze[0].size
return true
end
false
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment