Google Foobar Challenge level 4 – Escape Pods


Google Foobar is a hidden coding challenge by Google, and Escape Pods is the challenge I solved using Python in order to complete level 4.

This post is part of a series on Google Foobar, with all the challenges I encountered. The full series is available here.

Getting ready to run

The eighth task I got for Foobar was to calculate the maximum flow of bunnies that can move across various rooms and reach the escape pods. The full description of the challenge is the following:

Escape Pods

You've blown up the LAMBCHOP doomsday device and relieved the bunnies of their work duries -- and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time.
Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak.
Write a function solution(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step. There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.

For example, if you have:
entrances = [0, 1]
exits = [4, 5]
path = [
[0, 0, 4, 6, 0, 0], # Room 0: Bunnies
[0, 0, 5, 2, 0, 0], # Room 1: Bunnies
[0, 0, 0, 0, 4, 4], # Room 2: Intermediate room
[0, 0, 0, 0, 6, 6], # Room 3: Intermediate room
[0, 0, 0, 0, 0, 0], # Room 4: Escape pods
[0, 0, 0, 0, 0, 0], # Room 5: Escape pods

Then in each time step, the following might happen:
0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5

So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step. (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5, such as 2/6 and 6/6, but the final solution remains the same.)


The challenge also list a couple of test cases you will need to pass. However, it also indicates that there will be additional hidden tests that you need to pass. But you may not know what those test are about. Nice, uh?

Test cases
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases --
solution.solution([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]])


solution.solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])



You also need to keep in mid a few constraints. They are divided between Java and Python ones.

Your code will run inside a Python 2.7.13 sandbox. All tests will be run by calling the solution() function.

Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.
Input/output operations are not allowed.
Your solution must be under 32000 characters in length including new lines and and other non-printing characters.

There are two important caveats to consider:

  • Even if in the Python section there is no mention, execution time is limited. They say so in the Java section, but somehow they do not repeat it in the Python one.
  • There are additional blacklisted libraries. For instance, I got a “BLACKLISTED CODE” exception when I tried to import the sys library

Putting a solution together

Spoiler alert: you can find a complete working solution below. However I think that just copy-pasting a solution will not do you any good. But maybe looking at the flow and understanding the thinking behind the code may put you in the right direction to solve the challenge and learn something in the doing!

Coming to our challenge, the task is basically a maximum flow calculation. We need to check how many bunnies can go from the entrance levels to the exit ones, considering the maximum capacity that can flow from one level to the other.

At the beginning I tried to put together a recursive function, starting from the exit levels and progressing throughout all connections to the entrance level while keeping note of the minimum number of bunnies that may transit at each step. However, this approach led me nowhere.

As usual, when I felt lost I started to search and I found those maximum flow problems are better solved using some algorithm like Ford-Fulkerson (Wikipedia) or Dinic (again, Wikipedia).

Getting to the point

In this post by Suraj I found a complete implementation of Dinic’s algorithm, tuned for the same Google Foobar task I was facing. There are also many other Google Foobar solutions over there (also to tasks that I did not face), very well done! I report the code below.

def bfs(matrix, source, destination):
    visited = [-1 for i in range(len(matrix))]
    visited[source] = source
    queue = [source]
    while len(queue) > 0:
        top = queue.pop(0)
        for i in range(len(matrix)):
            if (matrix[top][i][1] - matrix[top][i][0]) != 0 and visited[i] == -1:
                if i == destination:
                    # Get route
                    visited[destination] = top
                    path = [destination]
                    temp = destination
                    while temp != source:
                        temp = visited[temp]
                    # Get flow value and update augmented graph
                    temp = 1
                    total = float("inf")
                    cur = source
                    while temp != len(path):
                        entry = matrix[cur][path[temp]]
                        diff = abs(entry[1]) - entry[0]
                        total = min(total, diff)
                        cur = path[temp]
                        temp += 1
                    temp = 1
                    cur = source
                    while temp != len(path):
                        entry = matrix[cur][path[temp]]
                        if entry[1] < 0: # Already augmented need to flip
                            entry[1] += total
                            entry[0] += total
                        entry = matrix[path[temp]][cur]
                        if entry[1] <= 0: # Already augmented need to flip
                            entry[1] -= total
                            entry[0] += total
                        cur = path[temp]
                        temp += 1
                    return True
                    visited[i] = top
    return False

def answer(entrances, exits, path):
    max_val = sum(list(map(sum, path)))
    aug = []
    for i in range(len(path)):
        for j in range(len(path[i])):
            aug[i].append([0, path[i][j]])
        aug[i].append([0, 0])
        if i in exits:
            aug[i].append([0, max_val])
            aug[i].append([0, 0])
    for i in range(len(path[0]) + 2):
        if i in entrances:
            aug[-2].append([0, max_val])
            aug[-2].append([0, 0])
        aug[-1].append([0, 0])
    while bfs(aug, len(aug)-2, len(aug)-1):
    total = 0
    for i in range(len(aug)):
        total += aug[-2][i][0]
    return total

Also this time I got a good chance to see the work of brighter minds. It’s good that I can learn from them!

Once you are ready, you can check your work by typing:


If you completed your work correctly, a happy green message like this one will greet you:

Google Foobar Challenge level 4 - Escape Pods
Verifying solution...
All test cases passed. Use submit to submit your solution
Job done! 🙂 Time to move on…

You can then submit the solution as indicated. And that’s it for Google Foobar Challenge level 4 – Escape Pods!

Google Foobar Challenge level 4 - Escape Pods
Level 4 complete
You are now on level 5
Challenges left to complete level: 1
It's dangerous to go alone! To invite a friend to try a challenge, send the link below. This is a single-use code, so choose wisely.
Towards the endgame!

I received another invitation code to let another friend into the Google Foobar challenge, like at the end of level 2.

I will write about each individual challenge in a dedicated post. You will find the post series via the link at the end of this post, stay tuned for updates!

Related links

  • Google Foobar link (it is by invitation only)
  • My series of posts on Google Foobar link

Do you like our content? Check more of our posts in our blog!