```#!/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

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

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

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

```