Exercise 3 solution

    from collections import deque, defaultdict

    def build_order(tasks):
        """tasks maps each task to the list of tasks it needs first."""
        waiting = {t: len(set(deps)) for t, deps in tasks.items()}
        needed_by = defaultdict(list)
        for t, deps in tasks.items():
            for d in set(deps):
                needed_by[d].append(t)
                waiting.setdefault(d, 0)
        ready = deque(sorted(t for t, n in waiting.items() if n == 0))
        order = []
        while ready:
            t = ready.popleft()
            order.append(t)
            for nxt in sorted(needed_by[t]):
                waiting[nxt] -= 1
                if waiting[nxt] == 0:
                    ready.append(nxt)
        if len(order) < len(waiting):
            raise ValueError("cycle among: " + ", ".join(sorted(t for t in waiting if t not in order)))
        return order

    tasks = {
        "deploy": ["test", "package"],
        "test": ["build"],
        "package": ["build"],
        "build": ["fetch", "configure"],
        "fetch": [],
        "configure": [],
    }
    print(build_order(tasks))
    print(build_order({"a": ["b"]}))
    print(build_order({}))
    try:
        build_order({"a": ["b"], "b": ["c"], "c": ["a"], "d": []})
    except ValueError as e:
        print(e)

Output:
    ['configure', 'fetch', 'build', 'package', 'test', 'deploy']
    ['b', 'a']
    []
    cycle among: a, b, c

A dict holds, for each task, how many of its requirements are still
unfinished; a dict of lists says who is waiting on whom (a graph stored as an
adjacency list). A deque is the queue of tasks that are ready to run. Taking
one off the queue "finishes" it and lowers the count of everything that was
waiting on it, and anything reaching zero joins the queue. Each task and each
requirement is handled once, so the whole job is linear in their number.
If the queue empties before every task has been placed, what remains must
wait on each other in a loop, so a cycle is reported. Sorting the names only
makes the output the same on every run.