google foo.bar max path algorithm puzzle optimization [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it.

Closed 9 years ago.

Improve this question

I got a programming puzzle described as follows:

Save Beta Rabbit

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.

Languages

To provide a Python solution, edit solution.py To provide a Java solution, edit solution.java

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

I 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 recursion
And start from the end point and work our way back to the starting point
"""
def 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 remainder

I timed it with the following inputs:

grid = [[0, 2, 5], [1, 1, 3], [2, 1, 1]] food = 12

The result is:

--- 7.58171081543e-05 seconds ---

Do you know if it is a performance issue (speed or memory) or if it is a correctness issue? Do you get the correct results? — Simon Forsberg, Commented May 21, 2016 at 19:29
I am pretty sure it is not a correctness issue, I ran the two test examples in the description of the problem and got the same result. This is my 6th problem and I have run into several instances where the last two tests fail and then after improving the time comlexity it passes everything. — tjbadr, Commented May 21, 2016 at 19:31
This code is broken, see my answer, it's not down to speed but to incorrect implementation. — Peilonrayz, Commented May 22, 2016 at 15:21
I have rolled back the last edit. Please see What to do when someone answers. — Mast, Commented May 22, 2016 at 18:39

Peilonrayz · Accepted Answer · 2016-05-22 15:20:24Z

This code is broken. If we look at the test cases that are used, and implement them in Python, you should get something like:

import unittest
class TestAnswer(unittest.TestCase):
    def test_tiny_grid(self):
        self.assertEqual(0, answer(0, [[0]]))
    def test_google_cases(self):
        self.assertEqual(0, answer(7, [
            [0, 2, 5],
            [1, 1, 3],
            [2, 1, 1]
        ]))
        self.assertEqual(1, answer(12, [
            [0, 2, 5],
            [1, 1, 3],
            [2, 1, 1]
        ]))
    def test_simple_grid(self):
        self.assertEqual(-1, answer(2, [
            [0, 2],
            [3, 1]
        ]))
        self.assertEqual(0, answer(3, [
            [0, 2],
            [3, 1]
        ]))
        self.assertEqual(0, answer(4, [
            [0, 2],
            [3, 1]
        ]))
        self.assertEqual(1, answer(5, [
            [0, 2],
            [3, 1]
        ]))
        self.assertEqual(2, answer(5, [
            [0, 2],
            [2, 1]
        ]))
    def test_some_other_things(self):
        # Tricky case; ensures that top row/left row only assume one direction of entry
        self.assertEqual(2, answer(9, [
            [0, 2, 5],
            [1, 1, 3],
            [2, 1, 1]
        ]))
        self.assertEqual(189, answer(200, [
            [0, 2, 5],
            [1, 1, 3],
            [2, 1, 1]
        ]))
        self.assertEqual(0, answer(4, [
            [0, 1, 1],
            [1, 1, 1],
            [1, 1, 1]
        ]))
        self.assertEqual(0, answer(30, [
            [0, 7, 4, 3],
            [3, 5, 5, 3],
            [5, 2, 7, 9],
            [1, 9, 8, 4]
        ]))
        self.assertEqual(0, answer(37, [
            [0, 7, 4, 3],
            [3, 5, 5, 3],
            [5, 2, 7, 9],
            [1, 9, 8, 4]
        ]))
    def test_not_enough_food(self):
        self.assertEqual(-1, answer(3, [
            [0, 2, 5],
            [1, 1, 3],
            [2, 1, 1]
        ]))
        self.assertEqual(-1, answer(4, [
            [0, 7, 4, 3],
            [3, 5, 5, 3],
            [5, 2, 7, 9],
            [1, 9, 8, 4]
        ]))
unittest.main()

Your code fails to pass two of these tests. Which are:

class TestAnswer(unittest.TestCase):
    def test_simple_grid(self):
        self.assertEqual(0, answer(3, [
            [0, 2],
            [3, 1]
        ]))
    def test_some_other_things(self):
        # Tricky case; ensures that top row/left row only assume one direction of entry
        self.assertEqual(2, answer(9, [
            [0, 2, 5],
            [1, 1, 3],
            [2, 1, 1]
        ]))

Nice find! Are these the actual tests that are run by google when verifying the solution to this puzzle? Looks like I have some debugging to do. I better hurry up it's due tonight. — tjbadr, Commented May 22, 2016 at 15:49
@TBadr It's from the src of the thing that you linked, so I'd assume so — Peilonrayz, Commented May 22, 2016 at 15:50
I have addressed the failed test by adding additional checks for two scenarios. If we are at the last step (1,1) and going either up or left result in 0 remainder, then go ahead, otherwise default to the original logic. Of course now that I try to verify solution through foobar I am getting an http bad request error. This is third puzzle of level 3 with less than 9 hours to go. Arrrgghhh — tjbadr, Commented May 22, 2016 at 18:37

tjbadr · Accepted Answer · 2016-05-22 18:51:55Z

I have updated my code to the following:

def answer(food, grid):
    # Set coordinates to end point
    # N = len(grid)
    x = len(grid) - 1
    y = len(grid) - 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:
            print 'case1: done'
            return f
        # If we run out of food, return -1
        elif f < 0:
            print 'case2: undoable'
            return -1
        # If we reach the left wall, the only way is up
        elif x == 0 and y > 0:
            print 'case3: Reached top wall, go left'
            return backtrack(f, x, y-1)
        # If we reach the top wall, the only way is left
        elif x > 0 and y == 0:
            print' case4: Reached left wall, go up'
            return backtrack(f, x-1, y)
        # If we are at the last step (1,1) and going up or left leaves us with 0, do it
        elif (f - grid[x-1][y] == 0 and (x==1 and y==1)):
            print' case5: Last step, go up'
            return backtrack(f, x-1, y)
        elif (f - grid[x][y-1] == 0 and (x==1 and y==1)):
            print' case6: Last step, go left'
            return backtrack(f, x, y-1)
        # 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):
            print'case7: Not last step, go up'
            return backtrack(f, x-1, y)
        else:
            print 'case8: Not last step, go left'
            return backtrack(f, x, y-1)
            # return min(filter(lambda i: i >= 0, (backtrack(f, x-1, y), backtrack(f, x, y-1))))
    return backtrack(food, x, y)

This fixes the cases that I was failing but when i verify my solution through foobar it still says failing tests 3 and 5 out of 5.

hmmm, only fails one scenario: answer(30, [[0, 7, 4, 3], [3, 5, 5, 3], [5, 2, 7, 9], [1, 9, 8, 4]]) — tjbadr, Commented May 22, 2016 at 19:13

Stack Exchange Network

google foo.bar max path algorithm puzzle optimization [closed]

Save Beta Rabbit

Languages

Test cases

2 Answers 2

Linked

Hot Network Questions

google foo.bar max path algorithm puzzle optimization [closed]

Save Beta Rabbit

Languages

Test cases

2 Answers 2

Linked

Related

Hot Network Questions