Building the scheduler

Section 6, step by step: from your BFS to a planner that moves every drone without collisions. The concept is on page 4 · Time & bookings; this page is about how to build it.

1 · What changes from your BFS

Your shortest_path() is the skeleton. Almost every line survives; these are the changes:

2 · The state: (zone, turn)

("junction", 2) means: at the end of turn 2, the drone is in junction. Every drone starts at (start, 0). A route is the list of states from there to the goal, one entry per turn the drone is in a zone:

[("start", 0), ("start", 1), ("junction", 2), ("path_a", 3), ("goal", 4)]
#  waited at start in turn 1 ──┘        then one zone per turn

Because the turn is part of the state, ("start", 0) and ("start", 1) are different states. That's what makes waiting possible, and it's why came_from never loops forever on the same zone.

3 · The three moves

From a state (zone, t) there are exactly three kinds of next states. Each one has a time it lands, things it must check, and things it books once the route is chosen.

4 · Why the queue must be sorted by turn

With plain BFS every step costs 1, so the FIFO queue is automatically in turn order. A restricted move costs 2, and that breaks it. Small example: from s you can go via restricted r (slow) or via a (fast), and both lead to g.

pop (s,0) → push (s,1) (r,2) (a,1)
pop (s,1) → push (s,2) (r,3) (a,2)
pop (r,2) → push (s,3) (g,3)
pop (a,1) → push (g,2)
pop (s,2) … (r,3) … (a,2) … (s,3)
pop (g,3) → "done, 3 turns" ✗
         (g,2) is still in the queue behind it

pop (s,0) → push (s,1) (r,2) (a,1)
heap order:  (a,1) (s,1) (r,2)
pop (a,1) → push (g,2)
pop (s,1) …
pop (a,2) …
pop (g,2) → "done, 2 turns" ✓
         every turn-1 state came first

FIFO happened to look at the slow branch first, and returned the first goal it pulled out. I measured this on the real maps too: with FIFO, hard/03 takes 27 turns instead of 26 and medium/03 takes 7 instead of 6.

The fix is the standard library's heapq: a list that always hands you the smallest item. Tuples compare by their first element first, so put the turn first:

import heapq

heap: list[tuple[int, str]] = [(0, "start")]   # (turn, zone): turn first!
heapq.heappush(heap, (2, "r"))
heapq.heappush(heap, (1, "a"))
turn, zone = heapq.heappop(heap)               # → (0, "start"), then (1, "a"), then (2, "r")

That's the only change: queue.append(x) → heapq.heappush(heap, x), queue.pop(0) → heapq.heappop(heap). (For the evaluation: this makes it Dijkstra's algorithm. With costs of only 1 and 2 it's the same idea as BFS, just always expanding the earliest state.)

5 · The two calendars

Both are plain dicts that count how many drones use a slot. They belong to the scheduler, not the models: the map is static, the calendar is the plan.

zone_use: dict[tuple[str, int], int]              # ("junction", 2) → 1
link_use: dict[tuple[frozenset[str], int], int]   # (frozenset({"start", "junction"}), 1) → 2

"Is there room?" for a zone:

• network.capacity(name) returns None for start and end → always room (you wrote that in section 2).
• otherwise: zone_use.get((name, turn), 0) < capacity. The .get(…, 0) means "nobody booked it yet → 0".

For a link it's the same with network.link(a, b).capacity, keyed by link.endpoints (the frozenset, so a-b and b-a share one slot).

Booking a finished route: walk through it in pairs, (a, ta) → (b, tb):

• always: add 1 to zone slot (b, tb) (that covers waits too)
• only if a != b (a real move): add 1 to link slot (a-b, ta + 1)

6 · Watch the calendar fill

This runs the algorithm from this page, live, one drone at a time. Red cells are full. Dashed chips are drones in flight on a connection. The newest drone is outlined.

7 · The search, in plain words

This is the loop you'll write. Compare it with your shortest_path() line by line:

1. Heap starts with (0, start). came_from starts with {(start, 0): None}.
2. Pop the earliest (turn, zone). If zone is the goal: walk back through came_from and return the route.
3. Build the candidate next states: wait (zone, turn+1), plus for every non-blocked neighbour (nb, turn + move_cost).
4. For each candidate: skip it if already in came_from, if the zone has no room at the landing turn, or (for a real move) if the link has no room at turn+1.
5. Otherwise: record it in came_from and push it on the heap.

And around it, the planner:

for each drone 1..nb_drones:
    route = search()          # sees the bookings of every drone before it
    book(route)
    keep route

8 · The class skeleton

Types and names only. The bodies are yours.

class Scheduler:
    """Plan every drone's route through a shared booking calendar."""

    def __init__(self, network: Network) -> None:
        # store network, create the two empty calendars

    def plan(self) -> list[list[tuple[str, int]]]:
        # one route per drone, in drone order (Pathfinder guard first)

    def _search(self) -> list[tuple[str, int]]:
        # section 7: heap, came_from, the three moves

    def _zone_has_room(self, zone: str, turn: int) -> bool:
    def _link_has_room(self, a: str, b: str, turn: int) -> bool:
    def _book(self, route: list[tuple[str, int]]) -> None:

Suggested order, each with a check in between:

1. __init__, _zone_has_room, _link_has_room, _book: small and testable on their own.
2. _search with only wait + normal moves. Test: easy/01 → 4 turns, easy/02 → 4 turns.
3. Restricted moves (+2) and heapq. Test: the restricted example above.
4. plan() with the Pathfinder guard. Then all 10 maps against the benchmark table in PROGRESS.md.

Priority zones: skip them for now. The algorithm already hits the optimum on medium/03_priority_puzzle without special handling. If you want them later, they're a tie-breaker in the heap tuple, never a reason to take a slower route.

9 · Check yourself

• Why does came_from need the turn in its key now?
• A drone moves from a at turn 3 into a restricted r. Which two slots does it book, and at which turns?
• Why is the link booked at t+1, not t?
• What goes wrong with a FIFO queue, and why can't it happen without restricted zones?
• Why do start and goal never show up red in the calendar?
• What happens if you forget the Pathfinder guard and the goal is unreachable?