# Cookie Monster (#178)

**URL:** <https://www.ruby-forum.com/t/cookie-monster-178/150058>\
**Category:** Ruby\
**Created:** [October 2, 2008, 11:22pm UTC](https://www.ruby-forum.com/t/cookie-monster-178/150058 "2008-10-02T23:22:57Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [October 2, 2008, 11:22pm UTC](https://www.ruby-forum.com/t/cookie-monster-178/150058/1 "2008-10-02T23:22:57Z")

</div>

I managed to get the summary done today, so here you go!

We’re going to look at the solution from _Christian N._ this  
week. It’s a recursive solution, as several of the submissions were,  
but I found it easy to follow.

First, Christian defines our dataset, the forest maze:

```
@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

```

This is a fairly straightforward “2D” matrix, where our data is stored  
in an array of rows, each row an array of that row’s column data. One  
thing to keep in mind: throughout the rest of the code, `x` is the row  
index and `y` is the column index. This doesn’t matter as far as the  
code is concerned, but I mentioned it for those of you who are used to  
seeing `x` as column and `y` as row, to avoid confusion.

One nice, Ruby-ish technique here is the definition of `max_x` and  
`max_y` on the _instance_ `@maze`. I always seem to forget that this  
is quite possible in Ruby, and a handy technique to add data and  
methods to a single object, to avoid modifying classes or creating new  
ones. The calculation of `max_y` ensures safe access to the matrix in  
the case where some row is too short, by essentially ignoring any  
incomplete columns – a reasonable approach, though we prefer if the  
user gives us a good matrix to start with.

The use of `@maze` rather than simply `maze` is strange; it works by  
setting a member of the “main” runtime environment object, but is  
certainly unusual for a simple script like this. However, making it a  
member of “main” then allows the `traceback` function (which  
effectively is also a member of “main”) to use `@maze` freely. This  
seems to be a sort of “safe global”, since it is hidden from other  
classes, whereas a “real” global (e.g. `$maze`) would not be.

Now we get to the heart of the code, the `traceback` function:

```
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)

```

The last line initiates the process, starting at the lower-right  
corner of the matrix and working backwards. The argument `steps` will  
become our path through the matrix (initially empty), while the  
`score` argument is the number of cookies eaten along that path  
(initially zero). `traceback` examines three cases in our matrix.

First case: We are at the origin (i.e. both `x` and `y` are zero).  
This is a terminating (i.e. non-recursive) case, that simply appends  
the origin to the path via `steps + [[x,y]]` and adds in the origin’s  
score to the overall score via `score + @maze[x][y]`. These two values  
are returned as a two-component array, as all the cases do and as the  
initial call to `traceback` expects.

Second case: We have stepped outside the maze (either `x < 0` or `y < 0`) or have stepped into an impassible cell (i.e. `@maze[x][y] < 0`).  
In this case, we return an overall score of -1, which when we compare  
scores corresponding to particular paths, this will be eliminated as  
being too small. That’s why we also don’t bother to modify `steps`  
here or recurse further.

Third case: We are inside the maze. This is, obviously, where the  
recursion occurs – and in fact, occurs twice. At each point in the  
maze, we can try tracing back either to the north (i.e. `x - 1`) or to  
the west (i.e. `y - 1`). In both cases, we append the current cell to  
the path and add in the current cell’s cookie count to the score.

What we get back from `traceback`, as mentioned before, is a  
two-component array consisting of score and path. These, then, are  
passed to the `max` function. Since score appears first in these  
arrays, the “larger” array is the one with the highest score; that is,  
the most cookies. That array will be returned, ensuring that  
`traceback` always returns a two-component array.

One thing that threw me off just a little is the difference between  
the arguments to `traceback` (path followed by score) versus its  
return value (score followed by path). This is entirely a code style  
issue and has zero effect on the algorithm. Still, I like to keep  
similar things parallel for the sake of clarity, and would swap the  
order of arguments (and make the appropriate adjustments in the  
recursive calls).

It is perhaps not the most efficient solution: take a look at the  
A-star solution provided. It is likely to beat out all the others for  
large cookie forests.

\*\*  
FYI, there will be no Rubyquiz tomorrow, as I am unavailable for the  
week. See you next week!  
\*\*