3 people like it.

Project Euler Problem 31

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: 1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p How many different ways can £2 be made using any number of coins?

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
// Generator of change variants for any sum and set of coin denominations
let rec change sum coins =
    if sum = 0 then [[]]
    else 
        match coins with
        | h::t -> 
            let xs = change sum t
            if sum >= h then
                let ys = change (sum - h) coins |> List.map (fun xs -> h :: xs)
                List.append xs ys
            else
                xs
        | [] -> []

// Application to Problem 31
change 200 [200;100;50;20;10;5;2;1]
|> List.length
|> printfn "Project Euler Problem 31 Answer: %d"
val change : sum:int -> coins:int list -> int list list

Full name: Script.change
val sum : int
val coins : int list
val h : int
val t : int list
val xs : int list list
val ys : int list list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val xs : int list
val append : list1:'T list -> list2:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.append
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Raw view Test code New version

More information

Link:http://fssnip.net/89
Posted:12 years ago
Author:Gene Belitski
Tags: project euler , puzzles