secret
Last active — forked from kpumuk/dmytroshteflyuk.rb

  • Download Gist
dmytroshteflyuk.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
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.