From: Christian Neukirchen <chneukirchen@...>
Date: 2008-09-29T06:34:14+09:00
Subject: Re: [QUIZ] Cookie Monster (#178)

# A simple recursive solution, not very efficient.
# One could use dynamic programming, similar to what I used in
# http://chneukirchen.org/repos/blogcode/dynprog-haskell.pdf

@maze = [
[ 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],
]
def @maze.max_x; size - 1; end
def @maze.max_y; map { |x| x.size - 1 }.min; end

def traceback(x, y, steps, score)
  if x == 0 && y == 0
    [score+@maze[x][y], steps+[[x,y]]]
  elsif x < 0 || y < 0 || @maze[x][y] < 0
    [-1, steps]
  else
    [traceback(x-1, y, steps+[[x,y]], score+@maze[x][y]),
     traceback(x, y-1, steps+[[x,y]], score+@maze[x][y])
    ].max
  end
end

score, steps = traceback(@maze.max_x, @maze.max_y, [], 0)

puts "Optimal pathway: #{score} cookies."
0.upto(@maze.max_x) { |x|
  0.upto(@maze.max_y) { |y|
    print steps.include?([x, y]) ? "[#{@maze[x][y]}]" : ("%2d " % @maze[x][y])
  }
  puts
}

-- 
Christian Neukirchen  <chneukirchen@gmail.com>  http://chneukirchen.org