‹ back to the board

Tuesday, November 3

Adeptalgorithms & data structures

The Sigil-Causeway of Vel Orrimar

Across the salt flats of Vel Orrimar runs an old causeway of carved stones, each bearing one sigil. The Orrimar Wardens pay well for a binding: a warden must stand on an unbroken stretch of the causeway whose stones together carry every sigil the binding calls for. The Wardens want the shortest stretch that will serve, so the warden's circle can be drawn as small as possible.

Write shortestStretch(stones, needed).

  • stones is a list of strings: the sigil on each stone of the causeway, in order from one end to the other. It may be empty.
  • needed is a list of strings: the sigils the binding requires. It may contain the same sigil more than once. Each occurrence must be matched by a different stone, so needing "fire" twice requires two stones bearing "fire". The order of needed does not matter.

Sigils are compared exactly, as strings.

Return an integer: the length (number of stones) of the shortest contiguous stretch of stones that contains every sigil in needed, with multiplicity. A stretch may contain extra stones beyond those needed.

  • If needed is empty, return 0.
  • If no stretch of the causeway satisfies the binding, return -1.
  • two pointers and sliding windows
  • Adept

examples

  1. case 1stones of ["moon", "fire", "moon", "salt", "fire", "fire", "moon"], needed of ["fire", "fire", "moon"]3 - the last three stones (fire, fire, moon); no shorter stretch holds two fire stones and a moon stone
  2. case 2stones of ["fire", "salt", "moon", "fire", "iron", "moon", "salt"], needed of ["moon", "salt"]2 - the stones salt, moon at positions 1 and 2
  3. case 3stones of ["iron", "iron"], needed of ["iron", "iron", "iron"]-1 - the causeway has only two iron stones
  4. case 4stones of ["salt"], needed of []0
reward
320 XP
signature
shortestStretch
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…
  • two distinct sigils side by side
  • repeated sigil needs distinct stones
  • not enough copies on the causeway
  • empty needed
  • empty causeway
  • single stone match
  • whole causeway required
  • needed sigil absent
  • best stretch near the end
  • extra stones inside the stretch
  • three distinct with repeats around
The Sigil-Causeway of Vel Orrimar · bitwick