From: Harry Kakueki <list.push@...>
Date: 2008-09-30T15:53:54+09:00
Subject: Re: [QUIZ] Cookie Monster (#178)

>
> 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. An example forest is provided below:
>

Here is my solution.
It only works for square forests.
It finds and stores every possible path then outputs the best one.
So, it is not very fast ( about 30 sec. ).
But it is short and (hopefully) easy to read.


str = <<DATA
1  3  0  5 -1  7 -1 -1  0  4  2  1
-1  3  2  1 -1  4 -1  5  3 -1  1  0
 5  4  8 -1  3  2  2 -1  4 -1  0  0
 2  1  0  4  1 -1  8  0  2 -1  2  5
 1  4  0  1 -1  0  3  2  2  4  1  4
 0  1  4  1  1  6  1  4  5  2  1  0
 3  2  5  2  0  7 -1  2  1  0 -1  3
 0 -1  4 -1 -1  3  5  1  4  2  1  2
 5  4  8 -1  3  2  2 -1  4 -1  0  0
 2  1  0  4  1 -1  8  0  2 -1  2  5
1  3  0  5 -1  7 -1 -1  0  4  2  1
 0  0  3  1  5  2  1  5  4  1  3  3
DATA

forest, choices, paths = [],[],[]
str.each {|x| forest << x.strip.split(/\s+/).map{|x| x.to_i}}
top = forest[0].length - 1
nums = (0..top).map {Array.new}
(0...2**top).each do |x|
nums[x.to_s(2).split(//).map{|f| f.to_i}.inject{|a,b| a+b}] <<
x.to_s(2).rjust(top,"0")
end

(0..top).each{|x| nums[x].each{|y| nums[top-x].each{|z| choices << (y+z)}}}

choices.each do |a|
trypath = []
south,east = 0,0
trypath << forest[south][east]
  a.split(//).each do |c|
  south += 1 if c == "0"
  east += 1 if c == "1"
  trypath << forest[south][east]
  break if forest[south][east] == -1
  end
paths << trypath unless trypath.include?(-1)
end

p paths.max{|x,y| x.inject{|a,b| a+b} <=> y.inject{|a,b| a+b} }


Harry

-- 
A Look into Japanese Ruby List in English
http://www.kakueki.com/ruby/list.html