-
-
Save rb2k/1a40b12a2c17b9d81c98 to your computer and use it in GitHub Desktop.
My RPCFN: Mazes (#5) solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
puts "test started" | |
require "maze.rb" | |
MAZE1 = %{##################################### | |
# # # #A # # # | |
# # # # # # ####### # ### # ####### # | |
# # # # # # # # # | |
# ##### # ################# # ####### | |
# # # # # # # # # | |
##### ##### ### ### # ### # # # # # # | |
# # # # # # B# # # # # # | |
# # ##### ##### # # ### # # ####### # | |
# # # # # # # # # # # # | |
# ### ### # # # # ##### # # # ##### # | |
# # # # # # # | |
#####################################} | |
MAZE2 = %{##################################### | |
# # # # # # | |
# ### ### # ########### ### # ##### # | |
# # # # # # # # # # | |
# # ###A##### # # # # ### ########### | |
# # # # # # # # # | |
####### # ### ####### # ### ####### # | |
# # # # # # # # | |
# ####### # # # ####### # ##### # # # | |
# # # # # # # # # # # | |
# ##### # # ##### ######### # ### # # | |
# # # # #B# | |
#####################################} | |
# Maze 2 should SUCCEED | |
MAZE3 = %{##################################### | |
# # # # # | |
# ### # ####### # # # ############# # | |
# # # # # # # # # # | |
### ##### ### ####### # ##### ### # # | |
# # # # A # # # # # | |
# ######### ##### # ####### ### ### # | |
# ### # # # # # | |
# ### ### ####### ####### # # # # ### | |
# # # # # #B# # # # # # # | |
# # # ##### ### # # # # ### # ##### # | |
# # # # # # | |
#####################################} | |
# Maze 3 should FAIL | |
[MAZE1, MAZE2, MAZE3].each_with_index do |input_maze, index| | |
my_maze = Maze.new(input_maze) | |
#cleaning screen | |
puts "\e[H\e[2J" | |
my_maze.pretty_print | |
puts "Starting with Maze #{index+1}" | |
puts "Is solvable: #{my_maze.solvable?}" | |
puts "Shortest path is #{my_maze.steps} steps long" if my_maze.solvable? | |
sleep 3 | |
my_maze.movie_time(false) | |
sleep 3 | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'test/unit' | |
require 'maze' | |
MAZE1 = %{##################################### | |
# # # #A # # # | |
# # # # # # ####### # ### # ####### # | |
# # # # # # # # # | |
# ##### # ################# # ####### | |
# # # # # # # # # | |
##### ##### ### ### # ### # # # # # # | |
# # # # # # B# # # # # # | |
# # ##### ##### # # ### # # ####### # | |
# # # # # # # # # # # # | |
# ### ### # # # # ##### # # # ##### # | |
# # # # # # # | |
#####################################} | |
# Maze 1 should SUCCEED | |
MAZE2 = %{##################################### | |
# # # # # # | |
# ### ### # ########### ### # ##### # | |
# # # # # # # # # # | |
# # ###A##### # # # # ### ########### | |
# # # # # # # # # | |
####### # ### ####### # ### ####### # | |
# # # # # # # # | |
# ####### # # # ####### # ##### # # # | |
# # # # # # # # # # # | |
# ##### # # ##### ######### # ### # # | |
# # # # #B# | |
#####################################} | |
# Maze 2 should SUCCEED | |
MAZE3 = %{##################################### | |
# # # # # | |
# ### # ####### # # # ############# # | |
# # # # # # # # # # | |
### ##### ### ####### # ##### ### # # | |
# # # # A # # # # # | |
# ######### ##### # ####### ### ### # | |
# ### # # # # # | |
# ### ### ####### ####### # # # # ### | |
# # # # # #B# # # # # # # | |
# # # ##### ### # # # # ### # ##### # | |
# # # # # # | |
#####################################} | |
# Maze 3 should FAIL | |
class MazeTest < Test::Unit::TestCase | |
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Maze | |
def initialize(ascii_maze) | |
#used to store start + end info | |
@maze_info = Hash.new | |
#used to store a 2d array representation of the maze | |
@maze_array = Array.new | |
#used to store data where the solving algorithm has been in the maze | |
@been_there = Array.new | |
#this is the shortest path, destilled by filtering loops from @been_there | |
@steps = Array.new | |
#if we find a solution, this will be set to true | |
@found_way_to_the_exit = false | |
#let's convert the ascii maze to a 2 dimensional array | |
#also: take a note where start and exit are | |
current_index = 0 | |
ascii_maze.each_line do |line| | |
current_line = line.chomp.split("") | |
@maze_array << current_line | |
@maze_info["maze_start"] = [current_index, current_line.index("A")] if current_line.include?("A") | |
@maze_info["maze_exit"] = [current_index, current_line.index("B")] if current_line.include?("B") | |
current_index += 1 | |
end | |
#start the algorithm (fills @been_there and @found_a_way_to_the_exit) | |
self.find_exit(@maze_info["maze_start"]) | |
#now let's look for the actual shortest path, we basically elimitate loops from @been_there | |
@been_there.each do |step| | |
if !@steps.include?(step) | |
@steps << step | |
else | |
@steps = @steps[0..@steps.index(step)] | |
end | |
end | |
end | |
def pretty_print(maze = @maze_array) | |
#just print out a visual representation of the maze | |
#also used in movie_time | |
maze.each do |line| | |
puts line.join(" ") | |
end | |
end | |
def movie_time(optimal = true) | |
#show the shortest path in a movie :) | |
movie_array = @maze_array | |
#do we want the ACTUAL way the algorithm looked for the exit or just the shortest (optimal) path? | |
if optimal | |
move_list = @steps | |
else | |
move_list = @been_there | |
end | |
move_list.each do |step| | |
movie_array[step[0]][step[1]] = "X" | |
puts "\e[H\e[2J" | |
self.pretty_print(movie_array) | |
puts "Current position: #{step.inspect}" | |
puts "Distance to exit (#{@maze_info["maze_exit"].inspect}): #{aerial_point_distance(step, @maze_info["maze_exit"])}" | |
puts "possible moves:" | |
self.possible_moves(step).each do |possibility| | |
puts "#{possibility.inspect} --> distance to exit: #{aerial_point_distance(possibility[1], @maze_info["maze_exit"])}" | |
end | |
sleep 0.1 | |
puts @maze_info.inspect | |
puts "used #{move_list.size - 1} steps to arrive at #{move_list.last}" | |
end | |
end | |
def aerial_point_distance(position1, position2) | |
#calculates the direct distance between two points in a maze | |
distance = 0 | |
#vertical distance | |
distance += (position1[0] - position2[0]).abs | |
#horizontal distance | |
distance += (position1[1] - position2[1]).abs | |
#return accumulated distance | |
distance | |
end | |
def possible_moves(current_pos) | |
#will return an array of possible moves and their resulting coordinates from position current_pos such as: | |
#[ ["up", [5,9]] , ["left", [4,8]] ] | |
possible_array = Array.new | |
if @maze_array[current_pos[0] - 1][current_pos[1]] != "#" | |
possible_array << ["up", [current_pos[0] - 1, current_pos[1]]] | |
end | |
if @maze_array[current_pos[0] + 1][current_pos[1]] != "#" | |
possible_array << ["down", [current_pos[0] + 1, current_pos[1]]] | |
end | |
if @maze_array[current_pos[0]][current_pos[1] - 1] != "#" | |
possible_array << ["left", [current_pos[0], current_pos[1] - 1]] | |
end | |
if @maze_array[current_pos[0]][current_pos[1] + 1] != "#" | |
possible_array << ["right", [current_pos[0], current_pos[1] + 1]] | |
end | |
#let's sort the moves by aerial distance to the exit... might make things quicker on big mazes | |
possible_array.sort{|pos1,pos2| self.aerial_point_distance(pos1[1],@maze_info["maze_exit"]) <=> self.aerial_point_distance(pos2[1],@maze_info["maze_exit"]) } | |
end | |
def find_exit(current_pos) | |
#let's iterate though all the possibles moves from our current direction | |
#we'll only look at moves that lead to a position we haven't been at so far | |
#for each new position, we'll look (recursively) for possible moves again | |
#we quit once we find the exit marked "B" or once we run out of moves | |
possible_moves(current_pos).each do |direction| | |
#if we already set the found flag, we might as well quit :) | |
break if @found_way_to_the_exit | |
if @been_there.include?(direction[1]) | |
#We've already been in this direction, no need to try again | |
next | |
else | |
#yay, a new direction we haven't been at so far | |
#let's add this to our array of visited coordinates | |
@been_there << current_pos | |
#let's check if we've arrived at the exit | |
if @maze_array[direction[1][0]][direction[1][1]] == "B" | |
@found_way_to_the_exit = true | |
#add our last step to the @been_there array | |
@been_there << [direction[1][0],direction[1][1]] | |
break | |
else | |
#not at the exit yet, let's try again using recursion | |
self.find_exit(direction[1]) | |
end | |
end | |
end | |
end | |
def solvable?() | |
@found_way_to_the_exit | |
end | |
def steps | |
if @found_way_to_the_exit == false | |
return 0 | |
else | |
#because I actually count the amount of coordinates we pass, we have to subtract 1 | |
return @steps.size - 1 | |
end | |
end | |
def print_steps_list | |
@steps.each{|step| print "#{step.inspect} -> "} | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment