M
Matthew Moss
I managed to get the summary done today, so here you go!
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.
**
FYI, there will be no Rubyquiz tomorrow, as I am unavailable for the
week. See you next week!
**
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.
**
FYI, there will be no Rubyquiz tomorrow, as I am unavailable for the
week. See you next week!
**