11:
edge(1,2).
edge(1,5).
edge(2,3).
edge(2,5).
edge(3,4).
edge(4,5).
edge(4,6).


:- dynamic nod_vizitat/1.
% d_search(Source, Path)
d_search(X,_):-df_search(X,_). % parcurgerea nodurilor
d_search(_,L):-!, collect_perms(L). % colectarea rezultatelor
df_search(X,L):-
assertz(nod_vizitat(X)),
edge(X,Y),
not(nod_vizitat(Y)),
df_search(Y,L).

% colectarea se face în ordine inversa
collect_reverse(L,P):-
retract(nod_vizitat(X)), !,
collect_reverse([X|L],P).
collect_reverse(L,L).

collect_perms([L1|R]):- retract(nod_vizitat(L1)), !, collect_perms(R).
collect_perms([]).

% b_search(Source, Path)
b_search(X,_):- % parcurgerea nodurilor
assertz(nod_vizitat(X)),
assertz(nod_de_expandat(X)),
bf_search.
b_search(_,R):-!, collect_reverse([],R). % colectarea rezultatelor
bf_search:-
retract(nod_de_expandat(X)),
expand(X),!,
bf_search.
expand(X):-
edge(X,Y),
not(nod_vizitat(Y)),
asserta(nod_vizitat(Y)),
assertz(nod_de_expandat(Y)),
fail.
expand(_).

d_search1(X,L,_):- dl_search(X,L,_).
d_search1(_,_,L):- !, collect_reverse([],L). % colectarea rezultatelor

dl_search(X,D,L):- D>0 ,
 asserta(nod_vizitat(X)),
 edge(X,Y),
 not(nod_vizitat(Y)),
 D1 is D-1,
 dl_search(Y,D1,L).


 %Lab 10, capra varza

edge([F1,L,C,V],[F2,L,C,V]):-
    ship(F1,F2),
    check(F1,L,C,V).

9:
add1(X, [H|T], [H|R]):- add1(X, T, R).
add1(X, [], [X]).

add2(X, LS, LE, RS, RE):- RS = LS, LE = [X|RE].

tree1(t(6, t(4,t(2,nil,nil),t(5,nil,nil)), t(9,t(7,nil,nil),nil))).

append_dl(LS1,LE1, LS2,LE2, RS,RE):- RS=LS1, LE1=LS2, RE=LE2.

inorder_dl(nil,L,L). % lista vida este reprezentată de 2 variabile
inorder_dl(t(K,L,R),LS,LE):-
inorder_dl(L,LSL,LEL), % apel pe subarbore stâng
inorder_dl(R,LSR,LER), % apel pe subarbore drept
LS=LSL,
LEL=[K|LSR], % K este adăugat în fața la LSR
LE=LER.

quicksort_dl([H|T], S, E):- % s-a adăugat un parametru nou
partition(H, T, Sm, Lg), % predicatul partition a rămas la fel
quicksort_dl(Sm, S, [H|L]),
quicksort_dl(Lg, L, E).
quicksort_dl([], L, L). % condiția de terminare s-a modificat

:-dynamic memo_fib/2.
fib(N,F):- memo_fib(N,F), !.
fib(N,F):- N>1,
N1 is N-1,
N2 is N-2,
fib(N1,F1),
fib(N2,F2),
F is F1+F2,
assertz(memo_fib(N,F)).
fib(0,1).
fib(1,1).

print_all:-memo_fib(N,F),
write(N),
write(' – '),
write(F),
nl,
fail.
print_all.

perm(L, [H|R]):-append(A, [H|T], L), append(A, T, L1), perm(L1, R).
perm([], []).


all_perm(L,_):- perm(L,L1), % predicatul de generare a unei permutări (vezi lucrare de laborator cu sortări)
assertz(p(L1)),
fail.
all_perm(_,R):- collect_perms(R).
collect_perms([L1|R]):- retract(p(L1)), !, collect_perms(R).
collect_perms([]).

tolistdif(H, L, L):- var(H), var(L), !.
tolistdif([H|T], [H|LS], LE) :- tolistdif(T, LS, LE).

comptolistdif([], L, L):- var(L), !.
comptolistdif([H|T], [H|LS], LE) :- comptolistdif(T, LS, LE).

all_deco(L,_):- append(L2,L1,L), % predicatul de generare a unei permutări (vezi lucrare de laborator cu sortări)
assertz(p(L1, L2)),
fail.
all_deco(_,R):- collect_perms1(R).
collect_perms1([[L1,L2]|R]):- retract(p(L1,L2)), !, collect_perms1(R).
collect_perms1([]).

8:


member_il(_, L):-var(L), !, fail.
member_il(X, [X|_]):-!.
member_il(X, [_|T]):-member_il(X, T).

insert_il(X, L):-var(L), !, L=[X|_].
insert_il(X, [X|_]):-!. % elementul există deja
insert_il(X, [_|T]):- insert_il(X, T).

delete_il(_, L, L):-var(L), !. % am ajuns la finalul listei
delete_il(X, [X|T], T):-!. % ștergem prima apariție și ne oprim
delete_il(X, [H|T], [H|R]):-delete_il(X, T, R).

search_it(_, T):-var(T),!,fail.
search_it(Key, t(Key, _, _)):-!.
search_it(Key, t(K, L, _)):-Key<K, !, search_it(Key, L).
search_it(Key, t(_, _, R)):-search_it(Key, R).

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


delete_it(Key, T, T):-var(T),!.
delete_it(Key, t(Key, L, R), L):-var(R),!.
delete_it(Key, t(Key, L, R), R):-var(L),!.
delete_it(Key, t(Key, L, R), t(Pred,NL,R)):-!,get_pred(L,Pred,NL).
delete_it(Key, t(K,L,R), t(K,NL,R)):-Key<K,!,delete_it(Key,L,NL).
delete_it(Key, t(K,L,R), t(K,L,NR)):-delete_it(Key,R,NR).
% caută nodul predecesor
get_pred(t(Pred, L, R), Pred, L):-var(R),!.
get_pred(t(Key, L, R), Pred, t(Key, L, NR)):-get_pred(R, Pred, NR).

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

reverse2(V, P, R):- var(V), !, R=P.
reverse2([H|T], P, R):- reverse2(T,[H|P], R).

conv(X, []) :- var(X), !.
conv([H|T], [H|R]):- conv(T, R).

preorder(V, []):- var(V), !.
preorder(t(K,L,R), List):-preorder(L,LL), preorder(R, LR), append1([K|LL], LR, List).

7:
tree1(t(6, t(4,t(2,nil,nil),t(5,nil,nil)), t(9,t(7,nil,nil),nil))).
tree2(t(8, t(5, nil, t(7, nil, nil)), t(9, nil, t(11, nil, nil)))).
tree3(t(6, t(4, nil, nil,nil), t(5,nil,nil,nil),t(9,nil,nil,nil))).

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

% cheie, subarbore stâng și subarbore drept
preorder(t(K,L,R), List):-preorder(L,LL), preorder(R, LR), append([K|LL], LR, List).
preorder(nil, []).

% subarbore stâng, subarbore drept și apoi cheia
postorder(t(K,L,R), List):-postorder(L,LL), postorder(R, LR), append(LL, LR,R1), append(R1, [K], List).
postorder(nil, []).

pretty_print(nil, _).
pretty_print(t(K,L,R), D):-D1 is D+1,
pretty_print(L, D1),
print_key(K, D),
pretty_print(R, D1).
% predicat care afișează cheia K la D tab-uri față de marginea din stânga și inserează o linie nouă
print_key(K, D):-D>0, !, D1 is D-1, write('\t'), print_key(K, D1).
print_key(K, _):-write(K), write('\n').
% write('\n') îi echivalent cu predicatul nl

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).

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).

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).

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


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

max1(A, B, C):- A > B, C = A.
max1(_, B, C):- C = B.

max2(A, B, C, D):- max1(A, B, D1), max1(C, D1, D).

inorder3(t(K,L,M,R), List):-inorder3(L,LL), inorder3(R,LR),inorder3(M,LM),
   append(LL, [K|LM], List1), append(List1, LR, List).
inorder3(nil, []).

preorder3(t(K,L,M,R), List):-preorder3(L,LL), preorder3(R,LR),preorder3(M,LM),
   append([K|LL], LM, List1), append(List1, LR, List).
preorder3(nil, []).

postorder3(t(K,L,M,R), List):-postorder3(L,LL), postorder3(R, LR), postorder3(M, LM),
append(LL, LM,R1), append(R1, [K|LR], List).
postorder3(nil, []).


6:list1([1,2,3,[4]]).
list2([[1],[2],[3],[4,5]]).
list3([[],2,3,4,[5,[6]],[7]]).
list4([[[[1]]],1,[1]]).
list5([1,[2],[[3]],[[[4]]],[5,[6,[7,[8,[9],10],11],12],13]]).
list6([alpha,2,[beta],[gamma,[8]]]).

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

max1(A, B, C):- A > B, C = A.
max1(A, B, C):- C = B.

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

heads([],[],_).
% dacă flag=1 atunci suntem la început de lista și putem extrage capul listei; în apelul recursiv setam flag=0
heads([H|T],[H|R],1):- atomic(H), !, heads(T,R,0).
% dacă flag=0 atunci nu suntem la primul element atomic și atunci continuam cu restul elementelor
heads([H|T],R,0):- atomic(H), !, heads(T,R,0).
% dacă am ajuns la aceasta clauza înseamnă că primul element nu este atomic și atunci trebuie să apelam recursiv și pe acest element
heads([H|T],R,_):- heads(H,R1,1), heads(T,R2,0), append(R1,R2,R).
heads_pretty(L,R):- heads(L, R, 1).

member2(X,L):- flatten(L,L1), member(X,L1).

count(L, R):- flatten(L, R1), length1(R1, R).

length1([], 0).
length1([H|T], Len) :- length1(T, Lcoada), Len is 1+Lcoada.

sum(L, R):- flatten(L, L1), s1(L1, R).

s1([], 0).
s1([H|T], Sum1) :- s1(T, S2), Sum1 is H+S2.


5:

perm_sort(L,R):-perm(L, R), is_ordered(R), !.

perm(L, [H|R]):-append(A, [H|T], L), append(A, T, L1), perm(L1, R).
perm([], []).

is_ordered([H1, H2|T]):-H1 =< H2, is_ordered([H2|T]).
is_ordered([_]).

sel_sort(L, [M|R]):- min(L, M), delete1(M, L, L1), sel_sort(L1, R).
sel_sort([], []).

min([H|T], M) :- min(T, M), M<H, !.
min([H|_], H).

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

ins_sort([H|T], R):- ins_sort(T, R1), insert_ord(H, R1, R).
ins_sort([], []).

insert_ord(X, [H|T], [H|R]):-X>H, !, insert_ord(X, T, R).
insert_ord(X, T, [X|T]).

bubble_sort(L,R):-one_pass(L,R1,F), nonvar(F), !, bubble_sort(R1,R).
bubble_sort(L,L).

one_pass([H1,H2|T], [H2|R], F):-H1>H2, !, F=1, one_pass([H1|T],R,F).
one_pass([H1|T], [H1|R], F):-one_pass(T, R, F).
one_pass([], [] ,_).

quick_sort([H|T], R):- % alegem pivot primul element
partition(H, T, Sm, Lg),
quick_sort(Sm, SmS), % sortam sublista cu elementele mai mici decât pivotul
quick_sort(Lg, LgS), % sortam sublista cu elementele mai mari decât pivotul
append(SmS, [H|LgS], R).
quick_sort([], []).

partition(H, [X|T], [X|Sm], Lg):-X<H, !, partition(H, T, Sm, Lg).
partition(H, [X|T], Sm, [X|Lg]):-partition(H, T, Sm, Lg).
partition(_, [], [], []).

merge_sort(L, R):-
split(L, L1, L2), % împarte L în doua subliste de lungimi egale
merge_sort(L1, R1),
merge_sort(L2, R2),
merge(R1, R2, R). % interclasează sublistele ordonate
merge_sort([H], [H]). % split returnează fail dacă lista ii vidă sau are doar un singur element
merge_sort([], []).
split(L, L1, L2):- length(L, Len), Len>1, K is Len/2, splitK(L, K, L1, L2).
splitK([H|T], K, [H|L1], L2):-K>0,!,K1 is K-1,splitK(T, K1, L1, L2).
splitK(T, _, [], T).
merge([H1|T1], [H2|T2], [H1|R]):-H1<H2, !, merge(T1, [H2|T2], R).
merge([H1|T1], [H2|T2], [H2|R]):-merge([H1|T1], T2, R).
merge([], L, L).
merge(L, [], L).

perm2(L, [H|R]):- member(H, L), delete1(H, L, L1), perm(L1, R).
perm2([], []).

sel_sort2(L, [M|R]):- max(L, M), delete1(M, L, L1), sel_sort(L1, R).
sel_sort2([], []).

max2([H|T], M) :- max2(T, M), char_code(M,M1), char_code(H,H1), M1>H1, !.
max2([H|_], H).

charsort(L, [M|R]):- max2(L, M), delete1(M, L, L1), charsort(L1, R).
charsort([], []).

lensort(L, [M|R]):- max3(L, M), delete1(M, L, L1), lensort(L1, R).
lensort([], []).

max3([H|T], M) :- max3(T, M), length(H,H1), length(M,M1), M1>H1, !.
max3([H|_], H).

4:
member1(X, [X|_]) :- !.
member1(X, [_|T]) :- member1(X, T).

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

length1([], 0).
length1([H|T], Len) :- length1(T, Lcoada), Len is 1+Lcoada.

length2([], Acc, Len) :- Len=Acc.
length2([H|T], Acc, Len) :- Acc1 is Acc + 1, length2(T, Acc1, Len).
length2_pretty(L, R) :- length2(L, 0, R).

reverse1([], []).
reverse1([H|T], R) :- reverse1(T, Rcoada), append(Rcoada, [H], R).

reverse2([], Acc, R) :- Acc=R.
reverse2([H|T], Acc, R) :- Acc1=[H|Acc], reverse2(T, Acc1, R).
reverse2_pretty(L, R) :- reverse2(L, [], R).

min1([H|T], M) :- min1(T, M), M<H, !.
min1([H|_], H).

min2([], Mp, M) :- M=Mp.
min2([H|T], Mp, M) :- H<Mp, !, min2(T, H, M).
min2([H|T], Mp, M) :- min2(T, Mp, M).
min2_pretty([H|T], M) :- min2(T, H, M).

union([], L, L).
union([H|T], L2, R) :- member(H, L2), !, union(T, L2, R).
union([H|T], L2, [H|R]) :- union(T, L2, R).

inters([],L2,[]).
inters([H|T], L2, [H|R]) :- member(H, L2), !, inters(T, L2, R).
inters([H|T], L2, R) :- inters(T, L2, R).

diff([],_,[])
diff([H|T], L2, R) :- member(H, L2), !, diff(T, L2, R).
diff([H|T], L2, [H|R]) :- diff(T, L2, R).

delmin(L,R) :- min1(L,M), delete(L,M,R).

reverse_k(L,K,R) :- K = 1, reverse1(L,R).
reverse_k([H|T],K,R) :- K1 is K-1 , reverse_k(T,K1,R1), R = [H|R1].
reverse_k([],_,[]).