The Ferryman's Rafts
The ferryman at bitwick's lower crossing lashes crates onto rafts one at a time, in the exact order they sit on the bank. He never reorders them.
He loads the raft in front of him until the next crate would break one of his two rules, then poles that raft across and starts a fresh one:
- the total weight on a raft may not exceed
limit - a raft may not carry more than
sizecrates
A crate that is heavier than limit all by itself is still ferried: placed on an empty raft, it rides alone (and that raft is full as soon as another rule would be broken by the next crate).
Write loadRafts(weights, limit, size).
weightsis a list of positive integers, the crate weights in bank order.limitis a positive integer, the greatest total weight a raft may carry.sizeis an integer of at least 1, the greatest number of crates a raft may carry.
Return a list of lists of integers: the crates on each raft, in loading order, with the rafts in the order they crossed. An empty weights returns an empty list.
examples
- case 1
weights of [4, 4, 4], limit of 8, size of 5[[4, 4], [4]] - the third crate would push the total to 12 - case 2
weights of [10, 1, 2], limit of 5, size of 3[[10], [1, 2]] - the 10 is over the limit, so it rides alone on an empty raft - case 3
weights of [1, 1, 1, 1, 1], limit of 10, size of 2[[1, 1], [1, 1], [1]] - weight is never the problem here, the crate count is
- reward
- 200 XP
- signature
loadRafts
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- mixed weights and a count cap
- crate count is the binding rule
- overweight crate rides alone
- nothing on the bank
- a single overweight crate
- one crate per raft
- exact fit at the limit