Google Foobar Challenge: Save Beta Rabbit in Python

I'm going through the Google Foobar challenges and am currently on the first challenge of level three. I've come up with a working solution, however, it's not an acceptable solution because it runs out of time. How can I optimize it?


Problem Statement


Oh no! The mad Professor Boolean has trapped Beta Rabbit in an NxN
grid of rooms. In the center of each room (except for the top left
room) is a hungry zombie. In order to be freed, and to avoid being
eaten, Beta Rabbit must move through this grid and feed the zombies.


Beta Rabbit starts at the top left room of the grid. For each room in
the grid, there is a door to the room above, below, left, and right.
There is no door in cases where there is no room in that direction.
However, the doors are locked in such a way that Beta Rabbit can only
ever move to the room below or to the right. Once Beta Rabbit enters a
room, the zombie immediately starts crawling towards him, and he must
feed the zombie until it is full to ward it off. Thankfully, Beta
Rabbit took a class about zombies and knows how many units of food
each zombie needs be full.


To be freed, Beta Rabbit needs to make his way to the bottom right
room (which also has a hungry zombie) and have used most of the
limited food he has. He decides to take the path through the grid such
that he ends up with as little food as possible at the end.


Write a function answer(food, grid) that returns the number of units
of food Beta Rabbit will have at the end, given that he takes a route
using up as much food as possible without him being eaten, and ends at
the bottom right room. If there does not exist a route in which Beta
Rabbit will not be eaten, then return -1.


food is the amount of food Beta Rabbit starts with, and will be a
positive integer no larger than 200.


grid will be a list of N elements. Each element of grid will itself be
a list of N integers each, denoting a single row of N rooms. Th

1. Performance

Did you measure the performance of your solution? If you don't measure, then you'll have no idea how far off you are from a solution that's good enough.

So let's generate the largest possible test case (given the constraints in the problem description):

>>> from random import randrange
>>> N = 20
>>> grid = [[randrange(1, 6) for _ in range(N)] for _ in range(N)]
>>> T = 200

How long does the original code take? Well, it examines all paths from top left to bottom right in the grid, unless it gets lucky and find a path with remainder 0, in which case it exits early. But this test case is carefully designed so that there are no paths with remainder 0 (the maximum sum on any path is \$39×5 = 195\$).

There are \${2N-2 \choose N-1} = 35345263800\$ paths through this grid. On my computer I find that answer examines about \$60000\$ paths a second, so it will take about 7 days to finish!

You don't say what the time limit is, but I'm guessing that it's a few seconds at most. When a program is this far away from meeting the time limit, it's no good trying to optimize what you're got: instead, you have to completely rethink the algorithm.

1. Abstract the problem

The rabbit, professor, zombies and food are just set-dressing. They are distractions from the actual problem, which can be stated much more briefly:


Given an integer \$1≤N≤20\$, an \$N×N\$ grid of integers \$1≤G_{ij}≤10\$, and a target \$1≤T≤200\$, find the path from top left to bottom right in the grid (moving right or down at each step) which, when subtracted from \$T\$, leaves the smallest remainder \$r≥0\$ (if any such path exists).

1. Recursion

Combinatorial problems like this can often be solved recursively, that is, by breaking them down into subproblems and combining the solutions.

So let's consider these subproblems:


Given an integer \$1≤N≤20\$, an \$N×N\$ grid of integers \$1≤G_{ij}≤10\$, a target \$1≤T≤200\$, and a position \$(i, j)\$ in the grid, find the path from top left to \$(i, j)\$ (moving right or down at each step) which, when subtracted from \$T\$, leaves the smallest remainder \$r≥0\$ (if any such path exists).

We can solve these problems recursively: to find the solution for the parameters \$(T, i, j)\$, consider the last step on the path, which must have been down or right. If the last step was down, then the rest of the path is given by the solution for the parameters \$(T - G_{ij}, i, j-1)\$; if the last step was right, the rest of the path is given by the solution for the parameters \$(T - G_{ij}, i-1, j)\$. The direction of the last step is determined by whichever is the better of these two solutions.

This is probably easier to understand by reading the code:

def smallest_remainder(total, grid):
    """Return the smallest remainder from total after subtracting the
    numbers on a path from top left to bottom right of grid, or -1 if
    there is no path whose sum is less than or equal to total.

    >>> smallest_remainder(7, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
    0
    >>> smallest_remainder(12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
    1

    """
    def r(t, i, j):
        # Smallest remainder from t after subtracting the numbers on a path
        # from top left to (i, j) in grid, or total + 1 if there is no
        # path whose sum is less than or equal to t.
        t -= grid[i][j]
        if i < 0 or j < 0 or t < 0:
            return total + 1
        elif i == j == 0:
            return t
        else:
            return min(r(t, i - 1, j), r(t, i, j - 1))

    remainder = r(total, len(grid) - 1, len(grid) - 1)
    return remainder if remainder <= total else -1

Note that I've defined the helper function r so that it returns total + 1 for unsuitable paths, not -1. That's so the best path can easily be selected by calling min. (Try adjusting this function to use -1 for unsuitable paths: you'll see that the selection logic becomes more complex.)

1. Memoization

The trouble with this implementation is that the same subproblems are encountered several times. To solve the subproblem for \$(t=20,i=5,j=5)\$ you may need to solve the subproblems \$(t=18,i=4,j=5)\$ and \$(t=18,i=5,j=4)\$ and both of these may need you to solve the subproblem \$(t=17,i=4,j=4)\$.

To avoid this kind of duplicated work, the function r should be memoized. That is, it should maintain a table of values that it has already computed, and return an entry from the table if possible.

(Computer scientists will recognize that recursion plus memoization is very similar to the tabular method, also known as "dynamic programming". With the tabular method, you build up a table of values by looping over its cells; with recursion plus memoization you start with an empty table and fill in any cells that you need to compute.)

Memoization is most elegantly done using a decorator (this keeps the memoization logic separated from the rest of the code, and makes it reusable too). You could use `@functools.lru_ca

StackExchange Code Review Q#91317, answer score: 13