
/************************************************************************
*									*
*	There are twelve coins, visibly indistinguishable, but one of	*
*	which is false. The eleven true coins all weigh the same, but	*
*	the false coin has a slightly different weight.  You have a set	*
*	of scales that you can use to compare the weights of two piles	*
*	of coins. You may use the scales to discover which coin is	*
*	false, and whether it weighs more, or less, than the others.	*
*	The only constraint is that you may only use the scales for	*
*	three weighings. How do you proceed?				*
*									*
*	Problem posed by Matthias Rieger (original source? ...)		*
*	This solution by Oscar Nierstrasz 24.11.96.			*
*									*
************************************************************************/

% =======================================================================
% ===== SOLUTION ========================================================

/************************************************************************
*									*
*	findFalse -- report which of twelve coins is heavier or lighter *
*									*
*	This is the main predicate, which can be called if		*
*	weight(X,W) defines a weight W for each coin X.			*
*									*
************************************************************************/

findFalse :-
	firstTest([1,2,3,4,5,6,7,8,9,10,11,12]).

% =======================================================================

% One of A-L is false
firstTest([A,B,C,D,E,F,G,H,I,J,K,L]) :-
	GroupA = [A,B,C,D],
	GroupB = [E,F,G,H],
	GroupC = [I,J,K,L],
	print('	FIRST WEIGHING'), nl,
	heavier(GroupA, GroupB, Which),
	( Which == neither, secondTestA(GroupC, GroupA) % => IJKL false
	; Which == first,   secondTestB(GroupA, GroupB, GroupC) % => ABCD > EFGH
	; Which == second,  secondTestB(GroupB, GroupA, GroupC) % => EFGH > ABCD
	).

% -----------------------------------------------------------------------

% One of A-D is false; X is true
secondTestA([A,B,C,D], [X|_]) :-
	print('	SECOND WEIGHING (A)'), nl,
	heavier([A,B], [C,X], Which),
	( Which == neither, thirdTestA(D, X)  % => D is false
	; Which == first,   thirdTestC(A,B,C) % =>  AB > CX
	; Which == second,  thirdTestD(C,A,B) % => CX > AB
	).

% ABCD > EFGH; X is true
secondTestB([A,B,C,D], [E,F,G,H], [X|_]) :-
	print('	SECOND WEIGHING (B)'), nl,
	heavier([A,E,X], [B,F,G], Which),
	( Which == neither, thirdTestC(C,D,H) % => CD > HX
	; Which == first,   thirdTestD(A,F,G) % => AX > FG
	; Which == second,  thirdTestB(B,E,X) % => B > E
	).

% -----------------------------------------------------------------------

% A is false; X is true
thirdTestA(A,X) :-
	print('	THIRD WEIGHING (A)'), nl,
	heavier([A], [X], Which),
	( Which == neither, print('IMPOSSIBLE'), nl
	; Which == first,   isFalse(A, heavier)
	; Which == second,  isFalse(A, lighter)
	).

% A > B; X is true
thirdTestB(A,B,X) :-
	print('	THIRD WEIGHING (B)'), nl,
	heavier([A], [X], Which),
	( Which == neither, isFalse(B, lighter)
	; Which == first,   isFalse(A, heavier)
	; Which == second,  print('IMPOSSIBLE'), nl
	).

% Aside -- we can also implement this predicate as follows:
% thirdTestB(A,B,X) :- thirdTestC(A,X,B).

% AB > CX; X is true
thirdTestC(A,B,C) :-
	print('	THIRD WEIGHING (C)'), nl,
	heavier([A], [B], Which),
	( Which == neither, isFalse(C, lighter)
	; Which == first,   isFalse(A, heavier)
	; Which == second,  isFalse(B, heavier)
	).

% AX > BC; X is true
thirdTestD(A,B,C) :-
	print('	THIRD WEIGHING (D)'), nl,
	heavier([B], [C], Which),
	( Which == neither, isFalse(A, heavier)
	; Which == first,   isFalse(C, lighter)
	; Which == second,  isFalse(B, lighter)
	).

% Aside -- thirdTestD is complementary to thirdTestC
% We could make heavier/lighter a parameter and use just a single predicate.

% -----------------------------------------------------------------------

% Print utility
isFalse(F, Status) :-
	print('Coin #'), print(F), print(' is '), print(Status), nl.

% -----------------------------------------------------------------------

% Reports which list of coins is heavier (first, second or neither)
heavier([], [], neither).
heavier([X|XS], [Y|YS], Which) :-
	weight(X,XW), weight(Y,YW),
	( XW > YW, Which = first
	; XW < YW, Which = second
	; XW == YW, heavier(XS, YS, Which)
	).

% =======================================================================
% ===== TESTING =========================================================

/************************************************************************
*									*
*	doTest(X, Status) -- set coin X to be heavier/lighter, and test	*
*	weight(X,W) -- weight of coin X is W				*
*									*
*	You can, of course, implement your own weight predicate.	*
*	This one is simple, because you just need to call dotest()	*
*	to change the weight predicate.					*
*									*
************************************************************************/

doTest(X,Status) :-
	print('TEST CASE: '), print(X), print(' is '), print(Status), nl,
	setFake(X, Status), findFalse, nl.

% Remember which coin is fake
setFake(X, Status) :-
	removeFalse,
	assert(fake(X, Status)).

% Forget which coin was previously fake.
removeFalse :-
	retract(fake(X,Status)),
	removeFalse.
removeFalse.

% A true coin weighs 10; a false coin weighs 9 or 11
weight(X,W) :-
	( fake(X, lighter), W = 9
	; fake(X, heavier), W = 11
	; W = 10
	).

/************************************************************************
*									*
*	test -- test all cases of coins 1-12 heavier or lighter		*
*									*
*	Run this to exhaustively test all cases.			*
*									*
************************************************************************/

test :-
	genTest([1,2,3,4,5,6,7,8,9,10,11,12]).

genTest([X|XS]) :-
	doTest(X, heavier),
	doTest(X, lighter),
	genTest(XS).

genTest([]) :-
	print('FINISHED TESTING'), nl.

% =======================================================================

