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