SHOW:
|
|
- or go back to the newest paste.
1 | - | let rec sumListBy selector xs = |
1 | + | let rec sumListBy money coins highestCoinUsed xs = |
2 | match xs with | |
3 | - | | x::xs -> selector x + sumListBy selector xs |
3 | + | | x::xs -> countChangeImpl (money - x) coins (max x highestCoinUsed) + sumListBy money coins highestCoinUsed xs |
4 | | [] -> 0 | |
5 | and filterList highestCoinUsed xs ys = | |
6 | - | let rec filterListImpl predicate xs ys = |
6 | + | |
7 | | x::xs when x >= highestCoinUsed -> filterList highestCoinUsed xs (x::ys) | |
8 | - | | x::xs when predicate x -> filterListImpl predicate xs (x::ys) |
8 | + | | _::xs -> filterList highestCoinUsed xs ys |
9 | - | | _::xs -> filterListImpl predicate xs ys |
9 | + | |
10 | and countChangeImpl (money: int) (coins: int list) (highestCoinUsed: int) = | |
11 | match money with | |
12 | - | let filterList predicate xs = filterListImpl predicate xs [] |
12 | + | |
13 | | money when money < 0 -> 0 | |
14 | - | let rec countChangeImpl (money: int) (coins: int list) (highestCoinUsed: int) = |
14 | + | |
15 | let usableCoins = filterList highestCoinUsed coins [] | |
16 | sumListBy money coins highestCoinUsed usableCoins | |
17 | ||
18 | let countChange money coins = countChangeImpl money coins 0 | |
19 | - | let usableCoins = filterList (fun coin -> coin >= highestCoinUsed) coins |
19 | + | |
20 | - | sumListBy (fun coin -> countChangeImpl (money - coin) coins (max coin highestCoinUsed)) usableCoins |
20 | + | |
21 | let actual = countChange money coins | |
22 | printf "money = %d; coins = %A; expected %d; actual %d\n" money coins expected actual | |
23 | ||
24 | [<EntryPoint>] | |
25 | let main argv = | |
26 | countChangeTest 301 [5;10;20;50;100;200;500] 0 | |
27 | countChangeTest 300 [500;5;50;100;20;200;10] 1022 | |
28 | countChangeTest 30 [10;20;100;50;5] 6 | |
29 | countChangeTest 4 [1;2] 3 | |
30 | System.Console.ReadLine() |> ignore | |
31 | 0 |