The slipway job cards

A boatyard writes every lay-up job on a card and pins a note to any card that must wait for another. Before booking the slipway, the foreman asks whether the cards can all be cleared.

The problem

The lay-up has jobs jobs, numbered 0 to jobs - 1. A note [a, b] means job a cannot start until job b is finished: repainting waits on fairing.

Nobody checked the notes against each other. Return True if some order of working clears every card, False if the notes make that impossible. A job with no notes can go at any time.

Input. jobs — an integer. notes — a list of [a, b] pairs, a waits on b. A pair may repeat.

Output. A boolean.

Example.

jobs = 5
notes = [[1, 0], [2, 1], [3, 1], [4, 3], [4, 2]]   ->  True

Haul out (0), strip the antifouling (1), then recaulk the seams (2) and fair the hull (3) in either order, then prime and paint (4).

A second example, where three notes chase each other:

jobs = 4
notes = [[0, 1], [1, 2], [2, 0], [3, 0]]   ->  False

The engine (0) goes in after the beds are painted (1), the beds after the shaft is aligned (2), the shaft after the engine is in: none can be first, and the exhaust (3) is stranded behind them.

Constraints.

• 1 <= jobs <= 10^5
• 0 <= len(notes) <= 2 * 10^5
• 0 <= a, b < jobs; a note may read [a, a]

Hints

Approach

Brute force

Check every one of the jobs! orders for a note with a before b. Twelve jobs is 479,001,600 orders, each checked in O(len(notes)).

The insight

The notes can all be satisfied exactly when the arrow graph has no directed cycle, and a peel that keeps removing a job nothing waits on stops early exactly when one exists.

Count the notes still holding each job back — its in-degree. A job at 0 can be done now; do it, and every job it releases loses one. An acyclic graph always has a job at 0 (walk backwards along arrows and you run out of jobs), so the peel takes all jobs. On a ring no job ever reaches 0, because the job before it is never done.

The alternative colours jobs during a depth-first walk — white unseen, grey on the current path, black finished — and a grey job met again means the path has looped. It costs the same; see the solution file.

Algorithm

1. Build releases[b], the jobs b releases, and waiting[a], the notes pointing at a. A repeated note adds to both, so they stay matched.
2. Queue every job with waiting == 0.
3. Pop a job, add one to done, and decrement waiting for each job it releases; push any that reaches 0.
4. When the queue empties, return done == jobs.

Complexity

Time O(jobs + notes) — every job is queued at most once and every note walked once. Space O(jobs + notes) for the lists and counts.

Solution

"""The slipway job cards — can every lay-up job be done, given which waits on which."""

from collections import deque


def solve(jobs, notes):
    # A note [a, b] is the arrow b -> a: finishing b releases a.
    releases = [[] for _ in range(jobs)]
    waiting = [0] * jobs                  # notes still holding each job back
    for a, b in notes:
        releases[b].append(a)
        waiting[a] += 1

    ready = deque(j for j in range(jobs) if waiting[j] == 0)
    done = 0
    while ready:                          # invariant: every job in `ready` has
        job = ready.popleft()             # all of its notes satisfied
        done += 1
        for nxt in releases[job]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:         # last note cleared, and only then
                ready.append(nxt)

    # A job on a ring never reaches waiting == 0, so it is never emitted.
    return done == jobs


def completable_by_colouring(jobs, notes):
    """The alternative: three-colour depth-first walk, iterative."""
    WHITE, GREY, BLACK = 0, 1, 2          # unseen / on the current path / finished
    releases = [[] for _ in range(jobs)]
    for a, b in notes:
        releases[b].append(a)

    colour = [WHITE] * jobs
    for start in range(jobs):
        if colour[start] != WHITE:
            continue
        colour[start] = GREY
        stack = [(start, 0)]              # (job, next child index to look at)
        while stack:                      # invariant: every job on the stack is GREY
            job, i = stack[-1]
            if i < len(releases[job]):
                stack[-1] = (job, i + 1)
                nxt = releases[job][i]
                if colour[nxt] == GREY:   # the path has come back on itself
                    return False
                if colour[nxt] == WHITE:
                    colour[nxt] = GREY
                    stack.append((nxt, 0))
            else:
                colour[job] = BLACK       # finished, safe to meet again
                stack.pop()
    return True

TESTS = [
    ((5, [[1, 0], [2, 1], [3, 1], [4, 3], [4, 2]]), True),
    ((4, [[0, 1], [1, 2], [2, 0], [3, 0]]), False),
    ((1, []), True),
    ((3, [[2, 2]]), False),
    ((6, [[1, 0], [2, 1], [4, 3], [3, 4]]), False),
    ((3, [[1, 0], [1, 0], [2, 1]]), True),
    ((100000, [[i + 1, i] for i in range(99999)]), True),
]

# The colouring must agree with the peel on every case.
for _args, _want in TESTS:
    assert completable_by_colouring(*_args) == _want

Pitfalls

• Pushing a job every time its count drops, not only at 0. Job 4 in the first example has two notes, so it is counted twice: done is 6, not 5, and a valid lay-up returns False.
• Skipping a self-note [a, a]. It is a cycle of length one. The peel handles it unaided: waiting[a] starts at 1 and nothing releases it.
• Two colours instead of three. Without "on the path" kept apart from "finished", a job reached by two paths — job 4 above — is reported as a cycle when it is not.

Variants

• Winters on the cut — the same peel a layer at a time, asked for the round count.
• Dye house shade index — the same peel, where the emitted order is the answer.