Last active
April 14, 2017 18:02
-
-
Save smcl/d8a519189155586f4ef72d324b209e41 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(* | |
Problem 31 - Coin sums | |
---------------------- | |
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? | |
*) | |
let targetAmount = 200 | |
let coins = [ 200; 100; 50; 20; 10; 5; 2; 1 ] | |
let rec coinCombs coin target = | |
if target < 0 then 0 | |
elif target = 0 then 1 | |
else | |
coins | |
|> List.filter (fun c -> c <= coin && (target-c) >= 0) | |
|> List.map (fun c -> coinCombs c (target-c)) | |
|> List.sum | |
coins | |
|> List.map (fun coin -> coinCombs coin (targetAmount-coin)) | |
|> List.sum |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment