THE LABYRINTH CodeEval 157 https://www.codeeval.com/open_challenges/157/

gistfile1.rb

class Maze
  require 'singleton'
  include Singleton

  def process_maze_matrix(maze_matrix)
    @maze_matrix = maze_matrix
    set_max_coordinates_for_maze!
    set_entrances_to_maze!
  end

  def solve_maze
    shorted_steps_path.each { |step| @maze_matrix[step.y][step.x] = '+' }
    @maze_matrix.map(&:join)
  end

  def is_it_possible_to_move_to?(y, x)
    @maze_matrix[y][x] != '*' && !is_present_step_at?(y, x)
  end

  def are_these_coordinates_valid?(y, x)
    x > 0 && x <= @max_x && y > 0 && y <= @max_y
  end

  def assign_step_at(step, coordinates)
    @steps[coordinates[:y]][coordinates[:x]] = step
  end

  def are_these_coordinates_for_exit?(y, x)
    [y, x] == @exit_coordinates
  end

  private

  def shorted_steps_path
    @next_steps = entry_step.next_steps
    loop do
      @next_steps = @next_steps.flat_map(&:next_steps)
      exit_step = @next_steps.detect(&:is_it_exit?)
      return exit_step.steps_path if exit_step
    end
  end

  def is_present_step_at?(y, x)
    @steps[y] && @steps[y][x]
  end

  def set_entrances_to_maze!
    @entry_coordinates = entrances_coordinates.first
    @exit_coordinates = entrances_coordinates.last
  end

  def set_max_coordinates_for_maze!
    @max_x = @maze_matrix.first.size - 1
    @max_y = @maze_matrix.size - 1
  end

  def entrances_coordinates
    @entrances_coordinates ||= begin
      @maze_matrix[0].each_with_index.map { |char, index| [0, index] if char == ' ' }.compact +
          @maze_matrix[@max_y].each_with_index.map { |char, index| [@max_y, index] if char == ' ' }.compact
    end
  end

  def entry_step
    @steps = Hash.new { |hsh, k| hsh[k] = {} }
    Step.new(*@entry_coordinates)
  end
end

class Step
  attr_reader :x, :y

  def initialize(y, x, parent = nil)
    @x = x
    @y = y
    @parent = parent
  end

  def next_steps
    valid_next_coordinates.map do |(y, x)|
      Step.new(y, x, self).tap do |step|
        Maze.instance.assign_step_at(step, {y: y, x: x})
      end
    end
  end

  def is_it_exit?
    Maze.instance.are_these_coordinates_for_exit?(@y, @x)
  end

  def steps_path
    @parent ? @parent.steps_path << self : [self]
  end

  private

  def valid_next_coordinates
    all_sibling_coordinates.select do |(y, x)|
      Maze.instance.are_these_coordinates_valid?(y, x) &&
          Maze.instance.is_it_possible_to_move_to?(y, x) &&
            !is_parent_in_coordinates?(y, x)
    end
  end

  def is_parent_in_coordinates?(y, x)
    @parent && @parent.x == x && @parent.y == y
  end

  def all_sibling_coordinates
    [[@y - 1, @x], [@y + 1, @x], [@y, @x - 1], [@y, @x + 1]]
  end
end

maze_matrix = File.read(ARGV[0]).split("\n").map { |line| line.split('') }
Maze.instance.process_maze_matrix(maze_matrix)
puts Maze.instance.solve_maze