% cv. 4 ; na 15.3.2017 (St) ; Jan Hric
% v. 1.2.1 	26.3.2018
% v. 1.3.0 	18.3.2019
% 14.3.2020
% 25.3.2021

% Obsah: cv4

% concat/2 ...
% generovani podmnozin subset(+Superset,-Subset); a varianty
%   prototypovy priklad na seznam vysledku
% deklarativni podminky 
%   ordered/1
% kombinace, a varianty
%   a variace
% kartezsky soucin
%   i vic seznamu
% stromy, binarni



%%%%%%%%%%%%%%%%%%%%%%%%%
% priprava adresare
% :- cd('c:/moje'). % s doprednymi lomitky, a s diskem c:
% oznam adresare
% :- pwd.
% kolik mate a potrebujete pameti ...
% :- statistics.


%%%%%%%%%%%%%%%
% spojeni seznamu concat2/2 , concat(+Xss,-Xs)

te1(Vs):- concat2([[1,2],[],[3],[4,5]],Vs), 
  check(Vs,=,[1,2,3,4,5]).

% mnoho vstupu:
% concat(+Xss,-Vs) :- Xss je seznam vnorenych seznamu, Vs je jejich pospojovani
concat2([],[]).	
concat2([Xs|Xss],Vs0) :-		% bylo cviceni
  	% priprava vstupu (1.arg) je v hlave
  append(Xs,Vs1,Vs0), % mod (+,-,-) (A)
    % Xs \= [], % pro generovani
  concat2(Xss, Vs1),
    % postprocesing; jednoduchy postp. se obvykle pise do hlavy
  true. % konec

% (A) tok dat: append muze byt pred rekurzivnim concat2/2 nebo za nim ;
%  pred concat/2 muze byt, protoze vysledek concat/2 zaintegruje 
%   jako celek (skladanim substituci) do celkového výsledku

% Pouziti pro (usporadane) rozdeleni seznamu: 
% 1. potrebujeme append/3 jako prvni cil, aby 3. arg. byl definovan
%	jinak pospecifikovani, tj. leva rekurze
% 2.(B) Pri deleni muzeme libovolne vkladat prazdne seznamy, ty chceme
% 	vynechat

te2(Xss):- concat2(Xss,[1,2,3,4]).
% test rozdelovani:
% preteceni: Out of local stack
% po uprave/pridani testu na prazdne seznamy OK

% Vyuzivame append/3 v mode (+,-,-):
te2a([X,V]):- append([1,2,3],X,V). 
% V=[1,2,3|X] 	% V ma na konci volnou promennou




%%%%%%%%%%%%%%%%%
% podmnoziny: subset
% 1. generovani podmnozin subset1(+Superset,-Subset)
% 2. overeni podmnoziny   subset2(+Superset,+Subset)
%      podmnozina je dana, pripadne v jinem poradi
% 3. generovani vsech podmnozin subsets(+Superset, -Subsets)
%      prototypovy priklad na seznam vysledku

% predpokladame korektni vstupy, 
%   pripadne kontrolujeme predtim 
%   - metoda 2 interfejsů

% generovani podmnozin, backtrackingem
% subset1(+Superset, -Subset).
% ?- subset1([1,2,3],Vs). % vzorove volani, test
% CVICENI/bylo
subset1([],[]).
subset1([X|Xs],Vs0) :-
    subset1(Xs,Vs1), Vs0=[X|Vs1] 
  ; subset1(Xs,Vs1), Vs0=    Vs1 .
% - složená klauzule jde rozdelit na dvě klauzule
% - stejna promenna Vs1 nevadi, pouziva se v ruznych vetvich
% - priklad na pouziti stredniku
% (lepsi) varianta: 2x ... Vs0=.., subset1(Xs,Vs1).
%   - postspracovani je trivialni
% (trochu) efektivnější varianta:
subset3([],[]).
subset3([X|Xs], Vs0) :- 
  subset3(Xs,Vs1), 
  (Vs0 = [X|Vs1] ; Vs0 = Vs1 ).


% testovani podmnoziny, mod (+,+)
% ?- subset1([1,2,3],[1]). % vzorove volani
% CVICENI
subset2(_,[]).
subset2(Xs,[V|Vs]) :- 
  delete2(Xs,V,Xs1),!,	
  subset2(Xs1,Vs),
  true.

% delete/3 (+,+,-)
% v seznamu A1 musi najit A2, vypustí ho a zbylé prvky vrátí v A3
delete2(Xs,X,Vs):-
  append(As,[X|Bs],Xs),
  append(As,   Bs ,Vs).

% test
te3(_Vs):- subset2([1,2,3],[3]),
  subset2([1,2,3],[]),
  subset2([1,2,3],[3,1,2]),
  subset2([],[]),
  not(subset2([1,2,3],[1,2,3,4])),
  true.



% ! programatorsky idiom: seznam vysledku
%   - misto backtrackingu vracime datovou strukturu (najednou) ;
% - neuspech odpovida prazdnemu seznamu vysledků (napriklad, i jine moznosti) ;
% - bude (take) v Hs, kde (neni backtracking a) funkce vraci 1 hodnotu, i strukturovanou

% vsechny podmnoziny, subsets(+Superset, -Subsets)
%   - Chceme: seznam vysledku, na poradi nezalezi
% ?- subsets([1,2],Vs). % volani
%  Vs = [[1,2],[1],[2],[]]  % nebo jine poradi vysledků
% zalozeno na subset1/2, jen skopirovano
% CVICENI/bylo
subsets([],[[]]).	
subsets([X|Xs],Vs0) :-
    subsets(Xs,Vs1), % neobsahuji X 
    map(pridejZac(X),Vs1,Vs2), % Vs2 obsahuji X ,
    append(Vs1,Vs2,Vs0).

% Q: na cem zalezi poradi prvku ve vysledkem seznamu?

% bude se hodit: pridejZac/3 
% pridejZac(+X,+Xs,-[X|Xs]).
pridejZac(X,Xs,[X|Xs]).
% map(+P,+Ins,-Outs) 
map(_P,[],[]).
map( P,[I|Is],[O|Os]) :- 
  call(P,I,O), 	% magie, zatim
  map( P,Is,Os).
% map/3 využívá call/3, které je mimo predikátovou logiku 1. řádu (proto magie)
% lze napsat "specializovanou" relaci pridejZačátky/3_(X,Ins,Outs), která místo call volá pridejZac/3.

te4(Vs) :- map(pridejZac(9),[[],[1],[1,3,5]],Vs).


% Popiste deklarativni podminky (pro spravny vystup) na 
% - permutace/2
% - sort vracejici usporadanou mnozinu (v seznamu, vstup s/bez opakovani)
% - merge/3 z mergesortu
% ... za urcitych vstupnich podminek. 
% ... i castecne podminky, ktere zachyti nektere spatne vystupy
% Priklad: sort, predpoklad: na vstupu je mnozina.
%  1. Vystup je usporadany, viz ordered/1 nize.
%  2. Delka vystupu se rovna delce vstupu.
%  3. Vystup je permutaci vstupu, nebo rozepsane:
%  3a. Vystup je podmnozina vstupu. (subset2/2 vyse)
%  3b. Vstup je podmnozina vystupu.
% Kdyz jsou vystupni data uz spocitana, tak jdou testy casto delat efektivne.

% test usporadanosti: ordered/1 :- uspeje, kdyz je vstupni seznam usporadany
% CVICENI/bonus
ordered([]).
ordered([_X|Xs]) :- 
   % vhodny test
  ordered(Xs).


%%%%%%%%%%%
% kombinace (bez opakovani)
% interface: C(5,3), prvky explicitne - jako u permutaci
% a) komb1(3, [1,2,3,4,5], V) :- backtrackingem ; az budou cisla
% b) komb2(s(s(s(0))), [1,2,3,4,5], V) :- dtto
% c) komb3([1,2,3,4,5], [X1,X2,X3]) :- V = [X1,X2,X3], ...
% 	delka vystupu je urcena delkou seznamu V
% c1) komb4/3, komb4([_,_,_],[1,2,3,4,5], Vs) :- 1.arg je citac, ze ktereho synchronne vybirame;
%       varianta na permutace
% pro a) a b) lze jednoduse generovat seznam vsech kombinaci
%  - ale je to pametove narocne, Prolog nema line vyhodnocovani (pro postupne generovani)

% Nektere NP-uplne problemy lze jednoduse _popsat_. 
%   Porad budou vypocetne tezke.
% Metoda generuj a testuj (pomoci backtrackingu).


% kombinace, bez opakovani ...
% predpoklad: aritmetika
% interface a)
komb1(0,_,[]).
komb1(N,[X|Xs],[X|Vs]) :-  % X pridame do kombinace
  N>0, % test kvuli deklarativite a backtrackingu 
  N1 is N-1,
  komb1(N1,Xs,Vs).
komb1(N,[_X|Xs],Vs) :-	% X nepridame do kombinace (-> a ani do rekurze)
  N>0, % test kvuli deklarativite a backtrackingu; zkuste vypustit 
  komb1(N,Xs,Vs).
% test je laciny, nevadi, ze je 2x; if-then-else bude pozdeji
% pri vypustenem testu se (spravne) vysledky opakuji:
%   deklarativne OK, proceduralne nevhodne

te5(Vs) :- komb1(3,[1,2,3,4,5],Vs).


% kombinace s opakovanim, 
% CVICENI, upravte 
komb2(0,_,[]).
komb2(N,[X|Xs],[X|Vs]) :-
  N>0, % test kvuli deklarativite a backtrackingu 
  N1 is N-1,
  komb2(N1,Xs,Vs).
komb2(N,[_X|Xs],Vs) :-
  N>0, 
  komb2(N,Xs,Vs).

te6(Vs) :- komb2(2,[1,2,3,4],Vs).

% Variace bez opakovani, 
% CVICENI, upravte
variace1(0,_,[]).
variace1(N,[X|Xs],[X|Vs]) :-
  N>0, 
  N1 is N-1,
  variace1(N1,Xs,Vs).
variace1(N,[_X|Xs],Vs) :-
  N>0, 
  variace1(N,Xs,Vs).

te7(Vs) :- variace1(2,[1,2,3,4],Vs).


% kombinace, bez opakovani 
% interface b) ; 
% bez aritmetiky, tj. pomoci numeralu 
komb1b(0,_,[]).
komb1b(s(N),[X|Xs],[X|Vs]) :-  % X pridame do kombinace
  % N>0  % (A) test nepotrebujeme
  komb1b(N,Xs,Vs).
komb1b(N,[_X|Xs],Vs) :-	% X nepridame do kombinace (-> a ani do rekurze)
  N\=0, % test kvuli deklarativite a backtrackingu; zkuste vypustit 
  komb1b(N,Xs,Vs).
% pri vypustenem testu se (spravne) vysledky opakuji:
%   deklarativne OK, proceduralne nevhodne

te5b(Vs) :-  %  
    write(komb(2,4)),nl, 
  komb1b(s(s(0)),[1,2,3,4],Vs) 
    , write(Vs), nl ,fail ; 
    write(komb(3,5)), nl,
  komb1b(s(s(s(0))),[a,b,c,d,e],Vs)
    , write(Vs), nl ,fail . 


% programatorsky idiom: seznam vysledku: 
% na rozmysleni/do tramvaje: 
% kombinace, seznam vsech v seznamu
% hint: potrebujete soucasne vysledky obou klauzuli z predchoziho prikladu, 
%	proto musite obe rekurzivni volani mit v jedne klauzuli.

% varianta: spocitat, kolik je kombinaci
% pozn1: pametove prijatelne, casove narocne - jako predtim, 
% pozn2: kombinace *nebudete* pocitat po jedne, protoze je znamy explicitni vzorec.
%	Ale pokud mate dodatecnou podminku
%	a chcete spocitat jen *ty_spravne* kombinace, tak je to pouzitelne.


%%%%%%%%%%%%%%%
% kartezsky soucin
% - dvou
% - i vic
% - vyber z indexovaneho seznamu

%%%%%%%%%%%%%%%
% stromy, binarni: funktory: t/3, nil/0
% proc. prohledani/2, vyda casy otevreni a uzavreni vrcholů, v seznamu

prohledani(BS, Vs) :-
  prohledani(BS,1,_N,Vs).  % 2. a 3. arg. jsou cisla prvni a po-posledni akce
% predavani stavu v 2. a 3. arg

% :-) jsou i jine zpusoby prohledavani nez preorder, inorder a postorder
prohledani(nil,N,N,[]).
prohledani(t(LS,X,PS), N1, N0, [open(X,N1)|Vs]) :-
   % Vs = ... v hlave
  N2 is N1+1,
  prohledani(LS,N2,N3, VL),  % N1,N2,N3,... obsahuji predavany stav
  prohledani(PS,N3,N4, VP),
  N0 is N4+1,
  concat2([VL,VP,[close(X,N4)]],Vs).
  % append(VP,[close(X,N4)],VP1), append(VL, VP1,Vs).  % varianta



te8(Vs) :- 
  dataT(t1,TT),
  prohledani(TT, Vs),
  write(Vs),nl.

% testovaci data, pojmenovane t1:
dataT( t1, t(t(nil,a,nil),
             b,
             t(t(nil,c,nil),
               d,
	       t(nil,e,nil)
            ) )
     ).

/*   b           1b10
    / \          / \
   a   d       2a3 4d9
      / \          / \
     c   e       5c6 7e8
*/

% Vrcholy stromu: vrcholyT/2
vrcholyT(nil,[]).
vrcholyT(t(L,X,R),V):-
  vrcholyT(L,VL), vrcholyT(R,VR),
  append(VL, [X|VR],V).	% vhodnejsi by bylo sjednoceni, obecne

te9(Vs):-  
  dataT(t1,TT),
  vrcholyT(TT, Vs).

% rotace, ty z AVL a Cerveno-cernych stromu
% - skoro urcite neudelate chybu
% rot/2 : [a1]doleva vyrotovany strom, [a2]doprava vyrotovany strom
rot(t(t(A,X,B),Y,C), t(A,X,t(B,Y,C)) ).

te10([LS,S,RS]):- dataT(t1,S),
rot(LS,S), % rotace jednim smerem
rot(S,RS), % rotace druhym smerem, v koreni
write(LS),nl,
write(S), nl,
write(RS),nl.



%%%%%%%%%%%%%%%%
% Q: Deklarativni a proceduralni semantika
% - co znate: castecnou spravnost, konecnost, uplnou spravnost;
%   - modely (z logiky)
% - program je spravny vuci pozadavkum/specifikaci (, 
%   - zamysleny vyznam/semantika (bez chyb) vs. (skutecny) vyznam,
% - deklarativni semantika: chovani "cisteho" Prologu: plati cil v modelu programu?
%   - zkratka: deklarativne spravny program nevyda nespravny vysledek,
%     muze neskoncit (tj. je castecne spravny)
% - ne kazdy program/predikat ma deklarativni semantiku
% - proceduralni semantika: 
%   - mnohe vestavene predikaty (is, not), ! (tj. řez) nemaji deklarativni sem. 
%   - popisuje kolikrat program vyda reseni (a jestli vubec~konecnost), 
%	v jakem poradi, ...
%   -


%%%%%%%%%%%%%%%%%%%%
% souhrn: co jste si vyzkouseli:
% - idiom: seznam vysledku
% - deklarativni testy
% - reprezentaci stromu
% - aritmetiku
% - idiom: predavani stavu
% - rozdil mezi deklarativni a proceduralni semantikou



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% cv.3
% zbylo

% dva vystupy:
% rozdeleni na prvni a druhou polovinu: z prednasky?
% idea: seznam v akumulatoru jsme pouzili jako pocitadlo delky 
% je dobre vedet, jak se rozdeli seznam liche delky
%  Q: proc?

% rozdel/3, rozdel(+Xs,-Sude,-Liche) :- rozdeli Xs na Sude a Liche prvky
% cviceni

% pouziti v mergesort/2, mergesort(Xs,Vs) :- Vs je usporadana verze Xs.
% predikaty pro porovnani: X < Y, X =< Y
% predpokladejte, ze mate merge/3, 
%  merge(+Xs1,+Xs2,-Vs) :- Vs je usporadane zmergovani Xs1 a Xs2
% pro pouziti v mergesortu chceme nechavat i opakujici se hodnoty.
mergesort(Xs,Vs):- 	% cviceni
  rozdel(Xs,_Xs1,_Xs2),
   % doplnit
  merge(_Vs1,_Vs2,Vs),
  true.

% rozdel/3 (+,-,-)
% metoda zde: sude-liche
rozdel([],[],[]).
rozdel([X],[X],[]).
rozdel([X,Y|Xs],[X|Xs1],[Y|Xs2]) :-
  rozdel(Xs,Xs1,Xs2).
% varianta: první/druhá polovina, trochu efektivnější, lze i bez explicitního počítání délky 
% tj. s implicitním počítáním 

% ordered(Xs) :- test, zde prvky jsou v neklesajicim poradi.
% ordered(_) :- true. % cviceni/bonus

% pro ladeni: 
% - deklarativni specifikace podminek (typicky castecnych, ale i uplnych)
%  - lepsi nez unit testy
% priklad: podminky pro merge/3
% Q: podminky na delku/mohutnost seznamů 
% Q: dalsi, az uplne podminky
% - vyuziva se mj. deklarativnosti, procedur bez sideefektů

% DC: trans/2, transpozice matice, predpokladame korektni zadani ;-)
% trans(+Mat, -Transp) 
  % Q: proc korektni zadani
% dve moznosti, ...

% dalsi: (rezerva)
% na prednasce: permutace, vypust
% idea/idiom: rekurze podle vystupu
%   - jiny priklad tehoz: selectSort/trideni vyberem

%--------

%%%%%%%%%%%%%%%%%%%%%%%%%%%
% runtime
check(Tested,=,Pattern) :- 
  Tested = Pattern -> write(passed),nl
                   ;  write(error),nl, 
		      write(value__(Tested)),nl, 
		      write(expected(Pattern)),nl.

%----------------

% konec.
