The Tithe-Barn Tally
The tithe-barn at the edge of bitwick accepts grain only in sealed sacks, and the barn stocks a fixed set of sack sizes, each available in unlimited number. A tithe is settled when the sacks handed over add up to exactly the amount owed — no more, no less. The reeve wants to know, before the carts arrive, how many different deliveries would settle a given tithe.
Write titheWays(amount, sizes):
amount— a non-negative integer, the grain owed. It may be0.sizes— a list of distinct positive integers, the sack sizes the barn stocks, in no particular order. It may be empty.
Return an integer: the number of distinct deliveries whose sack sizes sum to exactly amount. Two deliveries are the same delivery when they use the same number of sacks of each size; the order the sacks are handed over does not distinguish them. The delivery of no sacks at all sums to 0.
examples
- case 1
amount of 5, sizes of [1, 2, 5]4 — the deliveries are 5; 2+2+1; 2+1+1+1; 1+1+1+1+1 - case 2
amount of 4, sizes of [1, 3]2 — namely 1+1+1+1 and 3+1. A 3 then a 1 is the same delivery as a 1 then a 3. - case 3
amount of 0, sizes of [4, 7]1 — handing over nothing settles a tithe of nothing - case 4
amount of 7, sizes of [2, 4]0 — no collection of 2s and 4s sums to 7
- reward
- 320 XP
- signature
titheWays
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- five in ones, twos and fives
- nothing owed
- no sack fits
- order is not a delivery
- a single stocked size
- single size that does not divide
- the barn stocks nothing
- sizes listed in any order
- thirty in twos, threes and sevens
- the reeve's full board