The Wormway Under Hagsback Tor
Long ago a great worm bored a passage straight through Hagsback Tor. The Pathwardens now keep that passage, the Wormway, as the only road between the Westmarch and the Eastmarch. It is too narrow for two travellers to pass each other, so the Pathwardens run it by strict rules. They offer a bounty for a reckoning of the tick at which each traveller in a party will emerge on the far side.
Write wormwayExits(travellers, length, cap, k).
Arguments - travellers: a list of [arrival, side] pairs. arrival is a non-negative integer, the tick at which that traveller reaches a mouth of the Wormway. side is the string "W" (the west mouth) or "E" (the east mouth). A traveller always enters by the mouth they arrived at. - length: a positive integer. A traveller who enters at tick t exits at tick t + length. - cap: a positive integer, the most travellers that may be inside the Wormway at once. - k: a positive integer, the crossing limit described below.
Rules
Time moves in whole ticks. At every tick the following happens, in this order:
1. Every traveller whose exit tick equals this tick leaves the Wormway. 2. Every traveller whose arrival tick equals this tick joins the queue at their mouth. Each mouth's queue is ordered by arrival tick. Ties are broken by position in travellers, earlier first. 3. At most one traveller enters the Wormway. It is always the front traveller of one queue, chosen as follows.
*If the Wormway is empty* after step 1: - If exactly one queue is non-empty, its front traveller enters. - If both queues are non-empty, the front traveller of the mouth opposite to the one used by the most recent traveller to enter goes in. If nobody has entered yet, the west mouth goes. - This entry begins a new crossing.
*If the Wormway is not empty*, everyone inside entered from the same mouth. Only the front traveller of that mouth's queue may enter. They enter only if both of these hold: - fewer than cap travellers are inside; - either the other mouth's queue is empty, or fewer than k travellers have entered during the current crossing, counting the one who began it.
A crossing lasts until the Wormway is empty after step 1.
If none of these cases admits anyone, nobody enters this tick.
Return a list of integers giving the exit tick of each traveller, in the same order as travellers. An empty travellers gives an empty list.
examples
- case 1
travellers [[0,"W"],[0,"W"],[0,"W"],[1,"E"]], length 3, cap 2, k 2[3, 4, 10, 7]. Two westerners fill the crossing. The third is then held back, because two have already entered and someone waits at the east mouth. When the Wormway empties at tick 4 the east mouth goes, and the last westerner enters at tick 7. - case 2
travellers [[0,"W"],[1,"W"],[1,"E"]], length 1, cap 5, k 1[1, 3, 2]. At tick 1 the first traveller leaves before anyone enters, so the Wormway is empty. Both mouths wait, and the east goes because the last entrant came from the west. - case 3
travellers [[0,"W"],[0,"W"],[0,"W"]], length 2, cap 3, k 1[2, 3, 4]. Nobody waits at the east mouth, so the limit k never stops anyone.
- reward
- 540 XP
- signature
wormwayExits
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- crossing limit hands the road to the east
- empty party
- lone traveller
- limit ignored when other mouth is empty
- exit and entry on the same tick
- west goes first when nobody has entered
- capacity and arrival tie-break
- mixed party over several crossings
- single file alternates mouths
- new crossing flips the mouth
- long gap between arrivals