The Star-Scale of Calderhorn
High on Calderhorn, above the snowline, the vault of the vanished Astrarch is sealed by a great bronze Star-Scale. The seal releases only when its pan holds star-iron counterweights whose masses add up to exactly the seal's mark. Any other total leaves the vault shut.
The Lodestar Foundry in Bitwick casts counterweights in a fixed set of sizes. It can cast as many of each size as you ask for. Every weight must be hauled up the mountain by hand, so the expedition wants to carry as few as possible.
Write fewestWeights(weights, target).
weightsis a list of positive integers, the masses the Foundry can cast. The list may be empty, may contain repeated values, and may contain masses larger thantarget.targetis a non-negative integer, the seal's mark. It is at most 10000.
The function returns an integer: the smallest number of counterweights whose masses sum to exactly target. Any size may be used any number of times, including not at all.
- If
targetis 0, return 0. - If no combination of the available sizes sums to exactly
target, return -1.
examples
- case 1
weights of [1, 3, 4], target of 62 (two weights of 3; taking the 4 first would need three weights: 4 + 1 + 1) - case 2
weights of [4, 6], target of 7-1 (no combination of 4s and 6s makes 7) - case 3
weights of [5, 7], target of 00 (an empty pan already reads 0)
- reward
- 320 XP
- signature
fewestWeights
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- heaviest-first trap
- target zero
- impossible total
- no sizes at all
- single size exact multiple
- single size odd miss
- mixed sizes to one hundred
- duplicates and oversized
- coin-like sizes
- large awkward total