coin sums
(This one is from Project Euler).
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins? Can you make a lazy sequence of these ways?
| (defn count-change | |
| ([amount] | |
| (count-change amount 8)) | |
| ([amount kinds-of-coins] | |
| (let [coins [1, 2, 5, 10, 20, 50, 100, 200]] | |
| (cond (= amount 0) 1 | |
| (< amount 0) 0 | |
| (= kinds-of-coins 0) 0 | |
| :else (+ (count-change amount (- kinds-of-coins 1)) | |
| (count-change (- amount (nth coins (dec kinds-of-coins))) kinds-of-coins)))))) | |
| (defn problem-31 [] | |
| (count-change 200)) |
| (def denoms [1 2 5 10 20 50 100 200]) | |
| (defn coin-sums [target] | |
| (for [p1 (range 201) | |
| p2 (range 101) | |
| p5 (range 41) | |
| p10 (range 21) | |
| p20 (range 11) | |
| p50 (range 5) | |
| p100 (range 3) | |
| p200 (range 2) | |
| :let [vals [p1 p2 p5 p10 p20 p50 p100 p200]] | |
| :when (= target (apply + (map * vals denoms)))] | |
| vals)) | |
| (coin-sums 200) ;; never returns | |
| (defn coin-sums [target coins denominations] | |
| (let [s (:sum coins 0)] | |
| (cond | |
| (> s target) | |
| nil | |
| (= s target) | |
| [coins] | |
| (empty? denominations) | |
| nil | |
| :else | |
| (lazy-cat | |
| ;; coin sums with one more of max coin | |
| (let [c (first denominations)] | |
| (coin-sums target (-> coins | |
| (update c (fnil + 0) 1) | |
| (update :sum (fnil + 0) c)) | |
| denominations)) | |
| ;; coin sums without max coin | |
| (coin-sums target coins (rest denominations)))))) | |
| (coin-sums 200 {} (reverse (sort denoms))) |
| (defn ways-of-changing | |
| "Computes all the ways to change `amount-pence` using the allowed coins (expressed as a seq of numbers, in pence). | |
| Returns a lazy sequence of maps representing bags of coins, which keys are the coin amounts, and values are the numbers of coins used." | |
| ([amount-pence] | |
| (ways-of-changing [1 2 5 10 20 50 100 200] amount-pence)) | |
| ([allowed-coins amount-pence] | |
| (letfn [(aux [allowed-coins-vec amount-pence] | |
| (cond | |
| (neg? amount-pence) [] | |
| (zero? amount-pence) [{}] | |
| (empty? allowed-coins-vec) [] | |
| :else | |
| ;; Algorithm: we partition all the ways by their highest coin, and recur | |
| (->> allowed-coins-vec | |
| (mapcat | |
| (fn [i max-coin] | |
| (->> (aux | |
| (subvec allowed-coins-vec 0 (inc i)) | |
| (- amount-pence max-coin)) | |
| (map | |
| (fn [change-bag] | |
| (update change-bag | |
| max-coin | |
| #(-> % (or 0) inc)))))) | |
| (range)))))] | |
| (aux | |
| (->> allowed-coins sort dedupe vec) | |
| amount-pence)))) |