🚀 go-pugleaf

What, no tuppence?

-- 
:-  Michael A. Covington     internet mcovingt@uga.cc.uga.edu :    *****
:-  Artificial Intelligence Programs       phone 706 542-0358 :  *********
:-  The University of Georgia                fax 706 542-0349 :   *  *  *
:-  Athens, Georgia 30602-7415 U.S.A.     amateur radio N4TMI :  ** *** **

In article <1993Jan7.141322.22240@ecrc.de> thom@ecrc.de writes:

#  min_coins(Value,Coins):-
#  	list(Coins),
#  	sum_coins(Coins,Value).
#  
#  list([]).
#  list([X|L]):- list(L).
#  
#  sum_coins([],0).
#  sum_coins([Coin|Coins],Sum):-
#  	coin(Coin,Value),
#  	Value =< Sum,
#  	NewSum is Sum-Value,
#  	sum_coins(Coins,NewSum).
# ...
# coins detail omitted


This is a short solution, but it is really just a neat way of doing
iterative deepening.  To be honest, I hadn't thought of doing it quite
this way.  However, it might be spectacularly inefficient.  Supposing
the fewest coins needed to make up some sum is seven.  This algorithm
will try a large number of combinations of 2 coins, then 3, then 4, then
5, then 6, before finding the optimal solution.  So this does not really
qualify as the Ultimate Answer. 

Adding a clause

   sum([],X) :-
	X > 0,
	write('failed'),
	nl.

will print the word `failed' for each unsuccessful combination.

Ken Johnson
-- 
Son, all the pretty, intelligent, healthy     #    Ken Johnson, AIAI,
young women are taken. It's a basic rule of   #    80 South Bridge, Edinburgh
the universe, and if you don't like it, go    #    Tel 031-650 2756 
somewhere else.        -- my dad  1906-1992   #    Fax 031-650 6513

/* Problem: to find the smallest number of old British coins
   that sum up to some amount.

   Technique: iterative deepening, with a limit from the first
   solution found.  (If the limit isn't provided, there would
   be infinite backtracking if you tried to use this predicate
   to find all solutions.)  The iterative deepening calls sum//1
   with the lists [_], [_,_], [_,_,_] up to the limit length.
*/

shortest_sum(Sum, Coins) :- 
	sum(Sum, Coins1), !, /* we want one solution for a bound */
	length(Coins1, MaxLength),
	shortest_sum(Sum, Coins, 1, MaxLength),
	!. /* and no need to compute any more solutions */

shortest_sum(Sum, Coins, Length, MaxLength) :-
	Length =< MaxLength,
	shortest_sum2(Sum, Coins, Length, MaxLength).

shortest_sum2(Sum, Coins, Length, _) :-
	length(Coins, Length), /* create Coins list of given Length */
	sum(Sum, Coins).
shortest_sum2(Sum, Coins, Length, MaxLength) :-
	Length2 is Length + 1,
	shortest_sum(Sum, Coins, Length2, MaxLength).

/* Here is John Dowding's DCG method for generating lists of
   possible solutions (I've removed one cut from his code): */

sum(Sum, Coins) :- phrase(sum(Sum), Coins).

sum(Sum) --> coin(V), {V =< Sum, Rest is Sum-V}, sum(Rest).
sum(0) --> [].

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

- Peter Ludemann