% TESTARE PROLOG - SUBIECTE 
% NUMARUL 1

% SUBIECTUL I 

% Fie urmatoarea baza de cunostinte, definita prin predicatele 
%	brands/3, 		brands(brandId, brandName, countryOfOrigin).
%	watchTypes/2, 	watchTypes(typeId, typeName).
%	watches/5, 		watches(watchId, modelName, brandId, watchTypeId, price).
% 	features/2,		features(featureId, featureName).
%	watchFeatures/3 watchFeatures(watchId, featureId).

brands(1, 'Rolex', 'Switzerland').
brands(2, 'Seiko', 'Japan').
brands(3, 'Omega', 'Switzerland').
brands(4, 'Orient', 'Japan').
brands(5, 'Tissot', 'Switzerland').

watchTypes(1, 'Automatic').
watchTypes(2, 'Quartz').

features(1, 'Water Resistant').
features(2, 'Chronograph').
features(3, 'Date Indicator').
features(4, 'Sapphire Crystal').
features(5, 'Luminous Hands').

watches(101, 'Submariner', 1, 1, 10500).
watches(102, 'Presage', 2, 1, 550).
watches(103, 'Seamaster', 3, 1, 4700).
watches(104, 'Bambino', 4, 1, 300).
watches(105, 'PRX', 5, 2, 375).
watches(106, 'Daytona', 1, 1, 13000).
watches(107, 'Prospex', 2, 1, 725).
watches(108, 'Speedmaster', 3, 1, 6500).
watches(109, 'Mako', 4, 1, 450).
watches(110, 'Le Locle', 5, 1, 525).

watchFeatures(101, 1).
watchFeatures(101, 4).
watchFeatures(102, 1).
watchFeatures(102, 5).
watchFeatures(103, 1).
watchFeatures(103, 3).
watchFeatures(103, 4).
watchFeatures(104, 1).
watchFeatures(105, 2).
watchFeatures(106, 1).
watchFeatures(106, 4).
watchFeatures(107, 1).
watchFeatures(107, 3).
watchFeatures(108, 1).
watchFeatures(108, 2).
watchFeatures(109, 1).
watchFeatures(109, 5).
watchFeatures(110, 1).
watchFeatures(110, 3).

% [2 puncte]
% I a) Scrieti un predicat isFromJapan(X) care este true atunci cand firma de ceasuri e produsa in Japonia, si false altfel.
% ?- isFromSwitzerland('Tissot'). atunci true 
% ?- isFromSwitzerland('Seiko').  atunci false 
% Scrieti un exemplu de apel pentru a determina toate ceasurile care sunt din Elvetia.

isFromSwitzerland(X) :- brands(_, X, 'Switzerland').
% Exemplu de apel: ?- isFromSwitzerland(X).

% [2 puncte]
% I b) Scrieti un predicat isFromOmega/1 care sa verifice daca un anumit model de ceas este de la Omega sau nu.
% ?- isFromOmega('PRX'). atunci false 
% ?- isFromOmega('Seamaster'). atunci true 

isFromOmega(Model) :- watches(_, Model, 3, _, _).

% [3 puncte]
% I c) Scrieti un predicat allInfo/6 care sa determine toate informatiile posibile referitoare la un ceas, primind numele modelului.
% ?- allInfo('Seamaster', Brand, CountryOfOrigin, WatchTypeName, Price, Feature).
% Brand = 'Omega', CountryOfOrigin = 'Switzerland', Feature = 'Water Resistant', Price = 4700, WatchTypeName = 'Automatic' ; 
% Brand = 'Omega', CountryOfOrigin = 'Switzerland', Feature = 'Date Indicator', Price = 4700, WatchTypeName = 'Automatic'
% Brand = 'Omega', CountryOfOrigin = 'Switzerland', Feature = 'Sapphire Crystal', Price = 4700, WatchTypeName = 'Automatic'

allInfo(Model, Brand, CountryOfOrigin, WatchTypeName, Price, Feature) :-
    watches(WatchId, Model, BrandId, WatchTypeId, Price),
    brands(BrandId, Brand, CountryOfOrigin),
    watchFeatures(WatchId, FeatureId),
    features(FeatureId, Feature),
    watchTypes(WatchTypeId, WatchTypeName).

% [3 puncte = 1 punct predicat ajutator + 2 puncte predicatul principal]
% I d) Scrieti un predicat allModelsWithFeature/3 care primeste ca intrare o lista de ceasuri, un Feature, si pastreaza in rezultat doar modelele care au Feature-ul respectiv.
% ?- allModelsWithFeature(['Seamaster', 'PRX', 'Speedmaster', 'Bambino', 'Submariner'], 'Sapphire Crystal', L).
% L = ['Seamaster', 'Submariner']

% Pentru rezolvare, definiti un predicat ajutator watchHasFeature/2 care returneaza true daca un anumit model are un Feature, si false in caz contrar.
% ?- watchHasFeature('Submariner', 'Sapphire Crystal').
% true
% ?- watchHasFeature('Bambino', 'Sapphire Crystal').
% false 

watchHasFeature(Watch, Feature) :-
    watches(WatchId, Watch, _, _, _),
    watchFeatures(WatchId, FeatureId),
    features(FeatureId, Feature).

allModelsWithFeature([], _, []).
allModelsWithFeature([H | T], Feature, [H | TR]) :-
    watchHasFeature(H, Feature),
    allModelsWithFeature(T, Feature, TR).
allModelsWithFeature([H | T], Feature, TR) :-
    not(watchHasFeature(H, Feature)),
    allModelsWithFeature(T, Feature, TR).


% SUBIECTUL al II-lea

% Fie urmatoarea lista reprezentand o forma clauzala a unei formule:
% List = [[a, non(b), non(c)], [non(a), a, non(c)], [c], [non(a), non(d), e]]

% [3 puncte]
% II a) Scrieti un predicat isTrivialClause/1 care returneaza true daca o clauza este triviala, respectiv false in caz contrar. 
% O clauza se numeste triviala daca exista p variabila propozitionala, astfel incat atat p, cat si non(p) sunt in clauza
% ?- isTrivial([a, b, non(c), d]). atunci false 
% ?- isTrivial([a, b, non(a), non(c), d]). atunci true 

isTrivial([X | T]) :- member(non(X), T), !.
isTrivial([non(X) | T]) :- member(X, T), !.
isTrivial([_ | T]) :- isTrivial(T).

% [7 puncte]
% II b) Scrieti un predicat removeTrivialClauses/2 care returneaza noua forma clauzala, cu clauzele triviale eliminate.
% ?- removeTrivialClauses([[a, non(b), non(c)], [non(a), a, non(c)], [c], [non(a), non(d), e]], Result).
% Result = [[a, non(b), non(c)], [c], [non(a), non(d), e]]

removeTrivialClauses([], []).
removeTrivialClauses([H | T], TR) :-
    isTrivial(H),
    removeTrivialClauses(T, TR).
removeTrivialClauses([H | T], [H | TR]) :-
    not(isTrivial(H)),
    removeTrivialClauses(T, TR).


% SUBIECTUL al III-lea

% Scrieti o gramatica pentru generarea expresiilor aritmetice de forma 
% a + a + ... + a + b + ... b + b
% -----------------~~~~~~~~~~~~~~~~~
%     n a-uri		  m b-uri 
% cu urmatoarea conditie: avem obligatoriu un numar PAR de a-uri (inclusiv 0 a-uri).
% (nu avem nicio restrictie pe numarul de b-uri)

% Vi se da urmatorul operator (pentru a nu fi necesara parantezarea expresiilor): 
:- op(900, xfy, +).

% de exemplu, pentru un predicat start/1
% ?- start(a + a + a + a + b + b + b + b + b + b + b + b + b). 
% atunci true => numar par de a-uri si oricate b-uri
% ?- start(a + a + a + a + b + b + b + b + b + b + a + b + b).
% atunci false => avem un a intercalat intre b-uri 
% ?- start(a + a + a + b).
% atunci false => avem numar impar de a-uri 
% ?- start(b + b + b + b).
% atunci true => avem 0 a-uri


% Propunere Solutie 
% Start ::= a + a | a + a + Start | GenB
% GenB ::= b + GenB | GenB 

start(a + a).
start(a + a + A) :- start(A).
start(B) :- genb(B).

genb(b).
genb(b + B) :- genb(B).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% INCEPUTUL BREVIARULUI TEORETIC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Predicate predefinite in Prolog si breviar teoretic 
% 
% atom/1 - verifica daca un string este atom in Prolog
% atom = orice sir de caractere care incepe cu litera mica sau care e scris intre simboluri ''
% ?- atom(X). false
% ?- atom(myAtom). true 
% ?- atom('My Atom'). true 
%
% In scrierea regulilor, folosim structura
% Head :- Body. Daca Body e satisfacut, atunci satisfacem si Head. (Head if Body)
% Facts - contin doar Head, sunt cunostintele de baza
% Rules - cele care contin Body. In Body, putem inlantui cunostintele prin , (SI = conjunctie)
% 															respectiv prin ; (SAU = disjunctie)
% Pentru a limita recursia pe cazurile de baza, folosim !/0. (predicatul CUT)
% el este util cand avem clauze scrie una sub alta - atunci se face disjunctie intre clauze.
% Daca se satisface o clauza, Prolog incearca satisfacerea celorlalte clauze, imediat urmatoare.
% Pentru a opri acest mecanism, e util CUT. 
% Exemplu: base_case(params) :- !.  
%
% Operatorii aritmetici
% uzuali: +, -, *, / (floats), // (cat), div (cat), mod (rest), ** (exponentiere)
% egalitati: = (cauta unificator), == (structural), =:= (aritmetic) 
% inegalitati: \= (pentru unificator), \== (pentru structura), =\= (aritmetic)
% comparatii: >, >=, <, =< (singurul ne-standard)
% is/2 - operator de atribuire aritmetica
% ?- X is 1 + 2. atunci X = 3
% is/2 functioneaza cand membrul drept este COMPLET instantiat 
% Y = 2, X is Y + 2. raspunde Y = 2, X = 4
% dar X is Y + 2. e eroare, pentru ca Y nu e instantiat ("Arguments are not sufficiently instantiated")
% 
% Listele in Prolog 
% MyList = [se, reprezinta, prin, paranteze, patrate, si, cu, elemente, separate, prin, virgula]
% pot contine elemente de orice tip, amestecate oricum [0, [], [X], f(X), Y] etc 
% notatia utila: [Head | Tail] (sau [H | T] in general, in probleme)
% Head-ul unei liste vide conduce la eroare!!! Tail-ul listei vide este lista vida
% [H | T] = [1] atunci H = 1, T = []
% [H | T] = [] atunci EROARE
% [A, B | T] = [a,b,c,d] atunci A = a, B = b, T = [c, d]
% [A, B | T] = [a, b] atunci A = a, B = b, T = []
% [A, B | T] = [a] atunci EROARE pentru ca B e in Head (inainte de | ) si nu se poate instantia
% length/2 - returneaza lungimea unei liste
% ?- length([1,2,3],L). atunci L = 3
% member/2 - verifica daca un element apare sau nu intr-o lista
% ?- member(b, [a,b,c,d]). atunci true
% ?- member(t, [a,b,c,d]). atunci false 
% union/3 - reuniunea a doua liste, cu rezultatul o lista reprezentand o multime - elementele sunt distincte
% ?- union([1,2,3,2],[1,4,3,2],L). atunci L = [1,4,3,2]
% append/3 - concateneaza doua liste, mai intai prima lista, apoi a doua 
% ?- append([1,2,3,2],[1,4,3,2],L). atunci L = [1, 2, 3, 2, 1, 4, 3, 2]
% string_chars/2 - split-uieste un sir de caractere intr-o lista de caractere corespunzatoare
% ?- string_chars(prolog, Res). atunci Res = [p, r, o, l, o, g]
% ?- numlist/3 - primeste doua capete de interval, si returneaza lista intregilor din intervalul inchis 
% ?- numlist(-2, 3, Res). atunci Res = [-2, -1, 0, 1, 2, 3]
% select/3 - in select(X, List, ListResult) se elimina prima aparitie a lui X din List si se returneaza in ListResult
% ?- select(a, [b,a,c], LR).
% LR = [b, c]
% ?- select(a, [a,b,a,c], LR).
% LR = [b, a, c]
% ?- select(a, [b, c], LR).
% false 
% daca primul argument > al doilea, returneaza false 
% findall/3 - findall(X, P, L). pune in L toti acei X astfel incat sa respecte P 
% divisorsPairs(A, B, List) :- 
% 	numlist(A, B, Range),
% 	findall((X, Y), (member(X, Range), member(Y, Range), X mod Y =:= 0), List).
% i.e. gaseste toate perechile (X, Y)
% cu proprietatea ca X apartine Range, Y apartine Range si restul impartirii lui X la Y este 0
% 															(adica Y este divizor al lui X)
% si pune toate aceste perechi in List 
% 
% reverse/2 - reverse(ListInput, ListOutput). returneaza in ListOutput reverse-ul listei ListInput
% 
% predsort/3 - utilizat pentru sortare cu un compare: predsort(MyCompare, InputList, SortedList).
%
% Predicate utile, dar care nu sunt definite in Prolog

% sum/2 - returneaza suma dintr-o lista
sum([], 0) :- !.
sum([H | T], Res) :-
    sum(T, ResT),
    Res is ResT + H.

% zip/3 - face perechi de elemente de pe aceeasi pozitie intre doua liste
% ?- zip([1,2,3],[a,b,c],Res). atunci Res = [(1, a), (2, b), (3, c)]
% zip se opreste la lungimea celei mai scurte dintre cele doua liste! 
% ?- zip([1,2,3,4],[a,b,c],Res). atunci Res = [(1, a), (2, b), (3, c)]
% ?- zip([1,2,3],[a,b,c,d,e],Res). atunci Res = [(1, a), (2, b), (3, c)]
zip([], _, []) :- !.
zip(_, [], []) :- !.
zip([H1 | T1], [H2 | T2], [(H1, H2) | TR]) :-
    zip(T1, T2, TR).

% all_symb/2 - verifica daca toate elementele dintr-o lista sunt egale cu un simbol dat
% ?- all_symb([a,a,a], a). atunci true
% ?- all_symb([a,A,a], a). atunci A = a, true (este satisfacut cand A = a)
all_symb([S], S) :- !.
all_symb([H | T], S) :-
    H = S,
    all_symb(T, S).

% max/2 - returneaza maximul dintr-o lista 
max([], 0) :- !.
max([H | T], MaxTail) :-
    max(T, MaxTail),
    MaxTail >= H, !.
max([H | T], H) :-
    max(T, MaxTail),
    H >= MaxTail.

% remove_duplicates/2 - returneaza lista primita ca prim argument, dar fara elemente duplicate
remove_duplicates([], []) :- !.
remove_duplicates([H | T], [H | TR]) :-
    not(member(H, T)), 
    remove_duplicates(T, TR), !.
remove_duplicates([_ | T], TR) :-
    remove_duplicates(T, TR).

% Exemplu de BFS 
s(1, 2).
s(1, 3).
s(1, 4).
s(2, 4).
s(2, 5).
s(3, 5).
s(3, 4).
s(4, 3).
objective(5).


extend([Node | Path], NewPath) :-
    findall([NewNode, Node | Path], (s(Node, NewNode), not(member(NewNode, [Node | Path]))), NewPath).

breadthfirst([[Node | Path] | _], [Node | Path]) :- objective(Node).
breadthfirst([Path | PathTail], Solution) :-
    extend(Path, ExtendedPath),
    append(ExtendedPath, PathTail, NewPath),
    breadthfirst(NewPath, Solution).

solve(Start, Solution) :-
    findall(S, breadthfirst([[Start]], S), Solution).

% Exemplu de arbori si parcurgere

def(myTree, tree(1, tree(2, tree(4, nil, tree(7, nil, nil)), nil), tree(3, tree(5, nil, nil), tree(6, nil, nil)))).

% inordine
srd(nil, []).
srd(tree(Root, Left, Right), Result) :-
    srd(Left, ResultLeft),
    srd(Right, ResultRight),
    append(ResultLeft, [Root | ResultRight], Result).

% Pentru UNIFICARE
% unify_with_occurs_check/2 verifica daca doi termeni pot unifica sau nu
% atentie la specificatia de limbaj! variabilele din limbaj sunt si cele din Prolog, deci se scriu cu Majuscula

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SFARSITUL BREVIARULUI TEORETIC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%