```------art_52877_31030006.1222672631029
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Hi,

my solution is also a recursive path finding algorithm, but stores
intermediate results. The idea behind the solution is that the best path to
a position is either coming from north or west, depending on whether the
path up to the northern or western square is better, i.e. allows to collect
more cookies. Non crossing can be handled very naturally in this framework.
In order to not calculate the same path over and over again I use a hash to
store optimal paths for each square.

Thank you for this quiz. I learned a lot, especially I never used a hash
with block in this way.

Regards
Holger

# array representing forest
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]
]

# hash storing [number of cookies, path to this field]
# for each position [x, y]

path  ash.new do |hash, key|

x, y  ey

# 1) outside forest or no crossing
if x<0 || y<0 || data[y][x] -1 then
hash[key]  -1, nil]

# 2) Starting Position
elsif key [0, 0] then
hash[key]  data[y][x], "."]

# 3) otherwise
else

# 3a) cookies and path to the northern field
c_north, p_north  ath[[x, y-1]]
# 3b) cookies and path to the western field
c_west, p_west  ath[[x-1, y]]

# if both are impossible to reach, this one also is
if !p_north and !p_west then
hash[key]  -1, nil]

# take the path with more cookies and add s/e step and number of
elsif c_north > c_west then