The Cairn Line of the Windcaller Peaks
Commission of the Skyward Surveyors' Company, posted at Bitwick
An expedition means to cross the Windcaller Peaks along the old ridge road. Along that road stand stone cairns, one after another, and the Company's scouts have recorded the altitude carved on each, in order from the eastern foot of the ridge to the western end.
The expedition will make camp on a single unbroken run of consecutive cairns. That run must be as long as possible. Its highest altitude minus its lowest altitude must not exceed a given limit. The Company pays for the length of the longest such run.
The contract, plainly:
Write longestCairnRun(heights, limit).
heightsis a list of integers, the altitudes of the cairns in road order. Values may be negative or repeated. The list may be empty.limitis a non-negative integer.
Return an integer: the greatest length of a contiguous run of heights in which the maximum value minus the minimum value is at most limit. A single cairn always qualifies, because its spread is zero. If heights is empty, return 0.
examples
- case 1
heights of [3, 8, 6, 5, 9, 4], limit of 33: the run 8, 6, 5 has a spread of exactly 3. Every longer run spreads 4 or more. - case 2
heights of [4, 4, 4, 2, 4, 4], limit of 03: with a limit of 0, only equal altitudes may share a run, and the 2 breaks the line. - case 3
heights of [], limit of 50: there are no cairns, so there is no run.
- reward
- 320 XP
- signature
longestCairnRun
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- mixed ridge with a spread of exactly the limit
- empty road
- single cairn with zero limit
- zero limit needs equal heights
- whole ridge fits a generous limit
- best run lies late on the road
- negative altitudes
- stale extreme must be dropped
- descending then ascending