The Cooper's Cart Queue
The cooper of bitwick rolls her finished barrels out to the yard gate one at a time, and the carter loads them onto carts in exactly the order they arrive. A cart may carry no more than limit in total weight, and no more than cap barrels however light they are.
The carter works with one cart at a time. Each barrel that arrives is added to the cart he is loading if, after adding it, that cart's total weight is still at most limit and it holds at most cap barrels. Otherwise he sends the cart he was loading on its way and starts a new cart holding only that barrel — even if that single barrel weighs more than limit by itself. When the barrels run out, the cart he is loading is sent off too, unless it is empty.
Write loadCarts(weights, limit, cap):
weightsis a list of positive integers, the barrel weights in the order they arrive.limitis a positive integer, the weight a cart may carry.capis an integer of at least 1, the number of barrels a cart may hold.
Return a list of carts in the order they were sent off, each cart a list of the barrel weights it carries, in arrival order. No cart in the result is empty. If weights is empty, return an empty list.
examples
- case 1
weights of [4, 2, 5, 1, 3], limit of 7, cap of 3[[4, 2], [5, 1], [3]] - case 2
weights of [9, 1], limit of 5, cap of 4[[9], [1]] — the 9 is too heavy for any cart, so it rides alone, and the 1 cannot join it - case 3
weights of [1, 1, 1, 1], limit of 100, cap of 2[[1, 1], [1, 1]] - case 4
weights of [], limit of 10, cap of 3[]
- reward
- 220 XP
- signature
loadCarts
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- mixed load with both rules biting
- a barrel heavier than the limit rides alone
- the barrel count is what closes the cart
- no barrels at all
- a cap of one
- one barrel exactly at the limit
- everything fits on a single cart
- a long run of arrivals
- oversize barrel in the middle