The Sun-Mirrors of Kesh Varrun
East of Bitwick the caravan road crosses the Kesh Varrun salt-waste. The road is marked by a single straight line of stone obelisks, each crowned with a polished sun-mirror. The Caravan Wardens of Kesh Varrun pay a bounty for a full survey of which mirrors can flash signals to which.
A mirror on one obelisk can signal a mirror on an obelisk further east only if every obelisk standing strictly between them is strictly shorter than both of them. Two neighbouring obelisks, with nothing between them, can always signal each other.
Write countSightlines(heights).
heightsis a list of positive integers giving the obelisk heights in order from west to east. It may be empty, and heights may repeat.- Return a list of integers with the same length as
heights. Elementiis the number of indicesj > ifor which every indexkwithi < k < jsatisfiesheights[k] < min(heights[i], heights[j]).
Only obelisks to the east are counted, so the last element is always 0. An empty heights returns an empty list.
examples
- case 1
heights of [5, 2, 3, 2, 6][3, 1, 2, 1, 0]. The first obelisk (height 5) reaches the 2, the 3 and the 6, but not the second 2, because the 3 stands between them. - case 2
heights of [4, 4, 4][1, 1, 0]. Each obelisk reaches only its neighbour, because an equal height in between blocks the signal.
- reward
- 320 XP
- signature
countSightlines
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- worked example
- all equal heights
- empty road
- single obelisk
- strictly increasing
- mixed heights
- equal pair blocks between tall ends
- repeated height after a dip
- alternating peaks