I got a programming puzzle described as follows:Save Beta RabbitOh 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.LanguagesTo provide a Python solution, edit solution.py To provide a Java  solution, edit solution.javaTest casesInputs:      (int) food = 7      (int) grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]] Output:      (int) 0Inputs:      (int) food = 12      (int) grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]] Output:      (int) 1I came up with a solution but it is failing 2 out of 5 tests (specifically tests 3 and 5. Of course I have no clue what these tests do but my hunch is that it is an optimization issue. I would greatly appreciate any suggestions on enhancing the code.This is a max cost path with a cap. The approach is to use recursionAnd start from the end point and work our way back to the starting pointdef answer(food, grid):    # Set coordinates to end point    N = len(grid)    x = N - 1    y = N - 1    def backtrack(f, x, y):        #print 'food: %d, x: %d, y: %d'%(f, x, y)        f -= grid[x][y]        print 'food: %d, x: %d, y: %d'%(f, x, y)        # This is our base case, reaching the starting point.        if x == 0 and y == 0:            return f        # If we run out of food, return -1        elif f < 0:            return -1        # If we reach the left wall, the only way is up        elif x == 0 and y > 0:            return backtrack(f, x, y-1)        # If we reach the top wall, the only way is left        elif x > 0 and y == 0:            return backtrack(f, x-1, y)        # for each step, after we subtract current food from total food,        # Subtract the amount in the left and top cells and pick the smallest        # non-negative value.         elif (f - grid[x-1][y] < f - grid[x][y-1]) and (f - grid[x-1][y] >= 0):            return backtrack(f, x-1, y)        else:            return backtrack(f, x, y-1)    remainder = backtrack(food, x, y)    return remainderI timed it with the following inputs:grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]]food = 12The result is:--- 7.58171081543e-05 seconds ---
google foo.bar max path algorithm puzzle optimization
python;recursion;matrix;dynamic programming