# 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 '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 – Martin York Feb 7 '11 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&][[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 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. – ericw31415 Jun 16 '17 at 1:02
• OP doesn't specify input/output format. – J42161217 Jun 16 '17 at 1:17
• This question doesn't use 100 dollar bills and there's no bonus. – ericw31415 Jun 17 '17 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" – J42161217 Jun 17 '17 at 2:15
• Whoops, I guess I didn't see that then! – ericw31415 Jun 22 '17 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