The Swaying Span of Thistledrop Chasm
Thistledrop Chasm is crossed by a single rope span: one plank wide, strung between two cliffs, and kept by the Wardens of the Span. Caravans of adventurers bound for the far wilds must cross it. The Wardens post this contract: reckon the exact minute each member of a waiting line reaches the far cliff, so the guides on the other side know when to expect them.
Write crossingTimes(travelers, limit).
Arguments - travelers: a list of travelers in queue order. Each traveler is a list of three integers [arrival, weight, pace]. arrival is the minute they reach the near end (arrival >= 0, and arrivals never decrease along the list). weight is their weight (1 <= weight <= limit). pace is how many minutes they need to cross an empty span (pace >= 1). The list may be empty. - limit: a positive integer, the most total weight the span may carry at any minute.
The rules of the span. Time is measured in whole minutes. Each traveler steps onto the span at one minute (their *entry*) and steps off at a later minute (their *exit*). A traveler counts as on the span at every minute m with entry <= m < exit. So a traveler who exits at minute x no longer counts toward the weight at minute x, and someone else may step on at minute x using that freed weight.
Travelers step on strictly in queue order. Traveler i's entry is the smallest integer minute t that satisfies all of these: 1. t >= arrival of traveler i; 2. t is strictly greater than the entry of traveler i - 1 (at most one traveler steps on per minute; this does not apply to the first traveler); 3. the total weight of travelers on the span at minute t, plus traveler i's weight, is at most limit.
No one may pass the traveler ahead of them on the span. Traveler i's exit is entry + pace, or the exit of traveler i - 1 if that is later. (For the first traveler, it is simply entry + pace.) A traveler held back this way stays on the span, and their weight still counts, until their exit.
Return a list of integers: the exit minute of each traveler, in queue order. An empty travelers list returns an empty list.
examples
- case 1
travelers [[0,4,5], [0,4,2], [1,5,3], [2,1,1]], limit 10[5, 5, 8, 8]. The second traveler would finish at 3 but cannot pass the first, so exits at 5. The third waits until minute 5, when both step off, then enters. The fourth enters at 6 and is held behind the third until 8. - case 2
travelers [[0,4,3], [1,4,3], [2,4,3]], limit 4[3, 6, 9]. Each traveler fills the span alone, and each steps on in the very minute the one before steps off. - case 3
travelers [], limit 5[]
- reward
- 540 XP
- signature
crossingTimes
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- worked_example
- empty_line
- single_traveler_at_limit
- one_per_minute_spacing
- no_overtaking
- late_arrival_after_gap
- partial_release_of_weight
- step_on_as_other_steps_off
- mixed_caravan
- held_weight_blocks_light_traveler