Fly-in

Fly-in is a milestone M3 Python project about routing. A map file describes a network of hubs linked by connections, a start hub, an end hub and a number of drones. Your program moves every drone from start to end in as few turns as possible, respecting the capacity of each hub and each link and the type of each zone, and prints the moves turn by turn. It is a graph and scheduling problem, close in spirit to the classic lem-in, written in typed, object-oriented Python without any graph library. Details below come from student repositories (Reported by students); check them against your subject.

What you will learn

• Modelling a graph with classes: hubs, connections, capacities
• Shortest paths with BFS and Dijkstra (with heapq), and why one shortest path is not enough for many drones
• Spreading flow over several paths and scheduling moves turn by turn
• Resource constraints: capacity per hub, capacity per link, multi-turn edges
• Writing a strict parser that reports the line and cause of every error
• Visualising state in the terminal with colours

Before you start

• Previous nodes: Python Modules and A-Maze-ing (BFS on a grid is the warm-up for this graph).
• Tools: Python 3.10+, flake8, mypy. Graph libraries such as networkx are reported as forbidden; heapq from the standard library is fine.
• Reported map format: the first line is the drone count; then start_hub, end_hub and hub lines with a name, coordinates and optional metadata in brackets; connection lines a-b with an optional link capacity; # comments.
• Reported zone types: normal (one turn), restricted (two turns, the drone stays on the link), priority (one turn, preferred on ties), blocked (cannot be entered).

Plan of attack

1. Day 1: write the parser with one class per element. Reject duplicate hubs, connections to unknown hubs, duplicate or reversed connections and names containing dashes, with the line number in the message.
2. Day 1: build the graph and check that the end hub is reachable; fail cleanly when it is not.
3. Day 2: shortest path with Dijkstra where the edge cost is the zone cost of the destination, with priority zones winning ties.
4. Day 3: simulate one drone, then many drones on the same path, honouring hub capacity (start and end are unlimited) and link capacity.
5. Day 3: find several disjoint or partially shared paths and assign drones to them so the last drone arrives as early as possible.
6. Day 4: handle restricted zones: a drone entering one is in transit for a turn and must be printed accordingly.
7. Day 4: output one line per turn with only the drones that moved, and a coloured terminal view.
8. Day 5: run all provided maps, compare your turn counts with the reference values, then lint and write the README.

An illustrative map (check the exact syntax against your subject):

nb_drones: 3
start_hub: home 0 0
hub: relay 1 0 [zone=restricted max_drones=2]
end_hub: base 2 0
connection: home-relay
connection: relay-base

Common pitfalls

• Freeing a hub's capacity in the same turn a drone leaves it, or not, inconsistently: decide the rule and apply it everywhere.
• Sending every drone down the single shortest path when a longer parallel path would finish sooner.
• Infinite loops when no path exists or capacities block every move.
• Confusing link capacity with hub capacity.
• Printing drones that did not move.
• Any use of a graph library, or untyped code that fails mypy --strict.

How it is evaluated

• Peer evaluation. The evaluator runs the linters, then the provided maps from easy to hard and compares the number of turns with the reference for each map.
• Invalid maps must produce a clear error, not a traceback.
• You explain your path search, its complexity, and how drones avoid collisions.
• The hardest maps (reported as "challenger", for example 25 drones with a reference around 45 turns) are reported as bonus.

Resources

• Dijkstra's algorithm on Wikipedia
• heapq: heap queue algorithm
• Maximum flow problem on Wikipedia
• mypy documentation
• Student repo: mpouillo 42-fly-in
• Student repo: leblanc-i Fly-in