2008/5/9 Kai Krakow <hurikhan77@[...].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_prog
ramming
> >
> > 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