```On Fri, Sep 26, 2008 at 4:53 PM, Matthew Moss <matthew.moss / gmail.com> wrote:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

> 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:

Hi,

Thanks for the fun quizzes. This is my solution:

It starts from the last square moving backwards (same row, east to west,
then previous row, etc), calculating the better path, noting in each "node"
which is the optimal direction and the sum of cookies for that path.
At the end, the number of cookies is the value of the first node, and
the program
follows the directions in each node to report the path. I represent
the forest as
a  two dimension array, where each position is an array of the number of cookies
and the direction to follow. I also take into account squares that
shouldn't be passable
because both their east and south neighbours are impassable:

1 50 -1
1 -1 2
1 1 1

so when processing it I change it to a -1 so that upper neighbours don't take it
into account.

data =<<EOD
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
EOD

def get_possible_destinations field,i,j
destinations = []
south = (field[i+1] || [])[j]
if south && south[0] != -1
destinations << [south[0], :S]
end
east = field[i][j+1]
if east && east[0] != -1
destinations << [east[0], :E]
end
destinations
end

field = data.map {|line| line.split.map {|e| [e.to_i, nil]}}
(field.length - 1).downto(0) do |i|
(field[i].length - 1).downto(0) do |j|
#skip the -1 so they don't get updated
next if field[i][j][0] == -1
dest = get_possible_destinations(field,i,j)
unless dest.empty?
add = dest.max {|x,y| x[0] <=> y[0]}
else
# This square is not passable, since it
# doesn't have any valid destination, unless
# it's the lower-right corner.
field[i][j][0] = -1 unless (i == field.length - 1 && j ==
field.last.length - 1)
end
end
end

i = j = 0
current = field[i][j]
path = []
until current[1].nil?
path << current[1]
current[1] == :E ? j += 1 : i += 1
current = field[i][j]
end
puts path.join(",")

Thanks for the quiz.

Jesus.

```