Practice: Scheduling the Jobs of a Kitchen Refit

from collections import deque

JOBS = ["Strip", "Electrics", "Plumbing", "Plaster", "Units", "Worktop", "Tiles", "Paint"]
NEEDS = [
    ("Strip", "Electrics"),
    ("Strip", "Plumbing"),
    ("Electrics", "Plaster"),
    ("Plumbing", "Plaster"),
    ("Plaster", "Units"),
    ("Plaster", "Paint"),
    ("Units", "Worktop"),
    ("Worktop", "Tiles"),
]


def schedule(jobs, needs, take_from_front=True, trace=False):
    after = {job: [] for job in jobs}
    waiting = {job: 0 for job in jobs}
    for first, then in needs:
        after[first].append(then)
        waiting[then] += 1
    ready = deque(job for job in jobs if waiting[job] == 0)
    order = []

    def cells():
        return " ".join(f"{j}:out" if j in order else f"{j}:{waiting[j]}" for j in jobs)

    if trace:
        print(f"TRACE | Start | {cells()} |")
    while ready:
        job = ready.popleft() if take_from_front else ready.pop()
        order.append(job)
        for then in after[job]:
            waiting[then] -= 1
            if waiting[then] == 0:
                ready.append(then)
        if trace:
            print(f"TRACE | {job} | {cells()} | next={jobs.index(job)}")
    left = [job for job in jobs if job not in order]
    return order, left


order, _ = schedule(JOBS, NEEDS, trace=True)
print("queue:", " ".join(order))
order, _ = schedule(JOBS, NEEDS, take_from_front=False)
print("stack:", " ".join(order))
order, left = schedule(JOBS, NEEDS + [("Tiles", "Units")])
print(f"with Tiles before Units: output {len(order)} of {len(JOBS)}: {' '.join(order)}; left {' '.join(left)}")