maze.rb

# http://rubylearning.com/blog/2009/12/27/rpcfn-mazes-5/
#
# Not efficient, but fairly readable.
# Author: ralph@newrelic.com

class Maze
  class Node
    attr_reader :x, :y, :distance
    attr_accessor :neighbors
    def initialize(x, y)
      @x = x
      @y = y
      @neighbors = []
      @distance = nil
    end

    def ==(other)
      x == other.x and y == other.y
    end

    def accessible_from?(other)
      accessible = search(other)
      unvisit!
      accessible
    end

    def steps_from(other)
      accessible = search(other)
      steps = accessible ? other.distance : 0
      unvisit!
      steps
    end

    def find_neighbors(nodes)
      return unless nodes
      @neighbors << nodes.find { |m| north == m }
      @neighbors << nodes.find { |m| south == m }
      @neighbors << nodes.find { |m| east == m }
      @neighbors << nodes.find { |m| west == m }
      @neighbors.compact!
      @neighbors
    end

    protected
    def search(other, distance=0)
      return false unless visit!(distance)
      self == other or neighbors.select { |n| n.search(other, distance+1) }.length > 0
    end

    def visit!(distance=0)
      if not visited? or @distance > distance
        @distance = distance
      end
    end
    
    def unvisit!
      @distance = nil
      neighbors.each { |n| n.visited? and n.unvisit! }
    end

    def visited?
      @distance != nil
    end

    def north; @north ||= Node.new(x, y-1); end
    def south; @south ||= Node.new(x, y+1); end
    def east; @east ||= Node.new(x+1, y); end
    def west; @west ||= Node.new(x-1, y); end

  end  # Node

  attr_accessor :nodes, :a, :b

  def initialize(maze='')
    @nodes = []
    add_nodes(maze)
    find_neighbors
  end

  def solvable?
    @a.accessible_from?(@b)
  end

  def steps
    @a.steps_from(@b)
  end

  def add_nodes(maze)
    x = y = 0
    maze.each_char do |c|
      if c == ' '
        node = Node.new(x,y)
        nodes << node
      elsif c == 'A'
        @a = Node.new(x,y)
        nodes << @a
      elsif c == 'B'
        @b = Node.new(x,y)
        nodes << @b
      end

      if c =~ /\n/
        x = 0
        y += 1
      else
        x += 1
      end
    end
  end

  def find_neighbors
    nodes.each do |n|
      n.find_neighbors(nodes)
    end if nodes
  end

end

maze_contest.rb

require 'test/unit'
require 'maze'

MAZE1 = %{#####################################
# #   #     #A        #     #       #
# # # # # # ####### # ### # ####### #
# # #   # #         #     # #       #
# ##### # ################# # #######
#     # #       #   #     # #   #   #
##### ##### ### ### # ### # # # # # #
#   #     #   # #   #  B# # # #   # #
# # ##### ##### # # ### # # ####### #
# #     # #   # # #   # # # #       #
# ### ### # # # # ##### # # # ##### #
#   #       #   #       #     #     #
#####################################}
# Maze 1 should SUCCEED

MAZE2 = %{#####################################
# #       #             #     #     #
# ### ### # ########### ### # ##### #
# #   # #   #   #   #   #   #       #
# # ###A##### # # # # ### ###########
#   #   #     #   # # #   #         #
####### # ### ####### # ### ####### #
#       # #   #       # #       #   #
# ####### # # # ####### # ##### # # #
#       # # # #   #       #   # # # #
# ##### # # ##### ######### # ### # #
#     #   #                 #     #B#
#####################################}
# Maze 2 should SUCCEED

MAZE3 = %{#####################################
# #   #           #                 #
# ### # ####### # # # ############# #
#   #   #     # #   # #     #     # #
### ##### ### ####### # ##### ### # #
# #       # #  A  #   #       #   # #
# ######### ##### # ####### ### ### #
#               ###       # # # #   #
# ### ### ####### ####### # # # # ###
# # # #   #     #B#   #   # # #   # #
# # # ##### ### # # # # ### # ##### #
#   #         #     #   #           #
#####################################}
# Maze 3 should FAIL

class MazeTest < Test::Unit::TestCase
  def test_good_mazes
    assert_equal true, Maze.new(MAZE1).solvable?
    assert_equal true, Maze.new(MAZE2).solvable?
  end

  def test_bad_mazes
    assert_equal false, Maze.new(MAZE3).solvable?
  end

  def test_maze_steps
    assert_equal 44, Maze.new(MAZE1).steps
    assert_equal 75, Maze.new(MAZE2).steps
    assert_equal 0, Maze.new(MAZE3).steps
  end
end

maze_test.rb

require 'set'
require 'test/unit'
require 'maze'

class MazeTest < Test::Unit::TestCase
  def setup
    # abc-
    # de--
    # f--g
    @a = Maze::Node.new(0,0)
    @b = Maze::Node.new(1,0)
    @c = Maze::Node.new(2,0)
    @d = Maze::Node.new(0,1)
    @e = Maze::Node.new(1,1)
    @f = Maze::Node.new(0,2)
    @g = Maze::Node.new(3,2)
    @nodes = [@a,@b,@c,@d,@e,@f,@g]
    @maze = Maze.new
    @maze.nodes = @nodes
  end

  module NodeTest
    def set_neighbors
      @a.neighbors = [@b, @d]
      @b.neighbors = [@a, @c, @e]
      @c.neighbors = [@b]
      @d.neighbors = [@a, @e, @f]
      @e.neighbors = [@b, @d]
      @f.neighbors = [@d]
      @g.neighbors = []
    end

    def test_equality
      assert @a != @b
      assert @a == @a
      assert @a == Maze::Node.new(@a.x, @a.y)
    end
    
    def test_accessible_from?
      set_neighbors
      
      assert @a.accessible_from?(@a)
      
      assert @a.accessible_from?(@b)
      assert @a.accessible_from?(@d)
      assert @a.accessible_from?(@e)
      assert @a.accessible_from?(@f)
      assert !@a.accessible_from?(@g)
    end
    
    def test_node_find_neighbors
      assert @a.find_neighbors(@nodes).to_set == [@b, @d].to_set
    end
    
    def test_steps_from
      set_neighbors
      
      # 0 also means "not found", unfortunately
      assert_equal 0, @a.steps_from(@a)
      
      assert_equal 1, @a.steps_from(@b)
      assert_equal 0, @a.steps_from(@g)
    end
  end
  
  include NodeTest
  
  def test_find_neighbors
    @maze.find_neighbors
    
    assert @a.neighbors.to_set == [@b, @d].to_set
    assert @b.neighbors.to_set == [@a, @c, @e].to_set
    assert @c.neighbors.to_set == [@b].to_set
    assert @d.neighbors.to_set == [@a, @e, @f].to_set
    assert @e.neighbors.to_set == [@b, @d].to_set
    assert @f.neighbors.to_set == [@d].to_set
    assert @g.neighbors.to_set == [].to_set
  end

  def test_init_from_string
    maze_str = %{   #
  ##
 ## }
    maze = Maze.new(maze_str)

    assert_equal @maze.nodes.length, maze.nodes.length
    @maze.nodes.each {|x| assert maze.nodes.find(x) }
  end

  def test_solvable?
    @maze.find_neighbors

    @maze.a = @a
    @maze.b = @b
    assert @maze.solvable?

    @maze.b = @g
    assert !@maze.solvable?
  end

  def test_steps
    @maze.find_neighbors

    @maze.a = @a
    @maze.b = @b
    assert_equal 1, @maze.steps

    @maze.b = @e
    assert_equal 2, @maze.steps

    @maze.b = @g
    assert_equal 0, @maze.steps
  end
end