A* (#98)

Here’s some test code against which you can test your solutions.

Note that if you follow the quiz statement, and pay no heed to my
correction to the distance formula, you will fail one of the tests.

Adapters can easily be written for solutions that don’t use the same
interface; for example, Roland S.'s solution can be adapted by
adding this small chunk of code:

class Astar
def do_quiz_solution(puzzle)
@m = TileMap::Map.new(puzzle)
results = TileMap.a_star_search(@m)
out = puzzle.split(/\n/)
results.each{|r,c| out[r][c] = ?#}
out.join("\n")
end
end

Anyway, here’s the test code:

require ‘test/unit’
require ‘astar’

class TC_Astar < Test::Unit::TestCase
def setup
@solver = Astar.new
end

def assert_paths_equal(expected,actual,message=nil)
actual = actual.sub(/^(\s*\n)/, ‘’)
expected = expected.sub(/^(\s
\n)/, ‘’)
actual.sub!(/(\s
\n)$/, ‘’)
actual.gsub!(/^\s
/m,’’)
actual.gsub!(/\s*$/m,’’)
expected.sub!(/(\s*\n)$/, ‘’)
expected.gsub!(/^\s
/m,’’)
expected.gsub!(/\s*$/m,’’)
expected.scan(/?/) {|x| expected[$~.begin(0)] =
actual[$~.begin(0)]}
assert_equal(expected,actual,message)
end

def test_simple_horizontal
map = %q(@…X)
solution = @solver.do_quiz_solution(map)
assert_paths_equal(%q(####), solution)
end

def test_simple_vertical
map = %q(@…X).split(//).join("\n")
solution = @solver.do_quiz_solution(map)
assert_paths_equal(%Q(#\n#\n#\n#), solution)
end

def test_quiz_statement
map = %q(@^^^
~~
~.
**…
^…~
~~
~X).sub(/ +/,’’)
solution = @solver.do_quiz_solution(map)
assert_paths_equal(
%q(##^^^
~~#~.
**??.
^…#~
~~*~#), solution, “Didn’t do test solution”)
end

def test_bad_distance
map = %q(@.*…
…~…
…^.X).sub(/ +/,’’)
solution = @solver.do_quiz_solution(map)
assert_paths_equal(
%q(#?#…
.?~#.
…^.#), solution, “Got tripped up by manhattan distance”)
end
end