Created
January 18, 2010 08:51
-
-
Save patio11/279891 to your computer and use it in GitHub Desktop.
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
#This solves the maze using regular expressions, because I am too | |
#lazy to worry about arrays, darn it. It is inefficient as heck and designed | |
#purely to demonstrate perversion of sound CS principals. | |
# | |
# Code by Patrick McKenzie, 2010. I release this work unto the public domain. | |
class Maze | |
def initialize(maze_string) | |
@width = maze_string.split("\n")[0].length #width of maze in characters | |
@guts = maze_string.gsub("\n", "") #maze as a flat string -- no newlines | |
@size = @guts.length #Sanity check, ho. | |
end | |
#Use regular expressions to do a single step in any possible direction from | |
#any square on the board reachable from a square previously reached. | |
# | |
#Uses C to mark a square which we reached this turn, and reuses A to mark | |
#a square already reached. | |
# | |
#The width of the maze in dots, minus one dot, is enough to wrap around to the | |
#same column on the next row. | |
# | |
#Note side effect of last line returns nil if no square was marked this turn. | |
#Sidenote: this could all be one regexp but even I'm not that evil. | |
def floodfill_with_inefficient_magic! | |
@guts.gsub!(/A /, "AC") | |
@guts.gsub!(/A(#{"." * (@width - 1)}) /, 'A\1C') | |
@guts.gsub!(/ A/, "CA") | |
@guts.gsub!(/ (#{"." * (@width - 1)})A/, 'C\1A') | |
@guts.gsub!("C", "A") #Mark all new places as reached simultaneously. | |
end | |
#If a square we've reached is adjacent to the exit B, game over, we win. | |
def is_solved? | |
@guts =~ /AB|BA|A#{"." * (@width - 1)}B|B#{"." * (@width - 1)}A/ | |
end | |
#Implements specified API. | |
def solvable? | |
!(solution.nil?) | |
end | |
#Implements specified API. | |
def steps | |
solution || 0 | |
end | |
#Caches solution to avoid solving twice if using both solvable? and steps. | |
def solution | |
@solution ||= solve! | |
end | |
#Actual logic. Floodfill until you find the exit or floodfill returns nil, | |
#which terminates the algorithm in failure. | |
def solve! | |
i = 1 | |
while (true) | |
if is_solved? | |
return i #Found exit in i steps. | |
else | |
result = floodfill_with_inefficient_magic! | |
if result.nil? | |
return nil #No new steps reached this turn, exit unreachable. | |
else | |
i += 1 | |
end | |
end | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment