···
#
# 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
