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())