On 9/26/08, Matthew Moss <matthew.moss / gmail.com> wrote:
> ## Cookie Monster (#178)
>
> _Quiz description provided by Lee Jarvis._
>
> Cookie Monster is trying to walk through the Cookie Forest and consume
> as many cookies as possible. However, there are many different paths
> that Cookie Monster can take, and he isn't sure which way is the best
> way. Help him eat as many cookies as possible by writing a program
> which finds the optimal path from the upper left part of the forest to
> the bottom right. Cookie Monster can only move south and east. There
> are also several thorn patches through which he cannot cross. The
> forest can be represented as a grid of numbers, where the number
> represents the amount of cookies in that acre and -1 represents an
> impassible thorn patch.

I worked up 2 solutions.  For the code, forest maps, and sample output:

http://github.com/fjc/rubyquiz/tree/master/178

First, solution number 2:

Since Cookie Monster can only make one of 2 moves at any given time, I
thought I would use (binary) integers to store his possible paths.
So, for example, for a 2x2 forest his only possible paths are
South->East or East->South: encode one as "10" and the other as "01".
Then, for a 3x3 forest, his moves would range from
South->South->East->East to East->East->South->South: "0011" to
"1100":

min_path = ("1" * (ysize - 1)).to_i(2)
max_path = (("1" * (ysize - 1)) << ("0" * (xsize - 1))).to_i(2)

Then a brute-force loop through all the possible paths:

min_path.upto(max_path) do |path|
  x, y, eats = 0, 0, map[0][0]

  begin
    path_len.times do |i|
      path[i] == 0 ? x += 1 : y += 1
      raise if map[x][y] < 0
      eats += map[x][y]
    end
  rescue
  end

  if eats > best_eats
    best_eats = eats
    best_path = path
  end
end


The first solution I worked on was to use a Ruby Astar implementation
by Marcin Coles (I found this library on rubyforge while I was playing
with the rubyist's wig-wug homework assignment).  I had to modify the
stock behavior of the library to fit within the constraints of the
Cookie Monster problem:

  * On-disk format of the map was different
  * Use -1 instead of 0 to indicate a wall/thorn
  * Higher-number locations are preferred

I originally abandoned this because I couldn't understand why it
wasn't eating an optimal number of cookies.  After I wrote the above
version, I compared the two and saw they both produced the same path,
but different counts!  So, I swapped x and y into the correct
positions on lines 73 and 81.  Code excerpt:

require "astar/AMap.rb"

class CookieMonsterAMap < AStar::AMap
  # override to munge the costmap array for the constraints of the
cookie monster problem
  def initialize(costmap)
    #...
  end

  # override load to return this class instead of the parent AMap class
  def self.load(filename)
    #...
  end

  # override to only generate South and East successors
  def generate_successor_nodes(anode)
    #...
  end
end

###################################################
# based on AStar tester by Marcin Coles 27/Sep/2007

amap = CookieMonsterAMap.load(ARGV[0] || "map.txt")
cmap = amap.costmap

start, finish = amap.co_ord(0, 0), amap.co_ord(cmap[0].size - 1, cmap.size - 1)

goal = amap.astar(start, finish)
raise "Lost in forest @_@" unless goal

puts "The path:"
current, cookies = goal, 0
while current.parent do
  x, y = current.x, current.y
  cookies += amap.original_costmap[y][x]

  print "[#{x}, #{y}] <- "
  current = current.parent
end
x, y = current.x, current.y
puts "[#{x}, #{y}]"

cookies += amap.original_costmap[y][x]


Output comparison:

178.rb, map 01, Eaten: 1, 0.040u 0.010s 0:00.01
178.rb, map 02, Eaten: 7, 0.050u 0.010s 0:00.09
178.rb, map 03, Eaten: 19, 0.030u 0.010s 0:00.00
178.rb, map 04, Eaten: 23, 0.060u 0.000s 0:00.02
178.rb, map 05, Eaten: 25, 0.080u 0.030s 0:00.14
178.rb, map 06, Eaten: 32, 0.240u 0.020s 0:00.22
178.rb, map 07, Eaten: 40, 0.870u 0.110s 0:01.05
178.rb, map 08, Eaten: 48, 3.630u 0.240s 0:03.95
178.rb, map 09, Eaten: 56, 14.390u 1.090s 0:16.06
178.rb, map 10, Eaten: 60, 57.620u 3.880s 1:01.81
178.rb, map 12, Eaten: 65, 232.480u 14.420s 4:09.59
178.rb, map 12, Eaten: 74, 949.270u 62.310s 17:06.38

178_aster.rb, map01, 1 cookie, 0.040u 0.010s 0:00.03
178_aster.rb, map02, 7 cookies, 0.050u 0.000s 0:00.05
178_aster.rb, map03, 19 cookies, 0.070u 0.000s 0:00.01
178_aster.rb, map04, 23 cookies, 0.060u 0.010s 0:00.04
178_aster.rb, map05, 25 cookies, 0.060u 0.020s 0:00.06
178_aster.rb, map06, 32 cookies, 0.080u 0.010s 0:00.04
178_aster.rb, map07, 40 cookies, 0.080u 0.040s 0:00.09
178_aster.rb, map08, 48 cookies, 0.110u 0.020s 0:00.12
178_aster.rb, map09, 56 cookies, 0.130u 0.030s 0:00.12
178_aster.rb, map10, 60 cookies, 0.170u 0.040s 0:00.20
178_aster.rb, map11, 65 cookies, 0.210u 0.060s 0:00.26
178_aster.rb, map12, 74 cookies, 0.330u 0.050s 0:00.36

(Times are a single run on an OLPC XO.)