% Define edges in a directed graph

edge(a,b).

edge(a,e).

edge(b,d).

edge(b,c).

edge(c,a).

edge(e,c).

edge(e,f).

% Compute various paths over the above edges

edge2(Node1, Node2) :- edge(Node1, Se), edge(Se, Node2).

edge3(Node1, Node3) :- edge(Node1, S1), edge(S1, S2), edge(S2, Node3).

edge3a(N1, N2) :- edge(N1, S1), edge2(S1, N2). 

path(N1, N2) :- edge(N1, N2).

path(N1, N2) :- edge(N1, S1), path(S1, N2).

path(X, X).



% is a value a member of a list

mem(A, [A|Tail]).

mem(A, [B|Tail]) :- mem(A, Tail).


% append to a list
% my implementation rather than the one included with prolog
appgt([], X, X).
appgt([H|T], X, [H|NT]) :- appgt(T, X, NT).




% reverse a list
rse([], []).
rse([H|Tail], Res) :- rse(Tail, TaRse), append(TaRse, [H], Res).
inform(Tail) :- write([remaining,Tail]).


% is a list a palindrome
% a list is palindromic if it is the same as its reverse
pali(A) :- pali(A,X), rse(A,X).
pali([],[]).
pali([X|At], [X|Bt]) :- pali(At, Bt).

% a different way of checkin for palindromes
pali3([]).
pali3(A) :- pali3(A, A, X).
pali3(A,B):-fail.
pali3([],[],[]).
pali3([], [X|Y], [X|Z]) :- pali3([], Y,Z).
pali3([], A, B) :- nl, write([no]), pali3(A,B).
pali3([H|T],B,X) :- append([H], X, App), pform(T, B, App), pali3(T,B,App).
pform(T, X,Y):-nl, write(T), write(X), write(Y).

%% recognize a*b*
ab([], q1).
ab([], q2).
ab([]).
ab(X) :- ab(X, q1).
ab([a|X], q1) :- ab(X, q1).
ab([b|X], q1) :- ab(X, q2).
ab([b|X], q2) :- ab(X, q2). 


% recognize a^nb^n
anbn([]).
anbn([a|X]) :- anbn(X, [a]).
anbn([a|X], App) :- anbn(X, Res), append([a], App, Res).
anbn([b|X], [C|Y]) :- anbn(X,Y).
anbn([], []).

 a different way of doin a^nb^n
anbn2([]).
anbn2([a|T]) :- anbn2(T, 1).
anbn2([], 0).
anbn2([a|T], N) :- anbn2(T, Sm), plus(N, 1, Sm).
anbn2([b|T], N) :- anbn2(T, Sm), plus(N, -1, Sm).


% a^nb^nc^n
abc([]).
abc([a|X]) :- abc(X, [a]).
abc([a|X], App) :- abc(X, Res), append([a], App, Res).
abc([b|X], [C|Y]) :- abc(X,Y, [b]).
abc([b|X], [C|Y], App) :- abc(X, Y, Res), append([b], App, Res).
abc([c|X], [], [C|Y]) :- abc(X, [], Y).
abc([], [], []). 


% (abcd)*
abcd(X) :- abcd(s1, X).
abcd(s1, []).
abcd(s1, [a|X]) :- abcd(s2, X).
abcd(s2, [b|X]) :- abcd(s3, X).
abcd(s3, [c|X]) :- abcd(s4, X).
abcd(s4, [d|X]) :- abcd(s1, X). 



% length
leng([], 0).
leng([B|X], Summ) :- leng(X, Res), plus(Res, 1, Summ).



% count the a
acou([], 0).
acou([a|X], Summ) :- acou(X, Res), plus(Res, 1, Summ).
acou([B|X], Summ) :- acou(X, Summ).

% count the occurrences of something
cnt(A, [], 0).
cnt(A, [A|T], Summ) :- cnt(A, T, Res), plus(Res, 1, Summ).
cnt(A, [B|T], Summ) :- cnt(A, T, Summ).
 


% nth fibbonacci number
fib(0, 0).
fib(1,1).
fib(N,Res) :- plus(N, -2, R), fib(1,1,R,Res).
fib(X,Y,0,Res) :- plus(X,Y, Res).
fib(X, Y, A, Res) :- plus(X, Y, Ss), plus(A, -1, Ad), fib(Y, Ss, Ad, Res).


% golden ration from Nth fibbonacci
gr(0, 0).
gr(1,1).
gr(N,Res) :- plus(N, -2, R), gr(1,1,R,Res).
gr(X, Y, A, Res) :- plus(X, Y, Ss), plus(A, -1, Ad), gr(Y, Ss, Ad, Res).



% countdown list
ctl(0, []).
ctl(N, Res) :- plus(N, -1, S), append([N], Tl, Res), ctl(S, Tl). 
  

% flatten a list
flt([], []).
flt([A|T],B) :- atom(A), flt(T, Rb), append([A], Rb, B).
flt([A|T], B) :- append(A,T,App), pp(A,T, app), flt(App, B).
pp(X,Y,Z) :- nl, write(X), write(Y), write(Z).


% another way of flattening a list
flt2([],[]).
flt2([[A]|T), B) :- flt2(A,C), flt2(T, Rb), append(C, Rb, B).
flt2([A|T], B) :- flt2(T,Rb), append([A], Rb, B).