%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% CSE 428 -- SPRING 2000 -- SOLUTION OF ASSIGNMENT 9 %%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% EXERCISE 1

brother(X,Y) :- father(Z,X), father(Z,Y), not(X=Y).

uncle(X,Y) :- father(Z,Y), brother(Z,X).

cousin(X,Y) :- father(Z,X), father(W,Y), brother(Z,W).

grandson(X,Y) :- father(Z,X), father(Y,Z).

descendant(X,Y) :- father(Y,X).
descendant(X,Y) :- father(Z,X), descendant(Z,Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% EXERCISE 2

path(X,X).
path(X,Y) :- arc(X,Z), path(Z,Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% EXERCISE 3

sublist(L1,L2) :- append(L,M,L2), append(K,L1,L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% EXERCISE 4

flat([],[]).
flat([L|K],[L|M]) :- not_list(L), flat(K,M).
flat([L|K],M) :- flat(L,L1), flat(K,K1), append(L1,K1,M).
                      
not_list(X) :- not(X=[]), not(X=[_|_]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% EXERCISE 5

quicksort([],[]).
quicksort([X|L],K) :- split(X,L,L1,L2),
                      quicksort(L1,K1),
                      quicksort(L2,K2),
                      append(K1,[X|K2],K).
split(_,[],[],[]).
split(X,[Y|L],K,[Y|M]) :- X < Y, split(X,L,K,M).
split(X,[Y|L],[Y|K],M) :- X >= Y, split(X,L,K,M).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%