From: Holger Mack <hmack.gm@...>
Date: 2008-09-29T16:16:21+09:00
Subject: Re: [QUIZ] Cookie Monster (#178)

------=_Part_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 = Hash.new do |hash, key|

  x, y = key

  # 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
    cookies = data[y][x]

    # 3a) cookies and path to the northern field
    c_north, p_north = path[[x, y-1]]
    # 3b) cookies and path to the western field
    c_west, p_west = path[[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
cookies
    elsif c_north > c_west then
      hash[key] = [cookies + c_north, p_north+"s"]
    else
      hash[key] = [cookies + c_west, p_west+"e"]
    end
  end
end

# print number of cookies and path for the lower right corner
puts path[[11,11]]

------=_Part_52877_31030006.1222672631029--