/* Model-based diagnosis. Kennissystemen 2007
 * 0440949 Andreas van Cranenburgh
 * 0518808 Joris de Groot
 *
 * Data representation: possible solutions are lists of attribute-value pairs,
 * 	where the attribute stands for the name of a component, and the value
 *	for its output.
 *
 * Algorithms:
 *  - findfault: brute-force, using findall; wants all measurements (do not try
 *	with 2nd model)
 *  - correctfirst: assumes everything works and asks for first possible error
 *  - firstfault: takes two possible solutions and asks about first difference
 *		between them */

:- dynamic fact/1.	%used by 'findtwo' predicate

%the reference example with three multipliers and two adders
ex1 :-
	write('Welcome to the model-based fault-finder'), nl,
	write('Current model:'), listing(model(1,_)),
	OutputValues = [m1=_X, m2=_Y, m3=_Z, a1=_F, a2=_G],
	%reverse(OutputValues, ReverseValues), findfault(1, ReverseValues, OutputValues).
	firstfault(1, OutputValues).
	%correctfirst(1, OutputValues).

%a more complex example with six multipliers and four adders
ex2 :-
	write('Welcome to the model-based fault-finder'), nl,
	write('Current model:'), listing(model(2,_)),
	OutputValues = [m1=_X, m2=_Y, m3=_Z, a1=_F, a2=_G, m4=_H, m5=_I, m6=_J, a3=_K, a4=_L],
	correctfirst(2, OutputValues).

%taken from 2005 exam:
ex3 :-
	write('Welcome to the model-based fault-finder'), nl,
	write('Current model:'), listing(model(3,_)),
	OutputValues = [m1=_X, m2=_Y, a1=_Z, a2=_F, a3=_G],
	firstfault(3, OutputValues).
	%correctfirst(3, OutputValues).

%the models, input values are pre-defined
model(1, [m1=X, m2=Y, m3=Z, a1=F, a2=G]) :-
	A = 3, B = 2, C = 2, D = 3, E = 3,
	multiplier(A, C, X), 
	multiplier(B, D, Y),
	multiplier(C, E, Z),
		adder(X, Y, F),
		adder(Y, Z, G).

model(2, [m1=X, m2=Y, m3=Z, a1=F, a2=G, m4=H, m5=I, m6=J, a3=K, a4=L]) :-
	A = 7, B = 1, C = 21, D = 5, E = 9,
	multiplier(A, C, X), 
	multiplier(B, D, Y),
	multiplier(C, E, Z),
		adder(X, Y, F),
		adder(Y, Z, G),
	multiplier(F, A, H),
	multiplier(G, C, I),
	multiplier(H, I, J),
		adder(J, G, K),
			adder(K, X, L).

model(3, [m1=X, m2=Y, a1=Z, a2=F, a3=G]) :-
	A = 3, B = 2, C = 2, D = 3, E = 1,
	multiplier(A, B, X), 
	multiplier(C, D, Y),
		adder(X, Y, Z),
		adder(Y, E, F),
		adder(Z, F, G).

%get input from user, assume the domain is integers.
observable(X, Y) :-
	%might be handy to print expected value
	write('Enter output value of '), write(X), tab(2),
	readln([Y]), integer(Y).

%traverse a list of measurement points and ask what output the user sees,
%succeed when only one possible situation can lead to the collected measurement points
findfault(_, [], _) :-
	write('No conclusion reached'), nl.

findfault(Model, [Component=_Value|Values], AllValues) :-
	%observable(Component, UserInput), 
	%%substitute(AllValues, Component=UserInput, [], NewValues),
	(observable(Component, UserInput) ->
		substitute(AllValues, Component=UserInput, [], NewValues)
	;	NewValues = AllValues),
	findall(NewValues, model(Model, NewValues), List),
	length(List, N), write('Number of possibilities: '), write(N), nl, write(List), nl,
	(N = 0 ->
		write('This situation is impossible. Aborting'), nl, fail
	;	(N = 1 ->
			write('Only one possibility left: '), write(List), nl
		;	findfault(Model, Values, NewValues))).

/* Algorithm without findall:
 * - get values of a correctly working model
 * - ask first measurement (output value)
 * - get first possible model that explains this measurement
 * - try to confirm this model, by asking for measurements
 *   of those values that differ from the correctly working model. */
correctfirst(ModelNo, Input) :-
	copy_term(Input, Hypothesis),	%do deep-copy
	model(ModelNo, Hypothesis),
	member(X=Y, Input), var(Y),
	member(X=0, Hypothesis),
	write('Hypothesis: '), write(Hypothesis), nl,
	observable(X, NewY), 
	substitute(Input, X=NewY, [], NewInput),
	correctfirst(ModelNo, NewInput).

correctfirst(ModelNo, Input) :-
	(model(ModelNo, Input) ->
		write('Found solution:'), nl,
		write(Input)
	;	write('Impossible data; giving up')).

%succesively take two models and ask for an observable
%of the first difference between them.
firstfault(ModelNo, Input) :-
	copy_term(Input, Values),	%do deep-copy
	findtwo(Values, model(ModelNo, Values), [Hypothesis, AltHypothesis]),
	member(X=Y, Hypothesis),
	\+ member(X=Y, AltHypothesis),
	write('Current hypotheses: '), nl,
	write(Hypothesis), nl, write(AltHypothesis), nl,
	observable(X, NewY), 
	substitute(Input, X=NewY, [], NewInput),
	firstfault(ModelNo, NewInput).

firstfault(ModelNo, Input) :-
	(model(ModelNo, Input) ->
		write('Found solution:'), nl,
		write(Input)
	; write('Impossible data; giving up')).

%In a list of attribute=value pairs, do the given substitution
substitute([], _Component=_Value, Acc, Result) :-
	reverse(Acc, Result).
substitute([Component=_|List], Component=Value, Acc, Result) :-
	substitute(List, Component=Value, [Component=Value|Acc], Result), !.
substitute([H|List], Component=Value, Acc, Result) :-
	substitute(List, Component=Value, [H|Acc], Result).
	
%The adder and multiplier, with built-in failure mode
%also sports both a forward and backward mode of operation
adder(A, B, C) :-
	(nonvar(A), nonvar(B) -> C is A + B)
	; (nonvar(C), nonvar(B) -> A is C - B)
	; (nonvar(C), nonvar(A) -> B is C - A).
adder(A, B, 0) :-
	nonvar(A), nonvar(B).

multiplier(A, B, C) :-
	(nonvar(A), nonvar(B) -> C is A * B)
	; (nonvar(C), nonvar(B) -> A is C / B)
	; (nonvar(C), nonvar(A) -> B is C / A).
multiplier(A, B, 0) :-
	nonvar(A), nonvar(B).

%like findall but only finds two matches
findtwo(Term, Goal, List) :-
	call(Goal), 
	(fact(_) -> 
		asserta(fact(Term)) 
	; 	asserta(fact(Term)), fail),
	collect([], List).

collect(L, List) :-
	fact(X), retract(fact(X)),
	collect([X|L], List).
collect(List, List).