The Ferryman's Smallest Barge
The barrels of the autumn pressing stand on the Bitwick dock in one long line, and the ferryman will not rearrange them. He loads from the front of the line onward, never skipping and never reordering, so every crossing carries a block of consecutive barrels, and each barrel crosses exactly once. He will make at most `trips` crossings, and no crossing may carry more total weight than the barge's capacity.
The shipwright charges by capacity, so the ferryman wants the smallest barge that can still do the work.
Write ferryCapacity(weights, trips).
weightsis a non-empty list of positive integers: the weight of each barrel, in line order.tripsis a positive integer: the greatest number of crossings allowed.
Return an integer: the smallest capacity such that the whole line can be carried, front to back in consecutive blocks, in at most trips crossings.
examples
- case 1
weights of [7, 2, 5, 10, 8], trips of 218 — the line splits into [7, 2, 5] (14) and [10, 8] (18); every other split of the line into two blocks has a heavier block - case 2
weights of [3, 1, 4, 1, 5], trips of 95 — with more crossings available than barrels, each barrel can go alone, so the capacity need only match the heaviest barrel - case 3
weights of [7], trips of 17
- reward
- 350 XP
- signature
ferryCapacity
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- single barrel
- one crossing takes everything
- more crossings than barrels
- two crossings, five barrels
- three crossings, rising weights
- equal barrels, four crossings
- long dock, two crossings
- long dock, three crossings