🚀 go-pugleaf

Once you have a simple solution (e.g. my previous posting)
you can make it fast. As we are interested in a set of coins
rather than a sequence of coins as the solution,
we can restrict ourselves to a sorted list (descending by
value). We simply add another argument to sum_coins that
holds the previous value and take care that the new value
is not greater.

The resulting program gives a 25-fold speed-up on min_coins(119,L).
The average time to compute one of the first 120 solutions is about
5 milliseconds (Eclipse on Sun SLC). This speed should suffice.
*/

% British coinage problem

min_coins(Value,Coins):- list(Coins),sum_coins(Coins,Value,Value). 

list([]).
list([X|L]):- list(L).

sum_coins([],0,_).
sum_coins([Coin|Coins],Sum,PrevVal):-
	coin(Coin,Value),
	Value =< PrevVal,
	Value =< Sum,
	NewSum is Sum-Value,
	sum_coins(Coins,NewSum,Value).

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).

% thom