Shunting to an exit

A warehouse aisle is one long run of bays, each painted with the distance a released trolley rolls from it. Can the shunter get out?

The problem

The bays are numbered 0 upwards along the aisle. bays[i] is the distance painted on bay i: a trolley released there stops at bay i + bays[i] or at bay i - bays[i], the shunter's choice, and nowhere else. A roll that would leave the aisle at either end is not allowed.

A bay painted 0 is an exit onto the yard. The shunter starts at bay start. Report whether any exit bay can be reached.

Input. bays — a list of non-negative integers. start — the index the shunter begins at.

Output. True if some bay painted 0 can be reached, False otherwise.

Example.

bays = [4, 2, 3, 0, 3, 1, 2], start = 5   ->  True

Bay 5 is painted 1, so the trolley stops at bay 4 or bay 6. From bay 4 a roll of 3 leaves the aisle forwards but reaches bay 1 backwards, and bay 1 rolls 2 forward to bay 3, painted 0.

A second example, where an exit exists and is still out of reach:

bays = [1, 2, 3, 4, 0], start = 0   ->  False

Bay 0 reaches bay 1, bay 1 reaches bay 3, and both rolls out of bay 3 leave the aisle. Bay 4 is the exit and nothing ever stops there.

Constraints.

• 1 <= len(bays) <= 5 × 10^4
• 0 <= bays[i] < len(bays)
• 0 <= start < len(bays)

Hints

Approach

Brute force

Follow every route to a cut-off depth. Each bay offers two rolls, so 40 rolls deep is 2^40, about 1.1 × 10^12 routes — and with no cut-off a pair of bays that roll to each other keeps the search running for ever.

The insight

The paint fixes the arrows before the search starts, so nothing a route does changes what a bay offers next: arriving at a bay twice can never help, and one flag per bay is enough.

That turns a search over routes into plain reachability. Flag a bay when it is queued rather than when it is popped and it enters the queue once, which caps the work at one visit per bay and stops the bouncing.

Algorithm

1. Keep a seen flag per bay. Flag start and queue it.
2. Pop a bay. If its paint is 0, the answer is yes.
3. Otherwise work out both stopping bays, discard any outside the aisle or already flagged, and flag and queue the rest.
4. An empty queue means no exit can be reached.

Complexity

Time O(n) — each bay is queued at most once and offers two rolls: 10^5 steps for the longest allowed aisle, not 10^12 routes. Space O(n) — the flags, and at worst every bay queued at once.

Solution

"""Shunting to an exit — a breadth-first walk over the jumps the paint allows."""

from collections import deque


def solve(bays, start):
    seen = [False] * len(bays)
    seen[start] = True
    queue = deque([start])
    while queue:
        # Invariant: every bay marked seen is reachable from start, and no bay
        # is ever queued twice, so a loop of jumps cannot spin the walk.
        bay = queue.popleft()
        if bays[bay] == 0:
            return True
        for nxt in (bay + bays[bay], bay - bays[bay]):
            if 0 <= nxt < len(bays) and not seen[nxt]:
                seen[nxt] = True
                queue.append(nxt)
    return False

TESTS = [
    (([4, 2, 3, 0, 3, 1, 2], 5), True),
    (([3, 0, 2, 1, 2], 2), False),        # the exit at bay 1 is never jumped to
    (([1, 2, 3, 4, 0], 0), False),        # an exit exists but nothing reaches it
    (([0], 0), True),                     # the start is already an exit
    (([1, 1, 1, 1], 0), False),           # no exit painted anywhere
    (([2, 0], 1), True),
    (([1, 1, 1, 0], 0), True),            # bays 0 and 1 jump to each other first
]

Pitfalls

• Flagging nothing. With bays = [1, 1, 1, 1] bay 0 rolls to bay 1 and bay 1 rolls back to bay 0, so an unflagged search queues that pair for ever and never reports False.
• Letting a roll run off the end. At bay 3 of the second example i - bays[i] is -1, and Python reads bays[-1] as the last bay, painted 0: the answer comes back True for an exit no trolley can stop at.
• Testing the paint only after a roll. With bays = [0] the shunter starts on an exit, and the answer is True before anything moves.

Variants

• The cold store keyring — the same reachability question, with the arrows listed rather than painted.
• Crossing the mudflats — reachability on a grid, where the step count matters too.