Path: utzoo!attcan!uunet!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: The Craft of Prolog pp. 126-130
Message-ID: <4211@goanna.cs.rmit.oz.au>
Date: 6 Nov 90 09:28:48 GMT
References: <4473@swi.swi.psy.uva.nl> <7299.273583de@swift.cs.tcd.ie>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 47

In article <7299.273583de@swift.cs.tcd.ie>, brady@swift.cs.tcd.ie writes:
> I've been trying to run this to examine it. It's missing the select/3
> clauses, & I don't have the book. Could you post them please?

select/3 remains as it has been for the past 11+ years:

	select(X, [X|L], L).
	select(X, [H|T], [H|R]) :-
		select(X, T, R).

(If you have the DEC-10 Prolog, C Prolog, or QP libraries, you already
have it.)  The point is that the example starts out as

	answer(Solution) :-
		Solution = [D1,D2,D3,D4,D5,D6,D7,D8,D9],
		perm([1,2,3,4,5,6,7,8,9], Solution),
		forall(append(D1_to_N, _, Solution), (
		    length(D1_to_N, N),
		    divisible(N, D1_to_N)
		)).

The first step is to open up the call to perm/2 (producing 9 calls to
select/3) and expand the forall/2 (producing 9 calls to divisible/2).
Then we start shuffling things around, reducing ranges, eliminating
redundant tests, and so on.  The final version in the book can be
improved (following Anjo's observation) to

	answer([D1,D2,D3,D4, 5, D6,D7,D8,D9]) :-
		select(D1, [1,3,7,9], R1),
		select(D2, [2,4,6,8], R2),
		select(D3, R1, R3), ((D1*10+D2)*10+D3) mod 3 =:= 0,
		select(D4, R2, R4), (D3*10+D4) mod 4 =:= 0,
		select(D6, R4, [D8]), (D4*100+50+D6) mod 6 =:= 0,
		select(D7, R3, [D9]), ((D6*10+D7)*10+D8) mod 8 =:= 0,
		divisible(7, [D1,D2,D3,D4,5,D6,D7]).
		
But that can't be improved any further, because while it is reasonable
to expect a Prolog system to handle integers in < 1000, the seven
decimal digits we need in the last test are more than some otherwise
ok Prologs can provide.  (Actually, DEC-10 Prolog _could_ provide the
necessary 24 bits, but only within a single expression; Anjo's code
would not have worked.)


-- 
The problem about real life is that moving one's knight to QB3
may always be replied to with a lob across the net.  --Alasdair Macintyre.