PROLOG

fact(0,1).
fact(1,1).
fact(N, F):- N>1, N1 is N-1, fact(N1, F1), F is N*F1. %Factorial of an integer

sumfact(U,U,S):- fact(U,F), S is F.
sumfact(U,V,S):- V>=U, fact(V,F), X is V-1, sumfact(U,X,S1), S is S1+F. %Sum of factorials within a range

mypow(X,1,X).
mypow(X,0,1).
mypow(X,Y,P):- Y>0, Y1 is Y-1, mypow(X,Y1,P1), P is X*P1.
mypow(X,Y,P):- Y<0, Y1 is -Y, mypow(X,Y1,P1), P is 1/P1. %Calculate X^Y

myexp(P,0,1).
myexp(P,Q,E):- Q>0, Q1 is Q-1, myexp(P,Q1,E1), fact(Q, FACT), mypow(P,Q,POW), E is E1 + POW/FACT, !. % E = 1+P+P^2/2!+...+P^Q/Q!

gcd(A,B,G):- R is A mod B, R=0, G is B.
gcd(A,B,G):- R is A mod B, R>0, gcd(B,R,G). % hcf of two nos.


myappend([],L2,L2).
myappend([H|L1],L2,[H|T]):-myappend(L1,L2,T). % append two lists

count([_|Y],C):- count(Y,C1), C is C1+1.
count([],0). % length of a list

cpf([X|Y],N,[X|L]):- N1 is N-1, cpf(Y,N1,L).
cpf([X|Y],1,[X|[]]). % copy first N elements of a list

tail([X|Y],N,L):- N1 is N-1, tail(Y,N1,L).
tail([_|Y],1,Y). % show last N elements of a list

cpl([X|Y],N,L):- count([X|Y],C), N1 is C-N, tail([X|Y],N1,L).
cpl([_|Y],1,Y). % copy last N elements of a list

dividelist(L,A,B):- count(L,C), C1 is round(C/2), C2 is C-C1, cpf(L,C1,A), cpl(L,C2,B). % divide a list equally

splice(L,1,N,T):-cpf(L,N,T).
splice(L,M,N,T):- M1 is M-1,N1 is N-M1, tail(L,M1,T1), cpf(T1,N1,T). // extract M to N indices from a list

last(L,K):- count(L,C), C1 is C-1, tail(L,C1,K). % last element of a list

find([H|L],K,X):- K1 is K-1, find(L,K1,X).
find([H|L],1,H).  % find element in Kth position

search([H|L],K,X):- K=H, X is H, write('Found'),!.
search([H|L],K,X):- count([H|L],C), C1 is C-1, search(L,K,X).
search([],_,_):- write('Not found'). %Linear search

reverse([A|[]],[A|[]]).
reverse([H|L],T):- reverse(L,T1), myappend(T1,[H|[]],T). %Reverse list

replace(L,P,K,T):- P1 is P-1, cpf(L,P1,X),tail(L,P,Y), myappend(X,[K|[]],T1), myappend(T1,Y,T). %replace a given position with a new element

insert(L,P,K,T):- P1 is P-1, cpf(L,P1,X), tail(L,P1,Y), myappend(X,[K|[]],T1), myappend(T1,Y,T). %insert at a given position

delete(L,P,T):- P1 is P-1, cpf(L,P1,X), tail(L,P,Y), myappend(X,Y,T). %delete element from a given position


min([A|[]],A). % Minimum element in a list
less(A,B,R):- A=<B, R is A.
less(A,B,R):- B<A, R is B.
min([A|B],M):- min(B,M1),less(A,M1,M).

dellist([],_,[]).
dellist([X|Y],X,Y).
dellist([X|Y],M,N):-dellist(Y,M,N1), myappend([X|[]],N1,N). %Delete a specified element from a list


selectionsort([A|[]],[A|[]]).
selectionsort([A|B],[X|Y]):- min([A|B],X), dellist([A|B],X,Y1), selectionsort(Y1,Y). % Selection sort

palindrome(A):- reverse(A,B), A\=B, write('Not palindrome').
palindrome(A):- reverse(A,B), A=B, write('Palindrome'). % Checks whether a list is palindrome

rduplist([],_,[]).
rduplist([A|[]],A,[]).
rduplist([A|[]],_,[A|[]]).
rduplist([X|Y],X,Z):- rduplist(Y,X,Z).
rduplist([X|Y],M,R):- rduplist(Y,M,R1), myappend([X|[]],R1,R),!. %Remove all duplicates of a specified no.

rduplistall([],[]).
rduplistall([X|Y],[X|L]):- rduplist(Y,X,L1),rduplistall(L1,L). %Remove all duplicates from a list.


rleft([],_,[]).
rleft([X|Y],N,L):- cpf([X|Y],N,L1), tail([X|Y],N,L2), myappend(L2,L1,L). %rotate left

rright([],_,[]).
rright([X|Y],N,L):- count([X|Y],C), N1 is C-N, cpf([X|Y],N1,L1), cpl([X|Y],N,L2),myappend(L2,L1,L). %rotate right


tree(1, tree(2, tree(3,nil,nil), tree(4,tree(5,nil,nil), tree(6,nil,nil))), tree(7, nil, tree(8,tree(9,nil,nil),nil))).
preorder(tree(X,_,_),X).
preorder(tree(_,L,_),X):- inorder(L,X).
preorder(tree(_,_,R),X):- inorder(R,X).

inorder(tree(_,L,_),X):- inorder(L,X).
inorder(tree(X,_,_),X).
inorder(tree(_,_,R),X):- inorder(R,X).

postorder(tree(_,L,_),X):- postorder(L,X).
preorder(tree(_,_,R),X):- postorder(R,X).
preorder(tree(X,_,_),X).

leaves(nil,0).
leaves(tree(_,nil,nil),1).
leaves(tree(_,L,R),C):-  leaves(L,C1), leaves(R,C2), C is C1+C2.

edge(1,2).
edge(2,3).
edge(2,1).
edge(3,1).
edge(3,1).
edge(3,4).

vertex(1).
vertex(2).
vertex(3).
vertex(4).

path(U,V,P):- vertex(U), vertex(V),edge(U,V), P is 1.
path(U,V,P):- vertex(U), vertex(V),edge(U,X), path(X,V,P), P is 1,!.

cycle(U,P):- edge(U,U), P is 1.
cycle(U,P):- path(U,X,_), path(X,U,_), !, P is 1.