Making change with shell

2012-03-13

I was flicking through Wikström’s «Functional Programming Using Standard ML», when I noticed he describes the problem of making up change for an amount of money m using coins of certain denominations (18.1.2, page 233). He says we “want a function change that given an amount finds the smallest number of coins that adds to that amount”, and “Obviously, you first select the biggest possible coin”. Here’s his solution in ML:

exception change;
fun change 0 cs = nul
  | change m nil = raise change
  | change m (ccs as c::cs) = if m >= c
      then c::change (m-c) ccs
      else change m cs;

It’s pretty neat. The recursion proceeds by either reducing the magnitude of the first argument (the amount we are giving change for), or reducing the size of the list that is the second argument (the denominations of the coins we can use); so we can tell that the recursion must terminate. Yay.

It’s not right though. Well, it gives correct change, but it doesn’t necessarily find the solution with fewest number of coins. Actually, it depends on the denominations of coins in our currency; probably for real currencies the “biggest coin first” algorithm does in fact give the fewest number of coins, but consider the currency used on the island of san side-effect, the lambda. lambdas come in coins of Λ1, Λ10, and Λ25 (that’s not a wedge, it’s a capital lambda. It’s definitely not a fake A).

How do we give change of Λ30? { Λ10, Λ10, Λ10 } (3 tens); what does Wikström’s algorithm give? 1 twenty-five and 5 ones. Oops.

I didn’t work out a witty solution to the fewest number of coins change, but I did create, in shell, a function that lists all the possible ways of making change. Apart from trivial syntactic changes, it’s not so different from the ML:

_change () {
    # $1 is the amount to be changed;
    # $2 is the largest coin;
    # $3 is a comma separated list of the remaining coins

    if [ "$1" -eq 0 ] ; then
        echo ; return
    fi
    if [ -z "$2" ] ; then
        return
    fi
    _change $1 ${3%%,*} ${3#*,}
    if [ "$1" -lt "$2" ] ; then
        return
    fi
    _change $(($1-$2)) $2 $3 |
        while read a ; do
            echo $2 $a
        done
}

change () {
    _change $1 ${2%%,*} ${2#*,},
}

Each solution is output as a single line with the coins used in a space separated list. change is a wrapper around _change which does the actual work. The two base cases are basically identical: «”$1″ -eq 0» is when we have zero change to give, and we output an empty line (just a bare echo) which is our representation for the empty list; «-z “$2″» is when the second argument (the first element of the list of coins) is empty, and, instead of raising an exception, we simply return without output any list at all.

The algorithm to generate all possible combinations of change is only very slightly different from Wikström’s: if we can use the largest coin, then we generate change both without using the largest coin (first recursive call to _change, on line 12) and using the largest coin (second recursive call to _change, on line 16). See how we use a while loop to prepend (cons, if you will) the largest coin value to each list returned by the second recursive call. Of course, when the largest coin is too large then we proceed without it, and we only have the first recursive call.

The list of coins is managed as two function arguments. $2 is the largest coin, $3 is a comma separated list of the remaining coins (including a trailing comma, added by the wrapping change function). See how, in the first recursive call to _change $3 is decomposed into a head and tail with ${3%%,*} and ${3#*,}. As hinted at in the previous article, «%%» is a greedy match and removes the largest suffix that matches the pattern «,*» which is everything from the first comma to the end of the string, and so it leaves the first number in the comma separated list. «#» is a non-greedy match and removes the smallest prefix that matches the pattern «*,», so it removes the first number and its comma from the list. Note how I am assuming that all the arguments do not contain spaces, so I am being very cavalier with double quotes around my $1 and $2 and so on.

It even works:

$ change 30 25,10,1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 10 1 1 1 1 1 1 1 1 1 1
10 10 10
25 1 1 1 1 1
About these ads

7 Responses to “Making change with shell”

  1. Gareth Rees Says:

    That’s hilarious! Have you been doing a lot of shell programming recently?

    The only caveat I’d add is that without memoization this algorithm has exponential running time (as I learned when solving Project Euler problem 31).

    • drj11 Says:

      I’ve been doing a bit more shell programming, but i’m trying to amplify that by doing a lot more shell programming than i need to. And make 2012 the year of shell.

  2. Clive Says:

    Of course, the real problem is normally “using coins of denominations D0,D1,… transact amount X from A to B by A passing some coins to B then B returning change to A, so as to minimise the total number of coins exchanged. The way to make 9p using UK currency, for example, is give them a 10p piece and get a 1p piece in change, for a total of only two coins.

    Every now and then I re-visit the topic of optimising the denominations to minimise the number of coins exchanged (as opposed, of course, to maximising convenience for those used to a denary system) in an average transaction. Then I remember there’s no good definition of “an average transaction” and give up again.

    • drj11 Says:

      Why would you minimise the total number of voins exchanged? I often try and maximise (number I give – number I receive), in order to “get rid of change”.

  3. mathew Says:

    I seem to recall reading that there was some serious mathematics done on the subject of optimizing denominations while minimizing number of coin denominations, and the result came out basically the same as the US coin denominations. (0.01, 0.05, 0.10, 0.25).

  4. drj11 Says:

    we have 1p, 2p, 5p, 10p, 20p, 50p. It does seem that intuitively it would be better to have a 25p coin instead of a 20p coin, because the 20p coin can only save 1 coin in change.

    Holland used to have a 2½ guilder coin. Very sensible.

  5. Ian Taylor Says:

    That’s a coincidence: I just came back from Cuba where they have the following system for their convertible currency:

    Coins: 0.01 0.02 0.05 0.10 0.25 0.50 1.00
    Notes: 1.00 _3.00_ 5.00 10.00 20.00 50.00 …

    The three peso note got some getting used to! But it made me think, even then: Is this problem related to the “optimal radix” problem where (IIRC) the “best” radix is “e” (for some definition of “best”).

    So maybe the three peso note isn’t such a bad choice after all. Does that mean they should shift their five peso note to seven pesos?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: