‹ back to the board

Sunday, November 1

Adeptalgorithms & data structures

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).

  • length is a positive integer: the wall runs from pace 0 to pace length, measured from the north tower.
  • wards is a list of pairs [start, end] of integers with 0 <= start < end <= length. Each pair means the ward covers the wall from pace start to pace end. 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.

  • interval merging
  • Adept

examples

  1. case 1length of 20, wards [3, 7], [0, 2], [10, 15], [6, 9][[2, 3], [9, 10], [15, 20]]
  2. case 2length of 10, wards [0, 4], [4, 10][] (the wards touch at pace 4, so there is no breach)
  3. case 3length of 12, no wards at all[[0, 12]] (the whole wall is bare)
reward
320 XP
signature
findBreaches
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • 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
The Kraken-Breaches of Ebonquay Seawall · bitwick