The Vine-Bridge of Quessary Ravine
The Ruthwen Salt Company must move a caravan of porters and pack-beasts across Quessary Ravine. The only crossing is a living vine-bridge, one plank wide. The Wardens of the span allow only so much weight on the vines at once, and only so many bodies. Nobody can pass anyone else on the planks. The Company will pay whoever can tell them, before they set out, the minute the last of the caravan reaches the far side.
Write lastOffBridge(weights, times, limit, cap).
Arguments - weights: a list of positive integers. weights[i] is the weight of traveler i. Travelers are listed in queue order. - times: a list of positive integers, the same length as weights. times[i] is the number of minutes traveler i needs to cross when nothing blocks them. - limit: a positive integer, the most total weight allowed on the bridge at any minute. - cap: a positive integer, the most travelers allowed on the bridge at any minute.
Rules - Time is measured in whole minutes, starting at minute 0. - Travelers step onto the bridge strictly in queue order, and at most one steps on per minute. - Traveler 0 may step on at minute 0 at the earliest. Traveler i > 0 may step on no earlier than one minute after the minute traveler i-1 stepped on. - Suppose traveler i steps on at minute s. Their arrival minute is the larger of s + times[i] and the arrival minute of traveler i-1. Traveler 0's arrival minute is simply s + times[0]. - A traveler is on the bridge from the minute they step on until the minute before their arrival minute. At their arrival minute they are off the bridge. - Each traveler steps on at the earliest allowed minute m at which both limits hold. Count the travelers on the bridge at minute m, plus the newcomer. Their total weight must be at most limit, and their number must be at most cap.
Return the arrival minute of the last traveler, as an integer. - If the caravan is empty, return 0. - If any single traveler weighs more than limit, return -1.
examples
- case 1
weights [3, 4, 2], times [5, 2, 2], limit 7, cap 27. Traveler 0 steps on at minute 0 and arrives at 5. Traveler 1 steps on at 1 (weight 7, fits) and would finish at 3, but cannot pass traveler 0, so arrives at 5. Traveler 2 must wait for room: both leave at 5, so traveler 2 steps on at 5 and arrives at 7. - case 2
weights [6, 6], times [2, 1], limit 10, cap 23. Traveler 1 cannot join at minute 1 (weight 12). Traveler 0 is off the bridge at minute 2, so traveler 1 steps on at 2 and arrives at 3. - case 3
weights [], times [], limit 10, cap 30 - case 4
weights [2, 9, 1], times [1, 1, 1], limit 8, cap 3-1, because one traveler is heavier than the bridge allows
- reward
- 540 XP
- signature
lastOffBridge
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- empty caravan
- single traveler at exact limit
- one traveler too heavy
- worked example with no passing
- no limits bind, one per minute
- cap of one
- weight limit binds
- slow leader holds everyone
- count and weight both at boundary
- departure frees room same minute
- one departure not enough, wait for next
- partial departure lets newcomer in