:PROPERTIES: :ID: d69438b9-c2e4-415a-9dbe-faf0fc810413 :mtime: 20231023030009 20231018024124 20231013024234 :ctime: 20231013024227 :END: #+title: Coin Changing Problem #+filetags: :public:project: * Problem Statement The "coin changing problem" says given a list of coins in a till, make change for an amount from your till. You may assume that all the coins in your till have positive, integer values. * Solution in OCAML This solution uses a greedy algorithm. This solution assumes "till" is sorted. #+BEGIN_SRC ocaml let rec makeChange till amount = match till , amount with | _ , 0 -> [] | [] , _ -> raise (Failure "no more coins in till") | coin :: till , amount -> if amount < coin then makeChange till amount else coin :: makeChange (coin :: till) (amount - coin) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both makeChange [ 50 ; 20 ; 10 ; 5 ; 2 ; 1] (43) #+END_SRC #+RESULTS: | 20 | 20 | 2 | 1 | #+BEGIN_SRC ocaml :exports both makeChange [5 ; 2] 16 #+END_SRC #+RESULTS: : Exception: Failure "no more coins in till". Now let's do a non-greedy algorithm #+BEGIN_SRC ocaml let rec allChanges = function | 0 -> Fun.const [[]] | amount -> function | [] -> [] | coin :: till -> (if amount < coin then [] else List.map (List.cons coin) (allChanges (amount - coin) (coin :: till) )) @ allChanges amount till #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both allChanges 16 [5 ; 2] #+END_SRC #+RESULTS: | 5 | 5 | 2 | 2 | 2 | | | | | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |