The Storm-Glass Chain of Harrowick Tor
On the summit of Harrowick Tor hangs a long iron chain strung with storm-glasses. Each glass has drunk lightning from a hundred squalls and still holds a charge, counted in sparks. The Conclave of Lantern-Wrights will pay a bounty to whoever can tell their warlock how to cut the chain. The warlock must cut free one unbroken run of consecutive glasses whose combined charge is enough to wake the beacon on Brannoch Head. The shorter the run, the less of the chain is lost.
Write shortestCharge(charges, need).
chargesis a list of integers, each at least 1. It holds the spark count of every glass in chain order. It may be empty.needis an integer, at least 1. It is the number of sparks the beacon requires.
A run is any non-empty contiguous slice of charges. Its total is the sum of its elements. A run is sufficient when its total is greater than or equal to need.
Return an integer: the length (number of glasses) of the shortest sufficient run. If no run is sufficient, which includes the case where charges is empty, return 0.
examples
- case 1
charges of [2, 3, 1, 2, 4, 3], need of 72 (the run [4, 3] totals exactly 7) - case 2
charges of [1, 1, 1, 1], need of 100 (the whole chain holds only 4 sparks) - case 3
charges of [1, 4, 4], need of 41 (a single glass of 4 is already enough)
- reward
- 320 XP
- signature
shortestCharge
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- classic chain
- never enough
- empty chain
- single glass exact
- one glass suffices mid-chain
- run at the tail
- heavy ends light middle
- whole chain needed
- single glass too weak