Skip to content

Instantly share code, notes, and snippets.

@isaiah-perumalla

isaiah-perumalla/change.fs

Last active Dec 20, 2015
Embed
What would you like to do?
make change algorithm. compute change with using minimum number of coins
[<Measure>] type p
let count ps = let rec countcs acc = function
|[] -> acc
|(_, qty)::xs -> (countcs (acc+qty) xs)
in countcs 0 ps
let lessThan (x:int<p>) xs = List.filter (fun (coin, _) -> x >= coin) xs
let num_coins (coin:int<p>, qty:int) (amt:int<p>) = min qty (int(amt/coin))
let better ps bs =
match ps,bs with
|None,x | x,None -> x
|Some(x), Some(y) -> if ((count x) - (count y)) <= 0 then Some(x) else Some(y)
let rec choose_best chooser best =
function
|0 -> best
|qty ->
let sol = better best (chooser qty) in
if sol = best then best else choose_best chooser sol (qty-1)
(* uses a greedy heuristic to prune search tree, and backtracks to check solution is optimal *)
let mkchange denoms amount =
let rec mkch ps best amount =
function
|[] -> best
|(coin,qty)::remainingCoins ->
let qty = num_coins (coin,qty) amount in
let bal = amount - coin*qty in
let solution = better (Some ((coin,qty)::ps)) best in
if solution = best then best
elif bal = 0<p> then solution
else
let chg_with_coin q = mkch ((coin,q)::ps) best (amount - coin*q) (remainingCoins |> lessThan (amount-coin*q)) in
let candidate = chg_with_coin qty in
let optimal = choose_best chg_with_coin candidate (qty-1) in
mkch ps optimal amount remainingCoins
in mkch [] None amount (denoms |> (lessThan amount))
(* example - 6p problem *)
let coins_available = [(5<p>, 10); (3<p>, 3); (2<p>, 3);(1<p>, 0)]
mkchange coins_available 6<p> ;;
(* esoteric denominations *)
let coins_available = [(11<p>, 20); (7<p>, 20); (3<p>,4)]
mkchange coins_available 112<p> ;; (* 11p x 9 and 7p x1 and 3p x 2 *)
(* optimal change *)
let coins_available = [(10<p>, 20); (7<p>, 10); (1<p>,10)]
mkchange coins_available 24<p> ;; (* 10p x 1 and 7p x2 *)
(* large denominations and amounts *)
let coins_available = [(10000<p>, 20); (5000<p>, 20); (2000<p>,40);(1000<p>,40);(500<p>,40); (200<p>,40);(100<p>,40); (50<p>,40); (20<p>,40);(2<p>,4000);(1<p>,40000)]
mkchange coins_available 114000<p> ;;
(*correctness proof (work in prorgess )
early stop when decreasing coin qty amounts
change of amt
D = current highest denomination
c0 = D*qty + opt_chg (amt-(D*qty))
c1 = D*(qty-1) + opt_chg (amt- (D*(qty-1)))
.
.
.
cn = D*(qty-n) + opt_chg (amt - (D*(qty-n)))
if cn >= c_n-1 then stop
since
C_n-2 >= c_n-1
*)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment