%% Задачи от упражнения 2013-2014, Н. Белухов
%%%%%%%%%%%%%
%%% LISTS %%%
%%%%%%%%%%%%%

%% head(E, L) :- E is the head of the list L
head(E, [E|_]).

%% tail(E, L) :- T is the tail of the list L
tail(T, [_|T]).

%% fourth(E, L) :- E is the fourth element of the list L
fourth(E, [_,_,_,E|_]).

%% is_member(E, L) :- Checks if E is member of the list L
is_member(E, [E|_]).
is_member(E, [_|T]) :- member(E, T).

%% append_lists(X, Y, Z) :- Z is the result of appending X and Y together
append_lists([], Y, Y).
append_lists([X|Xs], Y, [X|L]) :- append_lists(Xs, Y, L).

%% remove_element(E, L, M) :- M is the result of removing the first appearance of E from L
remove_element(E, [E|T], T).
remove_element(E, [H|T], [H|S]) :- remove_element(E, T, S).

%% remove_element(E, L, M) :- second version
%remove_element(E, L, M) :- append_lists(A, [E|B], L), append_lists(A, B, M).

%% insert(E, L, M) :- M is the result of appending E at the begging of L
insert(E, L, M) :- remove_element(E, M, L).

%% is_perm(L, M) :- Checks if L is a permutation of M
is_perm([], []).
is_perm([H|T], M) :- is_member(H, M), remove_element(H, M, N), is_perm(T, N).

%% set(L) :- Checks if L is a multiset
set([]).
set([H|T]) :- not(is_member(H, T)), set(T).

%% subset(L, M) :- Checks if L is a subset of M
subset(L, M) :- not((is_member(E, L), not(is_member(E, M)))).

%% gensubset(L, M) :- Generates a subset of M in L 
gensubset([], []).
gensubset([H|T], [H|S]) :- gensubset(T, S).
gensubset(T, [_|S]) :- gensubset(T, S).

%% is_sorted(L) :- Checks if L is sorted (ascending order)
is_sorted([]).
is_sorted([_]).
is_sorted([A,B|T]) :- A =< B, is_sorted([B|T]).

%%%%%%%%%%%%%%
%%% MATRIX %%%
%%%%%%%%%%%%%%
% example: [[1,2,3], [4,5,6]]

%% transp(T, M) :- T is the transposition of the matrix M
heads([], []).
heads([H|S], [[H|_]|T]) :- heads(S, T).

% tails(result, matrix)
tails([], []).
tails([T|Ts], [[_|T]|S]) :- tails(Ts, S).

% M is an empty list of empty lists, so we need #flatten
transp([], M) :- flatten(M, []).
transp([H|T], M) :- heads(H, M), tails(U, M), transp(T, U).

%% transversal(T, F) :- Is T a trasversal for F
transversal(T, F) :- not((is_member(E, F), not((member(X, E), member(X, T))))).

%% min_trans(T, F) :- Is T a minimal transversal for F
min_trans(T, F) :- transversal(T, F), not((gensubset(T1, T), T1 \= T, transversal(T1, F))).

%%%%%%%%%%%%%%%%%%
%%% ARITHMETIC %%%
%%%%%%%%%%%%%%%%%%

%% list_length(N, L) :- The list L has length N
list_length(0, []).
list_length(N, [_|T]) :- list_length(N1, T), N is N1 + 1.

%% gennat(N) :- Generates natural numbers
gennat(0).
gennat(N) :- gennat(N1), N is N1 + 1.

%% is_nat(N) :- Is N a natural number
is_nat(0).
is_nat(N) :- N > 0, M is N - 1, is_nat(M).

%% between(A, B, C) :- Generates all natural numbers between B and C
between(B, B, C):- B =< C.
between(A, B, C) :- B1 is B + 1, B1 =< C, between(A, B1, C).

%% fibgen(F) :- Generates Fibonacci numbers
fibpair(0, 1).
fibpair(F, G) :- fibpair(H, F), G is H + F.

fibgen(0).
fibgen(1).
fibgen(F) :- fibpair(F, _).

%% is_fib(F) :- Is F a Fibonacii number?
fib(0, 0).
fib(1, 1).
fib(I, F) :- I >= 2, I1 is I - 1, I2 is I - 2,
			 fib(I1, F1), fib(I2, F2), F is F1 + F2.

is_fib(F) :- between(I, 0, F), fib(I, F).

%% div(X, A) :- X is a divisor of A
div(X, A) :- between(X, 1, A), 0 is A mod X.

%% cd(X, A, B) :- X is a common divisor of A and B
cd(X, A, B) :- div(X, A), div(X, B).

%% gcd(X, A, B) :- x is the greatest common divisor of A and B
gcd(X, A, B) :- cd(X, A, B), not((cd(Y, A, B), Y > X)).

%% fraction(A/B, C/D) :- C/D is the result of simplifying the fraction A/B 
fraction(A/B, C/D) :- gcd(X, A, B), C is A/X, D is B/X.

%% gen_triplet(X, Y, Z) :- Generates ordered triplets
gen_triplet(X, Y, Z) :- gennat(N), between(X, 1, N),
						between(Y, 1, N), between(Z, 1, N).

%% pyth(X, Y, Z) :- Generates pythagorean triplets
%pyth(X, Y, Z) :- gen_triplet(X, Y, Z), Z * Z is X * X + Y * Y.

%% term_at_depth(N, T) :- Generates all rt-terms T with depth <= from the given depth N
%% rt-term: [] or [A, [A, B]] where A and B are terms
term_at_depth(0, []).
term_at_depth(N, [A, [A, B]]) :- N >= 1, M is N - 1,
								 term_at_depth(M, A),
								 term_at_depth(M, B).

p(T) :- gennat(N), term_at_depth(N, T).

%% only_two(L) :- Given a list L checks if each two different elements (sets) of L
%% have a common element, which no other element of L has
only_two(L) :- not((
					is_member(X, L), is_member(Y, L), X \= Y,
					not((
						 is_member(E, X),
						 is_member(E, Y),
						 is_member(Z, L),
						 not(is_member(E,Z))
					   ))
				  )).