let rec sumListBy selector xs =
    match xs with
    | x::xs -> selector x + sumListBy selector xs
    | [] -> 0

let rec filterListImpl predicate xs ys =
    match xs with
    | x::xs when predicate x -> filterListImpl predicate xs (x::ys)
    | _::xs -> filterListImpl predicate xs ys
    | [] -> ys

let filterList predicate xs = filterListImpl predicate xs []

let rec countChangeImpl (money: int) (coins: int list) (highestCoinUsed: int) =
    match money with
    | 0 -> 1
    | money when money < 0 -> 0
    | money ->
        let usableCoins = filterList (fun coin -> coin >= highestCoinUsed) coins
        sumListBy (fun coin -> countChangeImpl (money - coin) coins (max coin highestCoinUsed)) usableCoins

let countChange money coins = countChangeImpl money coins 0

let countChangeTest money coins expected =
    let actual = countChange money coins
    printf "money = %d; coins = %A; expected %d; actual %d\n" money coins expected actual

[<EntryPoint>]
let main argv =
    countChangeTest 301 [5;10;20;50;100;200;500] 0
    countChangeTest 300 [500;5;50;100;20;200;10] 1022
    countChangeTest 30 [10;20;100;50;5] 6
    countChangeTest 4 [1;2] 3
    System.Console.ReadLine() |> ignore
    0