# Work out change [closed]

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, 2011 at 8:41 • How do bonus points work? Just if there is a tie for the shortest program? Feb 7, 2011 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." Feb 7, 2011 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 Feb 7, 2011 at 20:59 ## 6 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&][]&


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&][]&


(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.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),20,"");p(to!int(m),25,"/100");}


More Legibly:

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

void main(string[] a)
{
auto m = a.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), 20, "");
p(to!int(m), 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 the number of each type of 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

# Mathematica, 51 bytes

#~NumberDecompose~{10,5,2,1,.5,.25,.1,.05,.01}&


input

[1.53]

output

{0, 0, 0, 1, 1, 0, 0, 0, 3.}

# Mathematica, 82 bytes --WITH BONUS--

(s=#~NumberDecompose~#2;Row@Flatten@Table[Table[#2[[i]]"+",s[[i]]],{i,Length@s}])&


Input

[37.6, {15, 7, 2.5, 1, 0.88, 0.2, 0.01}]

output

15 +15 +7 +0.2 +0.2 +0.2 +

• Umm, this question uses different denominations from the duplicate. Jun 16, 2017 at 1:02
• OP doesn't specify input/output format. Jun 16, 2017 at 1:17
• This question doesn't use 100 dollar bills and there's no bonus. Jun 17, 2017 at 1:44
• ok.fixed and saved some bytes! As for the bonus, I am kindly requesting you to read the question again. Especially the part .."Bonus points for supporting other currencies" Jun 17, 2017 at 2:15
• Whoops, I guess I didn't see that then! Jun 22, 2017 at 20:44

# Javascript, 84 83 bytes

(n,v=[10,5,2,1,.5,.25,.1,.05,.01],l=[])=>{for(i in v)l[i]=n/v[i]|0,n%=v[i];return l}


(n,v=[10,5,2,1,.5,.25,.1,.05,.01],l=[])=>eval("for(i in v)l[i]=n/v[i]|0,n%=v[i];l")


Uses a greedy algorithm.

# APL (Dyalog), 19 bytes

Prompts for desired amount and then for denominations expressed in smallest unit (pennies/cents).

⎕CY'dfns'
⎕ stamps⎕


Try it online!

⎕CY'dfns'Copy the dfns workspace

⎕ stamps⎕ ask for inputs and use as arguments to the stamps function