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).
stonesis a list of strings: the sigil on each stone of the causeway, in order from one end to the other. It may be empty.neededis 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 ofneededdoes 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
neededis empty, return0. - If no stretch of the causeway satisfies the binding, return
-1.
examples
- case 1
stones 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 - case 2
stones of ["fire", "salt", "moon", "fire", "iron", "moon", "salt"], needed of ["moon", "salt"]2 - the stones salt, moon at positions 1 and 2 - case 3
stones of ["iron", "iron"], needed of ["iron", "iron", "iron"]-1 - the causeway has only two iron stones - case 4
stones of ["salt"], needed of []0
- reward
- 320 XP
- signature
shortestStretch
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- 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