‹ back to the board

Tuesday, November 3

Apprenticelogic & control flow

The Salamander Ferry of Kelthrace Caldera

Beyond the cinder-trail lies the lava lake of Kelthrace Caldera. The only way across is aboard the basalt rafts towed by the Ferrymaster's fire-salamanders. Each raft can bear only so much weight before it sinks into the molten rock. An expedition has formed a single line at the shore, and the Ferrymaster loads them strictly in that order.

The loading rule is fixed:

  • Members board the current raft one at a time, in line order.
  • A member joins the current raft if the raft's total weight, including that member, would be less than or equal to limit.
  • If adding the next member would push the total above limit, the current raft departs as it is. A new raft is started, and that member is its first rider.
  • Nobody ever changes place in line. A raft never skips a heavy member to take a lighter one from further back.

Write ferryLoads(weights, limit).

  • weights is a list of positive integers, one per expedition member, in line order. It may be empty.
  • limit is a positive integer, the maximum total weight a single raft may carry.
  • Every weight is guaranteed to be between 1 and limit inclusive, so every member can always ride a raft alone.

Return a list of rafts in departure order. Each raft is a list of the weights of its riders, in boarding order. If weights is empty, return an empty list.

  • grouping and partitioning
  • Apprentice

examples

  1. case 1weights of [3, 4, 2, 5, 1], limit of 7[[3, 4], [2, 5], [1]]. The first two rafts are each loaded to exactly 7, which is allowed.
  2. case 2weights of [5, 4, 1], limit of 6[[5], [4, 1]]. The 1 would fit beside the 5, but it cannot jump ahead of the 4.
  3. case 3weights of [], limit of 5[] (no one in line, so no rafts sail)
reward
210 XP
signature
ferryLoads
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • rafts filled exactly to the limit
  • empty line
  • single member at the limit
  • everyone fits on one raft
  • every member rides alone
  • no skipping ahead in line
  • mixed loads
  • heavy member mid-line
The Salamander Ferry of Kelthrace Caldera · bitwick