The Totem Road of the Quillfang Steppe
Commission of the Quillfang Shamans' Lodge
Across the Quillfang Steppe runs the Totem Road: a single line of carved spirit-totems standing one after another. Each totem holds a measure of spirit-power, always a positive whole number. A war-band riding out against the Howling Things needs a ward, and a ward is raised by binding a contiguous run of totems with one cord. The ward holds if the total power of the bound totems is at least the strength required. A longer cord takes longer to tie, so the Lodge wants the shortest run that will do.
Write shortestBinding(powers, target).
powersis a list of positive integers (each at least 1), the power of each totem in road order. It may be empty.targetis a positive integer, the strength the ward needs.
Return an integer: the smallest number of consecutive totems whose powers sum to a value greater than or equal to target. If no contiguous run reaches target (including when powers is empty), return 0.
examples
- case 1
powers of [2, 3, 1, 2, 4, 3], target of 72 (the run 4, 3 sums to 7, which counts) - case 2
powers of [1, 2, 3, 4, 5], target of 155 (only the whole road reaches 15) - case 3
powers of [1, 1, 1, 1, 1], target of 110 (even the whole road sums to only 5)
- reward
- 320 XP
- signature
shortestBinding
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- classic road
- single totem suffices
- never enough power
- empty road
- whole road exactly
- pair in the middle
- lone strong totem
- three at the tail
- all equal totems
- single totem road short
- exact single among many