Escape Pods

Created: Oct 27, 2026

Last modified: Oct 28, 2026

* AI-generated from the code I used in Google Foobar

TL, DR.

Show challenge description

The LAMBCHOP is rubble and everyone needs to get out. The bunnies are huddled in a few rooms of the station, the escape pods sit in others, and the corridors in between come in all sizes: some fit 2 bunnies at a time, others fit 8. The question isn't how long it takes to get everybody out. It's how many bunnies can reach the pods per time step once the station is running at full speed.

Full disclosure up front: I didn't solve this one on my own. At level 4, the only one I cracked by myself was Bringing a Gun to a Trainer Fight; I got through this one with outside help. What follows explains how the solution I submitted works.

# Corridors are pipes

Draw the station as a graph. Rooms are nodes, and each corridor is an arrow from A to B with a capacity, which is exactly what path[A][B] holds. A 0 means there's no corridor. Traffic in both directions between two rooms means two separate arrows, each with its own number.

Every time step follows two rules. No corridor carries more bunnies than it fits. And nobody piles up in a room along the way: whoever walks in also walks out. That's how water behaves in a network of pipes, and the problem has a name: maximum flow. Bunnies per step are the flow, the bunnies' rooms are the sources and the pods are the sinks.

# Lots of sources, lots of sinks

Max-flow algorithms expect one source and one sink, and this problem can have several of each. The fix is to make up two extra rooms. A super source S gets an unlimited corridor to every room with bunnies, and a super sink T gets an unlimited corridor from every pod. Those new corridors never slow anyone down, so the max flow from S to T is exactly the answer. That's the job of transform in my code: it wraps the matrix with a new row and column on each side.

# Ford-Fulkerson: find a path with room to spare

Ford-Fulkerson is about as intuitive as it gets. Find a path from S to T where every corridor still has room for at least one more bunny. Send as many bunnies down it as its narrowest corridor allows (the bottleneck), write that down, and look for another path. Stop when there are none left.

Each path comes from a BFS, the same one from Prepare the Bunnies' Escape, except that a corridor counts as open while it has room left. Since BFS always finds the shortest path first, this flavor has its own name: Edmonds-Karp. That buys a nice guarantee: it always finishes, in $O(V \cdot E^2)$ time no matter how big the capacities are. With 50 rooms, that's nothing.

# The trick: sending bunnies back

On its own, that greedy loop can get stuck. Take the third example in the demo. Every corridor fits 1 bunny, and the first path found is 0 → 1 → 3 → 5. That fills 3 → 5, and room 2 only leads to room 3. Nothing else seems to fit, so you'd answer 1. The real answer is 2: the bunny going through room 1 should have taken 4 instead, leaving room 3 free for the one coming from 2.

Ford-Fulkerson handles this without any guesswork. Whenever bunnies go from u to v, it also opens the option of "sending them back" from v to u. That's the reverse edge, and in the code it's these two lines:

Subtracting from flows[v][u] makes the room left on the way back, path[v][u] - flows[v][u], go up, even if that corridor doesn't exist at all. So the second BFS can go 0 → 2 → 3, step back from 3 to 1 to cancel the earlier shipment, and carry on through 1 → 4 → 5. Nobody actually walks backwards. In the end, one bunny takes 0 → 1 → 4 → 5 and the other takes 0 → 2 → 3 → 5.

# Watch the corridors fill up

Pick an example and step through it with the slider or the play button. Each step is one turn of the while True loop: the BFS path turns green, bunnies run along it, and every corridor shows flow/capacity, with thicker arrows for fuller corridors. In the third example, watch for the dashed arrow on the second path: those are the bunnies being sent back. Turn on "Show S and T" to see the super source and super sink too.

An empty station: nobody's moving yet. The BFS is about to find 1 path.

Legend: Corridor with bunnies, flow/capacity (thicker the fuller it is) Path the BFS found on this turn Bunnies sent back through a corridor (reverse edge) Full corridors of the minimum cut Rooms the last BFS still reaches

# How do we know it's the best?

The demo's last step answers that. When the BFS can no longer reach T, the rooms it did reach (the shaded ones) are cut off from the rest by corridors that are completely full. That set of corridors is called a cut, and every bunny that makes it to a pod has to cross it. So no flow can ever be larger than the sum of its capacities.

In the second example, the final BFS reaches rooms 0, 1 and 2, and the cut is made of 0 → 3, 1 → 3, 2 → 4 and 2 → 5: 6 + 2 + 4 + 4 = 16, the same as the flow we found. If the flow already fills a wall that everyone has to get through, there's no room for a single extra bunny. That's the max-flow min-cut theorem, and it's why Ford-Fulkerson can stop with a clear conscience once it runs out of paths.

# The code

Here's the code I submitted, written for Python 2.7, which is what Foobar ran:

import decimal


# Ford-Fulkerson Algorithm
inf = decimal.Decimal("Infinity")


def bfs(start, end, path, flows):
    global inf
    length = len(path)
    parents = [-1] * length  # parent table for reverse tracing path
    parents[start] = -2  # differentiate start point from others
    queue = []
    queue.append(start)
    while queue and parents[end] == -1:
        u = queue.pop(0)
        for v in range(length):
            cf = path[u][v] - flows[u][v]
            if cf > 0 and parents[v] == -1:
                queue.append(v)
                parents[v] = u
    if parents[end] == -1:  # if t can not been reached
        return 0, parents
    v = end
    delta = inf
    while v != start:
        u = parents[v]
        cf = path[u][v] - flows[u][v]
        delta = min(delta, cf)
        v = u
    return delta, parents


def transform(entrances, exits, path):
    global inf
    length = len(path)
    entrances = [i + 1 for i in entrances]
    exits = [i + 1 for i in exits]
    for row in path:
        row.insert(0, 0)
        row.append(0)
    start_row = [0] * (length + 2)
    for i in entrances:
        start_row[i] = inf
    path.insert(0, start_row)
    end_row = [0] * (length + 2)
    for i in exits:
        path[i][-1] = inf
    path.append(end_row)
    return entrances, exits, path


def solution(entrances, exits, path):
    transform(entrances, exits, path)
    flow = 0
    length = len(path)
    flows = [[0 for i in range(length)] for j in range(length)]
    start = 0
    end = length - 1
    while True:
        ap_flow, parents = bfs(start, end, path, flows)
        if ap_flow == 0:
            break
        flow += ap_flow
        v = end
        while v != start:
            u = parents[v]
            flows[u][v] += ap_flow
            flows[v][u] -= ap_flow
            v = u
    return flow

# Wrapping up

The statement talks about bunnies, corridors and time steps, but underneath it's plain maximum flow. Once you see that, two ideas do the rest: merge every source and every sink into a single one, and let later paths fix earlier ones through reverse edges. Whenever a problem asks "how much fits at once" through a network with limits, it's worth asking whether it's a flow in disguise.