[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[Challenge] Cookie Monster!

Lee Jarvis

5/8/2008 10:04:00 PM

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
6 Answers

Paul McMahon

5/9/2008 1:42:00 AM

0

Seems like a comp sci homework problem to me, as it is a classic example
of where you can use dynamic programming. See
http://en.wikipedia.org/wiki/Dynamic_p...

Jesús Gabriel y Galán

5/9/2008 7:43:00 AM

0

On Fri, May 9, 2008 at 12:06 AM, Lee Jarvis <ljjarvis@googlemail.com> 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 Quiz.

Jesus.

Lee Jarvis

5/9/2008 8:24:00 AM

0

On May 9, 2:41 am, Paul McMahon <p...@ubit.com> 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_p...

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.

Lee.

Kai Krakow

5/9/2008 11:07:00 AM

0

> > Seems like a comp sci homework problem to me, as it is a classic example=

> > of where you can use dynamic programming. =A0Seehttp://en.wikip...
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...

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

Robert Klemme

5/9/2008 12:57:00 PM

0

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_p...
>>
>> 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...
>
> 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

Quentin Sabah

5/10/2008 1:41:00 PM

0


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