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!
**