%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% find paths in directed graphs


%% path: does there exist a path in G from N to M
path(nil,N,N).
path(cons(_,G),N,M) :- path(G,N,M).
path(cons(edge(I,J),G),N,M) :- path(G,N,I), path(G,J,M).


example(cons(edge(1,2),cons(edge(2,1),cons(edge(2,2),cons(edge(1,3),cons(edge(2,3),cons(edge(3,4),cons(edge(4,4),nil)))))))).




%% list concatenation

append(nil,YS,YS).
append(cons(X,XS),YS,cons(X,ZS)) :- append(XS,YS,ZS).

%% path with output, last element contains list of edges

pathWO(nil,N,N,nil).
pathWO(cons(_,G),N,M,P) :- pathWO(G,N,M,P).
pathWO(cons(edge(I,J),G),N,M,P) :- 
  pathWO(G,N,I,P1), 
  pathWO(G,J,M,P2), 
  append(P1,cons(edge(I,J),P2),P).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% palindroms

%% last element of a list

last(cons(X,nil),X).
last(cons(_,cons(X,XS)), Y) :- last(cons(X,XS),Y).


%% delete last element of a list

deleteLast(cons(_,nil),nil).
deleteLast(cons(X,cons(Y,YS)),cons(X,ZS)) :- deleteLast(cons(Y,YS),ZS).


%% first version of palindrom: check from front and end

palindrom1(nil).
palindrom1(cons(_,nil)).
palindrom1(cons(X,cons(Y,YS))) :- 
  last(cons(Y,YS),X), 
  deleteLast(cons(Y,YS),ZS),
  palindrom1(ZS).



%% second version is based on stack automata

palindrom2(XS) :- palin21(XS,nil).
palin21(cons(X,XS),YS) :- palin21(XS,cons(X,YS)).
palin21(XS,YS) :- palin22(XS,YS).
palin21(cons(_,XS),YS) :- palin22(XS,YS).
palin22(nil,nil).
palin22(cons(X,XS),cons(X,YS)) :- palin22(XS,YS).



%improvement: delete palin22 and use this palin21
palin21_(XS,XS).
palin21_(cons(_,XS),XS).
palin21_(cons(X,XS),YS) :- palin21(XS,cons(X,YS)).



%% third version is based on reverse
reverse(XS,YS) :- rev(XS,nil,YS).
rev(nil,YS,YS).
rev(cons(X,XS),YS, ZS) :- rev(XS,cons(X,YS),ZS).

palindrom3(X) :- reverse(X,X).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ordered trees

%gt/2 (greater than) has to be implemented (deleted it)

insert1(X,leaf,node(X,leaf,leaf)).
insert1(X,node(Y,TL,TR),node(Y,ITL,TR)) :- gt(Y,X), insert(X,TL,ITL).
insert1(X,node(Y,TL,TR),node(Y,TL,ITR)) :- gt(X,Y), insert(X,TR,ITR).

%bad: no insertion of a value already in the tree 
%     like in insert(s(0),node(s(0),leaf,leaf),T).

%solution: gt/2 -> ge/2 (greater equal)

insert2(X,leaf,node(X,leaf,leaf)).
insert2(X,node(Y,TL,TR),node(Y,ITL,TR)) :- ge(Y,X), insert(X,TL,ITL).
insert2(X,node(Y,TL,TR),node(Y,TL,ITR)) :- ge(X,Y), insert(X,TR,ITR).

% yields multiple solutions (insertion non-deterministic for values
  already in the tree)
% => next idea, make a function from ge: ge/2 -> ge/3

insert3(X,leaf,node(X,leaf,leaf)).
insert3(X,node(Y,TL,TR),node(Y,ITL,TR)) :- ge(Y,X,true), insert(X,TL,ITL).
insert3(X,node(Y,TL,TR),node(Y,TL,ITR)) :- ge(Y,X,false), insert(X,TR,ITR).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% arithmetic

add(0,Y,Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).

mult(0,_,0).
mult(s(X),Y,Z) :- add(Y,Z1,Z), mult(X,Y,Z1).



% prime check using multiplication

% only the test of not being a prime number
noprime(X) :- mult(s(s(_)),s(s(_)),X).

% or with proof (giving two factors)
split(X,s(s(P1)),s(s(P2))) :- mult(s(s(P1)),s(s(P2)),X).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% utils
zahl(0,0).
zahl(N,s(M)) :- N > 0, N1 is N-1, zahl(N1,M).

lhaz(0,0).
lhaz(s(Z),N) :- lhaz(Z,N1), N is N1+1.
