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?
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.
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
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 =  * 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