🚀 go-pugleaf

Here's a (hopefully right) solution to Ken's minimum-coin-count problem
for old British coins.

tony

%
% No guarantees, use it if you will.  If you do, please
% acknowledge the source.  If you make money from the code
% then give me a share too!
%
% Tony Curtis
%

%
% these have to be sorted mono. descending
%
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).

%
% entry point
%
%           solve(+Sum, ?Coins)
%
% Generate a list of all the possible starting coins <= the
% initial value.
%
solve(0, []).
solve(Sum, Coins) :-
        Sum > 0,
	findall((Value, [Coin]), ok_coin(Coin, Value, Sum), FirstValues),
	search(FirstValues, Sum, Coins).

%
% generate solutions until the required sum appears
% in the coin list
%
search(Values, Sum, Coins) :-
	member((Sum, Coins), Values),
	!.
search(Values, Sum, Coins) :-
	iterate_solution(Values, Sum, VClist),
	search(VClist, Sum, Coins).

%
% each member of the list is (Value, [Coins]).  Value tracks
% the accumulated total of the coins in Coins.  Coins is a list
% of coin names
%
% for each value-coins pair, get the next lowest coin which can be
% used, and add its value to Value and the name to Coins.
%
iterate_solution([], _, []).
iterate_solution([(Value, Coins) | T1], Sum, [(NewValue, NewCoins) | T2]) :-
	SumLeft is Sum - Value,
	ok_coin(Coin, ThisValue, SumLeft),
	!,
	NewValue is ThisValue + Value,
	append(Coins, [Coin], NewCoins),
	iterate_solution(T1, Sum, T2).

%
% A coin is ok if it is <= the current sum
%
ok_coin(Coin, Value, Sum) :-
	coin(Coin, Value),
	Value =< Sum.