Work out change

Question

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.

Answer 1

Windows PowerShell, 108 111 117

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×$_"}}

Answer 2

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}

Answer 3

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