% al K lea element din lista L in X
% ( 1 )
extract_k([_|T],K,X) :- K > 0 , CONT is K - 1 , ! , extract_k(T,CONT,X).
extract_k([H|_],K,X) :- K = 0 , X is H.

%usage: extract_k([69,12,3,55,23],5,X).

% ?- diagonal([[1,2,3],[4,5,6],[7,8,9]], D).
% D = [1, 5, 9].
% ( 2 )
%diagonal_fun([],[],0).
diagonal([H|T],D,K) :- extract_k(H,K,X) ,
                        atomic(X),
                        %writeln(X),
                    append(D,[X],D1),
                    writeln(D1),
                    CONT is K + 1 ,
                    diagonal(T,D1,CONT).

%( 1 )
cmmdc(B,B,B).
cmmdc(A,B,C) :- A>B , A1 is A-B , cmmdc(A1,B,C).
cmmdc(A,B,C) :- B>A , B1 is B-A , cmmdc(A,B1,C).

%( 2 )
cmmmc(A,B,C) :- cmmdc(A,B,D) , C is A*B/D.

%( 3 ) suma
suma([H|T],R) :- suma(T,ACC) , R is ACC + H.
suma([],0).

%– suma([1,2,3,4,5], R).

% ( 4 )
%? – separate_parity([1,2,3,4,5,6], E, O).
%E = [2,4,6], O=[1,3,5]

separate_parity([H|T],E,[H|O]) :- 1 is H mod 2 , separate_parity(T,E,O).
separate_parity([H|T],[H|E],O) :- 0 is H mod 2 , separate_parity(T,E,O).
separate_parity([],[],[]).

% ( 5 ) Înlocui?i toate apari?iile lui X cu Y.
%Ex: ? – replace_all(1, a, [1,2,3,1,2], R).

replace_all(X,Y,[X|T],[Y|R]) :- replace_all(X,Y,T,R),!.
replace_all(X,Y,[H|T],[H|R]) :- not(H is X),  replace_all(X,Y,T,R).
replace_all(_,_,[],[]).

% ( 6 ) ?terge?i elementele de pe pozi?ii divizibile cu K.
%Ex: ? – sterge_k([6,5,4,3,2,1], 3, R).
%R = [6,5,3,2]

sterge( [H|T] , K , CONT , [H|R] ) :- CONT < K ,
                                     CONT1 is CONT + 1,
                                     sterge(T,K,CONT1,R) , !.
sterge( [_|T] , K , CONT , R ) :- 0 is CONT mod K , sterge(T,K,1,R).
sterge( [], _ , _ , [] ).

sterge_k(L,K,R) :- sterge(L,K,1,R).

% ( 7 ) Inverseaza o lista completa/incompleta.
%? – reverse([1, 2, 3, 4, 5], R).
%R = [5, 4, 3, 2, 1].

%reverse lista normala cu REC inainte
reverse1([],[]).
reverse1([H|T],R) :- reverse1(T,ACC) , append(ACC,[H],R).

reverse_il( L , R , R ) :- var(L),  !.
reverse_il( [H|T] , R , ACC ) :- reverse_il(T,R,[H|ACC]).
% reverse2([1, 2, 3, 4, 5|_], R ).
reverse2( L , R ) :- reverse_il(L,R,_).

% ( 8 ) Calcula?i adâncimea maxima a unei liste imbricate.
%Ex: ? – adancime([1, [2, [3]], [4]], R1), adancime([], R2).
%R1 = 3, R2 = 1.
%adancime([1, [2, [3]], [4]], R1), adancime([], R2).

max(A,B,A) :- A>B , !.
max(_,B,B).

adancime([],1).
adancime([H|T],R) :- atomic(H) ,!, adancime(T,R).
adancime([H|T],R) :- adancime(H,R1), adancime(T,R2),
                    R3 is R1 + 1,
                    max(R2,R3,R).

% ( 9 ) Aplatiza?i o lista imbricata cu liste complete/incomplete.
%Ex: ? - flat([1, [2, [3]], [4]], R).
%R = [1,2,3,4].

flat( [H|T] ,[H|R] ) :- atomic(H) , ! , flat(T,R).
flat( [H|T] , R ) :- flat(H,R1),flat(T,R2),  append(R1,R2,R).
flat( [],[] ).

%flat_il([[1|_], 2, [3, [4, 5|_]|_]|_], R).

append_il(L,L2,L2):- var(L),!.
append_il([H|T],L2,[H|R]) :- append_il(T,L2,R).

flat_il(L,_) :- var(L), !.
flat_il( [H|T] ,[H|R] ) :- atomic(H) , ! , flat_il(T,R).
flat_il( [H|T] , R ) :- flat_il(H,R1),flat_il(T,R2),  append_il(R1,R2,R).
%flat_il( [],[] ).
%flat_il([[1|_], 2, [3, [4, 5|_]|_]|_], R).


%( 11 ). Colecta?i toate nodurile unui arbore binar complet/incomplet în inordine folosind liste complete/diferen?a.
%tree1(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
%? – tree(T), inordine(T, R).
%R = [2,4,5,6,7,9].

%tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
inorder( t(K,L,R) , LIST ) :- inorder(L,LL) ,
                             inorder(R,LR) ,
                            append(LL,[K|LR],LIST).
inorder( nil , [] ).

preoder( t(K,L,R) , LIST ) :- preoder(L,LL) ,
                             preoder(R,LR) ,
                            append([K|LL],LR,LIST).
preoder( nil , [] ).

postorder( t(K,L,R) , LIST ) :- postorder(L,LL) ,
                             postorder(R,LR) ,
                            append(LL,LR,R1) ,
                            append(R1,[K],LIST).
postorder( nil , [] ).


%( 12 ). Colectați toate frunzele dintr-un arbore binar.
tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
%? – tree(T), collect_k(T, R).
%R = [2,5,7].
height3(nil, 0).
height3(t(_, L,Mid, R), H):-
    height3(L, H1),
    height3(Mid, H2),
    height3(R, H3),
    max(H1, H2, H4),
    max(H4, H3 ,H5),
    H is H5+1.

collect( t(K,nil,nil) , [K] ) :- !.
collect( t(_,L,R) , LIST  ) :-
    collect( L , LL ),
    collect( R , RR ),
    append(LL,RR,LIST).
collect( nil , [] ).

count_leaves( t(_,_,_) , 1 ).
count_leaves( t(_,L,R) , CONT ) :-
        count_leaves( L , CONT1 ),
        count_leaves( R , CONT2 ),
        CONT is CONT1 + CONT2.


height( nil , 0 ).
height( t(_,L,R) , H ) :-
        height(L, H1 ),
        height(R, H2 ),
        max(H1,H2,H3),
        H is H3+1.

% Toate ele pare dintr-un arbore binar incomplet/complet
tree2(t(6, t(4, t(2, _, _), t(5, _, _)), t(9, t(7, _, _), _))).

%extract_even(T, []):- var(T), !.
extract_even(nil,[]).
extract_even(t(K, L, R),Rez):-
    1 is K mod 2, !,
    extract_even(L,Rez1),
    extract_even(R,Rez2),
    append(Rez1,[K],RezP),
    append(RezP,Rez2,Rez).
extract_even(t(_, L, R),Rez):-
    extract_even(L,Rez1),
    extract_even(R,Rez2),
    append(Rez1,Rez2,Rez).

% 12. colectati toate frunzele dintr-un arbore binar
colect(t(K, nil, nil), [K]):- !.
colect(t(_, L, R), List) :- colect(L, LL), colect(R, RR) , append(LL, RR, List).
colect(nil, []).

% 13. stergeti toate elementele duplicate dintr-o lista
s_duplicate([], []).
s_duplicate([H|T], R):- member(H, T), s_duplicate(T, R).
s_duplicate([H|T], [H|R]):- s_duplicate(T, R).

% 14. stergeti toate aparitiile elem min dintr-o lista
min1([H|T], M):- min1(T, M), M<H, !.
min1([H|_], H).

delete(X, [X|T], T):- !.
delete(X, [H|T], [H|R]) :- delete(X, T, R).
delete(_, [], []).

s_min(L, R) :- min1(L, R1), delete(R1, L, R).

max2([H|T],M) :- max2(T,M1),
         H < M1,!,M=M1.
max2([H|_],H).

s_max(L, R) :- max2(L, R1), delete(R1, L, R).


% 15. inversati elementele dintr-o lista dupa pozitia K

revk([H|T],N,Count, [H|TR]) :- Count < N ,!, Count1 is Count +1 , revk(T, N, Count1, TR).
revk(L,N, Count, R) :- append(TL, [Last], L) , C1 is Count+1 , revk(TL, N, C1, TR), R = [Last|TR].
revk([], _, _, []).

% 17. rotire k pozitii la dreapta
rotire(L,K,R):-append(L1,L2,L),
        length(L,Len),
        K1 is Len -K,
        length(L1,K1),
        append(L2,L1,R).

% 18. sortati o lista de caractere in functie de codul ascii
del(X,[X|T],T).
del(X,[H|T],[H|R]) :- del(X,T,R).
del(_, [], []).

sort_chars(L, [M|R]):- min3(L, M), del(M, L, L1), sort_chars(L1, R).
sort_chars([], []).

min3([H|T], M) :- min3(T, M), char_code(M, R1), char_code(H, R2), R1<R2, !.
min3([H|_], H).

% 19. sortati o lista de liste in functie de lungimea listelor de nivel 2
length_lista([],0):-!.
length_lista([_|T],Len):-length_lista(T,Len1),
             Len is Len1 +1.

minim_list([],M,M).
minim_list([H|T],MP,M):-length_lista(H,Z1),
             length_lista(MP,Z2),
             Z1<Z2, ! ,
             minim_list(T,H,M).
minim_list([H|T],MP,M):-minim_list(T,MP,M).
minlista([H|T],R):-minim_list([H|T],H,R).


sort_len(L,[M|R]):-minlista(L,M),
           delete(M,L,L1),!,
           sort_len(L1,R).
sort_len([],[]).


% 20. suma elem de la niv k intr-o lista imbricata ??

sum_k([],_,_,0).
sum_k([H|T],K,C,R):- C<K,
                atomic(H),!,
                sum_k(T,K,C,R).
sum_k([H|T],K,C,R):- C<K,!,
                C1 is C+1,
                sum_k(H,K,C1,R1),
                sum_k(T,K,C1,R2),
                R is R1+R2.
sum_k([H|T],C,K,R):-collect(L,R).

collect1([],0).
collect1([H|T],S):- atomic(H),!,
           collect(T,S1), S is H+S1.
collect1([H|T],S):- collect1(H,S1),collect1(T,S2), S is S1 + S2.

% 21. inlocuiti toate aparitiile lui x cu y in lista imbricata

append1([H|T], L, [H|R]) :- append1(T, L, R).
append1([], L, L).


repl(X,Y,[X|T],[Y|R]):-repl(X,Y,T,R).
repl(X,Y,[H|T],[H|R]):-atomic(H), ! , repl(X,Y,T,R).
repl(X,Y,[H|T],R):- repl(X,Y,H,RH),repl(X,Y,T,RT),append1(RH,RT,R).
repl(_,_,[],[]).

% 22. colecteaza toate nodurile de la adancimea k dintr-un arbore binar
%tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).

collect_k(t(_,L,nil),K,C,List):- C<K,!,
                 C1 is C+1,
                 collect_k(L,K,C1,List).
collect_k(t(_,nil,R),K,C,List):- C<K,!,
                 C1 is C+1,
                 collect_k(R,K,C1,List).
collect_k(t(_,L,R),K,C,List):- C<K,!,
                   C1 is C+1,
                   collect_k(L,K,C1,L1),
                   collect_k(R,K,C1,R1),
                   append(L1,R1,List).
collect_k(t(K,_,_),_,_,[K]).
collect_k1(t(Ki,L,R),K,List):-collect_k(t(Ki,L,R),K,1,List).

% extrage elem pare dintr-un arbore binar incomplet
extract(T, []):- var(T), !.
extract(t(K, L, R),Rez):-0 is K mod 2, !, extract(L,Rez1),extract(R,Rez2),
    append(Rez1,[K],RezP),append(RezP,Rez2,Rez).
extract(t(_, L, R),Rez):-extract(L,Rez1),extract(R,Rez2),append(Rez1,Rez2,Rez).

col(t(_, L, nil), K, C, List):- C<K, !, 0 is K mod 2,
    C1 is C+ 1, col(L, K, C1,List).
col(t(_, nil, R), K, C, List):- C<K, !,0 is K mod 2,
    C1 is C+ 1, col(R, K, C1,List).
col(t(_, L, R), K, C, List):- C < K, !, 0 is K mod 2,
    C1 is C+1,
    col(L, K, C1 , L1),
    col(R, K, C1, L2),
    append(L1, L2, List).
col(t(K, _,_), _, _, [K]).

col_k(t(Key, L, R), K,List):- col(t(Key, L, R),K, 1, List).


%tree(t(6, t(4, t(2, nil, nil), t(5, nil, nil)), t(9, t(7, nil, nil), nil))).
% ARBORII _---
insert_key(Key, nil, t(Key, nil, nil)). % inserează cheia în arbore
insert_key(Key, t(Key, L, R), t(Key, L, R)):-!. % cheia există deja
insert_key(Key, t(K,L,R), t(K,NL,R)):- Key<K,!,insert_key(Key,L,NL).
insert_key(Key, t(K,L,R), t(K,L,NR)):- insert_key(Key, R, NR).

get_pred(t(Pred, L, nil), Pred, L):-!.
get_pred(t(Key, L, R), Pred, t(Key, L, NR)):-get_pred(R, Pred, NR).

delete_key(Key, t(Key, L, nil), L):-!.
delete_key(Key, t(Key, nil, R), R):-!.
delete_key(Key, t(Key, L, R), t(Pred,NL,R)):-!,get_pred(L,Pred,NL).
delete_key(Key, t(K,L,R), t(K,NL,R)):-Key<K,!,delete_key(Key,L,NL).
delete_key(Key, t(K,L,R), t(K,L,NR)):-delete_key(Key,R,NR).

search_key(Key, t(Key, _, _)):-!.
search_key(Key, t(K, L, _)):-Key<K, !, search_key(Key, L).
search_key(Key, t(_, _, R)):-search_key(Key, R).


%encode
max_encode([H1,H1|T],R,C):-!, C1 is C+1, max_encode([H1|T],R,C1).
max_encode([_, H2|T],[C|TR],C):- max_encode([H2|T],TR,1).
max_encode([_],[C],C).
max_encode([],[],_).
max_encode([H1,H2|T],R):- max_encode([H1,H2|T],R1,1), max(R1,R).

max_from_list([H|T],R,MAX) :- H>MAX , max_from_list(T,R,H).
max_from_list([_|T],R,MAX) :- max_from_list(T,R,MAX).
max_from_list([],_,_).

max_enc(L,R,X) :- max_encode(L,R,1),max_from_list(R,X).

%max_enc([a,a,b,b,b,d,a,a,a,a,d],R,X).
%