Winters on the cut

A canal restoration trust musters one working party a winter, and it dredges as many stretches at once as the silt rules allow. How many winters does the cut need?

The problem

The derelict canal is cut into stretches stretches, numbered 0 to stretches - 1. A silt rule [upper, lower] means upper must be dredged in an earlier winter than lower: spoil disturbed up the cut settles further down and would bury finished work.

A winter may take any number of stretches at once, so long as every rule pointing at a stretch names one finished earlier. Return the fewest winters that finish the cut, or -1 if the rules can never all be satisfied.

Input. stretches — an integer. rules — a list of pairs [upper, lower]; a pair may repeat, and never names the same stretch twice.

Output. The minimum number of winters, or -1.

Example.

stretches = 6
rules = [[0, 2], [1, 2], [2, 3], [2, 4], [5, 4]]   ->  3

Winter one takes 0, 1 and 5 — nothing points at them. Winter two takes 2, now both 0 and 1 are done. Winter three takes 3 and 4.

A second example, where the same rule count gives a different answer:

stretches = 3, rules = [[0, 1], [1, 2]]   ->  3
stretches = 3, rules = [[0, 1], [0, 2]]   ->  2

The shape of the rules sets the number of winters, not how many rules there are.

And a contradiction:

stretches = 3, rules = [[0, 1], [1, 2], [2, 0]]   ->  -1

Constraints.

• 1 <= stretches <= 10^5
• 0 <= len(rules) <= 2 * 10^5
• 0 <= upper, lower < stretches, and upper != lower

Hints

Approach

Brute force

Simulate winter by winter, each time walking every stretch and re-checking every rule pointing at it: O(stretches + rules) a winter, and a chain forces stretches winters. With 10⁵ stretches and 2·10⁵ rules, about 3·10¹⁰ checks.

The insight

The answer is the length of the longest chain of rules, and you can read it straight off by peeling the cut a whole layer at a time: everything unblocked right now is exactly one winter's work, and finishing it unblocks the next layer.

A rule stops blocking once and never starts again, so nothing is re-scanned. Keep a blocker count per stretch; dredging one decrements the counts below it. A count reaching zero means every rule into that stretch cleared this winter or earlier, so it goes next winter — and draining exactly the queue present when a round began is one winter.

Algorithm

1. Build, per stretch, the list of stretches below it and a count of the rules pointing at it.
2. Queue every stretch whose count is zero. That queue is winter one.
3. While the queue is not empty, read its length k before touching it.
4. Remove k stretches, decrementing the counts below each and pushing any that hit zero — those land behind the k, in the next round.
5. Add one to the winter tally and repeat.
6. If fewer than stretches were dredged, return -1; otherwise return the tally.

Complexity

Time O(stretches + rules) — each stretch enters the queue once, each rule is decremented once. Space O(stretches + rules) — lists, counts and queue.

Solution

"""Winters on the cut — peel the rules a whole layer at a time and count layers."""

from collections import deque


def solve(stretches, rules):
    below = [[] for _ in range(stretches)]
    blockers = [0] * stretches
    for upper, lower in rules:
        below[upper].append(lower)
        blockers[lower] += 1        # one unit per rule, repeats included

    ready = deque(s for s in range(stretches) if blockers[s] == 0)
    dredged = 0
    winters = 0
    while ready:
        # Invariant: `ready` holds exactly the stretches this winter can take —
        # every rule into them names a stretch dredged in an earlier winter.
        # The length is read once, so pushes made below fall into the next round.
        for _ in range(len(ready)):
            stretch = ready.popleft()
            dredged += 1
            for lower in below[stretch]:
                blockers[lower] -= 1
                if blockers[lower] == 0:
                    ready.append(lower)
        winters += 1

    # A stretch inside a cycle never reaches zero blockers, so it is never dredged.
    return winters if dredged == stretches else -1

TESTS = [
    ((6, [[0, 2], [1, 2], [2, 3], [2, 4], [5, 4]]), 3),
    ((3, [[0, 1], [1, 2]]), 3),
    ((3, [[0, 1], [0, 2]]), 2),
    ((3, [[0, 1], [1, 2], [2, 0]]), -1),
    ((1, []), 1),                                  # one stretch, one winter
    ((4, []), 1),                                  # no rules: all four together
    ((5, [[0, 1], [0, 1], [1, 2]]), 3),            # the same rule written twice
    ((4, [[1, 0], [3, 2], [2, 1]]), 4),            # a chain against the numbering
]

Pitfalls

• Counting a winter per stretch removed rather than per layer. That is a stretch tally wearing a winter's name: 6 on the first example, not 3.
• Re-reading the queue length inside the round. for _ in range(len(ready)) is correct only if the length is taken once, before any push; recompute it mid-round and next winter's stretches get dragged into this one.
• Returning the tally without counting what was dredged. A cycle leaves its stretches holding a blocker that never clears; the queue runs dry and you report a plausible number for a plan nobody can carry out.
• Half-deduplicating repeated rules. A repeat adds two blockers and is decremented twice, so it cancels out — filtering one side only does not.

Variants

• Dye house shade index — the same peel, reporting one sequential order instead of a round count.
• Conservation precedence — the same rules, asked as questions about what must come first.