Correctly determine the fewest number of coins to be given to a customer such that the sum of the coins' value would equal the correct amount of change.
For installation and learning resources, refer to the exercism help page.
To work on the exercises, you will need
Core. Consult opam website for instructions on how to install
opam for your OS. Once
opam is installed open a terminal window and run the following command to install core:
opam install core
To run the tests you will need
OUnit. Install it using
opam install ounit
A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:
utop is a command line program which allows you to run Ocaml code interactively. The easiest way to install it is via opam:
opam install utop
Consult utop for more detail.
The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.
If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue. We'll do our best to help you!
Software Craftsmanship - Coin Change Kata https://web.archive.org/web/20130115115225/http://craftsmanship.sv.cmu.edu:80/exercises/coin-change-kata
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
(* Test/exercise version: "1.1.0" *) open Base open OUnit2 open Change let printer = Option.value_map ~default:"None" ~f:(fun xs -> String.concat ~sep:";" (List.map ~f:Int.to_string xs)) let ae exp got _test_ctxt = assert_equal ~printer exp got let tests = [ "single coin change" >:: ae (Some ) (make_change ~target:25 ~coins:[1; 5; 10; 25; 100]); "multiple coin change" >:: ae (Some [5; 10]) (make_change ~target:15 ~coins:[1; 5; 10; 25; 100]); "change with Lilliputian Coins" >:: ae (Some [4; 4; 15]) (make_change ~target:23 ~coins:[1; 4; 15; 20; 50]); "change with Lower Elbonia Coins" >:: ae (Some [21; 21; 21]) (make_change ~target:63 ~coins:[1; 5; 10; 21; 25]); "large target values" >:: ae (Some [2; 2; 5; 20; 20; 50; 100; 100; 100; 100; 100; 100; 100; 100; 100]) (make_change ~target:999 ~coins:[1; 2; 5; 10; 20; 50; 100]); "possible change without unit coins available" >:: ae (Some [2; 2; 2; 5; 10]) (make_change ~target:21 ~coins:[2; 5; 10; 20; 50]); "another possible change without unit coins available" >:: ae (Some [4; 4; 4; 5; 5; 5]) (make_change ~target:27 ~coins:[4; 5]); "no coins make 0 change" >:: ae (Some ) (make_change ~target:0 ~coins:[1; 5; 10; 21; 25]); "error testing for change smaller than the smallest of coins" >:: ae None (make_change ~target:3 ~coins:[5; 10]); "error if no combination can add up to target" >:: ae None (make_change ~target:94 ~coins:[5; 10]); "cannot find negative change values" >:: ae None (make_change ~target:(-5) ~coins:[1; 2; 5]); ] let () = run_test_tt_main ("change tests" >::: tests)
open Core.Std let on ~f ~cmp x y = cmp (f x) (f y) let find_shortest_coins_list_summing_to_target (shortest_coins_lists: int list option array) (target: int) (coins: int list): int list option = coins |> List.filter_map ~f:(fun coin -> if coin > target then None else shortest_coins_lists.(target - coin) |> Option.map ~f:(List.cons coin) ) |> List.min_elt ~cmp:(on ~cmp:Int.compare ~f:List.length) let make_change ~target ~coins = if target < 0 then None else let shortest_coins_lists = Array.init (target+1) ~f:(function | 0 -> Some  | _ -> None) in for i = 1 to target do shortest_coins_lists.(i) <- find_shortest_coins_list_summing_to_target shortest_coins_lists i coins done; shortest_coins_lists.(target)
A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.
Here are some questions to help you reflect on this solution and learn the most from it.