Running with Bunnies

Created: Oct 28, 2026

Last modified: Oct 28, 2026

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

TL, DR.

Show challenge description

The station is falling apart and the bulkhead is sliding shut. You've got a clock showing time_limit seconds, a matrix telling you how long it takes to get from every spot to every other spot, and a handful of bunnies scattered along the way. Reach the bulkhead before it seals, carrying as many bunnies as you can. So far that's an ordinary routing problem, except for one twist: some corridors run through security checkpoints that add time back to the clock.

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.

# The rules in a nutshell

# Take it for a spin

Before any algorithms, go for a run yourself. Click a spot to move there. The arrows leave from where you're standing and show what each corridor does to the clock, and the green ones give time back. Bunnies jump into your arms as you pass by, and the table below logs your route just like the one in the statement. On the second example, try escaping with bunnies 1 and 2 when you only start with 1 second. Then, on "A cycle that gains time", see what happens when you go back and forth between bunny 0 and the bulkhead.

You're at the start with 1 second. Click another spot to move.

# Two separate questions

If you played with the second example, you probably noticed that the direct corridor is rarely the best one. Going from the start to bunny 1 takes 2, but swinging by the bulkhead first takes −1 + 2 = 1. That's a hint to split the problem in two:

# Bellman-Ford: shortest paths with negative numbers

The first question is a shortest-path problem, but the usual go-to, Dijkstra, doesn't work here. Dijkstra treats a spot as settled the moment it leaves the queue, and that only holds when no corridor takes time off. With negative corridors, a path that looked expensive can end up being the cheapest one.

Bellman-Ford is more patient. Everything starts at infinity except the origin, and then it goes over every corridor again and again, keeping any improvement it finds:

After the first pass, every shortest path made of one corridor is right. After the second, every one made of two, and so on. A shortest path that doesn't repeat spots has at most V − 1 corridors, so after V − 1 passes nothing can improve anymore... unless there's a catch. My relax does V passes, one extra that doesn't hurt. Since I need the times between every pair of spots, I run it once from each origin and build a distance matrix. With 7 spots at most, that's 7 passes over 49 corridors per origin, which is nothing.

# The catch: a negative cycle

The catch is a loop that adds up to a negative number. If going from bunny 0 to the bulkhead takes −1 and coming back takes 0, every lap hands you a free second. There's no such thing as "the shortest path" anymore, because one more lap always makes it shorter. For this problem that's great news: you have all the time in the world, so you take every bunny.

How do you spot one? Without negative cycles, shortest distances can't be improved: going from the start to u and then from u to v never beats the best path from the start to v. That's what isNegativeCycle checks. If dist[0][u] + dist[u][v] < dist[0][v] holds for some pair, something can still go down, and that only happens with a negative cycle around. Every spot connects to every other one, so any cycle can be reached from the start.

# Try every group

The second question doesn't need anything clever. With 5 bunnies there are 31 possible groups, and even counting every order you could visit them in, that's 325 routes in total. So try them all, in the order the statement asks for: bigger groups first and, among groups of the same size, lower IDs first. The first group with some order that fits in time_limit is the answer.

Each route uses the Bellman-Ford matrix: start → first bunny → … → last bunny → bulkhead. The neat part is that every leg already includes any detour worth taking, like stopping by the bulkhead to grab a second, so you never have to think about them. And if a leg happens to pass another bunny's spot, that bunny jumps in too. That doesn't break anything, since the bigger group was already tried earlier.

# Both halves together

On top is the time matrix. Flip the switch to compare the statement's times with Bellman-Ford's: green cells are shortcuts, and clicking one shows the route it takes and how its corridors add up. On "A cycle that gains time", the diagonal turns red. That's the time to get back to where you started, and a negative one is exactly the negative cycle. Below the matrix is the search, with every group it tried and the best order to visit it.

Legend: Faster than the direct corridor (click it to see the route) Back where you started with more time than you left with: a negative cycle

Bellman-Ford found 11 shortcuts. The search tried 4 groups, and the first one that fits in 1 is [1, 2].

# The tie-break gotcha

The version I submitted didn't loop over groups. It went straight through the orders with itertools.permutations(bunniesIndex, k) and returned the first one that fit, sorted. It works on the statement's examples, but there's a hole in it. Permutations come out in lexicographic order of the sequence, not of the group. Look at the last example in the demo: group {0, 1} only fits if you grab bunny 1 before bunny 0, and the sequence (1, 0) comes after (0, 2), which fits too. That version answered [0, 2] when the right answer is [0, 1].

The fix is to keep the two things apart. itertools.combinations hands out the groups in the right order, and each group then tries all of its permutations. That way the first group that fits is guaranteed to have the lowest IDs.

# The code

Here's the code I submitted, with the tie-break fix applied, written for Python 2.7, which is what Foobar ran:

import itertools


class BellmanFord:
    def __init__(self, edges):
        self.edges = edges
        self.distances = [float('inf') for vertex in edges]

    def relax(self, src):
        self.distances = [float('inf') for vertex in self.edges]
        self.distances[src] = 0 #self.edges[src][src]
        for _ in range(len(self.edges)):
            for u, v, w in self.enumerateEdges(self.edges):
                if self.distances[u] != float('inf') and self.distances[u] + w < self.distances[v]:
                    self.distances[v] = self.distances[u] + w
        return self.distances

    def enumerateEdges(self, edges):
        for u, row in enumerate(edges):
            for v, weight in enumerate(row):
                yield u, v, weight

    def isNegativeCycle(self, bellmanFordMatrix):
        distance = bellmanFordMatrix[0]
        for u, v, w in self.enumerateEdges(bellmanFordMatrix):
            if distance[u] != float('inf') and distance[u] + w < distance[v]:
                return True
        return False


def generateBellmanFordMatrix(edges):
    distance = []
    bell = BellmanFord(edges)
    for vertex in range(len(edges)):
        dist = bell.relax(vertex)
        distance.append(dist)
    return distance


def solution(times, time_limit):
    bunnies = len(times) - 2 if len(times) - 2 >= 0 else 0
    bunniesIndex = [i + 1 for i in range(bunnies)]
    bellmanFord = BellmanFord(times)
    dist = generateBellmanFordMatrix(times)
    if bellmanFord.isNegativeCycle(dist):
        return list(range(bunnies))
    for numbunnies in range(bunnies, 0, -1):
        # sets in lexicographic order, so the first one that fits has the lowest IDs
        for combination in itertools.combinations(bunniesIndex, numbunnies):
            for permutation in itertools.permutations(combination):

                cost = 0
                for i in range(len(permutation) - 1):
                    cost += dist[permutation[i]][permutation[i+1]]
                # from start to first bunny
                cost += dist[0][permutation[0]]
                # from last bunny to end
                cost += dist[permutation[len(permutation) - 1]][len(dist) - 1]

                if cost <= time_limit:
                    return [i - 1 for i in combination]
    return []

# Wrapping up

This challenge mixes two ideas. When a graph has negative weights, Bellman-Ford is the tool for the job, and it also tells you when there's a negative cycle, which here means infinite time. And when the combinatorial part is tiny, like 5 bunnies, trying everything is perfectly fine. Just be careful about the order you try things in, because that's where the tie-break bites.