/*                     Deklaratív programozás, 2. gyakorlat
                            Prolog programozás

			       MEGOLDÓKULCS

---------------------------------------------------------------------------


"A" Témakör: a Prolog alapelemei	
================================

A1.

  [a*b-X,c+X]=[Y-3|Z]                      

    bal:  .(-(*(a,b),X),.(+(c,X),[]))
    jobb: .(-(Y,     3),Z           )

  ----> X=3, Y=a*b, Z=[c+3]

A2.

  g(V*W,[1*2+3|Z])=g(K,[K+L,L])

    bal:  g(*(V,W),.(+(*(1,2),3),Z      ))
    jobb: g(K,     .(+(K,     L),.(L,[])))

  ----> K=1*2, L=3, V=1, W=2, Z=[3]

A3.

  s([a]-X/2,[X|Z])=s(Z-Y,[f,C]) 

    bal:  s(-(.(a,[]),/(X,2)),.(X,Z      ))
    jobb: s(-(Z,      Y),     .(f,.(C,[])))

  ----> C=a, X=f, Y=f/2, Z=[a]

A4.

  [A+B,C*2|T]=[x/C+2,y*B,B-C]

    bal:  .(+(A,     B),.(*(C,2),T           ))
    jobb: .(+(/(x,C),2),.(*(y,B),.(-(B,C),[])))

  ----> A=x/y, B=2, C=y, T=[2-y]


A5., A7., A8. lásd külön lapon.

Az ezekben használt program:

*/


% f(X, Y): X felmenője Y.
f(X, Y) :-
	sz(X, S),
	f(S, Y). 		  % (f1)
f(X, X).                          % (f2)

% sz(X, Y): X szülője Y.
sz(a, b).                         % (sz1)
sz(a, c).                         % (sz2)
sz(b, d).                         % (sz3)


/*


"P". Témakör: programok írása
=============================
*/

% 1.  Számsorozat generálása  

%     % seq(+N, +M, -L): Az L lista M-N+1 hosszú, elemei 1 különbségű 
%     % számtani sorozatot alkotnak, és L első eleme (ha van) N, 
%     % ahol N és M egész számok.

%     | ?- seq(2, 4, L).
%     L = [2,3,4] ? ; no
%     | ?- seq(4, 2, L).
%     no
%     | ?- seq(4, 3, L).
%     L = [] ? ; no
%     | ?- seq(-4, -2, L). 
%     L = [-4,-3,-2] ? ; no

% seq(+N, +M, -L): Az L lista M-N+1 hosszú, elemei 1 különbségű számtani
% sorozatot alkotnak, és L első eleme (ha van) N, ahol N és M egész számok. 
seq(N, M, []) :-
	M =:= N - 1.
seq(N, M, [N|Seq]) :-
	M >= N,
	N1 is N+1,
	seq(N1, M, Seq).


% 2.  Számintervallum felsorolása

%     % max(+N, ?X): X egy egész szám, melyre 0 < X =< N, ahol N adott
%     % pozitív egész szám. Az eljárás a fenti feltételeknek megfelelő X
%     % számokat sorolja fel. A felsorolás sorrendjére nem teszünk megkötést.

%     | ?- max(1,X).
%     X = 1 ? ; no 
%     | ?- max(4,X).
%     X = 4 ? ; X = 3 ? ; X = 2 ? ; X = 1 ? ; no 
%     | ?- max(4,3).
%     yes 
%     | ?- max(4,5).
%     no

% max(+N, ?X): X egy egész szám, melyre 0 < X =< N.
max(N, N) :-
	N > 0.
max(N, X) :-
	N > 1,
	N1 is N-1,
	max(N1, X).


% 3.  Hatványozás

%     % hatv(+A, +E, -H):  H = A ^ E, ahol A egész szám, E >= 0 egész szám.

%     | ?- hatv(3, 5, X).
%     X = 243 ? ; no

% hatv(+A, +E, -H):  H = A ^ E, ahol A egész szám, E >= 0 egész szám.
hatv(A, N, H) :-
	N > 0,
	N1 is N-1,
	hatv(A, N1, H1),
	H is A*H1.
hatv(_A, 0, 1).


% 4.  Fa csomópontjainak megszámolása

%     Egy fa csomópontjainak száma a benne előforduló node/2 struktúrák
%     száma. 
    
%     % fa_pontszama(*Fa, -N): A Fa bináris fa csomópontjainak száma N.

%     | ?- fa_pontszama(node(leaf(1),node(leaf(2),leaf(3))), N).
%     N = 2 ? ; no
%     | ?- fa_pontszama(node(leaf(1),node(leaf(2),node(leaf(4),leaf(3)))), 
%                       N).
%     N = 3 ? ; no

% fa_pontszama(+Fa, -N): A Fa bináris fa csomópontjainak száma N.
fa_pontszama(leaf(_), 0).
fa_pontszama(node(L,R), P) :-
	fa_pontszama(L, LP),
	fa_pontszama(R, RP),
	P is LP+RP+1.


% 5.  Fa minden levélértékének növelése
    
%     % fa_noveltje(*Fa0, ?Fa): Fa úgy áll elő a Fa0 bináris fából, hogy az
%     % utóbbi minden egyes levelében levő értéket 1-gyel megnöveljük.
    
%     | ?- fa_noveltje(node(leaf(1),node(leaf(2),leaf(3))), Fa).
%     Fa = node(leaf(2),node(leaf(3),leaf(4))) ? ; no

% fa_noveltje(+Fa0, ?Fa): Fa úgy áll elő a Fa0 bináris fából, hogy az
% utóbbi minden egyes levelében levő értéket 1-gyel megnöveljük.
fa_noveltje(leaf(X), leaf(Y)) :-
	Y is X+1.
fa_noveltje(node(L,R), node(NL,NR)) :-
	fa_noveltje(L, NL),
	fa_noveltje(R, NR).


% 6.  Lista hosszának meghatározása

%     Egy lista hosszának az elemei számát nevezzük.

%     % lista_hossza(*Lista, -Hossz): A Lista egészlista hossza Hossz.

%     | ?- lista_hossza([1,3,5], H).
%     H = 3 ? ; no

% lista_hossza(+Lista, -Hossz): A Lista egészlista hossza Hossz.
lista_hossza([], 0).
lista_hossza([_|L], H) :-
	lista_hossza(L, H0),
	H is H0+1.

% 6*. (szorgalmi, otthoni feladat) Lista hosszának meghatározása --
%     jobbrekurzív változat 
    
%     % lista_hossza2(*Lista, -Hossz): A Lista egészlista hossza Hossz.    
%     % Jobbrekurzív változat
%     Segédeljárás szükséges.

% lista_hossza2(+Lista, +H0, H): A Lista egészlista hossza H-H0.
lista_hossza2([], H0, H0).
lista_hossza2([_|L], H0, H) :-
	H1 is H0+1,
	lista_hossza2(L, H1, H).

% lista_hossza2(+Lista, -Hossz): A Lista egészlista hossza Hossz.
lista_hossza2(Lista, Hossz) :-
	lista_hossza2(Lista, 0, Hossz).


% 7.  Egészlista minden elemének növelése

%     % lista_noveltje(*L0, ?L): Az L egészlista úgy áll elő az L0
%     % egészlistából, hogy az utóbbi minden egyes elemét 1-gyel megnöveljük.
    
%     | ?- lista_noveltje([1,5,2], L).
%     L = [2,6,3] ? ; no

% lista_noveltje(+L0, ?L): Az L számlista úgy áll elő az L0		  
% számlistából, hogy az utóbbi minden egyes elemét 1-gyel megnöveljük.
lista_noveltje([], []).
lista_noveltje([X|L], [NX|NL]) :-
	NX is X+1,
	lista_noveltje(L, NL).


% 8.  Egy lista utolsó elemének meghatározása

%     % lista_utolso_eleme(*L, ?Ertek): Az L egészlista utolsó eleme Ertek.

%     | ?- lista_utolso_eleme([5,1,2,8,7], E).
%     E = 7 ? ; no
 
% lista_utolso_eleme(+L, ?Ertek): Az L egészlista utolsó eleme Ertek.
lista_utolso_eleme([E], E).
lista_utolso_eleme([_|L], E) :-
	lista_utolso_eleme(L, E).


% 9.  Egy fa leveleiben található értékek felsorolása

%     % fa_levelerteke(*Fa, -Ertek): A Fa bináris fa egy levelében található
%     % érték az Ertek.

%     Az eljárás nemdeterminisztikus módon sorolja fel az összes
%     levélértéket.  A felsorolás sorrendjére nem teszünk megkötést.

%     | ?- fa_levelerteke(node(leaf(1),node(leaf(2),leaf(3))), E).
%     E = 1 ? ; E = 2 ? ; E = 3 ? ; no

% fa_levelerteke(*Fa, -Ertek): A Fa bináris fa egy levelében található
% érték az Ertek.
fa_levelerteke(leaf(E), E).
fa_levelerteke(node(L,_), E) :-
	fa_levelerteke(L, E).
fa_levelerteke(node(_,R), E) :-
	fa_levelerteke(R, E).


% 10. Egy fa részfáinak a felsorolása
    
%     Egy fa (nem feltétlenül valódi) részfájának nevezzük saját magát,
%     valamint - ha a fa egy csomópont - akkor a bal és jobboldali ág
%     részfáit. 
    
%     % fa_reszfaja(*Fa, -Resz): Resz a Fa bináris fa részfája.
    
%     A fenti eljárás nemdeterminisztikus, azaz többféleképpen sikerül:
%     a Resz változóban fel kell sorolnia a Fa összes részfáját. A felsorolás
%     sorrendjére nem teszünk megkötést.

%     | ?- fa_reszfaja(node(leaf(1),node(leaf(2),leaf(3))), Fa).
%     Fa = node(leaf(1),node(leaf(2),leaf(3))) ? ;
%     Fa = leaf(1) ? ;
%     Fa = node(leaf(2),leaf(3)) ? ;
%     Fa = leaf(2) ? ;
%     Fa = leaf(3) ? ; no

%     Gondolja meg, hogy a predikátum klózai sorrendjének változtatásakor
%     hogyan változik a felsorolás sorrendje!

% fa_reszfaja(+Fa, -Resz): Resz a Fa bináris fa részfája.
fa_reszfaja(Fa, Fa).
fa_reszfaja(node(L,_), Fa) :-
	fa_reszfaja(L, Fa).
fa_reszfaja(node(_,R), Fa) :-
	fa_reszfaja(R, Fa).

%     A fa_reszfaja eljárás felhasználásával írja meg a 9. feladat
%     megoldását, fa_levelerteke2 néven!

% fa_levelerteke2(+Fa, -Ertek): A Fa bináris fa egy levelében található
% érték az Ertek.
fa_levelerteke2(Fa, E) :-
	fa_reszfaja(Fa, leaf(E)).

% 11. Egy lista prefixumainak a felsorolása

%     Egy L n-elemű lista prefixumának nevezzünk egy listát, ha az az L 
%     első k elemét tartalmazza (az L-beli sorrend megtartásával),
%     ahol 0 =< k =< n.

%     % lista_prefixuma(*L0, -L): L az L0 egészlista prefixuma.

%     A fenti eljárás nemdeterminisztikus, azaz többféleképpen sikerül: az L
%     változóban fel kell sorolnia a L0 összes prefixumát. A felsorolás
%     sorrendjére nem teszünk megkötést.

%     | ?- lista_prefixuma([1,4,2], Sz).
%     Sz = [1,4,2] ? ;
%     Sz = [1,4] ? ;
%     Sz = [1] ? ;
%     Sz = [] ? ; no

%     Gondolja meg, hogy a predikátum klózai sorrendjének változtatásakor
%     hogyan változik a felsorolás sorrendje!

% lista_prefixuma(*L0, -L): L az L0 egészlista prefixuma.
lista_prefixuma([X|L], [X|P]) :-
	lista_prefixuma(L, P).
lista_prefixuma(_, []).
