# Work out change

You are writing a program for an automatic cash register. The user needs change with the least number of coins used. Write a program which takes an amount (say \$1.53) and gives change in US denominations - in this instance: 1 x one dollar note, 1 x fifty cents and 3 x one cent. The shortest program shall be the winner. Bonus points for supporting other currencies (i.e. UK denominations) and unusual currencies (1, 2, 3 cents?)

You have these US denominations: 1 cent, 5 cents, 10 cents, 25 cents, 50 cents, 1 dollar (note or coin), 2 dollars, 5 dollars, 10 dollars.

You have these UK denominations: 1 pence, 2 pence, 5 pence, 10 pence, 20 pence, 50 pence, £1, £2, £5 (note or coin), £10.

-
This probably needs a little bit of clarification. Firstly you should probably specify we want the least number of coins (which makes the bonus question slightly more interesting, e.g. {1c,49c,50c} and 98c breaks a naive algorithm). Secondly, an input/output format is useful. Specifics of handling unobtainable values (for made-up currencies) would help. Lastly -- you might want to list the denominations here so people won't need to look it up if they're unfamiliar with it. – Nabb Feb 7 '11 at 8:41
How do bonus points work? Just if there is a tie for the shortest program? – gnibbler Feb 7 '11 at 8:51
@gnibber, quoting Stephen Fry: "[points are] impartially determined by a demographically-selected customer service focus consultancy, broken down by age and sex – i.e. me." – Thomas O Feb 7 '11 at 8:59
I am going to ask for 50c as i have not seen a 50 cent coin yet. But aparently they exist: usmint.gov/kids/coinnews/circulating/50centCoin.cfm – Loki Astari Feb 7 '11 at 20:59

## 3 Answers

### Windows PowerShell, 108 111117

Very first attempt, ungolfed so far:

``````\$i=+("\$input"-replace'[^\d.]')
\$args|%{0d+\$_}|sort -des|%{\$a=[math]::floor(\$i/\$_)
if(\$a){\$i-=\$a*\$_
"\$a×\$_"}}
``````

Implementation notes:

1. Accepts the quantity to return via the pipeline
2. Accepts the list of currency denominations via the command-line
3. The quantity can be given with a currency sign; that will be stripped (in fact, anything non-numeric).
4. The list of denominations does not need to be sorted.
5. The program will output the largest change smaller than the requested quantity achievable with the given denominations, i.e. 1.5 for 1.53 if the 1-cent coin is missing.

If 3 and 4 do not need to be satisfied (i.e. I control the input format ;-)), then the following program suffices (71):

``````\$i=+"\$input"
\$args|%{\$a=[math]::floor(\$i/\$_)
if(\$a){\$i-=\$a*\$_
"\$a×\$_"}}
``````
-

## Mathematica: 110 chars

``````Sort[IntegerPartitions[Rationalize@#,Infinity,{10,5,2,1,1/2,1/4,1/10,5/100,1/100}],
Length@#1<Length@#2&][[1]]&
``````

Usage

``````%[0.98]
{1/100, 1/100, 1/100, 1/10, 1/10, 1/4, 1/2}
``````

Or

``````Tally@Sort[IntegerPartitions[Rationalize@#,Infinity,
{10,5,2,1,1/2,1/4,1/10,5/100,1/100}],
Length@#1<Length@#2&][[1]]&
``````

(6 chars more) gives

``````{{1/100, 3}, {1/10, 2}, {1/4, 1}, {1/2, 1}}
``````

For other denominations, just change the rationals table {10,....,5/100,1/100}

-

# D: 225 Characters

``````import std.algorithm,std.conv,std.stdio;void main(string[]args){auto m=args[1].findSplit(".");void p(T,S)(T t,T u,S s){foreach(v;[u,10,5,1]){writefln("%s %s%s",t/v,v,s);t-=(t/v)*v;}}p(to!int(m[0]),20,"");p(to!int(m[2]),25,"/100");}
``````

More Legibly:

``````import std.algorithm,std.conv,std.stdio;

void main(string[] a)
{
auto m = a[1].findSplit(".");

void p(T, S)(T t, T u, S s)
{
foreach(v; [u, 10, 5, 1])
{
writefln("%s %s%s", t / v, v, s);
t -= (t / v) * v;
}
}

p(to!int(m[0]), 20, "");
p(to!int(m[2]), 25, "/100");
}
``````

Only handles US currency. Takes the value as a floating point value on the command line (must have the leading 0 for values under 1 dollar). Does not accept \$ as part of value. Outputs number for each bill/coin on a separate line. e.g. an input of 1.53 results in

0 20
0 10
0 5
1 1
2 25/100
0 10/100
0 5/100
3 1/100

-