From: Louis J Scoras <louis.j.scoras@...>
Date: 2006-10-17T08:28:23+09:00
Subject: Re: [QUIZ] A* (#98)

#!/usr/bin/env ruby
#
# Louis J. Scoras <louis.j.scoras@gmail.com>
# Monday, October 16, 2006
# Solution for Ruby Quiz number 98
#
##############################################################################
# astar.rb - quiz solution to RubyQuiz # 98
#   the interesting bits are in this file and see the map.rb part
#   for the use of Array.cartesian_product

require 'set'
require 'enumerator'
require 'pqueue'     # included below
require 'map'        #    "       "
require 'summary'    #    "       "

# Here we are, a nicely generalized A* method =) We could have easily just
# required that a node has a neigbors method (duck typing), but I wanted to
# make this as general as possible. So astar can have an additional proc
# passed in, which when called on a node returns an enumerator to its
# successors. Note the default value is what we would have had before.
#
def astar(start,finish,succ=nil,&h)
  closed = Set.new
  queue  = PQueue.new(&h) << [start]
  succ ||= lambda {|n| n.neighbors}

  until queue.empty?
    path = queue.dequeue
    node = path.last
    next if closed.include? node
    return path if node == finish
    closed << node
    successors = succ[node]
    successors.each do |location|
      queue << (path.dup << location)
    end
  end
end

# Nested loops for iterating over a multi-dimentional array hurt the head;
# this abstracts it away.  This also leads to a cool little method--well at
# least I think so--for computing neighboring nodes.
#
# cartesian_product([-1,0,1],[-1,0,1])
#    # => [ [-1,-1], [0, -1], [1, -1],
#           [-1, 0], [0,  0], [1,  0],
#           [-1, 1], [0,  1], [1,  1]]
#
def cartesian_product(*sets)
  case sets.size
  when 0
    nil
  when 1
    sets[0].collect {|i| [i]}
  else
    current = sets.pop
    tupples = []
    current.each do |element|
      cartesian_product(*sets).each do |partials|
        partials.each do |n|
          tupples << [n, element]
        end
      end
    end
  tupples
  end
end

map = Map.new(File.read(ARGV[0]))

path = astar(map.start,map.goal) do |path_a, path_b|
  score_a, score_b =
   [path_a, path_b].collect {|path|
       current  = path.last
       traveled = path.inject(0) {|t, node| t + node.cost}
       traveled + current.distance(map.goal)
   }
  score_b <=> score_a  # Ordered for min_heap
end

summary path

##############################################################################
# map.rb - Contains the code for the mapping part of the program

class Node
  attr_reader :x, :y, :cost

  def initialize(x,y,cost,map)
    @x, @y, @cost, @map = x, y, cost, map
  end

  # Look ma! No nested loops.  cartesian_product lets you generate the
  # offsets then we can just hack away at it with maps/filters until we get
  # the right nodes.
  #
  def neighbors
   h, w = @map.height, @map.width
   offsets = [-1,0,1].freeze
   cartesian_product(offsets,offsets).
     reject  {|i|       i == [0,0]                          }.
     collect {|dx, dy|  [x + dx, y + dy]                    }.
     reject  {|j,k|     j < 0 || k < 0 || j >= h || k >= w  }.
     collect {|j,k|     @map[j,k]                           }.
     select  {|n|       n.cost                              }.
     to_enum
  end

  def distance(node)
    [(x-node.x).abs,(y-node.y).abs].max
  end

  def to_s
    "(#{x},#{y}){#{cost}}"
  end
end

class Map
  TERRAIN_COST = {
      '@' => :start, 'X' => :goal,
      '.' => 1, '*' => 2, '^' => 3
  }.freeze

  attr_reader :width, :height

  def initialize(map_string)
    parse_from_string map_string
  end

  def [](x,y)
    @map[x+y*width]
  end

  def start
    self[*@start]
  end

  def goal
    self[*@goal]
  end

  private

  def parse_from_string(s)
    map = s.split(/\s+/).collect{ |l|
      l.scan(/./).collect {|t|
        TERRAIN_COST[t]
      }
    }

    @height = map.size
    @width  = map[0].size
    @points = cartesian_product((0..width-1),(0..height-1))
    @map    = []

    find_ends(map)

    @points.each do |x,y|
      @map << Node.new(x,y,map[y][x],self)
    end
  end

  def find_ends(map)
    @points.each do |x,y|
      case map[y][x]
        when :start
          @start    = [x,y]
          map[y][x] = 0
        when :goal
          @goal     = [x,y]
          map[y][x] = 0
      end
    end
  end
end

##############################################################################
# pqueue.rb - a max/min heap implementation of a priority queue

# By having the constructor take the comparison function, this makes
# using it for A* extremely easy

class PQueue
  def initialize(&sorter)
    @data = []
    @sorter = sorter ||
      lambda do |a,b|
        a <=> b
      end
  end

  def inspect
    @data.sort(&@sorter).reverse.inspect
  end

  def <<(element)
    @data << element
    bubble_up
    self
  end

  def size
    @data.size
  end

  alias_method :enqueue, :<<

  def dequeue
    if size == 1
      @data.pop
    else
      highest, @data[0] = @data[0], @data.pop
      bubble_down
      highest
    end
  end

  def empty?
    size == 0
  end

  private

  def bubble_up
    current_element = size - 1

    until root?(current_element)
      parent = parent_index(current_element)
      if @sorter[@data[parent], @data[current_element]] <= 0
        swap_nodes(parent, current_element)
      end
      current_element = parent_index(current_element)
    end
  end

  def bubble_down
    current_element = 0

    until leaf?(current_element)
      fc, sc = first_child(current_element), second_child(current_element)
      better = choose(fc,sc)

      if @sorter[@data[current_element], @data[better]] > 0
        break
      else
        swap_nodes(current_element, better)
        current_element = better
      end
    end
  end

  def parent_index(index)
    (index - 1) / 2
  end

  def root?(element)
    element == 0
  end

  def swap_nodes(a,b)
    @data[a], @data[b] = @data[b], @data[a]
  end

  def first_child(index)
    bounds_check(index * 2 + 1)
  end

  def second_child(index)
    fc = first_child(index)
    fc ? bounds_check(fc + 1) : nil
  end

  def bounds_check(index)
    index < size ? index : nil
  end

  def leaf?(index)
    ! first_child(index)
  end

  def choose(a,b)
    if b
      @sorter[@data[a], @data[b]] >= 0 ? a : b
    else
      a
    end
  end
end

##############################################################################
# summary.rb - Just prints the results

# This didn't need it's own file, but it's not interesting and I'm
# trying to keep the interesting bits near the top of the email =)

def summary(path)
  cost = 0
  back = [nil, 'across the plains', 'through the woods', 'over the moutain']

  path.each_with_index do |n,i|
    cost += n.cost
    puts case i
      when 0
        "Starting at #{n}"
      when path.size - 1
        "and to Grandmothers house #{n} we go!"
      else
        "#{back[n.cost]} to #{n}"
    end
  end
  puts "Found path. Total cost: #{cost}"
end