178 Cookie Monster

Description

Quiz description provided by Lee Jarvis.

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 

Summary

We’re going to look at the solution from Christian Neukirchen 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.


Wednesday, February 04, 2009