dmitriynagirnyak.rb

# Solution for the Ruby Challenge: http://rubylearning.com/blog/2009/12/27/rpcfn-mazes-5/
# By Dmitriy Nagirnyak

  # The class is responsible for solving arbitrary maze by searching for the smallest number of steps required to move from point A to B
  class Maze
    START_MARK = 'A'
    END_MARK = 'B'
    SPACE_MARKS = [' ', END_MARK, START_MARK]

    # Initializes the solver accepting the maze as a string.
    # The string can contain a number of rows separated by '\n' character. The length of the rows can be different.
    # Start and end positions are marked with A and B respectively.
    # Movable area is the one that contains space, A  or B marks.
    def initialize(maze)
      # Build the 2D area, like this: [%w{# # #}, %w{# A #}, %w{# B #}]
      @area = maze.split(/\r?\n/).map {|r| r.split('') }
      #Find start & the end - 2 arrays with coordinates: [row,column]
      @area.each_with_index do |r, ri|
        r.each_with_index do |c, ci|
          @start = [ri,ci] if c == START_MARK
          @end = [ri,ci] if c == END_MARK
          break if @start && @end
        end
        break if @start && @end
      end
      throw ArgumentError.new('No start and/or end positions provided on the maze') if !@start || !@end
    end

    # Returns minimal number of steps required to move from position marked as A to position B on the maze.
    def steps
      res = calc_steps @start, []
      # Always includes step for A, thus minimal value if solution exists is 2  
      res > 0 ? res-1 : 0
    end

    # Returns true if there is a path from A to B. Otherwise false.
    def solvable?
      steps > 0
    end

    private

    # The main worker - recursively finds the smallest number of steps
    def calc_steps(cur, traces)
      # Recursion bases
      return 0 if !can_move_to? cur # hit the wall
      return 0 if traces.include? cur #been here
      return 1 if cur == @end #found the guy
      
      # Keep the local copy of the traces, also adding current position to it
      cur_traces = traces.map {|e| e}.push cur    
      
      # Recursion step
      left  = calc_steps from_left(cur),  cur_traces
      right = calc_steps from_right(cur), cur_traces
      up    = calc_steps from_up(cur),    cur_traces
      dn    = calc_steps from_dn(cur),    cur_traces
      
      # Reject zero steps and get the minimal value if available
      sub_steps = [left, right, up, dn].reject! {|step| step == 0 }.min    
      # return the total number of steps keeping in mind:  no sub_steps  means no way to the guy, thus zero
      sub_steps ? sub_steps + 1 : 0
    end

    # Returns the new coordinates with the given offset
    def move(pos, down, right)
      [pos[0] + down, pos[1] + right]
    end  

    # Sugar - position on the left from current
    def from_left(cur)
      move(cur, 0, -1)
    end
    
    # Sugar - position on the right from current
    def from_right(cur)
      move(cur, 0, 1)
    end
    
    # Sugar - position on the front from current
    def from_up(cur)
      move(cur, -1, 0)
    end
    
    # Sugar - position on the back from current
    def from_dn(cur)
      move(cur, 1, 0)
    end

    # Checks if the given position is movable (so that a guy can step onto it)
    def can_move_to?(pos)
      # Check for the out-of-bounds
      row, col = pos[0], pos[1]
      return false if !(0...@area.length).include?(row) || !(0...@area[row].length).include?(col)
      SPACE_MARKS.include? from_area(pos)
    end

    # Returns the mark located at the given position of the area.
    # It doesn't check out-of-bounds conditions. Use can_move_to? for that.
    def from_area(pos)
      @area[pos[0]][pos[1]]
    end
  end