% TESTARE PROLOG - SUBIECTE 
% NUMARUL 2

% 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.
% ?- isFromJapan('Tissot'). atunci false 
% ?- isFromJapan('Seiko').  atunci true 
% Scrieti un exemplu de apel pentru a determina toate ceasurile care sunt din Japonia.

isFromJapan(X) :- brands(_, X, 'Japan').
% Exemplu de apel: ?- isFromJapan(X).

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

isQuartz(Model) :- watches(_, Model, _, 2, _).

% [3 puncte]
% I c) Scrieti un predicat findSwissWatchesByFeature/6 care determina toate informatiile posibile despre ceasurile care au Feature-ul primit ca intrare. 
% ?- findSwissWatchesByFeature('Sapphire Crystal', BrandName, CountryOfOrigin, WatchTypeName, Price, Name).
% BrandName = 'Rolex', CountryOfOrigin = 'Switzerland', Name = 'Submariner', Price = 10500, WatchTypeName = 'Automatic' ; 
% BrandName = 'Omega', CountryOfOrigin = 'Switzerland', Name = 'Seamaster', Price = 4700, WatchTypeName = 'Automatic' ; 
% BrandName = 'Rolex', CountryOfOrigin = 'Switzerland', Name = 'Daytona', Price = 13000, WatchTypeName = 'Automatic'

findSwissWatchesByFeature(Feature, BrandName, CountryOfOrigin, WatchTypeName, Price, Name) :-
   watches(WatchId, Name, BrandId, WatchType, Price), 
   brands(BrandId, BrandName, CountryOfOrigin),
   watchFeatures(WatchId, FeatureId),
   watchTypes(WatchType, WatchTypeName),
   features(FeatureId, Feature).

% [3 puncte = 1 punct predicat ajutator + 2 puncte predicatul principal]
% I d) Scrieti un predicat allFeaturesAssociatedWithWatch/3 care primeste o lista de feature-uri, un nume de model, si pastreaza toate acele feature-uri asociate modelului primit.
% ?- allFeaturesAssociatedWithWatch(['Water Resistant', 'Date Indicator', 'Luminous Hands', 'Chronograph'], 'Seamaster', L).
% L = ['Water Resistant', 'Date Indicator']

% Pentru rezolvare, definiti un predicat ajutator featureAssociatedWithWatch/2 care returneaza true daca feature-ul este asociat modelului, si false in caz contrar.
% ?- featureAssociatedWithWatch('Sapphire Crystal', 'Seamaster').
% true 
% ?- featureAssociatedWithWatch('Sapphire Crystal', 'Bambino').
% false 

featureAssociatedWithWatch(Feature, Model) :-
    features(FeatureId, Feature),
    watchFeatures(WatchId, FeatureId),
    watches(WatchId, Model, _, _, _).

allFeaturesAssociatedWithWatch([], _, []).
allFeaturesAssociatedWithWatch([H | T], Model, [H | TR]) :-
    featureAssociatedWithWatch(H, Model),
    allFeaturesAssociatedWithWatch(T, Model, TR).
allFeaturesAssociatedWithWatch([H | T], Model, TR) :-
    not(featureAssociatedWithWatch(H, Model)),
    allFeaturesAssociatedWithWatch(T, Model, TR).


% SUBIECTUL al II-lea

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

% O clauza se numeste triviala atunci cand contine atat o variabila propozitionala p, cat si negarea ei, non(p).
% De exemplu, o clauza [a, non(b), non(c), non(a)] este netriviala, intrucat contine atat a, cat si non(a). 
% In acest exercitiu, consideram ca toate clauzele sunt NETRIVIALE. 

% [3 puncte]
% II a) Scrieti un predicat literalForResolution/3 care primeste doua clauze C1 si C2, si returneaza primul literal care poate fi utilizat in rezolutie.
% In cazul in care nu exista un astfel de literal, se va intoarce false.
% Un literal se defineste ca literal ::= p | non(p), unde p este un atom propozitional (din Var). 
% Un literal poate fi utilizat in rezolutie daca apare intr-o clauza, iar in cealalta apare negat, sau vice-versa. 
% De exemplu, daca p apare in C1, si non(p) apare in C2, atunci p este un literal care poate fi utilizat in rezolutie.
% La fel, daca non(p) apare in C1, si p apare in C2, atunci p este un literal care poate fi utilizat in rezolutie.

% ?- literalForResolution([a, non(b), non(c)], [b, non(a)], L).
% L = a 
% ?- literalForResolution([d, non(b), non(c)], [b, non(a), c], L).
% L = b 
% ?- literalForResolution([d, non(b), non(c)], [x, non(y), z], L).
% false 

literalForResolution([H | _], C2, H) :-
    member(non(H), C2).
literalForResolution([non(H) | _], C2, H) :-
    member(H, C2).
literalForResolution([_ | T], C2, Literal) :-
    literalForResolution(T, C2, Literal).

% [7 puncte]
% II b) Scrieti un predicat rezolvent/3 care sa calculeze rezolventul a doua clauze, daca cele doua clauze au un rezolvent, si false in caz contrar.
% Pentru a calcula rezolventul, avem nevoie de o clauza C1 in care avem literalul p, si o clauza C2 in care avem literalul non(p)
% (sau invers, in C1 avem non(p) si in C2 avem p), unde p este orice variabila propozitionala (din Var)
% Rezolventul este C1 reunit C2
% C1 reunit {p}, C2 reunit {non(p)} => Rezolvent = C1 reunit C2
% 
% ?- rezolvent([a, non(b), c], [d, c, b, a], Rezolvent).
% ?- Rezolvent = [d, c, a]
% ?- rezolvent([b], [non(b)], Rezolvent).
% Rezolvent = []
% ?- rezolvent([p, q, r], [p, q, s], Rezolvent).
% false 

% Pentru a sterge un element dintr-o lista, puteti folosi predicatul select/3 
% Exemplu de apel:
% ?- select(a, [b, a, c], Result).
% Result = [b, c]


rezolvent(C1, C2, Rezolvent) :-
    literalForResolution(C1, C2, Literal),
    member(Literal, C1),
    member(non(Literal), C2),
    select(Literal, C1, C1WithoutLiteral),
    select(non(Literal), C2, C2WithoutLiteral),
    union(C1WithoutLiteral, C2WithoutLiteral, Rezolvent).
rezolvent(C1, C2, Rezolvent) :-
    literalForResolution(C1, C2, Literal),
    member(non(Literal), C1),
    member(Literal, C2),
    select(non(Literal), C1, C1WithoutLiteral),
    select(Literal, C2, C2WithoutLiteral),
    union(C1WithoutLiteral, C2WithoutLiteral, Rezolvent).


% 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 b-uri (inclusiv 0 b-uri).
% (nu avem nicio restrictie pe numarul de a-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). 
% atunci true => numar par de b-ui si oricate a-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 + b).
% atunci false => avem numar impar de b-uri 
% ?- start(b + b + b + b).
% atunci true => avem 4 b-uri 
% ?- start(a + a + a).
% atunci true => avem 0 b-uri 


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

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

genb(b + b).
genb(b + 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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%