Gas station problem: where the circular tour starts

The gas station problem asks where to start a circular tour. Pumps stand around a loop, each gives some fuel, each leg to the next pump costs some, and the tank starts empty. A start exists exactly when the pumps give at least as much fuel in total as the legs cost. To find it, drive once from pump 0 with a running tank, and whenever the tank goes below zero, start again at the next pump: no pump since the last start could have worked. That is one pass, O(n), and the last start it chooses is the smallest pump that completes the loop.

The problem: a van on a ring road

1. gain = [3, 1, 7, 2, 5, 0], cost = [4, 3, 2, 4, 1, 3] gives 2, the only pump that works, as in the figure.
2. gain = [1, 2, 3], cost = [2, 3, 2] gives −1: the pumps give 6 litres and the legs cost 7.
3. gain = [2, 2, 2], cost = [2, 2, 2] gives 0: every pump works, and 0 is the smallest.

The brute force, and why it fails at these sizes

Try each pump as the start, smallest first, and drive until the tank goes below zero or the loop closes:

# The ring road of the lesson: pump i gives gain[i] litres, and the leg from pump i to the next costs cost[i] litres.
GAIN = [3, 1, 7, 2, 5, 0]
COST = [4, 3, 2, 4, 1, 3]


def start_by_trying_each(gain, cost):
    """Tries pump 0, then 1, ...: drives the loop until the tank would go below zero. Returns (start, legs driven)."""
    n, legs = len(gain), 0
    for start in range(n):
        tank = 0
        for k in range(n):
            i = (start + k) % n
            tank += gain[i] - cost[i]
            legs += 1
            if tank < 0:  # the van runs dry on the leg out of pump i
                break
        else:
            return start, legs
    return -1, legs


print("the six-pump ring:", start_by_trying_each(GAIN, COST))
print("gain [1, 2, 3], cost [2, 3, 2]:", start_by_trying_each([1, 2, 3], [2, 3, 2]))
for n in (1_000, 2_000, 4_000):
    cost = [1] * (n - 1) + [2]  # every leg costs what its pump gives, except the last, one litre short
    print(f"{n:,} pumps, one litre short in all: {start_by_trying_each([1] * n, cost)[1]:,} legs driven")

the six-pump ring: (2, 8)
gain [1, 2, 3], cost [2, 3, 2]: (-1, 5)
1,000 pumps, one litre short in all: 500,500 legs driven
2,000 pumps, one litre short in all: 2,001,000 legs driven
4,000 pumps, one litre short in all: 8,002,000 legs driven

The six-pump ring costs 8 legs before pump 2 gets round. On a ring where each pump gives exactly what its leg costs, except for one leg a litre short, every start drives all the way to that leg: 500,500 legs for 1,000 pumps, 8,002,000 for 4,000, and about 5 × 10¹¹ for a million, far more than a time limit of a second or two allows.

What to notice

• The total decides whether any start works. If the pumps give less fuel than the legs cost, every start runs dry somewhere on the loop.
• One failure rules out a whole stretch of starts. A van that started at pump s and runs dry on the leg out of pump j shows that every start from s to j fails too: each of them would skip a part of the drive that never left the tank below zero.

The one-pass scan, step by step Pro: opens with a Pro, Premium or Ultimate pass