James Gray
10/16/2006 1:20:00 PM
Begin forwarded message:
> From: Edward <edward@ethelred.org>
> Date: October 16, 2006 3:23:30 AM CDT
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
> Reply-To: edward@ethelred.org
>
> Hi,
> Here is my submission for Ruby Quiz 98. I'm not sure how well the
> backtracking works in this version, I might think about that some
> more.
>
> cheers
> Edward Harman
>
> class TileType
> attr_reader :cost
> attr_reader :sym
> def initialize(sym, cost)
> @cost = cost
> @sym = sym
> end
> def passable?
> cost > 0
> end
> def newTile(x, y)
> Tile.new(x, y, self)
> end
> end
>
> class StartTileType < TileType
> def newTile(x, y)
> $start = Tile.new(x, y, self)
> end
> end
>
> class GoalTileType < TileType
> def newTile(x, y)
> $goal = Tile.new(x, y, self)
> end
> end
>
> TYPES = {
> '@' => StartTileType.new('@', 1),
> '.' => TileType.new('.', 1),
> 'X' => GoalTileType.new('X', 1),
> '~' => TileType.new('~', 0),
> '*' => TileType.new('*', 2),
> '^' => TileType.new('^', 3)
> }
>
> POINTS = [
> [-1, -1], [-1, 0], [-1, 1],
> [0, -1], [0, 1],
> [1, -1], [1, 0], [1, 1]
> ]
>
> class Tile
> attr_reader :x, :y
> def initialize(x, y, type)
> @x = x
> @y = y
> @type = type
> end
> def distance(goal)
> (@x - goal.x).abs + (@y - goal.y).abs
> end
> def cost(goal)
> distance(goal) + @type.cost
> end
> def passable?
> @type.passable?
> end
> def sym
> @type.sym
> end
> end
>
> class Map
> def initialize(mapstring)
> @map = []
> @height = 0
> mapstring.split.each_with_index do |line, y|
> @width = line.size
> @height += 1
> line.split("").each_with_index do |c, x|
> @map << TYPES[c].newTile(x, y)
> end
> end
> end
> def get(x, y)
> if(x >= 0 && x < @width && y >= 0 && y < @height)
> @map[x + @width * y]
> end
> end
> def adjacent(t)
> result = []
> POINTS.each do |dx, dy|
> test = get(t.x + dx, t.y + dy)
> result << test if test
> end
> result
> end
> def find_route
> @route = [$start]
> @current = $start
> checked = []
> bad = []
> while(@current != $goal)
> #find adjacent tiles
> choices = adjacent(@current).select{|t| t.passable? && !
> (checked.flatten + bad + @route).include?(t)}
> if(choices.size == 0)
> ##need to backtrack
> bad.push @current
> @current = @route.pop
> checked.pop
> else
> #sort by cost
> choices = choices.sort_by{|t| t.cost($goal)}
> checked.push choices
> #take lowest
> @current = choices.shift
> @route.push @current
> end
> end
> @route
> end
> def tile_to_s(t)
> if(@route && @route.include?(t))
> '#'
> else
> t.sym
> end
> end
> def print
> line = ""
> @map.each_with_index do |t, i|
> if(i > 0 && (i % @width ==0))
> puts line
> line = ""
> end
> line << tile_to_s(t)
> end
> puts line
> end
> end
>
> TESTMAP = <<-ENDTEST
> @*^^^
> ~~*~.
> **...
> ^..*~
> ~~*~X
> ENDTEST
>
> map = Map.new TESTMAP
> map.print
> puts ""
> map.find_route
> map.print
>
> LARGEMAP = <<-ENDLARGE
> @^.^~****^*~~.~^~..~~~^~.^~.*~**.^^*^*^~..*^^..~^.
> *.*~*.~^^^~~.*~*.**.~~^*^**.^~*^^.*^...^..^.**.~^*
> ^^***~.*^*^..^**.~~~.~*.~^^~^~^.^~^*~**.~*^.^**.*.
> *~~.~^.~*~^~^^*^**.~.*^^*~~^^*~.^.*^^*^.^.~~^^^*~.
> *.^~^^.~^.^.^^*~^~~*^..^~^~~^.*^^..**.**~.~~^~*~**
> ^.^^~^.*~**.*~*^*~^*~~^.^.~.~^**~.^^^^*.~.~~~^^.^.
> *~~.*.^~~~^*.^*~~~*^.^**^*^.^.^~~***^^*^.~^^.^^.~.
> .~.*~~^*.**.~^^~**^.^.^~~~^.~.^~~^^.~^^.^^~.~.~.*^
> .^^^~~*~.^.~.*~.~~..~*~^.~**~..^****~.*~^~~*~**^~^
> ^^^*^^**...*.^^*^^^.*~*~^^~*~~.~****~~~~***.^^~~^~
> ..*^^^^^.^~.^~.^.^^~*~^*~**^*^.~~~*^.^^~**~*~.....
> **.^~~~^~*~****.**^~.^.*^^^~.^...~.**^^^^~^.~^~.~*
> ^*~.*.~*^.~.^^^^^*~.**~^.*^*.~~..^~~~*~*^.~~^*^*^^
> ~*^.^..**~**^*^~***^~~*^*.*~..~^^***^.*~.^*^^^^.~.
> *~^~^**^^*^^~^*~^^*~~~*^*~~~~*~^^^*~..~~~~~.*~^~*.
> ^.*.^*^**^^^~**.*.~^~~~^..~~~*~~^*~..^^.^~*.^~^~**
> .***^..*^~~~~^~.*^~~.*.~^.^^*.***^~^.*....~.^.*~^^
> ^^~~~~.**.*.^^*.^~~^....*~*^~*^^.^~~~^*.~^^^~**^~~
> ^~~*^*.~.*^^^*^.*..~*...~**^.^^~.^^.^..^.^**.^^..*
> ~^***~^.~.~^^^*~~~.*..^~^^.~^.~.**...~^~**~^~~**^~
> ~~~^~.^*.^*.~*.*~~^..~*^^~~**.*.*.~^^^..^.~^.*.^~~
> ^^~...^.*~.^^**~^~*..^~^~*....^.^^**~.*.^^*..~*~.*
> ^..^...~.~.*.~***~*~~*..~*~^^~~^~**^~~^*^^~*.~*^*^
> *^.**^~*****.~~~..~^~.*.^*~^.^^*^..*~^.^.^*.^.~^^*
> ~...~*^....*^.*^^*...^.~~..^.*~.*~.*^.^*^*^.****^~
> ^..~***^.*^~~.****.~*^.~.^~*.~^*^~^.****~..~*..*^~
> .~^~**~^^..~~~^..*~*.^**~..^^*.~.*..*~~*~.^~.~*~~.
> .***~..~**^.~.~.~*.~~**..^.^~..~*~~~~*.**~~^..^.^^
> ~.*.~^*^*~^.~*..*~^~~.*.*..*.*..^~.*~^^*.~^.^~^**^
> .*^~^^*.^*.~*...*~~~*.**.~...*.*^.^*.^*~*.^~^**^*.
> .~..*....~..~.***~..~^..~~^*^*^~^^~~**^.*~**^**^^*
> ^.*.~.^.**^*^.~^^*.~..*^~*^***.~**..^.~~*..^*^~*.~
> ^~~^~~*.~^^~~^**.^.^^^*^.*^^~~.^.*~^*^^..**..**..^
> ^.^*.*^..*.~~.^^***^.*~..~.**^*.~^...^^~*.~^~^..~~
> ~^^.^..*^^.**.~~^*~*^~*~^~~.~*.^~.~*^~*.*..^.^^*^*
> ^^.~*^~~*.~~*~.^..~*.^.~**.^*^.^~.**.~*.~...~~..*.
> .~..^.~.~.^*.~^*~.~.*^*~~*.^.******~*~~*^~~~^.~~*~
> ~.*..^^*^~*.~~.~.^~..~.~^^^.*~*.**~^*~*^*^^~..^~^^
> *.^*^**^*.^^*....**..~^^~.^*^.*~*^**^^..*.^^*^^^.~
> ^*^~^^*.~*~^*~^~~.*.^*^~*^^~.*~.*~.**.*~^~~.~*^~~*
> ~~**~*.^.*~..~~^^^~^^^.~***^*.^*~^*~^~*~**...~..~.
> *~**^~~.^.*.~^**~*^^.*^*.^~~*~~~*^.*..~~^*^.*^.^.*
> .*^~..*~.*^^^^^~~^^*.~*.~~~.***~^.*..~~******~~^*.
> .^^..^.^*^~^.~*...**~~~.**^*~~~*^***~^*^~^~~^^^*.*
> **.**~.**~.*.*^~~.~^.*^.~~*.^*.~.***~*^^..~*.~*^*^
> ~..^.****^.****~^~***..^^^^*^.~*^^*.~~.^**^*~^*.~~
> ^*~^.~*...^^.^~.^^..~^...**...^****^*~*~*^..~^*~.~
> ...^~^.~^^~~~~.*^~.^~***~~^^^.*^^.~.^*~*~**^***^~^
> .~~~~~^^.~~*^.~^^^**~^~.^~^~*..^*~^^*..*~^~**.*.^.
> ~^**.~**..*^~^^^.^*^~^~*^.~*~.^.**.^.^^.~**^~~^~^X
> ENDLARGE
>
> map = Map.new LARGEMAP
> map.print
> puts ""
> map.find_route
> map.print
>
>