From: Lee Jarvis <ljjarvis@...>
Date: 2008-05-09T07:06:05+09:00
Subject: [Challenge] Cookie Monster!

Perhaps this isn't the correct place for this. Although I didn't feel
it was enough of a challenge to submit to RubyQuiz.. So I apologise
for my arrogance if that isn't so.

I had this challenge from a friend some time ago and thought I would
share it with others to see how everyone else would do it as I enjoyed
it.. So here goes..

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:

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

Thought it might be an interesting challenge for some. I for one would
love to see different ways of solving this.. Again sorry if this
challenge doesn't fit here.

Regards,
Lee