🚀 go-pugleaf

In article <1600011@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes:
>
>Here is the problem...
>
>Assume a relation "Y is contained in X", specified as:
>	contains( ?X, ?Y ).
>
>Assume also, two global predicates p/1 and q/1. (As is always the case in 
>these problems, p and q are expensive to compute :-).
>
>The problem is to define a predicate exactly_one/2:
>
>	exactly_one( +X, ?Y )
>	is true if X contains Y,  Y satisfies p/1 and all of the other
>	Y' contained by X satisfy q/1.
>
>Any offers?
>

Is this really supposed to be exactly_one?  If so, then you want a restriction
that none of the Y' satisfy p/1.  Of course, you could just have a negation of
p/1 as the first condition of q/1 to achieve this given the above definition.

First, a little proof:

Define CX as the cardinality (number of members) of X, CY as the cardinality of
Y, and CY' as the cardinality of Y'
________

THM: If exactly_one succeeds, then q/1 will be executed AT LEAST CY' times and 
   p/1 will be executed AT LEAST once.

This is clear since you have to find the Y which will satisfy p/1 and you must
also presumably check all the other Y' to make sure they satisfy q/1.
________

Now, since CY' = CX - 1, and since we need to make CY' calls to q/1 we may make
CX calls to q/1 without worrying too much more about efficiency (one extra
call).  Having made these calls, one of three possibilities will be true:

1. All q/1 will succeed
2. All but 1 q/1 will succeed
3. At least 2 q/1 will fail

In the first case, we must go on to check each potential Y in X to find one 
that satisfies p/1.  If there is only one, then this step will take (on average)
CX/2 calls to p/1.  The worst case is, of course CX, and the best case is 1 
(first try).

In case 2, as soon as q/1 fails, we should check to see if the offending Z
satisfies p/1 if it does, then we have found Y and we must check the
remaining Y' to determine if they satisfy q/1.  If the offending Z does not
satisfy p/1, then the algorithm fails, since we have found a Z in X which is
neither Y nor in Y'.

If Z satisfies p/1 and the check of the remaining unchecked member of
Y' reveals a failure, then exactly_once fails.

---
Thumbnail Analysis:

1. All q/1 will succeed
-- Takes CX calls to q/1 + CX/CY (on average) calls to p/1
   This is becuase all of X is checked for a candidate Y (calls to q/1).  
Finding none, each member of X must be checked until one satisfies p/1.
Assuming the CY possible Y are evenly distributed over X, the second step will
take CX/CY calls to p/1

2. All but 1 q/1 will succeed
-- Takes CX calls to q/1 + 1 call to p/1
   The CX calls are made since we must check all q/1 to find the only one 
which does not succeed.  It must therefore be Y and satisfy p/1.  If it does
not satisfy  p/1, then the algorithm takes only (on average) CX/2 calls to q/1
+ 1 call to p/1.

3. At least 2 q/1 will fail
-- Takes (on average) 2*CX/N+1 calls to q/1 + 1 call to p/1
-- (N is the number of members of X which fail q/1)
   Actually, it's better than this.  We make calls to q/1 until failure occurs.
When the failure occurs, if p/1 fails on that candidate, then we are done (in
CX/N calls to q/1 + 1 call to p/1).  On the other hand, if p/1 succeeds, then 
we must continue checking using q/1 until another failure.  Notice that if N=1
then this degenerates to case #2.

Thus, in the two cases where there is at least one Z in X which does not satisfy
q/1, my algorithm makes the minimum number of calls.  In the case where all X
satisfy q/1, my algorithm must make CX/2 calls more than minimum.  However, I
maintain that this is unavoidable by any algorithm, though I can't seem to
prove it.

=========
STOP HERE - Only the bold go further and many will not return.

Although I shudder at the thought of posting code because my style is so bad,
here's a shot.

My Algorithm:

% find_Z(+List, -Z, -Remainder) looks through the list of candidates and returns
% the first Z which does not satisfy q/1.  It also returns the remainder of the
% list of candidates.  If all candidates satisfy q/1, then find_Z fails.

find_Z([],_,[]) :- !, fail.

find_Z([Candidate|Rest], Z, Remainder) :-
   q(Candidate),
   find_Z(Rest,Z,Remainder).

find_Z([Z|Remainder],Z,Remainder).


% find_Y(+List,-Y) looks through the list (which is X originally) and finds a
% member which satisfies p/1.  If no member satisfies p/1 then find_Y fails.

find_Y([],_) :- !, fail.

find_Y([Candidate|Rest], Candidate) :-
   p(Candidate).

find_Y([_|Rest], Y) :-
   find_Y(Rest, Y).

% exactly_one(+X,-Y) uses find_Z/3 to check each member of X to find one that 
% does not satisfy q/1.  If any Y of X do not satisfy q/1 then Y must satisfy
% p/1 and all remaining X must satisfy q/1.  If all X satisfy q/1 then at least
% one Y of X must satisfy p/1

exactly_one(X, Y) :-
   find_Z(X, Y, Remainder),
   !,
   p(Y),
   not(find_Z(Remainder,_,[])).

exactly_one(X, Y) :-
   find_Y(X, Y).

Matthew Merzbacher	ARPA:	matthew@CS.UCLA.EDU
4 line signature	UUCP:	...!{cepu|ihnp4|sdcrdcf|ucbvax}!ucla-cs!matthew
limit is retarded	NOTENET:	...!bach%mozart!matthew@beethoven