# A\* (#98)

**URL:** <https://www.ruby-forum.com/t/a-98/229095>\
**Category:** Ruby\
**Created:** [October 15, 2006, 9:37pm UTC](https://www.ruby-forum.com/t/a-98/229095 "2006-10-15T21:37:06Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [October 15, 2006, 9:37pm UTC](https://www.ruby-forum.com/t/a-98/229095/1 "2006-10-15T21:37:06Z")

</div>

And here’s my solution - nothing particularl unusua;, beyond the  
definition of distance I’d mentioned already. I used a simple  
priority queue of my own design, though this could easily be adapted  
to use some off-the-shelf version.

require ‘enumerator’

# I suppose someone would think I should use a heap here.

# I’ve found that the built-in sort method is much faster

# than any heap implementation in ruby. As a plus, the logic

# is easier to follow.

class PriorityQueue  
def initialize  
@list = []  
end  
def add(priority, item)  
# Add @list.length so that sort is always using Fixnum comparisons,  
# which should be fast, rather than whatever is comparison on `item’  
@list \<\< [priority, @list.length, item]  
@list.sort!  
self  
end  
def \<\<(pritem)  
add(\*pritem)  
end  
def next  
@list.shift[2]  
end  
def empty?  
@list.empty?  
end  
end

class Astar  
def do\_quiz\_solution(puzzle)  
@terrain = []  
instr = “”  
puzzle.each {|rowstr|  
next if rowstr =~ /^\s\*$/  
rowstr.gsub!(/[^.@~X\*^]/,’’)  
instr += rowstr  
instr += “\n”  
row = []  
rowstr.scan(/[.@~X\*^]/) {|terrain|  
case terrain  
when /[.@X]/; row \<\< 1  
when /[\*]/; row \<\< 2  
when /^/; row \<\< 3  
when /~/; row \<\< nil  
end  
}  
xind = rowstr.index(‘X’)  
aind = rowstr.index(’@’)  
if (aind)  
@start = [@terrain.length, aind]  
end  
if (xind)  
@goal = [@terrain.length, xind]  
end  
@terrain \<\< row  
}  
if do\_find\_path  
outarr = instr.split(/\n/)  
@path.each{|row,col| outarr[row][col]=’#’}  
return outarr.join("\n")  
else  
return nil  
end  
end

def do\_find\_path  
been\_there = {}  
pqueue = PriorityQueue.new  
pqueue \<\< [1,[@start,[],1]]  
while !pqueue.empty?  
spot,path\_so\_far,cost\_so\_far = pqueue.next  
next if been\_there[spot]  
newpath = [path\_so\_far, spot]  
if (spot == @goal)  
@path = []  
newpath.flatten.each\_slice(2) {|i,j| @path \<\< [i,j]}  
return @path  
end  
been\_there[spot] = 1  
spotsfrom(spot).each {|newspot|  
next if been\_there[newspot]  
tcost = @terrain[newspot[0]][newspot[1]]  
newcost = cost\_so\_far + tcost  
pqueue \<\< [newcost + estimate(newspot),  
[newspot,newpath,newcost]]  
}  
end  
return nil  
end

def estimate(spot)  
# quiz statement version  
# (spot[0] - @goal[0]).abs + (spot[1] - @goal[1]).abs  
# my version  
[(spot[0] - @goal[0]).abs, (spot[1] - @goal[1]).abs].max  
end

def spotsfrom(spot)  
retval = []  
vertadds = [0,1]  
horizadds = [0,1]  
if (spot[0] \> 0) then vertadds \<\< -1; end  
if (spot[1] \> 0) then horizadds \<\< -1; end  
vertadds.each{|v| horizadds.each{|h|  
if (v != 0 or h != 0) then  
ns = [spot[0]+v,spot[1]+h]  
if (@terrain[ns[0]] and @terrain[ns[0]][ns[1]]) then  
retval \<\< ns  
end  
end  
}}  
retval  
end  
end

if **FILE** == $0  
puts Astar.new.do\_quiz\_solution(ARGF)  
end