The Dreaming Basilisk of Quorrin Deep
Contract of the Lantern Guild, posted at the inn of Bitwick
Beneath the hills lies Quorrin Deep, and in its lowest gallery sleeps a basilisk curled around the guild's lost reliquary. A party that creeps past it can reach the prize. The basilisk is not deaf, though. Every footfall stirs it a little, and when it has been stirred enough it wakes, glares, and settles back to sleep. The guild wants to know how many times a planned route will wake the beast before it sends anyone down.
Write countWakings(steps, limit).
stepsis a list of non-negative integers. Each one is the noise of one footfall, in the order the party takes them. The list may be empty.limitis a positive integer.
The basilisk's stir starts at 0. Process the footfalls in order. For each footfall:
1. If its noise is 0, the stir decreases by 1, but never below 0. Otherwise, the stir increases by the footfall's noise. 2. Then, if the stir is greater than or equal to limit, the basilisk wakes once and the stir resets to exactly 0. Any excess above limit is discarded.
Return the total number of times the basilisk wakes, as an integer.
examples
- case 1
steps of [3, 0, 0, 2, 4, 1, 5], limit of 52 (stir goes 3, 2, 1, 3, 7 → wakes and resets to 0, then 1, 6 → wakes) - case 2
steps of [0, 0, 5], limit of 51 (the quiet steps leave the stir at 0, and then 5 reaches the limit exactly) - case 3
steps of [5, 1], limit of 31 (5 wakes it and the stir resets to 0; the extra 2 is not carried over, so the final step only brings it to 1) - case 4
steps of [], limit of 40
- reward
- 220 XP
- signature
countWakings
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- worked route with two wakings
- empty route
- stir floors at zero
- steady small steps
- excess discarded on reset
- floor matters after a waking
- limit of one wakes on every noisy step
- alternating quiet keeps it asleep
- single huge step wakes once
- long quiet stretch after waking