🚀 go-pugleaf

Well, I thought this was a dry-as-dust topic, but correspondence by
E-mail has already revealed two interesting(?) facets.  Or maybe it
revealed how bored I am. 

Firstly: Here is a brute-force-and-ignorance way of minimising the
number of coins in old British money.  It works by applying the usual
largest-fit algorithm, and then searches by binary chop to see whether
it can find a combination of fewer coins.  There is an assumption that
if (say) the largest-fit algorithm requires 8 coins and in fact at least
4 coins are required, then solutions requiring exactly 5, 6 and 7 coins
also exist.  If this assumption is false, and it probably is, binary
chop won't work, and you have to try every number between
(Sum/Value_of_largest_coin) and (Number_required_by_largest_fit). 

Secondly: After that, I have written the largest-fit solution to the
problem as a DCG!

(A) Fewest Coins Algorithm:

          fewest_coins(Sum,Coins) :-
          	Sum > 0,
          	make(Sum,Sum,_,Max_needed),
          	chop(0,Max_needed,Limit,make(Sum,Limit,Coins),Fewest),
          	make(Sum,Fewest,Coins).

          make(Sum,Max_coins,Coins) :-
          	make(Sum,Max_coins,0,Coins,_).
          
          make(Sum,Max_coins,Coins,N_used) :-
          	make(Sum,Max_coins,0,Coins,N_used).
          
          make(0,_,Used,[],Used).
          
          make(Sum,Limit,Used,[Name|Rest],U_out) :-
          	Used < Limit,
          	coin(Name,Value),
          	Value =< Sum,
          	Residue is Sum - Value,
          	New_used is Used + 1,
          	make(Residue,Limit,New_used,Rest,U_out).
          
          
          % Coins; must be in order of decreasing 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).
          
          % Search for minimum by binary chop.  This is a utility you ought to
          % have in your filofax or somewhere. 
          
          chop(Highest_fail,Lowest_success,_,_,Lowest_success) :-
          	Lowest_success - Highest_fail =< 1,
          	!.
          
          chop(Highest_fail,Lowest_success,Var,Term,Result) :-
          	Try is (Lowest_success + Highest_fail) // 2,
          	\+ \+ (				% Avoid instantiating Var
          		Var = Try,
          		Term
          	      ),
          	!,
          	chop(Highest_fail,Try,Var,Term,Result).
          
          chop(Highest_fail,Lowest_success,Var,Term,Result) :-
          	Try is (Lowest_success + Highest_fail) // 2,
          	chop(Try,Lowest_success,Var,Term,Result).
          
Example run of (A)

           ?- fewest_coins(49,X).

              X=[florin,florin,penny]

(B) The problem expressed as a DCG

          sum(S) --> coin(V), {V =< S, !, T is S-V}, sum(T).
          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].

Example run of (B)

          ?- phrase(sum(49),X).
          
          X=[half-crown,shilling,sixpence,penny]

(this being of course correct, but less than optimal). 

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

In article <8090@skye.ed.ac.uk> ken@aiai.ed.ac.uk (Ken Johnson) writes:

   Secondly: After that, I have written the largest-fit solution to the
   problem as a DCG!

   (B) The problem expressed as a DCG

	     sum(S) --> coin(V), {V =< S, !, T is S-V}, sum(T).
	     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].


I realised a while back that you can use DCGs for many programs that
don't look like parsing.  My favorite (and most grotesque) is flatten:

flatten(List, FlattenedList):-
	phrase(flatten(List), FlattenedList).

flatten([]) --> [].

flatten([Head|Rest]) -->
	flatten(Head),
	flatten(Rest).

flatten(List) -->
	[List].


--
John Dowding
dowding@ai.sri.com

The following code works, but I have not a clue how to generalise it. 
At least, I have not chanced upon a case where it does not give the best
answer.  The reason for the op/3 call will become clear in a minute,
although those over thirty will recognise it on sight:

:-  op(500, xf, '/-').

make(A/-,C) :-
	Sum is 12 * A,
	make(Sum,C).

make(A/B,C) :-
	Sum is A * 12 + B,
	make(Sum,C).

make(0,[]).

make(Sum,[Name|Rest]) :-
	Sixpences is Sum//6,			% If the number of sixpences
	coin(Name,Value),			% in the sum is an exact
	Value =< Sum,				% multiple of 4, then do not
	\+ (	0 is Sixpences mod 4,		% allocate a half crown.
		Value is 30			% No clue how to generalise
	   ),					% this to other currencies.
	Residue is Sum - Value,			% The LCM of 4 and 5 is 20 so
	make(Residue,Rest).			% 10/- is dispensed as a
						% ten shilling note, not as
						% five florins (wrong)
% Coins; must be in order of decreasing 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).

% Sample Run

This program understands the traditional way of writing `four shillings'
as 4/- and four shillings and elevenpence as 4/11. 

 ?- make(4/-,X).
     X=[florin,florin]

 ?- make(4/6,X).
     X=[half-crown,florin]

 ?- make(5/-,X).
     X=[half-crown,half-crown]

 ?- make(5/11,X).
     X=[half-crown,half-crown,sixpence,threepenny bit,penny,penny]


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