‹ back to the board

Tuesday, October 6

Adeptalgorithms & data structures

The Ley-Stones of Vashtor Heath

Across Vashtor Heath runs a single line of standing stones, set along a ley-line older than any map. Each stone holds a charge of earth-magic, which may be positive, negative or zero. The Circle of the Heath is posting a bounty for anyone who can survey the line. A binding can be cast only across an unbroken run of neighbouring stones whose charges add up to exactly the strength the binding demands. Before they commit their casters, the Circle wants to know how many such runs the line offers.

Write countRuns(charges, k).

  • charges is a list of integers, one per stone, in their order along the line. It may be empty, and its values may be negative or zero.
  • k is an integer, the required total. It may be negative or zero.

Return an integer: the number of contiguous runs of one or more stones whose charges sum to exactly k. A run is identified by its first and last stone. Two runs with different start or end positions count separately, even if their charges look the same. A run of zero stones never counts. If charges is empty, return 0.

  • hash-map counting
  • Adept

examples

  1. case 1charges of [2, -1, 3, -2, 4], k of 43 (the runs [2, -1, 3], [-1, 3, -2, 4] and [4])
  2. case 2charges of [0, 0, 0], k of 06 (three single stones, two pairs, and the whole line)
  3. case 3charges of [], k of 50
reward
320 XP
signature
countRuns
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…
  • three ones, pairs of two
  • mixed charges with overlapping runs
  • alternating charges summing to zero
  • all zero stones with zero target
  • empty line
  • single stone matching
  • negative target
  • no run reaches the target
  • zero target with no zero run
The Ley-Stones of Vashtor Heath · bitwick