Path: utzoo!attcan!uunet!mcsun!hp4nl!swi.psy.uva.nl!anjo
From: anjo@swi.psy.uva.nl (Anjo Anjewierden)
Newsgroups: comp.lang.prolog
Subject: The Craft of Prolog pp. 126-130
Message-ID: <4473@swi.swi.psy.uva.nl>
Date: 2 Nov 90 16:27:04 GMT
Reply-To: anjo@swi.psy.uva.nl ()
Organization: SWI, UvA, Amsterdam
Lines: 92

I read:

	Richard A. O'Keefe, "The Craft of Prolog", MIT Press 1990.

with great interest.  There is at least one section that may be
inconsistent with statements made elsewhere in the book.  Section 4.4
gives the following problem (the section is about reducing the
search space):

The problem is as follows:

	"D1, D2, ..., D9 are distinct decimal digits, none of them
	zero, such that for each 1 <= n <= 9 the n digits D1 ... Dn
	form a number which is divisible by n." [p. 126]

A Prolog program solving this problem is the following (I have paired
the select/3 and divisible/2 calls inside answer/1):

%   "The Craft of Prolog", p. 127

divisible(N, Ds) :-
	divisible(Ds, 0, N).

divisible([], 0, _).
divisible([D|Ds], R0, N) :-
	R1 is (R0*10 + D) mod N,
	divisible(Ds, R1, N).

%   "The Craft of Prolog", p. 127 (adapted)

answer(Solution) :-
	Solution = [D1,D2,D3,D4,D5,D6,D7,D8,D9],
	R0 = [1,2,3,4,5,6,7,8,9],
	select(D1, R0, R1),	divisible(1, [D1]),
	select(D2, R1, R2),	divisible(2, [D1,D2]),
	select(D3, R2, R3),	divisible(3, [D1,D2,D3]),
	select(D4, R3, R4),	divisible(4, [D1,D2,D3,D4]),
	select(D5, R4, R5),	divisible(5, [D1,D2,D3,D4,D5]),
	select(D6, R5, R6),	divisible(6, [D1,D2,D3,D4,D5,D6]),
	select(D7, R6, R7),	divisible(7, [D1,D2,D3,D4,D5,D6,D7]),
	select(D8, R7, R8),	divisible(8, [D1,D2,D3,D4,D5,D6,D7,D8]),
	select(D9, R8, R9),	divisible(9, [D1,D2,D3,D4,D5,D6,D7,D8,D9]).

If you study the remainder of the book it is not at all difficult
to see what is wrong with this program: why is the partial solution
represented as a list?  By the time answer/1 gets to the last sub-goal
it will have considered D1 8 times, D2 7 times (etc.).

Applying the principle of not wasting space and time I arrived at:

%   Anjo Anjewierden, University of Amsterdam, 02/10/90

%   d(+N, +Value, +Digit, -NewValue)
%
%   Is true if appending Digit to Value is divisble by N
%   (all base 10).  Example: d(3, 12, 3, 123) is true
%   because 123 is divisible by 3.

divisible(N, Value, Digit, NewValue) :-
	NewValue is (10 * Value) + Digit,
	0 is NewValue mod N.


answer([D1,D2,D3,D4,D5,D6,D7,D8,D9]) :-
	R0 = [1,2,3,4,5,6,7,8,9],
	select(D1, R0, R1),	divisible(1,  0, D1, V1),
	select(D2, R1, R2),	divisible(2, V1, D2, V2),
	select(D3, R2, R3),	divisible(3, V2, D3, V3),
	select(D4, R3, R4),	divisible(4, V3, D4, V4),
	select(D5, R4, R5),	divisible(5, V4, D5, V5),
	select(D6, R5, R6),	divisible(6, V5, D6, V6),
	select(D7, R6, R7),	divisible(7, V6, D7, V7),
	select(D8, R7, R8),	divisible(8, V7, D8, V8),
	select(D9, R8, []),	divisible(9, V8, D9, _).

In Quintus Prolog 2.4 the O'Keefe version takes 0.9 seconds and my
version takes 0.5 seconds.  If you want you can apply the same
problem specific optimisations that O'Keefe uses and make it a lot
faster still.

I would greatly appreciate any comments on the above as I'm
currently writing a review of the book.

:- Anjo, !.

%--------------------------------------------------------------------------
%			    Anjo Anjewierden	NET: anjo@swi.psy.uva.nl
%
%   Department of Social Science Informatics
%   University of Amsterdam, Herengracht 196	TEL: +31 20 525 2337
%         1016 BS Amsterdam, The Netherlands    FAX: +31 20 525 2347
%---------------------------------------------------------------------------