```Hi,

Here is my solution - I haven't done much more than implement what was
asked for in the quiz. It produces this path on the large map:

0,0  1,1  2,2  3,3  4,4  5,5  6,6  7,7  8,8  9,9  10,9  11,10  12,11
12,12  13,13  14,14  15,15  15,16  15,17  16,18  17,18  18,19  19,20
20,21  21,22  22,22  23,23  22,24  22,25  23,26  24,27  25,28  26,29
27,29  28,29  29,30  30,31  30,32  31,33  30,34  30,35  31,36  32,37
33,38  34,39  34,40  35,41  36,42  37,43  38,43  39,44  40,44  41,45
42,46  43,46  44,47  45,48  46,48  47,48  48,49  49,49

I've used Brian Schröäer's PriorityQueue implementation, so to run
this you'll need to do gem install priorityqueue first.

In response to Martin about the quiz being "spoiled" - I don't come
from a Computer Science background and finding out about algorithms /
data structures which might be obvious to someone with a more technical
bent is one of the things I like getting out of ruby quiz. I think
there is room for a mix of quizes, some with more vague goals than
others.

Cheers,
Roland Swingler

My solution:

require 'rubygems'
require 'priority_queue'

class String
# Convenience method so we can iterate over characters easily

def to_chars
a = []
each_byte do |b|
a << b.chr
end
a
end
end

module TileMap
# Although start is a plains, its cost is 0

START  = 0
PLAINS = 1
FOREST = 2
MOUNTAIN = 3
WATER = nil

class TilePath < Array
def initialize(map)
@map = map
super([@map.start])
end

def cost
inject(0) {|sum, c| sum + @map.tile(*c) }
end
end

class Map
attr_reader :start, :goal

# parse a string contining a tile map into a nested array

def initialize(map_str)
@tiles = []
map_str.each do |line|
@tiles << []
line.chomp.to_chars.each do |c|
@tiles.last << case c
when "@"
START
when ".", "X"
PLAINS
when "*"
FOREST
when "^"
MOUNTAIN
when "~"
WATER
else
raise "Invalid tile type"
end
if '@' == c
@start = [@tiles.last.length - 1, @tiles.length - 1]
elsif 'X' == c
@goal = [@tiles.last.length - 1, @tiles.length - 1]
end
end
end
unless @start && @goal
raise "Either position or goal tile are not set"
end
end

def tile(x, y)
@tiles[y][x]
end

def move_choices(x, y)
if tile(x, y) == WATER
raise "Illegal tile"
end
choices = []
(-1..1).each do |i|
ypos = y + i
if ypos >= 0 && ypos < @tiles.length
(-1..1).each do |j|
xpos = x + j
if xpos >= 0 && xpos < @tiles[i].length
new_position = [xpos, ypos]
if new_position != [x, y] && tile(*new_position) != WATER
choices << new_position
end
end
end
end
end
choices
end

def self.manhattan(point1, point2)
((point2[0] - point1[0]) + (point2[1] - point1[1])).abs
end
end

def self.a_star_search(map)
# To store points we have already visited, so we don't repeat
ourselves
closed = []
open = PriorityQueue.new
# Start off the queue with one path, which will contain the start
position
open.push TilePath.new(map), 0
while ! open.empty?
# Get the path with the best cost to expand

current_path = open.delete_min_return_key
pos = current_path.last
unless closed.include?(pos)
if pos == map.goal
return current_path
end
closed << pos
# Create new paths and add them to the priority queue

map.move_choices(*pos).each do |p|
heuristic = Map.manhattan(p, map.goal)
new_path = current_path.clone << p
open.push(new_path, new_path.cost + heuristic)
end
end
end
raise "Cannot be solved"
end
end

@m = TileMap::Map.new(File.read('large_map.txt'))
results = TileMap.a_star_search(@m)
puts results.map! {|pos| pos.join(",") }.join("  ")

```