Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know, the title cracks you up


Given an amount of money output the fewest number of coins make up that amount

Examples

0.1
1 dime

0.01
1 penny

0.28
1 quarter 3 penny

0.56
2 quarter 1 nickel 1 penny

1.43
5 quarter 1 dime 1 nickel 3 penny

Spec

  • 100 cents in a dollar.
  • The values of each type of coin is:
    • penny 1 cent
    • nickel 5 cents
    • dime 10 cents
    • quarter 25 cents

Built-ins which trivialize this task are not allowed.

I/O

Input is a decimal representing the dollar value of the total

  • No need to pluralize
  • Order: quarter -> penny
  • Output should be <#_of_coins> <coin type>
  • Seperators: , or , or

The only trailing whitespace allowed is a single trailing newline/space.


If there is zero of a coin type, that coin type should not be shown. E.g. 0.25 -> 1 quarter not 1 quarter 0 dime 0 nickel 0 penny

share|improve this question
    
@VoteToClose no, but I'll allow commas as a seperaor – Upgoat Feb 3 at 1:12
    
Last example is 1.43, which is greater than 1 – Luis Mendo Feb 3 at 1:16
    
@LuisMendo oh whoops, the (less than 1) part shouldn't of been there. Forgot to remove that in the sandbox I guess – Upgoat Feb 3 at 1:17
    
Is it okay if the output is 2 quarter(2 spaces)1 nickel 1 penny? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 3 at 1:24
1  
@DigitalTrauma 13.00 can be a possible input but the input will never be 13. I'll always have a decimal – Upgoat Feb 3 at 6:29

18 Answers 18

up vote 4 down vote accepted

CJam, 60

q~e2i[25A5]{md}/]" quarterx dimex nickelx penny"'x/.+{0#},S*

This script seems to have alot of room for improvement but this is shorter than any so far. This makes use of the built in "md" command which returns both the integer result of a division and the remainder. It does the following:

  • reads input (if it were a function I guess you can remove q~ for two less characters)
  • multiples the input by 100 and converts it to an integer
  • performs "md" using [25 10 5] which results in the remainders on the stack
  • combines the numbers and coin names
  • removes the number and coin name if the former is 0
  • adds pre-number zeros

Try it here

prior versions:

q~e2i[25A5]{md}/]_:!:!" quarter x dime x nickel x penny"'x/.*.+e_0-
q~e2i[25A5]{md}/]_:!:!\" quarter x dime x nickel x penny"'x/.+.*
share|improve this answer

JavaScript ES6, 107 bytes

n=>((n*=100)/25|0)+` quarter ${(n%=25)/10|0} dime ${n%10/5|0} nickel ${n%5|0} penny`.replace(/ ?0 \S+/g,"")

Simple maths.

share|improve this answer
    
Nice job! I thought there was a closed-formula ish solution – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 3 at 1:45
    
? Doesn't this output the coin type if there are zero of that coin type ? – Frentos Feb 4 at 12:24
    
@Frentos no, there is a Regex at the end which removes coin types that have zero coins – Upgoat Feb 5 at 1:14
    
@Doᴡɴɢᴏᴀᴛ: sorry, didn't realise the text area scrolled right in the absence of visual clues :-) – Frentos Feb 5 at 1:23
    
Do you need the |0 after the n%5? – Neil Feb 7 at 19:51

Python 2, 120 bytes

n=int(round(input()*100))
a=25
for b in"quarter","dime","nickel","penny":
 if n>=a:print"%d "%(n/a)+b,
 n%=a;a=40/a+5^12

Just to be safe, changed to something that definitely works to fix @Ogaday's comment, for now at least. I'm uncertain whether or not I need the int() as well, but I'm having trouble convincing myself that I don't.

print`n/a`+" "+b,

is an extra byte off, but prints an extra L for large inputs (although this code doesn't work for extremely large inputs anyway, due to float precision).

share|improve this answer
1  
You just made all the time I spent improving my solution to outgolf Mego's go to waste. Good job though! – Alexander Revo Feb 3 at 8:41
1  
+1 - I wish I knew what magic you used to come up with a=40/a+5^12 – Digital Trauma Feb 3 at 23:11
    
@DigitalTrauma Tried a bunch of arithmetic operators, eg [x^k for x in [10, 5, 1]] and [k/y for y in [25, 10, 5]] for different k, then saw that two lists were offset by 5. Probably suboptimal, but I haven't had time to brute force. – Sp3000 Feb 3 at 23:20
    
This actually fails (for me at least) on inputs of 10.03 and 10.04. It's to do with Python's representation of floats and how it rounds them to ints. Try "print %d"%(10.03*100). – Ogaday Feb 5 at 18:09
    
n=int(''.join(raw_input().split("."))) may work, but it's pretty verbose. – Sherlock9 Feb 5 at 23:33

dc, 104

Newlines added for "readability":

[dn[ quarter ]n]sq
[dn[ dime ]n]sd
[dn[ nickel ]n]sn
[d1/n[ penny ]n]sp
?A0*
25~rd0<qst
A~rd0<dst
5~rd0<nst
d0<p
share|improve this answer
13  
dc: Now with Readability™ – Alex A. Feb 3 at 1:27

Retina, 97

Thanks (as always) to @randomra - saved 1 byte.

Assumes input is either in the form xxx.yy or xxx.y.

\..$
$&0
\.

.+
$0$*:
(:{25})+
$#1 quarter 
(:{10})+
$#1 dime 
(:{5})+
$#1 nickel 
(:)+
$#1 penny

Try it online.

share|improve this answer
1  
$& is the same as $0 so you can save a byte in $0.0 by $&0. – randomra Feb 3 at 14:58
    
By inputing something like 0.9999999, the output is a little crazy – PythonMaster Feb 3 at 22:46
    
@PythonMaster I'll add support for that when the Fed starts minting 10 micropenny pieces ;-) – Digital Trauma Feb 3 at 22:59

Vitsy, 110 100 97 bytes

Yeah, hold on, I'm still methodizing this.

aa**Dv52^1m([N' retrauq 'Z]v52^MDva1m([N' emid 'Z]vDvaM51m([N' lekcin 'Z]v5MD([N'ynnep 'Z]
/D1M-D

Explanation in soon-to-come verbose mode:

push a;
push a;
multiply top two;
multiply top two;
duplicate top item;
save top as temporary variable;
push 5;
push 2;
push second to top to the power of top;
push 1;
goto top method;
if (int) top is 0;
begin recursive area;
output top as number;
push " quarter ";
output stack as chars;
end recursive area;
save top as temporary variable;
push 5;
push 2;
push second to top to the power of top;
modulo top two;
duplicate top item;
save top as temporary variable;
push a;
push 1;
goto top method;
if (int) top is 0;
begin recursive area;
output top as number;
push " dime ";
output stack as chars;
end recursive area;
save top as temporary variable;
duplicate top item;
save top as temporary variable;
push a;
modulo top two;
push 5;
push 1;
goto top method;
if (int) top is 0;
begin recursive area;
output top as number;
push " nickel ";
output stack as chars;
end recursive area;
save top as temporary variable;
push 5;
modulo top two;
duplicate top item;
if (int) top is 0;
begin recursive area;
output top as number;
push " penny";
output stack as chars;
end recursive area;
:
divide top two;
duplicate top item;
push 1;
modulo top two;
subtract top two;
duplicate top item;

Try it online!

share|improve this answer
2  
retrauq almost seems like a word... – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 3 at 1:47
    
The permalink isn't working – Upgoat Feb 7 at 17:41
    
Fixed, sorry. Old code link. :P – VTCAKAVSMoACE Feb 7 at 18:43

JavaScript ES6, 202 200 bytes

I hope this can be golfed...

r=>eval('i=[.25,.1,.05,.01];v=[0,0,0,0];for(k=0;k<4;k++)for(;r>=i[k];v[k]++,r-=i[k],r=((r*100+.01)|0)/100);v.map((x,i)=>x?x+" "+"quarter0dime0nickel0penny".split(0)[i]:"").join` `.replace(/ +/g," ")')

Ungolfed code:

function m(r){
    i=[.25,.1,.05,.01]
    v=[0,0,0,0]
    for(k=0;k<4;k++)for(;r>=i[k];v[k]++,r-=i[k],r=((r*100+.01)|0)/100);
    return v.map((x,i)=>x?x+" "+"quarter0dime0nickel0penny".split(0)[i]:"").join(" ").replace(/ +/g," ");
}
share|improve this answer

Java 8 lambda, 165 bytes

Expects input y as either double or float.

y->{int c,d=(int)(y*100);return(((c=d/25)>0)?c+" quarter ":"")+(((c=(d=d%25)/10)>0)?c+" dime ":"")+(((c=(d=d%10)/5)>0)?c+" nickel ":"")+(((d=d%5)>0)?d+" penny":"");}

So much ternary. ;-;

share|improve this answer
    
;-; What is that? Is that a wampa? – beaker Feb 3 at 19:45
    
@beaker Crying. – VTCAKAVSMoACE Feb 3 at 19:52

MATL, 82 106 107

'%i quarter %i dime %i nickel %i penny'i[.25 .1 .05]"@2#\w]100*Yo5$YD'0 \S+ ?'[]YX

Try it online!

share|improve this answer
    
I really need to include string compression in MATL – Luis Mendo Feb 3 at 1:42

Japt, 77 bytes

` {U*=L /25|0} quÂòr {U%=25 /A|0} ÜX {U%A/5|0} Íõel {U%5|0} p¿ny` r" 0 %S+" x

Thankfully, all four coin names are compressable. The ¿ should be the literal byte 0x81. Test it online!

share|improve this answer
    
Just tried it with some random inputs, it's one cent off on 18.33: 73 quarter 1 nickel 2 penny. 73*.25 + 1*.05 + 2*.01 = 18.32 instead of 18.33. – D. Strout Feb 4 at 3:36

C, 147 144 142 140 bytes

a[]={25,10,5,1},m,i=0;f(float n){for(m=n*100;i<4;m%=a[i++])m/a[i]&&printf("%d %s ",m/a[i],(char*[]){"quarter","dime","nickel","penny"}[i]);}

Ungolfed with tests:

#include <stdio.h>

a[]={25,10,5,1},m,i=0;

f(float n)
{
    for(m=n*100;i<4;m%=a[i++])
        if(m/a[i])
            printf("%d %s ",m/a[i],(char*[]){"quarter","dime","nickel","penny"}[i]);
}

int main()
{
    float test[] = {.1, .01, .28, .56, 1.43};
    for(int j = 0; j < 5; i = 0)
    {
        f(test[j++]);
        printf("\n");
    }
}
share|improve this answer
1  
Maybe try replacing char*[] with char**, int a[] with int*a, and put the m%=a[i++] in the last part of the for loop. Should save 4 bytes. Haven't tested it yet, so just try each of them. – minerguy31 Feb 4 at 2:46
    
@minerguy31 I wouldn't be able to use list initializers if I use pointers instead of arrays. Moved the m%=a[i++] bit though, thanks. – Alexander Revo Feb 4 at 6:14
1  
Also, you may be able to replace if(m/a[i]) with m/a[i]&& to save 2 more bytes. – minerguy31 Feb 5 at 0:21
    
Also try using "quarter\0dime\0nickel\0penny" in the printf. Each \0 terminates the string,saving 1 char each – minerguy31 Feb 5 at 0:27
    
@minerguy31 using string with \0 causes the program to crash. I'm not sure how iteration is supposed to work over such string anyway. – Alexander Revo Feb 5 at 7:17

LabVIEW, 62 LabVIEW Primitives

Icreated 2 Arrays for the names and values and go through them from the top (index array with i) using a modulo operator (the R IQ thing). The remaining coins are passed into the shift register.

If the value is bigger than 0 i convert the number to string and concatenate the passed down string the number and the name of the coin and put it back into the shift register.

Ijus realized my gif doesn´t show the false case but there is nothing to see anyway, it just passes through the string that came in.

share|improve this answer
    
How do "primitives" compare to bytes? Does "x primitives" beat "y bytes" when x<y? Just asking – Luis Mendo Feb 3 at 15:12
    
You can check the link to see how primitives are counted. Giving size of labview code in byte would be kinda useless, since an empty vi is already ~10kb big. By experience there are a few more primitives than bytes in a golfing language so this would be around 50-60 bytes in CJam or the like. – Eumel Feb 3 at 16:00
1  
@LuisMendo We can't bound the information content of a LabView file above by one byte per primitive, so it would be unfair to count LabView at one byte per primitive. – lirtosiast Feb 6 at 4:00
    
@ThomasKwa tbh with a well made golfing language you probably could, each operation 1 byte 1 byte per wire for each input loops are 2-4 bytes for for and whiles are 3 primitives and so on – Eumel Feb 9 at 9:23

JavaScript, 156 145 144 bytes

No match to ETHproduction's formula answer, but anyway...

function c(t){n=['quarter','dime','nickel','penny'];v=[.25,.1,.05,.01];s='';for(i in v){c=t/v[i]|0;if(c>0)s+=c+' '+n[i]+' ';t-=c*v[i];}return s}

This is one of my first rounds of golfs, so any improvements are highly appreciated! I already stole ETH's "xor trunc" -- sorry man, it was just too smart :-)

More readable:

function c(t)
{
  n = ['quarter', 'dime', 'nickel', 'penny'];
  v = [.25, .1, .05, .01];
  s = '';
  for(i in v)
  {
    c = t/v[i]|0;
    if(c>0) s += c+' '+n[i]+' ';
    t -= c*v[i];
  }
  return s
}

Note: While testing I realised that JavaScript (at least on my machine?) divides 1.13 / 0.01 to 1.12999..., making my (and probably all other JS submissions) not work 100% properly...

share|improve this answer
    
I don't think you need the very last semicolon. – Upgoat Feb 3 at 23:31
    
Indeed, thanks! – Christallkeks Feb 3 at 23:38

Perl 5 - 128 124 bytes

I guess this can be re-written to be much shorter but I really can't see it.

$s=<>*100;@v=($s/25,$s%2.5,$s%25%10/5,$s%250%5);map{$l=int($_);print$l.$".qw(quarter dime nickel penny)[$i].$"if$l>0;$i++}@v

EDIT: Just a math trick to save 4 chars.

share|improve this answer

Perl 6, 96 bytes

$/=get;put map {$_=Int($//$^a);$/%=$a;"$_ $^b" if $_},<.25 quarter .1 dime .05 nickel .01 penny>
$/ = get; # set $/ to the input

# print the following list with spaces between
# and a newline at the end
put map {
  # the parameters to this block are $a, and $b
  # which are declared as placeholder parameters $^a, and $^b

  $_ = Int( $/ / $^a ); # set $_ to the count of the current coin

  $/ %= $a;             # set $/ to the modulus of itself and the current coin

  "$_ $^b" if $_        # return a string if $_, otherwise return Empty
},
<
  .25 quarter
  .1  dime
  .05 nickel
  .01 penny
>

Usage:

for amount in  0.1  0.01  0.28  0.56  1.43; do
  echo $amount | perl6 -e'…';
done
1 dime
1 penny
1 quarter 3 penny
2 quarter 1 nickel 1 penny
5 quarter 1 dime 1 nickel 3 penny
share|improve this answer

Python 2, 167 161 bytes

Update 1: Stole Sp3000's idea to use input() and make my code a script instead of a function.

a=input()*100;k={25:0,10:0,5:0,1:0}
for i in k:k[i]=a//i;a%=i
print' '.join(['%d %s'%(k[x],{25:'quarter',10:'dime',5:'nickel',1:'penny'}[x]) for x in k if k[x]])
share|improve this answer

C, 162 bytes

Unfortunately, doesn't work without the #include.

#include <stdlib.h>
i,a[]={25,10,5,1};main(c,v)char**v;{for(c=atof(v[1])/.01;c;c%=a[i++])c/a[i]?printf("%d %s ",c/a[i],"quarter\0dime\0   nickel\0 penny"+8*i):0;}

Ungolfed

#include <stdlib.h>

i,a[]={25,10,5,1}; /* loop index, coin values */

main(c,v) char**v;
{
    /* Get dollar amount from command line, convert to pennies */
    for (c=atof(v[1])/.01;c;c%=a[i++]) /* loop while still change... */
    {
        c/a[i] /* if there are coins at this index... */
            ? printf("%d %s ", c/a[i], "quarter\0dime\0   nickel\0 penny"+8*i) /* print out how many */
            : 0;
    }
}
share|improve this answer

Lua 5.3, 141 139 132 131 bytes

Sort of based on Sp3000's Python answer, but with my own magic formula.

n=.5+100*io.read'n'a=25
for s in("quarter dime nickle penny "):gmatch".- "do
_=n<a or io.write(s,~~(n//a)," ")n=n%a
a=35%a|#s%2
end

Edit -- improved the a formula. Previously it was a=a*3%13~#s%4.

Edit 2 -- previously I was using math.ceil to round and convert to integer. Now I am reusing // to round and adding ~~ to convert to integer.

Edit 3 -- shaved a character by changing the pattern from "%w+ " to ".- ".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.