The Aether-Skiff of Corvanth Reach
Above Corvanth Reach, a chain of floating rocks called the Drift hangs in the sky, and the only way across is by aether-skiff. A skiff burns glowing aether-crystals to fly, and it can hold at most capacity crystals at once. At the start of every hop, the skiff is moored at a dock where it may take on crystals. The Skyfarers' Guild pays a bounty to whoever can tell a pilot, before launch, how many times the skiff will have to take on crystals along a given route.
The pilot follows one fixed rule:
- The skiff launches from the first dock carrying exactly
capacitycrystals. This initial load is not counted as a refill. - Before each hop, if the crystals aboard are fewer than that hop costs, the skiff refills to exactly
capacitycrystals. This counts as one refill. If the crystals aboard are enough (including exactly enough), it does not refill. - The hop's cost is then subtracted from the crystals aboard.
Write skiffRefills(capacity, hops).
capacityis a positive integer.hopsis a list of non-negative integers;hops[i]is the number of crystals burned on the i-th hop, in the order they are flown. It may be empty.
Return the number of refills the pilot makes over the whole route, as an integer. If any single hop costs more than capacity, the route cannot be flown at all; return -1 in that case.
examples
- case 1
capacity of 10, hops of [4, 5, 3, 6, 2]2 (10 → 6 → 1; refill before the 3-hop; 7 → 1; refill before the 2-hop) - case 2
capacity of 5, hops of [5, 5, 5]2 (each hop lands with exactly 0 aboard, so the second and third hops each need a refill; the first launch is not counted) - case 3
capacity of 4, hops of [2, 7, 1]-1 (the 7-crystal hop can never be flown)
- reward
- 220 XP
- signature
skiffRefills
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- mixed route with two refills
- empty route
- exact-cost hops land at zero
- impossible hop returns -1
- zero-cost hop needs no refill
- never needs a refill
- capacity one
- longer route
- impossible hop at the very end