Please Forward: Ruby Quiz Submission

ruby-talk
1

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

···

Begin forwarded message:

2

James Edward Gray II <james@grayproductions.net> writes:

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

When I try this solution on the map I've been trying all the solutions
on, this happens:

@.*..
..~..
..^.X

#.*..
..~..
..###

That is, not only does it try to go over the mountain, it manages to
jump a square, jumping straight from the start at (0,0) to the
mountain at (2,2).

The culprit for going over the mountain instead of going through the
forest is almost certainly the manhattan distance, as it is in other
solutions. I have no idea why it jumps a square.

···

Begin forwarded message:

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]