Runway Controller: Priorities, Spacing, Wind and Scale

Runway Controller: Priorities, Spacing, Wind and Scale

You've joined the team that builds the runway scheduling core for a regional airport. Flights ask for a runway slot; the controller decides who goes next, on which runway, and when. The first release handles one runway with no spacing rules, and controllers have already complained about who it clears first. Spacing, multiple runways with wind closures, and a faster engine for the daily timetable are queued behind that.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh controller and returns one result per operation. Every operation is [name, ts, ...args]; ts is an integer number of seconds and never decreases. Errors are returned as strings, never raised.

• Each error is returned as "error: <code>". An unknown operation name returns "error: unknown operation"; a wrong number of arguments, a non-integer ts, an empty or non-string id, or a non-string kind returns "error: invalid arguments".
• A kind is "emergency" (an emergency landing), "landing" or "takeoff".
• A flight id can be requested only once, ever: it stays taken after the flight is cleared or cancelled (flight exists). cancel only works on a waiting flight; a cleared, cancelled or unknown flight returns flight not found.
• request_batch imports count flights (1 to 100000) named <prefix>1 ... <prefix>N, all at the same ts. Their kinds cycle through the kinds list (a non-empty list of kinds). It is all-or-nothing: if any generated id is already taken, nothing is added.
• queue lists waiting flights in clearing order; with a limit (an integer >= 0) only that many.
• clear_next removes the next flight from the line and assigns it to a runway. It returns [flight_id, runway_id, start], where start is when its operation begins (seconds). The runway you start with is "R1".
• Clearing order. Emergencies are served before landings, and landings before takeoffs. Within a kind, flights are served first come first served, meaning in the order their request (or position within a request_batch) was received, not alphabetically and not by ts.
• drain calls clear_next repeatedly, all at the drain's own ts, until nobody is waiting (or no runway can take the next flight, see Part 3). It returns {"cleared": n, "last_start": s, "checksum": c}: how many flights were cleared, the start of the last one (null if none), and a checksum that is the running zlib.crc32 over the ASCII text "<flight_id>:<runway_id>:<start>" of each clearance in order (starting from 0). Two runs that clear the same flights in the same order always produce the same checksum.

Worked example

[["request", 0, "AA10", "takeoff"],
 ["request", 1, "UA22", "landing"],
 ["request", 2, "MED1", "emergency"],
 ["request", 3, "DL5", "takeoff"],
 ["queue", 4],
 ["clear_next", 5],
 ["clear_next", 6],
 ["cancel", 7, "AA10"],
 ["clear_next", 8],
 ["clear_next", 9]]

returns

[true, true, true, true, ["MED1", "UA22", "AA10", "DL5"],
 ["MED1", "R1", 5], ["UA22", "R1", 6], true, ["DL5", "R1", 8], null]

Part 1 — Fix the clearing order (ATC-871, ATC-880)

Goal: the controller clears flights in the documented order.

Reports:

1. "An emergency landing sat in the line while routine takeoffs were cleared ahead of it."
2. "Two takeoffs requested in the order B7 then A3 were cleared as A3 first."

Rules: the clearing order in the section above is the contract: emergencies, then landings, then takeoffs, and first come first served within each kind. queue and clear_next must agree.

Part 2 — Minimum separation (ATC-902)

Goal: a runway can only be used again after the required gap.

set_separation configures a gap in seconds for a (previous kind, next kind) pair, e.g. ["set_separation", 0, "takeoff", "takeoff", 90]. Unset pairs have a gap of 0, so until separations are configured everything behaves exactly as in Part 1.

Rules

1. previous_kind and next_kind must be valid kinds (invalid kind, previous checked first); seconds must be an integer >= 0 (booleans are not integers) or the call returns invalid seconds. Setting a pair again replaces its value. The pair is directional: landing -> takeoff is configured separately from takeoff -> landing.
2. Each runway remembers the start time and kind of the last flight cleared on it. A new flight of kind k cleared by clear_next at ts starts at max(ts, last_start + gap(last_kind, k)). The gap is measured from the previous flight's start to this flight's start, and a start exactly at last_start + gap is allowed. A runway that has not been used yet imposes no delay.
3. Emergencies are never delayed: an emergency starts at ts. It still counts as the runway's last flight afterwards, so the next flight is spaced from the emergency's start.
4. The clearing order (Part 1) does not change; only start does. start may be later than ts. drain uses its own ts for every flight, so the starts it produces are spaced out.

Example

[["set_separation", 0, "takeoff", "takeoff", 90],
 ["set_separation", 0, "landing", "takeoff", 60],
 ["set_separation", 0, "takeoff", "emergency", 120],
 ["request", 1, "T1", "takeoff"],
 ["request", 1, "T2", "takeoff"],
 ["request", 1, "L1", "landing"],
 ["clear_next", 10],
 ["clear_next", 20],
 ["clear_next", 30],
 ["request", 161, "E1", "emergency"],
 ["clear_next", 162]]

returns [true, true, true, true, true, true, ["L1","R1",10], ["T1","R1",70], ["T2","R1",160], true, ["E1","R1",162]]. L1 goes first (landing before takeoff). T1 follows a landing, so it waits until 10 + 60. T2 follows a takeoff, so it waits until 70 + 90. E1 ignores the 120-second gap.

Part 3 — Multiple runways and wind closures (ATC-934)

Goal: the airport can have several runways, and strong wind closes some of them.

runway_status, add_runway and set_wind are the new operations. The airport still starts with only "R1" (heading 90) and calm wind, so Parts 1 and 2 are unchanged until you use them.

Rules

1. add_runway takes a non-empty string id and a heading that is an integer from 0 to 359 (otherwise invalid heading); an id that already exists (including "R1") returns runway exists.
2. set_wind takes direction (the integer degrees the wind blows from, 0 to 359) and speed (integer knots >= 0), otherwise invalid wind. It replaces the previous wind and stays in force until changed. The initial wind is speed 0.
3. A runway is closed when speed > 25, or when speed > 12 and the wind is more than 60 degrees off the runway's axis. The runway can be used in either direction, so the off-axis angle is gap = abs(direction - heading) % 180, then min(gap, 180 - gap). It is a value from 0 to 90; exactly 60 is not "more than 60". Heading 350 and wind 10 are 20 degrees apart, not 340.
4. clear_next takes the next flight in clearing order and chooses among the open runways the one where it can start soonest (Part 2's rule applied per runway, each runway with its own last flight); ties go to the runway with the smaller id (plain string comparison). If the line is empty it returns null first; otherwise, if every runway is closed, it returns no open runway and the flight stays in line.
5. drain stops, without error, as soon as no open runway is available; it reports what it cleared.
6. runway_status lists [id, "open" | "closed"] for each runway, sorted by id.

Example

[["add_runway", 0, "R2", 0],
 ["runway_status", 0],
 ["set_wind", 1, 0, 20],
 ["runway_status", 1],
 ["set_separation", 1, "takeoff", "takeoff", 60],
 ["request", 2, "A1", "takeoff"],
 ["request", 2, "A2", "takeoff"],
 ["clear_next", 3],
 ["clear_next", 4],
 ["set_wind", 5, 0, 30],
 ["request", 6, "A3", "takeoff"],
 ["clear_next", 7],
 ["set_wind", 8, 90, 5],
 ["clear_next", 9]]

returns

[true, [["R1","open"],["R2","open"]], true, [["R1","closed"],["R2","open"]], true, true, true,
 ["A1","R2",3], ["A2","R2",63], true, true, "error: no open runway", true, ["A3","R1",9]]

A wind from 0 at 20 knots is 90 degrees off R1's axis, so R1 is closed while R2 (heading 0) stays open. At 30 knots both close. Back in calm wind, R1 can start A3 at 9 while R2 would have to wait until 63 + 60.

Part 4 — The daily timetable (stretch)

Goal: request_batch followed by drain must stay fast with thousands of flights.

Airline schedules are imported in bulk. A hidden test imports thousands of flights (with a mix of kinds), cancels some of them, configures separations, runs several runways with wind changes, and drains the whole line. The output must be identical to the straightforward implementation (the same clearings in the same order, hence the same checksum), but each run has a time limit of a few seconds. queue with a small limit is also used on large lines.

Notes

• models.py, config.py and api.py are known-good. FlightQueue and the way Scheduler uses it is where the performance work belongs.
• You may use the AI assistant freely. Later parts must not break earlier ones.
• Parts 1-3 are a strong result; Part 4 is a stretch.