Sluice gate loop

An irrigation network was extended by four different crews over thirty years. Somewhere in it, water may be running in a circle instead of reaching a field.

The problem

Every sluice gate spills into exactly one gate downstream, and water released at the source follows that chain gate by gate. If the chain ends the water reaches the fields and the network is sound; if some gate spills back into a gate the water has already passed, it circles forever and the fields below get nothing.

You are walking the network on foot. At each gate you can read its number and see which gate it spills into, and that is all: there is no map, and no room on the tablet to list the gates you have already stood at. Find the first gate the water enters twice — where the circle closes — or report that it drains.

Input. gates — a list of distinct gate numbers, in the order water passes them from the source. spill — the index in that list of the gate that the last gate spills into, or -1 if the last gate empties onto the fields.

Output. The number of the first gate the water reaches twice, or None if the water drains.

Example.

gates = [12, 7, 30, 5], spill = 1   ->  7

Water runs 12, 7, 30, 5, then back round 7, 30, 5 forever. Gate 12 is passed once; gate 7 is the first reached twice.

A second example, covering the two edges:

gates = [12, 7, 30, 5], spill = -1  ->  None
gates = [9], spill = 0              ->  9

The first drains. The second is a single gate whose outlet was re-cut into its own inlet, so the water never leaves it.

Constraints.

• 1 <= len(gates) <= 10^5
• gate numbers are distinct, 1 <= number <= 10^6
• -1 <= spill < len(gates)
• Extra memory O(1): the tablet holds a few gate numbers, not a set of them.

Hints

Approach

Brute force

Record every gate number in a set as you pass it and stop at the first repeat: one walk, at most n lookups, and a set of up to 100,000 numbers — roughly 6 MB against the sixteen bytes two walkers need. Correct, and it fails the constraint the question exists to test.

The insight

Once both walkers are inside the circle, the fast one closes the gap by exactly one gate per hour, so the gap counts down through every value to zero and they cannot step past each other.

That is the whole proof of termination, and the step size is the precondition: a gap shrinking by exactly one must hit zero, while a walker moving three gates an hour shrinks it by two, so an odd gap steps straight over zero and the pair circles forever.

The entry gate then falls out of arithmetic. At the meeting slow has walked L + a and fast twice that, which is also L + a + kC, so L = kC - a: source to entry is the same distance as meeting gate forward to entry. Put one walker back at the source, move both one gate an hour, and they arrive together.

Algorithm

1. Set slow and fast to the source gate.
2. While fast and fast.spill exist: move slow one and fast two, stopping if they stand at the same gate.
3. If the loop ended because fast ran out of network, return None.
4. Move slow back to the source.
5. Advance slow and fast one gate at a time until they are at the same gate.
6. Return that gate's number.

Complexity

Time O(n) — the meeting happens within one lap, so fast walks at most about 2n gates and the second phase at most n more. Space O(1) — two references, whatever the size of the network.

Solution

"""Sluice gate loop — fast and slow walkers, then one walker reset to the source."""


class Gate:
    """One sluice gate; `spill` is the single gate it empties into, if any."""

    def __init__(self, number):
        self.number = number
        self.spill = None


def dig(gates, spill):
    """Build the network: gate i spills into gate i+1, the last into `spill`."""
    nodes = [Gate(number) for number in gates]
    for i in range(len(nodes) - 1):
        nodes[i].spill = nodes[i + 1]
    if spill >= 0:
        nodes[-1].spill = nodes[spill]
    return nodes[0]


def solve(gates, spill):
    source = dig(gates, spill)

    slow = fast = source
    met = False
    while fast and fast.spill:
        # invariant: fast has walked exactly twice as far as slow, so once both
        # are inside the circle the gap between them shrinks by one each step.
        slow = slow.spill
        fast = fast.spill.spill
        if slow is fast:
            met = True
            break
    if not met:
        return None            # fast walked off the end: the water drains

    # L = kC - a: source-to-entry equals meeting-point-forward-to-entry.
    slow = source
    while slow is not fast:
        slow = slow.spill
        fast = fast.spill
    return slow.number

TESTS = [
    (([12, 7, 30, 5], 1), 7),
    (([12, 7, 30, 5], -1), None),
    (([9], 0), 9),
    (([9], -1), None),
    (([4, 8], 0), 4),
    (([4, 8], 1), 8),
    (([61, 42, 17, 3, 88, 90, 12], 0), 61),
    ((list(range(1, 51)), -1), None),
]

Pitfalls

• Testing for the meeting before the first move. Both walkers start at the source, so an equality check at the top of the loop fires immediately and every network, drained or not, reports its source gate.
• Checking only fast.spill. On a draining network fast itself becomes None first — gates = [12, 7, 30, 5], spill = -1 raises an attribute error rather than returning None. Both fast and fast.spill must be tested, in that order.
• Returning the meeting gate. It sits inside the circle but is rarely where the circle closes: on the example it is gate 5, not gate 7.

Variants

• Turning the rope team — one walker over a chain that is guaranteed to end, rewiring as it goes.
• Pointer surgery — the lesson that derives the gap argument and the entry-point arithmetic in full.