### Coin Sums (Project Euler Problem 31)

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?

Original problem description...

Note

This is a clean, although slow, solution, taking longer than one minute to complete.

Solution

``````

// code for finding result, returned as a sequence
let sumCurrencies ones twos fives tens twenties fifties oneHundreds twoHundreds limit =
//seq{
[let counter = 0
for twoHundred in twoHundreds do
for oneHundred in oneHundreds do
for fifty in fifties do
for twenty in twenties do
for ten in tens do
for five in fives do
for two in twos do
for one in ones do
if ((one * 1) +
(two * 2) +
(five * 5) +
(ten * 10) +
(twenty * 20) +
(fifty * 50) +
(oneHundred * 100) +
(twoHundred * 200)) = limit then
yield one, two, five, ten, twenty, fifty, oneHundred, twoHundred]
//}

//call function for building possible currency arrays
let buildCurrencyArray currency limit = List.append [0] [for i=1 to limit/currency do
if limit % currency = 0 then
yield i]

//builds arrays of currencies
let buildCurrencyArray_200 = buildCurrencyArray 200 200
let buildCurrencyArray_100 = buildCurrencyArray 100 200
let buildCurrencyArray_050 = buildCurrencyArray 50 200
let buildCurrencyArray_020 = buildCurrencyArray 20 200
let buildCurrencyArray_010 = buildCurrencyArray 10 200
let buildCurrencyArray_005 = buildCurrencyArray 5 200
let buildCurrencyArray_002 = buildCurrencyArray 2 200
let buildCurrencyArray_001 = buildCurrencyArray 1 200

//builds sequence
let variousCurrencyFormulations =
sumCurrencies
buildCurrencyArray_001
buildCurrencyArray_002
buildCurrencyArray_005
buildCurrencyArray_010
buildCurrencyArray_020
buildCurrencyArray_050
buildCurrencyArray_100
buildCurrencyArray_200 200

//let variousCurrencyFormulationsResult =
//variousCurrencyFormulations |> Seq.iter (fun x -> printfn "%A" x)

//execution without timing
//let variousCurrencyFormulationsResultLength = List.length variousCurrencyFormulations

//execution with timing
let startCurrency = System.DateTime.Now
let variousCurrencyFormulationsResultLength = Seq.length variousCurrencyFormulations
printfn "%s" ((System.DateTime.Now - startCurrency).ToString())

``````