# Cookie Monster! **URL:** \ **Category:** Ruby\ **Created:** [May 9, 2008, 12:06am UTC](https://www.ruby-forum.com/t/cookie-monster/137109 "2008-05-09T00:06:38Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 9, 2008, 12:06am UTC](https://www.ruby-forum.com/t/cookie-monster/137109/1 "2008-05-09T00:06:38Z")
Perhaps this isn’t the correct place for this. Although I didn’t feel it was enough of a challenge to submit to RubyQuiz… So I apologise for my arrogance if that isn’t so. I had this challenge from a friend some time ago and thought I would share it with others to see how everyone else would do it as I enjoyed it… So here goes… Cookie Monster is trying to walk through the Cookie Forest and consume as many cookies as possible. However, there are many different paths that Cookie Monster can take, and he isn’t sure which way is the best way. Help him eat as many cookies as possible by writing a program which finds the optimal path from the upper left part of the forest to the bottom right. Cookie Monster can only move south and east. There are also several thorn patches through which he cannot cross. The forest can be represented as a grid of numbers, where the number represents the amount of cookies in that acre and -1 represents an impassible thorn patch. An example forest is provided below: 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 Thought it might be an interesting challenge for some. I for one would love to see different ways of solving this… Again sorry if this challenge doesn’t fit here. Regards, Lee ---
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 9, 2008, 3:42am UTC](https://www.ruby-forum.com/t/cookie-monster/137109/2 "2008-05-09T03:42:35Z")
Seems like a comp sci homework problem to me, as it is a classic example of where you can use dynamic programming. See > **[Dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming)** > > Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. > In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recur... ---
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 9, 2008, 9:44am UTC](https://www.ruby-forum.com/t/cookie-monster/137109/3 "2008-05-09T09:44:16Z")
On Fri, May 9, 2008 at 12:06 AM, Lee J. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > Perhaps this isn’t the correct place for this. Although I didn’t feel > it was enough of a challenge to submit to RubyQuiz… So I apologise > for my arrogance if that isn’t so. I think it’s a perfect quiz for Ruby Q… Jesus. ---
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 9, 2008, 10:26am UTC](https://www.ruby-forum.com/t/cookie-monster/137109/4 "2008-05-09T10:26:11Z")
On May 9, 2:41 am, Paul McMahon [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > 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 Q… Ah ok, shows how wrong I was… I’ll submit something to Ruby Q… Thanks. Lee. ---
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 9, 2008, 1:07pm UTC](https://www.ruby-forum.com/t/cookie-monster/137109/5 "2008-05-09T13:07:25Z")
> > 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 Q… > > Ah ok, shows how wrong I was… I’ll submit something to Ruby Q… > Thanks. Shouldn’t this easily and optimally solvable with Dijkstra’s algorithm: > **[Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra's_algorithm)** > > Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. > The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the s... 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. Regards, Kai ---
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 9, 2008, 2:58pm UTC](https://www.ruby-forum.com/t/cookie-monster/137109/6 "2008-05-09T14:58:12Z")
2008/5/9 Kai K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > Shouldn’t this easily and optimally solvable with Dijkstra’s > algorithm: > [Dijkstra's algorithm - Wikipedia](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 #\ 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 ---
**Author:** ![jarvo88](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/a8b319/32.png) [@jarvo88](https://www.ruby-forum.com/u/jarvo88)\ **Post date:** [May 10, 2008, 3:45pm UTC](https://www.ruby-forum.com/t/cookie-monster/137109/7 "2008-05-10T15:45:48Z")
Here is the result of my dynamic-programmed cookie monster: $ time ruby challenge.rb ESSESSSSSSESSEESEEEEEE = 74 real 0m0.022s user 0m0.012s sys 0m0.008s (ibook G4) $ wc -lc challenge.rb 50 1521 challenge.rb Same path as in Robert’s solution. regards, quentin