(* Coin Problem:
A group of coin denominations is given.
You are asked to represent a given sum with the least amount of coins.
How do you do that? *)
(* open modules to make things shorter *)
open Printf;; open List;;
(* printf utilities *)
(* Print a coin count pair ie: "(3 of 7)" *)
let print_pair pair oc =
output_char oc '(';
output_string oc (string_of_int (snd pair));
output_string oc " of ";
output_string oc (string_of_int (fst pair));
output_char oc ')' ;;
(* Print a path string ie: "(1 of 5),(3 of 2)" *)
let rec print_path path oc = match path with
pair :: [] >
print_pair pair oc
 pair :: tl >
print_pair pair oc;
output_string oc ", ";
print_path tl oc
 [] > () ;;
(* Print a path list (path strings separated by new lines *)
let print_paths paths oc =
let rec pp paths oc =
match paths with
path :: [] >
print_path path oc
 path :: tl >
print_path path oc;
output_string oc ".\n";
pp tl oc
 [] > () in output_char oc '\n'; pp paths oc ;;
(* Print a list... [1;2;3;4] *)
let rec print_list l oc =
let rec pl l oc =
match l with
i :: [] >
output_string oc (string_of_int i);
output_char oc ']'
 i :: tl >
output_string oc (string_of_int i);
output_char oc ';';
pl tl oc
 [] > () in output_char oc '['; pl l oc ;;
(* Count how many coins are in a path *)
let path_coins path =
let rec _c path c = match path with
[] > c
 pair :: tl > _c tl (c + (snd pair)) in _c path 0 ;;
(* Solve the coin problem.
@parameter: coins List containing coin values
@parameter: sum Integer of what we want to represent
@return: A path of coin value pairs *)
let solve coins sum =
(* Recursive helper matches 3 types
@parameter: coins List containing coin values
@parameter: remains Integer whats left to represent
@parameter: current_path How many of what coins have been used in this path
@parameter: best_path Best known path upto the current point in execution
@returns: Best known path so far *)
let rec gen_path coins remains current_path best_path =
(* filter out coins that are too big *)
let coin_opts = filter
(fun coin > remains >= coin) coins in
(* partition posible coins between divisible and non divisible *)
let coin_part = partition
(fun coin > remains mod coin = 0) coin_opts in
(* get the maximum coin value of each *)
let div_max = fold_left max 0 (fst coin_part) and
ndv_max = fold_left max 0 (snd coin_part) in
match coin_part with
(* no more coins to choose from, return best path known *)
_ when (length coin_opts) = 0 > best_path
(* remaining sum is not only divisible by a coin amount,
but also, that amount is the highest available *)
 (divs, ndvs) when ndv_max < div_max  ndvs = [] >
let new_path = (div_max, remains / div_max) :: current_path in
if (path_coins best_path) < (path_coins new_path) then
best_path
else
new_path
(* general case when we don't know which is a better choice,
we end up simply adding a coin of each, individualy..
@parameter: coin_optss List pf coin values we have yet to check
@returns: Best known path so far *)
 _ > let rec do_coin_opts coin_opts = match coin_opts with
(* we have already cycled through each coin,
leave this inner loop *)
[] > best_path
(* try adding one of coin and continue *)
 coin :: tl >
(* keep list short; filter and fold quantities *)
let cPath = filter
(fun pair > fst pair <> coin) current_path in
let count = fold_left
(fun c pair > if (fst pair) = coin then (c+ (snd pair)) else c) 0 current_path in
(* get what would have happened had we added another coin *)
let path_a = do_coin_opts tl in
(* finish building this path and compare it to our retrieved alternative *)
gen_path coin_opts (remains  coin) ((coin,count+1)::cPath) path_a
(* the general case is to go through each available coin *)
in do_coin_opts coin_opts
(* solve simply calls the gen_path function, with the appropriate parameters *)
in gen_path coins sum [] [(0,sum)]
;;
(* Coin Problem Test Cases *)
let coins = [3;5;7;9];;
let sum = 4;;
(* run it *)
let path = solve coins sum;;
(* printf "test print_pair %t\n" (print_pair (4,5));; *)
printf "Problem.\nCoin Values = %t\nRequested Sum = %d\n\n" (print_list coins) sum;;
if fst (hd path) = 0 then printf "Solution:\nImposible to do" else
printf "Solution:\nCoins = %d.\nPath = %t\n" (path_coins path) (print_path path);;
I've outgrown my own imagination and spent my youth on what was not yet needed. Maybe an escape will steal from the present the little bits of the past i've left behind. Here i'll be cheerful, imaginative and cheifly inconsistant. I might get gloomy though... Hopefully untied to myself.
Saturday, May 19, 2007
Coin Problem.. Code
Subscribe to:
Post Comments (Atom)
Ráptame
Ven, escápate conmigo! Por hoy, llévame donde quieras; pero hoy; regalame tu día Invitame a tus antojos Brindame tu sonrisa y Mírame a ...

Watch live video from ZeitgeistTV on Justin.tv It took me a long time to view the Zeitgeist videos , the first one, is a sensationalist ...

I remember telling someone, on her porch one afternoon: "That's because you have never really had your heart broken, and I will do ...
4 comments:
hot..
a que' hora te acostaste? :P
a gentleman never tells.
Yo fui que te puse en eso, deberias de poner mi nombre en los creditos :P
Ustedes si se entienden bien!!
yo no entendi NPI.
;P
Post a Comment