The Kraken-Breaches of Ebonquay Seawall
The harbour town of Ebonquay is guarded by a long seawall, and every night the warden-mages of the Tidebound Circle raise their wards along it. Each ward covers one stretch of the wall. The Kraken of the Sallow Deep circles below, feeling for any stretch the wards leave bare. The Circle pays a bounty to whoever can list every breach before the tide turns.
Write findBreaches(length, wards).
lengthis a positive integer: the wall runs from pace0to pacelength, measured from the north tower.wardsis a list of pairs[start, end]of integers with0 <= start < end <= length. Each pair means the ward covers the wall from pacestartto paceend. The list may be in any order. Wards may overlap, nest inside one another, or be exact duplicates. The list may be empty.
A breach is a maximal stretch [a, b] of the wall, with a < b, that lies within [0, length] and is not covered by any ward. Two wards that touch, with one ending at the same pace where another begins, leave no breach between them.
Return a list of every breach as [a, b] pairs of integers, sorted by a in increasing order. If the whole wall is covered, return an empty list.
examples
- case 1
length of 20, wards [3, 7], [0, 2], [10, 15], [6, 9][[2, 3], [9, 10], [15, 20]] - case 2
length of 10, wards [0, 4], [4, 10][] (the wards touch at pace 4, so there is no breach) - case 3
length of 12, no wards at all[[0, 12]] (the whole wall is bare)
- reward
- 320 XP
- signature
findBreaches
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- unordered overlapping wards
- no wards leaves whole wall bare
- touching wards leave no breach
- nested ward does not shrink reach
- single ward covers everything
- duplicates and scattered wards
- one-pace breach
- shortest wall with no wards
- long ward listed after short ones it swallows