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).
chargesis 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.targetis 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.
examples
- case 1
charges of [1, 1, 1], target of 22 (stones 0-1 and stones 1-2) - case 2
charges of [0, 0, 0], target of 06 (three single stones, two pairs, and the whole line) - case 3
charges of [3, -1, -2, 4, -4, 2], target of 04 (stones 0-2, 3-4, 0-4 and 2-5) - case 4
charges of [] (no stones), target of 00
- reward
- 320 XP
- signature
countRuns
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- 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