views:

1712

answers:

27

This question was posted by a C beginner and it was an exercise to calculate, given a dollar value input by the user, the minimum number of bills (or banknotes, depending on your locale) needed to reach that dollar value.

So, if the user entered 93, the output would be:

$20 bills = 4
$10 bills = 1
$5 bills = 0
$1 bills = 3

Finally succumbing to the phenomenon (it's a slow day here), I thought this would be ripe for a game of Code Golf.

For fairness, the input prompt needs to be (note the "_" at the end is a space):

Enter a dollar amount:_

I think I've covered all the bases: no identical question, community wiki. I won't be offended if it gets shut down though - of course, I'll never be able to complain about these types of questions again, for fear of being labelled a hypocrite :-)

Okay, let's see what you can come up with. Here's a sample run:

Enter a dollar amount: 127
$20 bills = 6
$10 bills = 0
$5 bills = 1
$1 bills = 2
+9  A: 

194 characters (with two lines, the #include and the rest combined on one line with leading spaces removed - formatted here for readability, though that's a relative term):

#include <stdio.h>
int main(void){
    int c,n;
    printf("Enter a dollar amount: ");scanf("%d",&c);
    for(n=20;n;n=(4600-6740*n+2213*n*n-73*n*n*n)/17100)
        {printf("$%d bills = %d\n",n,c/n);c=c%n;}
    return 0;
}
paxdiablo
Alright, I'm curious now. What's with the... ok, I'm gonna label it quadratic, even though I'm pretty sure that's wrong. What's with the quadratic in the 'increment' part of the loop?
Matthew Scharley
It's cubic, and my bet is it's purpose is to traverse the list `20, 10, 5, 1, 0`
Chris Lutz
I checked, and the function returns 10 when n is 20, 5 when n is 10, 1 when n is 5, and 0 when n is 1.
Chris Lutz
And while we're at it, I shortened this by 13 characters by replacing your function with a list of the proper numbers. But that cryptic function is still golf-worthy.
Chris Lutz
Toss it in an answer Chris, that function was just me being a wise-a** (or smart-a*se if you're antipodean).
paxdiablo
I'll toss it in when I can get it in the range the others are working in. Currently floating around 174.
Chris Lutz
As something you can add to your answer, Pax, C does have a largely useless but added for consistency `%=` (modulo assignment) operator.
Chris Lutz
Impressive - but, you can shave an extra char using `c%=n` rather than the overly verbose `c=c%n`. Put that in the 'increment' part of the `for` expressions and you can get rid of the braces. Initialize `n` in the declaration and you can leave that part of the for statement empty. Also strictly speaking (for C90 anyway) you can live without the `#include`.
Michael Burr
Wow, 25+ years using C and I've never seen '%=' :-) I won't update this answer with the suggestions, guys - I'd consider that cheating - you bods should add your own answers. In any case, shaving single characters won't approach the other solutions yet (though they're both very good tricks). Another thing: I'm not sure at what point the standard said you could drop return 0 from main and have it implicit.
paxdiablo
To drop the return just say the answer's C++...
Michael Burr
Good point, another few characters shaved by using cin/cout.
paxdiablo
Michael: The `#include` is needed because `printf` and `scanf` are varargs functions, which must have a prototype in scope.
caf
So the obfuscated longer answer gets more votes than the clearer C answer that is actually shorter? What does that say about us?
Andrew Shepherd
Michael Burr
@Andrew, it says this one got here first (about 7 seconds after the question was posted since I had it ready to go) and has had more time to garner votes. Such are the vagaries of SO. I expect over time, they'll be sorted based on descending length.
paxdiablo
@andrew - this longer C version was a first cut and got some early votes. Also, I think some of the votes were actually *because* of the clever (if non-obvious) way to generate the {20, 10, 5, 1, 0} list.
Michael Burr
Well, that's certainly why I voted it up :-)
Andrew Shepherd
+4  A: 

F#, 136 chars

Code-golf:

printf"Enter a dollar amount: ";Seq.fold(fun r b->printfn"$%d bills = %d"b (int(r/b));r%b)(System.Console.ReadLine()|>int)[20;10;5;1]

with whitespace added for readability:

printf "Enter a dollar amount: "
Seq.fold (fun r b->
            printfn "$%d bills = %d" b (int(r/b))
            r%b)
         (System.Console.ReadLine()|>int)
         [20;10;5;1]
Brian
+21  A: 

Python, 83 chars

(or 84 depending on the line ending)

c=input("Enter a dollar amount: ")
for n in 20,10,5,1:print"$%d bills ="%n,c/n;c%=n

Joel's original attempt:

#!/usr/bin/python
c = int(input("Enter a dollar amount: "))
for n in [20,10,5,1]:
    print n,"bills =",c//n
    c = c % n
Joel
Sorry for the edit... :) Nice job
Kalmi
removed shebang line, which is unnecessary, and used mod-assignment operator (`c%=n`)
Triptych
changed the print statement to use softspaces and I removed an unnecessary ";" from the end
Kalmi
I think the square brackets can be removed, possibly saving a byte. Also, / is sufficient, because integer division is default in python 2.x.
recursive
I did what recursive suggested and now we are down to 80 bytes. Nice finds.
Kalmi
Unfortunately, the softspace change causes this to break spec — it now prints `20 bills` instead of `$20 bills`.
Ben Blank
Uh... sorry... that was my fault... now corrected (+3 chars)
Kalmi
And this is the new winner.
paxdiablo
A: 

Perl 99 char

perl -MYAML -E'$d=<>;for(qw[100 50 20 10 5 1]){while(($t=$d-$_),$t>=0){$d=$t;$_{$_}++}}say Dump\%_'

Here is the code before I minimized it.

#! /opt/perl/bin/perl
use strict;
use warnings;
use 5.10.1;
use YAML;

my $dollar = <>;
my @bills = qw'100 50 20 10 5 1';

for( @bills ){
  my $t;
  while( ($t = $dollar - $_), $t >= 0 ){
    $dollar -= $_;
    $_{$_}++
  }
}

say Dump \%_;

If you insist on it printing a prompt, it goes up to 127

perl -MYAML -E'say"Enter a dollar amount:";$d=<>;for(qw[100 50 20 10 5 1]){while(($t=$d-$_),$t>=0){$d=$t;$_{$_}++}}say Dump\%_'

If you want to output the value as "$10 bills = 3", it goes up to 134

perl -E'say"Enter a dollar amount:";$d=<>;for(qw[100 50 20 10 5 1]){my$i;while(($t=$d-$_),$t>=0){$d=$t;$i++}say"\$$_ bills = $i"if$i}'
Brad Gilbert
I think it's generally considered cheating to use external modules. And I think doing it without YAML.pm wouldn't make it that much larger.
Chris Lutz
Can't comment on external modules (although if they're allowed, the C code could be much smaller) but you *must* have the prompt as specified.
paxdiablo
+3  A: 

Now down to 121 characters in MATLAB:

>> [email protected];x=input('Enter a dollar amount: ');for c=[20 10 5 1],disp(['$' p(c) ' bills: ' p(floor(x/c))]);x=mod(x,c);end

----Prior Version----

134 characters (not counting the >> prompt) in Matlab:

>> [email protected];x=input('Enter a dollar amount: ');b=[20 10 5 1];for c=1:4,d=b(c);disp(['$' p(d) ' bills: ' p(floor(x/d))]);x=mod(x,d);end

Or, with four more characters, ...b=[100 20 10 5 1];for c=1:5... would be all about the Benjamins.

mtrw
For those unfamiliar with US currency, I'm assuming the $100 note has Ben Franklin on it, yes?
paxdiablo
@Pax - yes. http://www.urbandictionary.com/define.php?term=benjamins
mtrw
+1 matlab in golf bag
mobrule
@mobrule - thanks!
mtrw
+10  A: 

Perl, 89 chars

not counting EOL

print"Enter a dollar amount: ";$d=<>;printf"\$$_ bills = %d\n",$d/$_,$d%=$_ for 20,10,5,1

Perl 5.10, 87 chars

print"Enter a dollar amount: ";$d=<>;for(20,10,5,1){
say"\$$_ bills = ",int$d/$_;$d%=$_}

This might be non-qualifying since it will only run under perl -E or perl -M5.010 or with use 5.010; prepended, and if you count any of those it's longer than the other. :)

hobbs
+1 though I bet you can shorten that with postfix notation. Also, consider Perl 5.10's `say()` function.
Chris Lutz
Almost identical to the one I was writing. Use `printf...%d`, lose the `int` and save 2 more chars.
mobrule
Don't know if it will apply as well here, but I discovered you could shave a few characters by changing the list of values to a single value starting at 20 (or 40), dividing by 2, rounding, and checking if the result isn't 2. That made my loop significantly smaller in C, and it might make the code a little shorter here too.
Chris Lutz
Postfix notation doesn't help because the savings from the parens are offset by the fact that assignment operators aren't the easiest thing to work into an expression. And `say` is only a tiny gain :) Likewise, @Chris Lutz, the thought is appreciated but I'm pretty sure the loop control would outweigh the literal list in any case. :)
hobbs
+2  A: 

Well, I'll toss in a shorter C answer based on Pax's and call it a night, and let the golf gurus try to shorten it. 157 characters (note the very important space):

#include <stdio.h>
int main(){int n=40,c;printf("Enter a dollar amount: ");scanf("%d",&c);while(n/=2)if(n-2)printf("$%d bills = %d\n",n,c/n),c%=n;return 0;}

Formatted:

#include <stdio.h>
int main()
{
    int n = 40, c;
    printf("Enter a dollar amount: ");
    scanf("%d", &c);
    while(n /= 2)
        if(n - 2)
            printf("$%d bills = %d\n", n, c / n), c %= n;
    return 0;
}
Chris Lutz
Oooh, gotta love that comma operator.
paxdiablo
Yep, the comma operator is your friend. I just wish I could do more with it. Or with anything, for that matter.
Chris Lutz
You can drop the `5` from the declaration of `p`, or at least gcc with `-ansi -pedantic` seems to think so.
Novelocrat
@Novelocrat - I'm not sure about that. That declares `p` with length 4 because `int` arrays (or generally speaking, `{ x }` declared arrays) aren't nul-terminated. So the resulting code might work, but invokes undefined behavior. But it's all moot now.
Chris Lutz
"But it's all moot now" - dang. I just spent far too much time working out how to save a character by declaring `n` like so: `char* n="\24\n\5\1";`. Then you have to go and get rid of the array altogether...
Michael Burr
@Michael Burr - I'm sorry. It was too good to pass up.
Chris Lutz
Ugh, damn GCC for not actually being pedantic when I ask it to.
Novelocrat
@Novelcrat - It's being pendantic. C just won't check to make sure you don't walk off the end of the array. Pendantic doesn't check for undefined behavior, it just checks for standards compliance.
Chris Lutz
A: 

c++ implementation, 193 not including space. might wanna add system("PAUSE") at the end of main to see output.

#include <iostream>
using namespace std;
void o(int a,int d)
{
    if(d!=2)
     if(a && d)
      cout << "$" << d << " bills = " << a/d << endl;
     else
      return;
    o(d!=2?a%d:a,d/2);
}
void main(){
    int n;
    cout << "Enter a dollar amount: ";
    cin >> n;
    o(n,20);
}
Funky Dude
Actually, looking at this, it would have been much easier if $2 was allowed. Then it would have been a simple int divide by two until zero.
paxdiablo
Chris Lutz
Actually, disregard point 4. My entry shrunk massively with that.
Chris Lutz
i thought either this or copy from everyone else, but i see your points.
Funky Dude
+1  A: 

Lua

128 chars

Shown as two lines (broken at a space) to fit on the screen.

p=print p"Enter a dollar amount: "m=io.read()for _,i in pairs{20,10,5,1}do
x=math.modf(m/i)p("$"..i.." bills = "..x)m=m-x*i end
Mark Rushakoff
+5  A: 

C#, 214

When formatted for Golf, the following C# is 214 characters in length:

using C = System.Console;
using System.Linq;
class P {
    static void Main() {
        C.Write("Enter a dollar amount: ");
        new[] { 20, 10, 5, 1 }.Aggregate(
            int.Parse(C.ReadLine()),
            (a, v) => { 
                C.Write("${0} bills = {1}\n", v, a / v);
                return a % v; 
            }
        );
    }
}

Thanks Andrew Shepherd!

Jason
Why do you have the var l line? Why not just: "new List<int>{20, 10, 5, 1}.Aggregate(Int32.Parse....)?
Andrew Shepherd
@Andrew Shepherd: Good. Thanks.
Jason
OK, now take out "using System.Collections.Generic" and replace "new List<int>" with "new int[]"
Andrew Shepherd
@Andrew Shepherd: You are on the ball today good sir. Thank you.
Jason
+1  A: 

Ruby, 97

$><<'Enter a dollar amount: '
n=gets.to_i
[20,10,5,1].map{|i|$><<"$%d bills = %d\n"%[i,n/i]
n%=i}


Would someone please do one of these for language-agnostic-but-not-perl? :-) :-)

DigitalRoss
That looks like Ruby to me, but might not look like Ruby to everyone. Please include the language and the character count when posting code golf answers.
Chris Lutz
Hey, we Perlers need something to do. Everyone else here just disses our language.
Chris Lutz
You mean something to do when we're *not* busy keeping the world running, right?
hobbs
+6  A: 

Ruby, 87

p"Enter a dollar amount: "
n=gets.to_i;[20,10,5,1].map{|b|p"$#{b} bills = #{n/b}";n%=b}
JRL
When I run this at the onlinje Ruby tester (there's no way in Hades I'm going to put a language like that on my hard disk :-) ), I get quotes around the strings and an extra line "[13,3,3,0]". Was that expected?
paxdiablo
Granted the extra line may be a return value of sorts, since it's the modulo for each denomination.
paxdiablo
@Pax: that's the string representation of the mapped array, which is the last statement evaluated. It's output because you're using an interactive shell which just evaluates and outputs any value you throw at it. If you ran this as a standalone program the extra line would not be output.
JRL
Right, irb is partly a debugger. If run normally as `ruby cgbn.rb` it will DTRT. It's true that `.map` actually builds a new array; it was 1 byte shorter than [].each. :-)
DigitalRoss
+5  A: 

C, 173

#include <stdio.h>
int n=20,c;int main(){
return (n-20||(printf("Enter a dollar amount: "),
scanf("%d",&c))),n?printf("$%d bills = %d\n",n,c/n),
c=c%n,(n/=2)-2||--n,main():0;}

All the linebreaks except the one after #include are removable. It's not the shortest solution, though it does make use of some less used features of C.


With some illegal hacks (C89 permits implicit int, C99 doesn't; C99 permits lack of return from main, C89 doesn't; neither permits omitting prototype of variadic printf) this still manages to compile and run in most compilers.

n=20,c;main(){n-20||(printf("Enter a dollar amount: "),scanf("%d",&c));
n?printf("$%d bills = %d\n",n,c/n),c=c%n,(n/=2)-2||--n,main():0;}

Only 136 characters (newlines removed)!

"(n/=2)-2||--n" : what a torturous, short-circuity, way to skip 2 :-)
paxdiablo
It's an interesting method, but it actually loses when I try to put it in my solution. Interesting that it appears to be shorter here.
Chris Lutz
I love the (n/=2)-2||--n part!
David Murdoch
+3  A: 

JavaScript, 135

JSBin Working Example

n=prompt('Enter a dollar amount: ');
s=[20,10,5,1];
for(i in s)
    b=s[i],
    document.write(b+' dollar bills = ' + Math.floor(n/b) + '<br/>'),
    n%=b;

Minified:

n=prompt('Enter a dollar amount: ');s=[20,10,5,1];for(i in s)b=s[i],document.write(b+' dollar bills = '+Math.floor(n/b)+'<br/>'),n%=b;

I can get it down to 129 characters if I cheat and remove semicolons, replace <br/> with \n, and leave an open <pre> at the end of the document:

n=prompt('Enter a dollar amount: ')s=[20,10,5,1]for(i in s)b=s[i],document.write(b+' dollar bills = '+Math.floor(n/b)+'\n'),n%=b
Kobi
Shave off a few more chars by replacing `Math.floor(n/b)` with `~~(n/b)` (double bitwise NOT).Also the output should say "xx bills" instead of "xx dollar bills". Read description
Infinity
+8  A: 

WinXP COM File

160 bytes

Source:

GetInput:
  mov si,offset Prompt
  call OutputString
  xor cx,cx
  xor bp,bp
  xor dx,dx
  mov bx,10
  mov di,Denoms
GetInputLoop:  
  mov ah,1
  int 21h
  mov ah,ch
  xchg ax,bp
  cmp bp,bx
  je DoneInput
  sub bp,'0'
  cmp bp,bx
  jae DoneInput
  mul bx
  add bp,ax
  adc dx,cx
  jmp GetInputLoop
EndDigits:  
  popa
  mov ax,dx
  xor dx,dx
  inc di
  cmp [di],cl
  je GetInput
DoneInput:
  pusha
  mov al,[di]
  aam
  add ax,'00'
  xchg ah,al
  mov word ptr [si+3],ax
  call OutputString
  popa  
  mov bl,[di]
  div bx
  pusha
  push cx
CalcDigitLoop:
  xor dx,dx
  mov bl,10
  div bx
  add dl,'0'
  push dx
  or ax,ax
  jnz CalcDigitLoop
PrintDigitLoop:
  pop dx
  or dx,dx
  jz EndDigits
  mov ah,2
  int 21h
  jmp PrintDigitLoop
OutputStringLoop:  
  mov ah,2
  mov dl,al
  int 21h
OutputString:
  lodsb
  or al,al
  jnz OutputStringLoop
  ret  
Prompt:
  db 10,13,'Enter a dollar amount: ',0
Output:
  db 10,13,'$   bills = ',0
Denoms:
  db 20,10,5,1,0

Skizz

Skizz
How to run it? Just put it in a .com file? :)
M28
@M28: no, assemble it using something like A86 (from here: http://eji.com/a86/index.htm)
Skizz
This isn't 160 bytes, it's more like 1KB, it's the source code that counts, not the compiled output.
Lasse V. Karlsen
@Lasse: If you want, I can put some Base64 encoded machine code up that decodes to 160 bytes. This is just the human readable form.
Skizz
+1  A: 

JAVA, 245 chars

class G{
  public static void main(String[] a) throws Exception{
    System.out.println("Enter a dollar amount: ");
    int l = new java.util.Scanner(System.in).nextInt();
    for (int i : new int[] {20,10,5,1}) {System.out.println("$"+i+" bills = "+l/i);l%=i;}
  }
}

245 chars are achieved by removing all unnecessary whitespace. As shown above it weighs 283 chars.

Gregory Mostizky
`throws Exception` is unnecessary.
missingfaktor
Input prompt not correct. Need to change println to print.
dogbane
+1  A: 

GROOVY, 146 chars

println "Enter a dollar amount: "
l=System.in.newReader().readLine().toInteger()
[20,10,5,1].each{println "\$$it bills = ${(int)(l/it)}";l%=it;}

Not sure if there is any way to improve the readline part. It looks clumsy compared to other scripting languages. The (int) is unfortunately required because by default groovy deals with decimals not integers so we have to cast it down there.

Gregory Mostizky
+1  A: 
Jon Seigel
Is this supposed to be C or C++? C needs a `return 0;` at the end to be valid.
Chris Lutz
I'm going to call it C++, because I'm not 100% sure if this is valid C code (disregarding the return 0 issue, as you mentioned). If someone could verify that it's valid C, I'll add the return 0 and say it's 161 characters.
Jon Seigel
code golf doesn't need to be valid. It just needs to produce the desired output. It can even terminate by crashing.
recursive
Fair enough (new to the game). But if I call it C, it has to _compile_ as C code, and I haven't checked that.
Jon Seigel
+1  A: 

Pascal, 204 chars

My first attempt at a code golf so I thought I'd keep it old-school. Compiled with the Free Pascal Compiler.

program a;uses sysutils;var i,b,c:integer;begin write('Enter a dollar amount: ');read(i);for b:=20 downto 1 do if b in[20,10,5,1]then begin c:=round(int(i/b));writeln('$',b,' bills = ',c);i-=b*c;end;end.
Steve Claridge
+3  A: 

J

J has a built-in it calls "anti-base".

   0 2 2 5#:93
4 1 0 3
   0 2 2 5(#:,.~[:*/\[email protected]}.[,1:)93
20 4
10 1
 5 0
 1 3

Unfortunately, the specified user interaction is impossible with only J built-ins.

ephemient
A: 

Javascript, 105 characters

105 characters (using console)

for(s="",n=prompt("Enter a dollar amount: "),i=0;b=[20,10,5,1][i++];n%=b)s+="$"+b+" bills = "+~~(n/b)+"\n"\

114 characters

for(s="",n=prompt("Enter a dollar amount: "),i=0;b=[20,10,5,1][i++];n%=b)s+="$"+b+" bills = "+~~(n/b)+"\n";alert(s)

Formatted:

var b,
    s = "", // holds our result...
    n = prompt("Enter a dollar amount: "),
    i = 0,
    a = [20, 10, 5, 1];
// increment the array until we can't increment anymore.
// get the amount left after each iteration.
for(;b=a[i++]; n %= b){
                             /* "~~" == Math.floor() */
    s += "$" + b + " bills = " + ~~(n/b) + "\n";
}
// display the results...
alert(s);
David Murdoch
A: 

Scala, 104

printf("Enter a dollar amount: ");(readInt/:Seq(20,10,5,1)){(a,b)=>printf("$%d bills = %d%n",b,a/b);a%b}
Ben Lings
+6  A: 

Too easy: DC - 73

A bit late, I know...

[Enter a dollar amount: ]P?20~A~5~1[36Pn[ bills = ]PnAP]dsPx5lPxAlPx20lPx
Dan Andreatta
*What* language is this?
BalusC
"desktop calculator", i.e. `dc` (in Linux/Unix). It is the stack-based, RPN calculator that used to be the backbone for `bc` (It still is in OpenBSD, I think)
Dan Andreatta
A: 

Vala, 223 Chars

The line breaks are not included and can be removed.

  public class BNC{public static int main(string[] p){
  int[] n={20,10,5,1};stdout.printf("Enter a dollar amount:");
  int a=stdin.read_line().to_int();foreach(int m in n){
  stdout.printf("$%i bills = % i\n",m,a/m);a%=m;}return 0;}}


Readable version:

  public class Main
  {
    public static int main (string[] args)
    {
        int[] notes = { 20, 10, 5, 1 };
        stdout.printf ("Enter a dollar amount:");
        int amount = stdin.read_line ().to_int ();

        foreach (int note in notes)
        {
            stdout.printf ("$%i bills = % i\n", note, amount / note);
            amount %= note;
        } 

      return 0;
    }
  }
Bobby
A: 

Bash, 108 Chars

echo -n Enter a dollar amount:\ ;read t;for i in 20 10 5 1;do echo \$$i bills = $(($t/$i));t=$(($t%$i));done

Readable version:

echo -n Enter a dollar amount:\ 
read t
for i in 20 10 5 1
do
    echo \$$i bills = $(($t/$i))
    t=$(($t%$i))
done
dogbane
+1  A: 

OCaml, 138 chars

open Printf
let _=printf "Enter a dollar amount: ";List.fold_left
(fun a b->printf"$%d bills = %d\n"b(a/b);a mod b)(read_int())[20;10;5;1]
bltxd
A: 

VBA

Was bored at work... 185 chars including all whitespaces

Sub a()
s = "Enter a dollar amount: "
i = InputBox(s)
Debug.Print s & i
For Each b In Array(20, 10, 5, 1)
c = Int(i / b)
i = i Mod b
Debug.Print "$" & b & " bills = " & c
Next
End Sub
Mike