The Winding-Cage of Deepshaft
The winding-cage of Deepshaft carries miners between the shaft's levels, numbered from 0 at the bottom upward. The winder keeps a tally of the order in which miners are set down, and wants that tally worked out before the shift begins.
riders is a list of pairs [from, to] of non-negative integers with from != to. The rider at index i waits at level from from the moment the shift begins and wants to be set down at level to. A rider travels up if to > from, and down if to < from.
cap is an integer, at least 1: the most riders the cage may hold at once.
The cage starts empty at level 0 with its direction set to up. Then, repeatedly, at its current level and in exactly this order:
1. every rider in the cage whose destination is the current level steps out, lowest rider index first, and is appended to the tally as they step out; 2. then every rider still waiting at the current level whose travel direction equals the cage's direction steps in, lowest rider index first, stopping as soon as the cage holds cap riders; 3. if every rider has been set down, the cage stops; 4. otherwise, if some rider in the cage has a destination strictly beyond the current level in the cage's direction, or some rider still waiting has an origin strictly beyond the current level in the cage's direction, the cage travels one level in its direction; if neither holds, the cage reverses its direction and does not move. Either way, the sequence begins again at step 1.
"Strictly beyond in direction up" means a greater level number; "strictly beyond in direction down" means a smaller one. A rider counts as *waiting* until they step in, and as *in the cage* until they step out.
cageOrder(riders, cap) returns the tally: a list of rider indices, in the order they stepped out. With no riders, the tally is empty.
examples
- case 1
riders of [[0, 4], [1, 2]], cap of 1[0, 1] - the cage takes rider 0 at level 0 and is full when it passes level 1, so rider 1 is left standing. Rider 0 is set down at level 4; nothing lies above, so the cage turns and runs down to level 1, where rider 1 travels up and so does not step in. Nothing lies below, so the cage turns again where it stands, rider 1 steps in, and is set down at level 2. - case 2
riders of [[2, 3], [1, 3], [0, 3]], cap of 3[0, 1, 2] - rider 2 steps in first, then rider 1, then rider 0, but all three step out at level 3 in rider-index order. - case 3
riders of [[2, 0], [0, 2]], cap of 2[1, 0]
- reward
- 530 XP
- signature
cageOrder
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- an empty shift
- a lone miner travelling down
- a full cage passes a waiting miner
- stepping out follows rider number
- capacity leaves one for a second sweep
- two riders crossing
- mixed traffic in both directions
- all bound for the sump