From: James Edward Gray II <james@...>
Date: 2006-10-19T04:06:02+09:00
Subject: Fwd: A*

--Apple-Mail-1-355046924
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=WINDOWS-1252;
	format=flowed

Begin forwarded message:

> From: "Brendan Bauer-Peters" <ptahwer@gmail.com>
> Date: October 18, 2006 1:58:38 PM CDT
> To: submission@rubyquiz.com
> Subject: A*
>
> This is my first Ruby Quiz. Please be gentle=85
>
> The methods I used are a bit more general than neccesary, mainly
> because I want to be able to use this to search other graphs,
> including ones with asymmetrical costs.
>
> -Brendan Bauer-Peters=

--Apple-Mail-1-355046924
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0666;
	name=astar.rb
Content-Disposition: attachment;
	filename=astar.rb

require "enumerator"

class Map
	
	def initialize(string, options={})
		@string = string
		@costs = options[:costs] || {'.' => 1,'*' => 2,'^' => 3}
		@filler_character = options[:filler_character] || ' '
	end
	
	def cost_for(x,y)
		@costs[self[x,y]]
	end
	
	def s_offset_for(x,y)
		split_s = @string.split(/\n/)
		
		raise 'y-value too high' if y > height
		raise 'x-value too high' if x > width
		
		row = split_self[y]
		
		unless x > row.length
			row[x].chr
		else
			filler_character
		end
	end
	
	def [](x,y)
		split_s = @string.split(/\n/)
		
		raise 'y-value too high' if y > height
		raise 'x-value too high' if x > width
		
		row = split_s[y]
		
		unless x > row.length
			row[x].chr
		else
			filler_character
		end
	end
	
	def []=(x,y,value)
		split_s = @string.split(/\n/)
		
		width = width
		
		raise 'y-value too high' if y > height
		raise 'x-value too high' if x > width
		
		@string = split_s.enum_for(:each_with_index).map do |row, i|
			row = row.ljust(width, filler_character)
			if i == y
				row[x..x] = value
			end
			row
		end.join("\n")
	end
	
	def height
		@string.split(/\n/).length
	end
	
	def width
		@string.split(/\n/).max { |a, b| a.length <=> b.length }.length
	end
	
	def to_s
		@string
	end
	
end

class Route
	
	include Enumerable
	
	attr_reader :start_node, :finish_node
	
	def initialize(start_node, finish_node)
		@start_node = start_node
		@finish_node = finish_node
		
		calculate
	end
	
	def calculate
		searched_nodes = {}
		upcoming_steps = [RouteStep.new(start_node, 0, start_node.heuristic_to(finish_node), nil)]
		found = false
		
		last_step = nil
		
		while !found && upcoming_steps.length > 0
			step = upcoming_steps.shift
			node, cost = step.node, step.cost
			
			if node == finish_node
				found = true
				last_step = step
			else
				existing_cost = searched_nodes[node]
				searched_nodes[node] = cost unless existing_cost && existing_cost >= cost
				
				good_neighbors = node.neighbors.reject do |(n, c)|
					sn = searched_nodes[n]
					sn && sn >= (cost + c)
				end.map{|(n, c)| RouteStep.new(n, cost + c, n.heuristic_to(finish_node), step)}
				
				enum = upcoming_steps.enum_for(:each_with_index)
			
				good_neighbors.each do |n_step|
					e_thing = enum.find { |e_step, i| e_step.total_cost >= n_step.total_cost }
					unless e_thing
						upcoming_steps << n_step
					else
						upcoming_steps.insert(e_thing[1], n_step)
					end
				end
			end
			
		end
		
		@array = found ? last_step.to_a : []
	end
	
	alias_method :recalculate, :calculate
	
	def start_node=(start_node)
		@start_node = start_node
		recalculate
	end
	
	def finish_node=(finish_node)
		@finish_node = finish_node
		recalculate
	end
	
	def each(*args, &blk)
		@array.each(*args, &blk)
	end
	
	def to_a
		@array
	end
	
end

class RouteStep < Struct.new(:node, :cost, :heuristic, :previous_step)
	
	def total_cost
		cost + heuristic
	end
	
	def to_a
		node ? previous_step.to_a << node : []
	end
	
end

class GraphNode
	
	# Pairs of neighbor nodes and costs for travel to each node
	def neighbors
		[]
	end
	
	def heuristic_to(other_node)
		1
	end
	
	def ==(other_node)
		object_id == other_node.object_id
	end
	
end

class MapNode < GraphNode
	
	attr_reader :map, :x, :y
	
	def initialize(map, x, y)
		@map = map
		@x = x
		@y = y
	end
	
	def neighbors
		neighbors = []
		my_class = self.class
		
		# x, y, width, length = x, y, width, length
		
		width = map.width
		height = map.height
		
		if x > 0
			neighbors << my_class.new(map, x-1, y-1) if y > 0
			neighbors << my_class.new(map, x-1, y)
			neighbors << my_class.new(map, x-1, y+1) if y < (height-1)
		end
		
		neighbors << my_class.new(map, x, y-1) if y > 0
		neighbors << my_class.new(map, x, y+1) if y < (height-1)
		
		if x < (width-1)
			neighbors << my_class.new(map, x+1, y-1) if y > 0
			neighbors << my_class.new(map, x+1, y)
			neighbors << my_class.new(map, x+1, y+1) if y < (height-1)
		end
		
		neighbors.map{|node| [node, node.travel_cost]}.reject{|(node,cost)| cost.nil?}
	end
	
	def heuristic_to(other_node)
		(x - other_node.x).abs + (y - other_node.y).abs
	end
	
	def ==(other_node)
		map == other_node.map && x == other_node.x && y == other_node.y
	end
	
	def travel_cost
		map.cost_for(x, y)
	end
	
end

small_map_string = <<ENDMAP
.*^^^
~~*~.
**...
^..*~
~~*~.
ENDMAP

small_map = Map.new(small_map_string)

start_node = MapNode.new(small_map, 0,0)
finish_node = MapNode.new(small_map, 4,4)

small_route = Route.new(start_node, finish_node)

small_string_rows = small_map_string.split(/\n/)
small_route.each do |node|
	small_string_rows[node.y][node.x..node.x] = '#'
end
small_csolved_string = small_string_rows.join("\n") + "\n"

puts small_csolved_string
--Apple-Mail-1-355046924
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed



--Apple-Mail-1-355046924--