Instantly share code, notes, and snippets.

# RLGGHC/dmytroshteflyuk.rbSecret forked from kpumuk/dmytroshteflyuk.rb Created Dec 28, 2009

 # 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