### The Problem

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?

### The Solution

In retrospect, this is not some of my best work. But it gets the job done.

Since this is a problem of combinations, I figured the first step was to generate all the things that could be combined to get the answer.

``````[<Literal>]
let target = 200

let coins = [1; 2; 5; 10; 20; 50; 100; 200]
let combos =
coins
|> List.map (fun x -> [for i in 0..(target / x) -> (i,x)])
``````

The above declares a list of coins and from that creates all lists of coin combinations. `combos` is a list of lists of tuples. Each tuple is the number of coins and the coin value. We only consider combinations up to `target/x` because, obviously, any solutions containing those combinations would be wrong.

Now, a few helper functions:

``````let coinValue (a,b) = a * b

let sumPile (pile : List<int * int>) =
pile
|> List.sumBy coinValue

let matchTarget pile =
sumPile pile = target
``````

`coinValue` takes a tuple and multiplies the numbers together to get the value of that combination of coins.

`sumPile` takes a pile of coins and gets the total value.

`matchTarget` tells us whether or not a pile of coins matches our target of 200.

So, now we need a function to combine the combinations of coins. This gets a little bit tricky.

``````let combine() =
let rec combineRec prefix prefixSum suffixes =
seq {
if prefixSum >= target then
yield prefix
else
match suffixes with
| [] -> yield prefix
| x::xs ->
for c in x do
yield! combineRec (c::prefix) (prefixSum + coinValue c) xs
}

combineRec [] 0 combos
``````

The `combineRec` function takes a `prefix` (some combination of coins) and a list of possible `suffixes` (other combinations of coins we haven't considered). It combines the prefix with all possible suffixes and looks at the value. If it's greater than or equal to our target, it returns that combination. Otherwise, it keeps generating more combinations. Eventually, we get lots and lots of combinations, and all the ones that match our target are in there somewhere.

``````#time
combine()
|> Seq.filter matchTarget
|> Seq.length
#time
``````

The above simply generates all the combinations, filters out those that don't match the target, and finds the length of the sequence. That's the answer.

This takes about 42 seconds to run on my machine. I wasn't really happy with that, so only then did I set about investigating if there was a better way to solve the problem.

As it turns out, there is a well-known algorithm for this called the Coin Change Algorithm.

Because of course there is. Darn it. Here is the very simple implementation of that algorithm that runs in about half a second.

``````let coinsArray = [| 1; 2; 5; 10; 20; 50; 100; 200 |]
let rec coinChange n m =
if n = 0 then 1
elif n < 0 then 0
elif m <= 0 && n >= 1 then 0
else (coinChange n (m - 1)) +
(coinChange (n - coinsArray.[m-1]) m)

#time
coinChange target coins.Length
#time
``````
Other Posts in This Series