-
-
Save kpumuk/fc0d1e2b23287ec1f682 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
# Solves mazes using classic painting algorithm. | |
# | |
# @example | |
# Maze.new(MAZE1).solvable? | |
# Maze.new(MAZE1).steps | |
# | |
class Maze | |
# Parses maze provided as a string showing a graphical | |
# representation of the maze’s layout. | |
# | |
# Internal representation of the maze is an Array of Integers, | |
# where -1 is a wall, 0 is a space, 1 is a starting point. | |
# | |
def initialize(maze) | |
maze = maze.split("\n") | |
@height = maze.size | |
@width = @height > 0 ? maze[0].size : 0 | |
@maze = Array.new(@height) { Array.new(@width) } | |
for i in 0...maze.size | |
for j in 0...maze[i].size | |
@maze[i][j] = parse_cell(maze, i, j) | |
end | |
end | |
end | |
# Returns true/false depending on whether it's possible to | |
# navigate the maze from point A to point B. | |
# | |
def solvable? | |
trace_steps > 0 | |
end | |
# Returns an integer of the least number of "steps" one would | |
# have to take within the maze to get from point A to point B. | |
# "Steps" can only be taken up, down, left or right. No diagonals. | |
# | |
def steps | |
trace_steps | |
end | |
private | |
# Returns an Integer value corresponding to the symbol | |
# from an original maze string. | |
# | |
def parse_cell(maze, row, col) | |
case maze[row][col] | |
when ?#: -1 | |
when ?A: 1 | |
when ?B | |
@exit_x = col | |
@exit_y = row | |
0 | |
when 32: 0 | |
else | |
raise ArgumentError, "Maze is invalid!" | |
end | |
end | |
# Painting algorithm implementation. | |
# | |
def trace_steps | |
return @steps if defined?(@steps) | |
more_steps = true | |
current_step = 1 | |
while more_steps | |
more_steps = fill_next_step(current_step) | |
break if @maze[@exit_y][@exit_x] > 0 | |
current_step += 1 | |
end | |
@steps = @maze[@exit_y][@exit_x] > 0 ? @maze[@exit_y][@exit_x] - 1 : 0 | |
end | |
# Fills free cells around ones with the value current_step | |
# with the value (current_step + 1). | |
# | |
def fill_next_step(current_step) | |
more_steps = false | |
for i in 0...@height | |
for j in 0...@width | |
next unless @maze[i][j] == current_step | |
if i > 0 && @maze[i - 1][j] == 0 | |
@maze[i - 1][j] = current_step + 1 | |
more_steps = true | |
end | |
if i < @height - 1 && @maze[i + 1][j] == 0 | |
@maze[i + 1][j] = current_step + 1 | |
more_steps = true | |
end | |
if j > 0 && @maze[i][j - 1] == 0 | |
@maze[i][j - 1] = current_step + 1 | |
more_steps = true | |
end | |
if j < @width - 1 && @maze[i][j + 1] == 0 | |
@maze[i][j + 1] = current_step + 1 | |
more_steps = true | |
end | |
end | |
end | |
more_steps | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment