🚀 go-pugleaf

If you want to make up a sum of money in British decimal currency using
the fewest coins, there is a safe deterministic algorithm.  Allocate the
largest coin that you can, until you have made up the sum exactly.  E.g. 
to make up 78p you allocate 50p (the largest coin -- no one-pound coins
in Scotland), leaving 28p; to make up 28p you allocate 20p (the largest
coin that fits) leaving 8p, then 5p, 2p, 1p.  A few experiments
convinces me this algorithm works. 

In old British money, however, it sometimes misses a trick.  The
following code works for the cases of two shillings and twopence (26
pence) and two shillings and sixpence (30 pence) as follows:

          | ?- make(26,C).

               C=[florin,penny,penny] ;

          | ?- make(30,X).

               X=[half-crown] ;

But it can't do four shillings (48 pence) correctly.

          | ?- make(48,X).

               X=[half-crown,shilling,sixpence]

since a solution in two coins is possible.  I'd be interested to hear of
any neat, deterministic algorithm that can do this problem even though
it is now twenty-one years too late.  I'm looking for something neater
than a depth first search with depth-of-search control. 

Here is my code, for the information of any who seek it.  You may
distribute this code freely, but please acknowledge the source and the
limitation described above.  If you sell copies of this code at a
profit, I want a share. 


          % Making up sums of pence in old British
          % currency.  Ken Johnson, 5-1-1993

          make(0,[]).

          make(Sum,[Name|Rest]) :-
          	coin(Name,Value),
          	Value =< Sum,
          	!,
          	Residue is Sum - Value,
          	make(Residue,Rest).


          % Note the ordering from greatest to least
          % value is essential to make the second clause
          % (above) work. If these clauses are randomly
          % ordered you will have to alter that second clause
          % to make it cope.

          coin('ten shilling note',120).
          coin('half-crown',30).
          coin(florin,24).
          coin(shilling,12).
          coin(sixpence,6).
          coin('threepenny bit',3).
          coin(penny,1).



-- 
Son, all the pretty, intelligent,      || Ken Johnson                           healthy young women are taken.         || A I Applications Institute
It's a basic rule of the universe,     || 80 South Bridge                       and if you don't like it,              || Edinburgh,  Scotland   EH1 1HN
go somewhere else.                     || Phone 031-650 2756   Fax 031-650 6513
               -- my dad  1906-1992    || E-mail ken@aiai.ed.ac.uk