%% Tutorial 4 (Week 6) sample solutions

%% 1.  Cut & negation quiz.

r(1). r(2).
s(1). s(3).

%% This is to give practice with following what happens 

% | ?- r(X),!,s(Y).
% X = 1,
% Y = 1 ? 
% yes
% | ?- r(X), s(Y), !.
% X = 1,
% Y = 1 ? ;
% no
% | ?- r(X), \+(s(X)).
% X = 2 ? ;
% no
% | ?- r(X), !, \+(s(X)).
% no
% | ?- r(X), \+(r(X)).
% no
% | ?- \+(\+(r(X))). 
% true ? ;
% no
% | ?- \+(\+(r(3))).
% no



%% 2 Lists and strings


zip([],[],[]).
zip([X|Xs],[Y|Ys],[(X,Y)|XYs]) :- zip(Xs,Ys,XYs).

caesartable(T) :- 
	atom_chars('ABCDEFGHIJKLMNOPQRSTUVWXYZ',UC1),
	atom_chars('XYZABCDEFGHIJKLMNOPQRSTUVW',UC2),
	atom_chars('abcdefghijklmnopqrstuvwxyz',LC1),
        atom_chars('xyzabcdefghijklmnopqrstuvw',LC2),
	atom_chars(' ,.;:/?\'"0123456789()-',Punct),
	zip(UC1, UC2, L1),
	zip(LC1, LC2, L2),
	zip(Punct,Punct,L3),
	append(L1,L2, T1),
	append(L3,T1,T).

caesarchar(X,Y) :- caesartable(T), member((X,Y),T).

caesarlist([],[]).
caesarlist([X|L],[Y|M]) :- caesarchar(X,Y), caesarlist(L,M).

caesar(X,Y) :- atom_chars(X,L),
	      caesarlist(L,M),
	      atom_chars(Y,M).


%3 I/O

encode :- read(X),
	  caesar(X,Y),
	nl,
	write(Y),
	nl,
	translate.



%% 4 Using cut & negation.

fib(0,0). 
fib(1,1). 
fib(N,P) :- N >= 2, 
	M is N-1, fib(M,F), 
	L is M-1, fib(L,G), 
	P is F+G. 

%% (a)

fib1(0,0) :- !. 
fib1(1,1) :- !. 
fib1(N,P) :- N >= 2, !,  
	M is N-1, fib1(M,F), 
	L is M-1, fib1(L,G), 
	P is F+G. 

%% (b) Avoiding the inequality test.

fib2(0,0) :- !. 
fib2(1,1) :- !. 
fib2(N,P) :- !,
	M is N-1, fib2(M,F), 
	L is M-1, fib2(L,G), 
	P is F+G. 

%% (c) Using negation.

fib3(0,0). 
fib3(1,1). 
fib3(N,P) :- \+(N = 0), \+(N = 1),
	M is N-1, fib3(M,F), 
	L is M-1, fib3(L,G), 
	P is F+G. 

%% Probably not any more efficient than (a) or (b)...

%% Could be a good place to talk about how to put complicated goals inside \+.
%% For example:

fib4(0,0). 
fib4(1,1). 
fib4(N,P) :- \+((N = 0 ; N = 1)),
	M is N-1, fib4(M,F), 
	L is M-1, fib4(L,G), 
	P is F+G. 

%% 5 a
%% some test data

father(homer, bart).
father(homer,lisa).
father(abe,homer).
mother(marge,bart).
mother(marge,lisa).

person(homer).
person(abe).
person(lisa).
person(bart).
person(marge).

parent(X,Y) :- father(X,Y); mother(X,Y).

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Z) :- parent(X,Y), ancestor(Y,Z).

% i

descendants_of(X,Ys) :- setof(Y,ancestor(X,Y), Ys).

% ii

two_or_more_descendants(Xs) :- setof(X,Ys^(descendants_of(X,Ys),Ys=[_,_|_]),Xs).

% iii

no_descendants_using_findall(Xs) :- setof(X,(person(X),findall(Y,ancestor(X,Y),[])),Xs).

no_descendants_using_negation(Xs) :- setof(X,(person(X),\+(ancestor(X,_))),Xs).			  
%% 5 b Setof/bagof

flatten(Ls,Xs) :- setof(X, Y^(member(Y,Ls), member(X,Y)),Xs).
flatten2(Ls,Xs) :- bagof(X, Y^(member(Y,Ls), member(X,Y)),Xs).
flatten3(Ls,Xs) :- findall(X, Y^(member(Y,Ls), member(X,Y)),Xs).

flatten4(Ls,Xs) :- setof(X, (member(Y,Ls), member(X,Y)),Xs).
flatten5(Ls,Xs) :- bagof(X, (member(Y,Ls), member(X,Y)),Xs).
flatten6(Ls,Xs) :- findall(X, (member(Y,Ls), member(X,Y)),Xs).


%% 6 Tabling  caesar
:- dynamic table/2.

buildcaesar :- caesartable(T), assertallpairs(T).
assertallpairs([]).
assertallpairs([(X,Y)|T]) :- assert(table(X,Y)), assertallpairs(T).

caesarlist_2([],[]).
caesarlist_2([X|L],[Y|M]) :- table(X,Y), caesarlist_2(L,M).

caesar_2(X,Y) :- atom_chars(X,L),
	caesarlist_2(L,M),
	atom_chars(Y,M).

test :- read(X),
	caesar_2(X,Y),
	nl,
	write(Y),
	nl,
	test.

