Google Foobar Challenge: Save Beta Rabbit in Python

Question

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. The first element of grid will be the list denoting the top row, the second element will be the list denoting second row from the top, and so on until the last element, which is the list denoting the bottom row. In the list denoting a single row, the first element will be the amount of food the zombie in the left-most room in that row needs, the second element will be the amount the zombie in the room to its immediate right needs and so on. The top left room will always contain the integer 0, to indicate that there is no zombie there.

The number of rows N will not exceed 20, and the amount of food each zombie requires will be a positive integer not exceeding 10.

Test Cases

Inputs:
 (int) food = 7
 (int) grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]]
Output:
 (int) 0
Inputs:
 (int) food = 12
 (int) grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]]
Output:
 (int) 1

Solution

My approach is to generate "paths", combinations of 1s/0s (with an equal number of each) representing right/down movement, and following them one by one on the grid, and for each one keeping track of the food the rabbit has left.

import itertools
def answer(food, grid):
 # dimension of NxN grid
 n = len(grid)
 results = []
 # max coordinate (length - 1)
 maxdir = n - 1
 # total moves to navigate to bottom right corner
 total = maxdir * 2
 # generator creates combinations of the bits to flip
 for bits in itertools.combinations(range(total), maxdir):
 # create path (1 is go right, 0 is go down)
 path = [0] * total
 for bit in bits:
 path[bit] = 1
 # current food left and coordinates
 foodleft = food
 x = 0
 y = 0
 # follow steps in path
 for step in path:
 if step:
 x += 1
 else:
 y += 1
 # get food needed in cell and subtract from foodleft
 foodat = grid[y][x]
 foodleft -= foodat
 # if he runs out of food, he's dead so skip
 if foodleft < 0:
 break
 # if he makes it to the bottom right cell...
 if x == maxdir and y == maxdir:
 # if he has 0 food left that's as good as it gets, return 0
 if not foodleft:
 return 0
 # otherwise keep track of food left and add to results
 results.append(foodleft)
 # return the minimum food left if there was a survivable path
 if results:
 return min(results)
 else:
 return -1

• Jaime: This has DP written all over it...

Answer 1

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 ×ばつ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.

2. 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\$ 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).

3. 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\$ 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.)

4. 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_cache, like this:

from functools import lru_cache
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
 """
 @lru_cache(maxsize=None)
 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

And this takes a fraction of a second to solve the test case from §1 above:

>>> timeit(lambda:smallest_remainder(T, grid), number=1)
0.01503253699047491

• user124384: How does this explore every possible path if it only moves up and left? Don't you have to move right and down as well?
• Gareth Rees: @user124384: The problem says, "the doors are locked in such a way that Beta Rabbit can only ever move to the room below or to the right."
• KevinKim: So for a 20 * 20 grid, your algorithm only takes 0.08 second to finish?
• Gareth Rees: @ChenJin: Try it yourself and see!
• KevinKim: I tried, the one without the Memorization. On my computer your method is 20% faster than mine

Answer 2

This condition can be optimized:

if foodleft < 0:
 break

Since every zombie requires at least 1 unit of food, if there are \$k\$ moves left, then at that point, if you don't have \$k\$ units of food left, then you can stop, because it's clear that you won't reach the exit.

That is, you can change the condition to this:

if foodleft < total - x - y:
 break

This will cut down on the number of paths that will be evaluated. Hopefully that helps.

• Andrew: Ah, thanks. That's good. Unfortunately, it still surpasses the time limit.
• janos: Actually, as @Jaime points out in a comment, DP can be a more important thing to try. In the current implementation, some sub-paths are checked multiple times. Using DP will cut down on those, and will surely get you pass the time limit

Answer 3

I only need two loop to solve this problem. Outer loop for each row. Inner loop for each column. Always take the maximum between the sum of adding left element and the sum of adding top element as long as not exceeding the food amount.

Case 1

0, 2, 5
1, 1, 3
2, 1, 1

Solution

0, 2, 7
1, 3, 6
3, 4, 7

Python Code (listing all combination)

def answer(food, grid):
 N = len(grid)
 ans_grid = [[set() for i in range(N)] for j in range(N)]
 ans_grid[0][0] |= {grid[0][0]}
 for (row, row_val) in enumerate(grid):
 for (col, val) in enumerate(row_val):
 if row != 0:
 ans_grid[row][col] |= {val + x for x in ans_grid[row-1][col]
 if (val + x) <= food}
 if col != 0:
 ans_grid[row][col] |= {val + x for x in ans_grid[row][col-1]
 if (val + x) <= food}
 all_ans = sorted(ans_grid[N-1][N-1], reverse=True)
 for el in all_ans:
 if el <= food:
 return food-el
 return -1
food = 7
grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]]
print(answer(food, grid))
food = 12
grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]]
print(answer(food, grid))

• Andrew: Hmm, I'm not sure how this would work. If I'm always taking the maximum of those two, then it seems like the food would go down to critical levels quite quickly, and I'll be stuck far from the goal corner with not enough food to continue. Or, if I'm not understanding you, then what's the meaning of your solution? How do I determine the food left from those numbers?
• inyoot: @Andrew you can find maximum number of food needed and minimum number of food needed by using only two loops (N^2) instead of listing all possible paths. If amount of food Beta Rabbit is less than minimum number of food then return -1 else backtrack maximum path and modify it until equal or less than Betta Rabbit food amount.
• Andrew: If you don't mind, can you write some example code? I'm afraid I still don't understand.
• inyoot: I add an example code in the answer for you @Andrew
• Andrew: Thank you! This answer worked great since I couldn't answer it in time, and I mostly understand it...looking forward to my algorithms class to understand this kind of stuff better.

Answer 4

This problem is a classic shortest-path traversal of a graph and you'd do well to make use of Dijkstra's algorithm for solving this. The key is in properly defining the vertices (nodes), and also making use of a min-heap (priority-queue) to keep track of the next room which would give you the lowest amount of food remaining from the current position.

A few points:

• Rabbit can never go to a room that will result in having food < 0, otherwise he'll be eaten!

• Rooms can only be traversed to the right or below

• Each decision (move right or left) is based solely on finding the room that minimizes the amount of food rabbit will have remaining after moving there. (i.e. we need to have a proper comparator for the nodes in the graph)

• Once we get to the bottom-right room, we're done!

• Rabbit starts in room [0][0], i.e. the top-left room.

With those things in mind, I've coded this up in python with the needed tests to verify. It's a basic breadth-first traversal, but we use a min-queue instead of a normal FIFO queue to enforce the constraints.

import unittest
import heapq
class Node:
 def __init__(self, food, position):
 self.food_remaining = food
 self.position = position
 def __lt__(self, other):
 return self.food_remaining < other.food_remaining
def ZombieGrid(food, grid):
 grid_height = len(grid)
 grid_width = len(grid[0])
 pq = []
 # Rabbit starts in the top-left corner: 0,0
 heapq.heappush(pq, Node(food, (0,0)))
 while len(pq) > 0:
 top = heapq.heappop(pq)
 # once we're in the bottom-right corner then we are done
 if top.position == (grid_height-1, grid_width-1):
 return top.food_remaining
 # try moving down
 if top.position[0] < grid_height-1:
 # will use the food up for the room below
 food_for_room_below = grid[top.position[0]+1][top.position[1]]
 # don't go to the room if we will get eaten!
 if top.food_remaining - food_for_room_below >= 0:
 heapq.heappush(pq, Node(top.food_remaining - food_for_room_below, (top.position[0] + 1, top.position[1]) ))
 # try moving right, same logic as for moving down
 if top.position[1] < grid_width-1:
 food_for_room_right = grid[top.position[0]][top.position[1]+1]
 if top.food_remaining - food_for_room_right >= 0:
 heapq.heappush(pq, Node(top.food_remaining - food_for_room_right, (top.position[0], top.position[1] + 1) ))
class UnitTests(unittest.TestCase):
 def test_first(self):
 self.assertEqual(0, ZombieGrid(7, [[0, 2, 5], [1, 1, 3], [2, 1, 1]]))
 def test_second(self):
 self.assertEqual(1, ZombieGrid(12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]]))