Adeptalgorithms & data structures
The Beacon Towers of Greyridge
The wardens of Greyridge keep a line of beacon towers along the spine of the mountains, running from west to east. When a tower's fire is lit, its signal is caught by the nearest tower to its east that stands strictly taller than it. A tower of equal or lesser height cannot see over the ridge to catch it. The Wardens' Guild of Bitwick posts a bounty for a full chart of how far each signal must travel.
Write beaconReach(heights).
heightsis a list of integers.heights[i]is the height of the tower at positioni, and position 0 is the westernmost tower. The list may be empty.- Return a list of integers of the same length. Entry
iisj - i, wherejis the smallest index greater thanisuch thatheights[j] > heights[i]. If no such tower exists, entryiis0.
examples
- case 1
heights [3, 1, 4, 1, 5][2, 1, 2, 1, 0] - case 2
heights [2, 2, 3][2, 1, 0], because the second tower is only as tall as the first, so the first tower's signal travels on to the tower of height 3 - case 3
heights [] (an empty ridge)[]
- reward
- 320 XP
- signature
beaconReach
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
loading the editor…
- mixed ridge
- empty ridge
- single tower
- all equal heights
- strictly decreasing
- strictly increasing
- equal neighbour skipped
- long varied ridge
- valley then peak