‹ back to the board

Friday, October 16

Adeptalgorithms & data structures

The Ley-Stones of Corvallan Moor

Across Corvallan Moor runs a single straight line of standing stones, and every stone holds a charge of old power. Most hum with a positive charge, some are dead at zero, and a few are soured and carry a negative charge. The Circle of Corvallan pays a bounty for a full survey of the line. They want to know every place a binding rite could be worked.

A rite is worked on a contiguous stretch of one or more neighbouring stones. It holds only if the charges of the stones in that stretch add up to exactly the target strength. Two stretches count as different if they start or end at a different stone, even when they have the same total.

Write countRuns(charges, target).

  • charges is a list of integers in the order the stones stand along the line. It may be empty, and its values may be negative, zero or positive.
  • target is an integer, and it may be negative, zero or positive.

Return the number of index pairs (i, j) with 0 <= i <= j < len(charges) such that the sum of charges[i] through charges[j], inclusive, equals target. The result is a non-negative integer. An empty stretch never counts.

  • hash-map counting
  • Adept

examples

  1. case 1charges of [1, 1, 1], target of 22 (stones 0-1 and stones 1-2)
  2. case 2charges of [0, 0, 0], target of 06 (three single stones, two pairs, and the whole line)
  3. case 3charges of [3, -1, -2, 4, -4, 2], target of 04 (stones 0-2, 3-4, 0-4 and 2-5)
  4. case 4charges of [] (no stones), target of 00
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 target two
  • empty line
  • all dead stones target zero
  • mixed charges target zero
  • single stone matches
  • single stone misses
  • alternating signs
  • rising line
  • negative target
The Ley-Stones of Corvallan Moor · bitwick