%% family (Simpsons) problems:

%% grandparent(X, Y)
grandparent(X, Y) :- parent( X, Z ), parent( Z, Y ).

%% siblings(X,Y)
siblings(X,Y) :- parent(Z,X), parent(Z,Y), X \== Y.

%% cousins(X, Y)
cousins(X, Y) :- parent(Z, X), siblings(Z, Z2), parent(Z2, Y).

%% hasYS(X) - X has a strictly younger sister
hasYS(X) :- siblings(X,Y), female(Y), age(Y,AY), age(X,AX), AY < AX.


%% hasFirstGC(X)
%%
%% This is a little bit tricky... the predicate hasFirstGC(X)
%% is true if X has a parent Y and one of X's children is Y's OLDEST
%% grandchild, i.e., Y has no grandchildren older than X's oldest child.
%% However, this predicate should be FALSE (fail) if X has no children.
%% Similarly, this predicate should be FALSE (fail) if X has no parents.
%
hasOlderGrandchild(G, Age) :- grandparent(G,GC), age(GC,AGC), AGC > Age.

hasFirstGC(X) :- parent(G,X), parent(X,C), age(C,AC), \+hasOlderGrandchild(G, AC).



%% Lists (trees, graphs) problems:

% removeOne(E, L)
removeOne( E, [E|R], R ).
removeOne( E, [F|R], [F|S] ) :- removeOne( E, R, S ).

% count( E, L, N ) ~ E appears exactly N times in L
count( _, [], 0 ).
count( X, [X|R], N ) :- count(X,R,M), N is M+1.
count( X, [Y|R], N ) :- nonvar(Y), count(X,R,N), nonvar(X), X \== Y.

% find( Pat, Target, Index ) ~ the list Pat appears as a contiguous sublist
%                              of the list Target at index Index
find( [X], [X|_], 0 ).
find( [PX|PR], [PX|R], 0 ) :- find( PR, R, 0 ).
find( P, [_|R], N ) :- find( P, R, M ), N is M+1.

% depth( E, Tree, D ) ~ if E is at depth D in tree Tree
depth( Data, [ Data, _, _ ], 0 ).
depth( Data, [ _, L, R ], D ) :- depth( Data, L, Shallow ), D is Shallow + 1.
depth( Data, [ _, L, R ], D ) :- depth( Data, R, Shallow ), D is Shallow + 1.

% insert( E, Tree, NewTree ) ~ if NewTree is Tree with E inserted
insert( Data, [ ], [ Data, [], [] ] ).
insert( Data, [ Data, L, R ], [ Data, L, R ] ).
insert( Data, [ Root, L, R ], [ Root, L2, R ] ) :- Data < Root, insert( Data, L, L2 ).
insert( Data, [ Root, L, R ], [ Root, L, R2 ] ) :- Data > Root, insert( Data, R, R2 ).

% kid( Parent, G, K ) ~ if K is a child of Parent in graph G
kid( P, Graph, K ) :- member( [P,K], Graph ).

% path( A, B, G, Path ) ~ if Path is a path from A to B in G
path( X, X, Graph, [X] ).
path( X, Y, Graph, [X|R] ) :- kid( X, Graph, K ), path( K, Y, Graph, R ).