From: Robert Klemme <shortcutter@...>
Date: 2008-05-09T21:57:23+09:00
Subject: Re: Cookie Monster!

2008/5/9 Kai Krakow <hurikhan77@googlemail.com>:
>> > Seems like a comp sci homework problem to me, as it is a classic example
>> > of where you can use dynamic programming.  Seehttp://en.wikipedia.org/wiki/Dynamic_programming
>>
>> Actually It's not homework. You don't normally get homework at my age.
>> Just something I thought would be interesting..
>>
>> > I think it's a perfect quiz for Ruby Quiz.
>>
>> Ah ok, shows how wrong I was.. I'll submit something to Ruby Quiz.
>> Thanks.
>
> Shouldn't this easily and optimally solvable with Dijkstra's
> algorithm:
> http://en.wikipedia.org/wiki/Dijkstra's_algorithm
>
> Dijkstra solves the problem bottom-up, solving smaller problems first
> and then solve the next bigger problem. One just has to make sure to
> negate the optimizer condition and to walk north and west (because
> Dijkstra's algorithm returns the previous nodes of the path, not the
> next nodes). This should be in sense of "dynamic programming" as
> mentioned before.

I did a rather straightforward backtracking implementation:

14:54:06 OZ-27759$ time /c/Temp/cookie.rb
#<struct Path
 cookies=74,
 coords=
  [[0, 0],
   [0, 1],
   [1, 1],
   [2, 1],
   [2, 2],
   [3, 2],
   [4, 2],
   [5, 2],
   [6, 2],
   [7, 2],
   [8, 2],
   [9, 2],
   [9, 3],
   [10, 3],
   [11, 3],
   [11, 4],
   [11, 5],
   [11, 6],
   [11, 7],
   [11, 8],
   [11, 9],
   [11, 10],
   [11, 11]]>

real    0m0.495s
user    0m0.436s
sys     0m0.061s
14:54:33 OZ-27759$ wc /c/Temp/cookie.rb
  76  295 1617 /c/Temp/cookie.rb
14:55:06 OZ-27759$

Kind regards

robert

-- 
use.inject do |as, often| as.you_can - without end