Prolog - male ulozky

Napsal: David

Sada malych uloh z Prologu i s resenim. Vyborne pro pripravu na zkousku z neproceduralniho programovani.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Male ulohy Prolog %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% 1. SPIRALA MATICE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Matici m*a muzeme reprezentovat jako seznam (delky m) radkovych seznamu
% (delek a) jejich prvku. Sestavte predikat otoc(+Mat,-OtMat), ktery otoci
% takto reprezentovanou matici o 90 stupnu proti smeru hodinovych rucicek.
% Na jeho zaklade sestavte predikat spirala(+Mat,-Sez), ktery "oloupa seznam
% z matice Mat do seznamu Sez". Postupujte pitom z leveho horniho rohu
% po smeru hodinovych rucicek.

% otoc(+Mat,-OtMat)
otoc(Mat,OtMat):-
otocAk(Mat,[],OtMat).

% getLine(+Mat,-Line,-NewMat)
getLine([],[],[]).
getLine([[Head|Tail]|MatTail],[Head|TailLine],[Tail|NewMatTail]):-
getLine(MatTail,TailLine,NewMatTail).

% otocAk(+Mat,+Ak,OtMat)
otocAk([],Ak,Ak).
otocAk([[]|_],Ak,Ak).
otocAk(Mat1,Ak,OtMat):-
getLine(Mat1,Line,NewMat1),
append([Line],Ak,NewAk),
otocAk(NewMat1,NewAk,OtMat).


% spirala(+Mat,-Sez)
spirala(Mat,Sez):-
spiralaAk(Mat,[],Sez).

% spiralaAk(+Mat,+Ak,-Sez)
spiralaAk([],Ak,Ak).
spiralaAk([Head|Tail],Ak,Sez):-
append(Ak,Head,NewAk),
otoc(Tail,NewMat),
spiralaAk(NewMat,NewAk,Sez).


% testy

sm_t1:-otoc([[1,2],[3,4],[5,6]],X), write(X).
sm_t2:-otoc([[1,2,3,4,5],[a,b,c,d,e],[x1,x2,x3,x4,x5]],X), write(X).
sm_t3:-spirala([[1,2,3],[4,5,6],[7,8,9]],X), write(X).
sm_t4:-spirala([[1,2,3,4],[5,6,7,8],[9,a,b,c]],X), write(X).
sm_t5:-spirala([[1,2,3],[4,5,6],[7,8,9],[a,b,c],[d,e,f]],X), write(X).




%% 2. TAUTOLOGY CHECKER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Sestavte predikat taut(+Formule), ktery pokud je Formule spravne utvorena
% formule vyrokov�o poctu:
% [spojky unarni: ~ (negace),
%  spojky binarni: & (konjunkce), # (disjunkce), => (implikace)
%  s obvyklymi prioritami, zavorky pro zmenu poradi vyhodnocovani,
%  vyrokove promenne - mala pismena]
% uspeje prave kdyz je tato formule tautologii (tautologie je formule, ktera
% nabyva hodnoty true nezavisle na ohodnoceni elementarnich formuli, ktere
% obsahuje).
% Napiste i predikaty, ktere zajisti pouziti prislusnych spojek jako
% operatoru.

% reseni s promennymi jako malymi pismenky nezname
% naznak reseni (=nefunkcni) s velkymi pismenky nasleduje
% pod nim v komentari jeste cizi tautology checker s jinou syntaxi

% taut(+Formule)
taut(Formule):-                         % formule je tautologie prave tehdy,
\+ sat(~(Formule)).                     % kdyz jeji negace neni splnitelna

sat(Formule):-                          % formule je splnitelna prave tehdy,
eval(Formule,1).                      % nejaka kombinace vede na 1

:-op(100,yfx,'=>').
:-op(200,yfx,'#').
:-op(300,yfx,'&').
:-op(400,fx,'~').

eval(V,V):-                             % vyhodnot promennou
var(V),
!,
evalute(V).

eval(V,V):-                             % ohodnot konstatny
evalute(V),
!.

eval(~E,R):-                            % vyhodnot negaci
!,
eval(E,V),
(
  (V=0,R=1)
  ;
  (V=1,R=0)
).

eval(A&B,R):-                           % ohodnot binarni operatory
!,
eval(A,Av),                           % vyhodnoceni podvyrazu nalevo
eval(B,Bv),                           % vyhodnoceni podvyrazu napravo
and(Av,Bv,R).                         % pouziti operatoru

eval(A#B,R):-                           % ohodnot binarni operatory
!,
eval(A,Av),                           % vyhodnoceni podvyrazu nalevo
eval(B,Bv),                           % vyhodnoceni podvyrazu napravo
and(Av,Bv,R).                         % pouziti operatoru
              
eval(A=>B,R):-                          % ohodnot binarni operatory
!,
eval(A,Av),                           % vyhodnoceni podvyrazu nalevo
eval(B,Bv),                           % vyhodnoceni podvyrazu napravo
imp(Av,Bv,R).                         % pouziti operatoru

% evalute udava mozne hodnoty promenne
evalute(0).
evalute(1).

% operatory
and(0,_,0):- !.
and(_,0,0):- !.
and(1,1,1):- !.

or(0,0,0).
or(1,_,1):-  !.
or(_,1,1):-  !.

imp(0,_,1):- !.
imp(1,V,V):- !.


% TAUTOLOGY CHECKER by Robert F. Staerk
%
% list([]).
% list([X|L]) :- list(L).
%
% member(X,[X|L]).
% member(X,[Y|L]) :- member(X,L).
%
% formula(p(X)).
% formula(neg(A)) :- formula(A).
% formula(and(A,B)) :- formula(A), formula(B).
% formula(or(A,B)) :- formula(A), formula(B).
%
% literal(p(X)).
% literal(neg(p(X))).
%
% literal_list([]).
% literal_list([A|I]) :-
%         literal(A),
%         literal_list(I).
%
% interpretation(I) :- literal_list(I), not incon(I).
%
% incon(I) :- member(p(X),I), member(neg(p(X)),I).
%
% valid(A) :- not satisfiable(neg(A)).
%
% satisfiable(A) :- true(A,[],I).
%
% true(p(X),I,[p(X)|I]) :- not member(neg(p(X)),I).
% true(neg(A),I,J) :- false(A,I,J).
% true(and(A,B),I,K) :- true(A,I,J), true(B,J,K).
% true(or(A,B),I,J) :- true(A,I,J).
% true(or(A,B),I,J) :- true(B,I,J).
%
% false(p(X),I,[neg(p(X))|I]) :- not member(p(X),I).
% false(neg(A),I,J) :- true(A,I,J).
% false(and(A,B),I,J) :- false(A,I,J).
% false(and(A,B),I,J) :- false(B,I,J).
% false(or(A,B),I,K) :- false(A,I,J), false(B,J,K).
%
% eval(p(X),I,1) :- member(p(X),I).
% eval(p(X),I,0) :- member(neg(p(X)),I).
% eval(neg(A),I,1) :- eval(A,I,0).
% eval(neg(A),I,0) :- eval(A,I,1).
% eval(and(A,B),I,1) :- eval(A,I,1), eval(B,I,1).
% eval(and(A,B),I,0) :- eval(A,I,0).
% eval(and(A,B),I,0) :- eval(B,I,0).
% eval(or(A,B),I,1) :- eval(A,I,1).
% eval(or(A,B),I,1) :- eval(B,I,1).
% eval(or(A,B),I,0) :- eval(A,I,0), eval(B,I,0).
%
% defined(p(X),I) :- member(p(X),I).
% defined(p(X),I) :- member(neg(p(X)),I).
% defined(neg(A),I) :- defined(A,I).
% defined(and(A,B),I) :- defined(A,I), defined(B,I).
% defined(or(A,B),I) :- defined(A,I), defined(B,I).




%% 3. NEZAVISLA MNOZINA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Je dan graf G=(V,E). Najdete libovolnou maximalni nezavislou mnozinu W.
% Nezavisla mnozina je takova podmnozina V, ze zadne jeji dva vrcholy nejsou
% spojeny hranou. Pozadavek maximality se nevztahuje na G, ale na W - tj.
% W nelze zvetsit, ale v G muze existovat jina nezavisla mnozina W', ktera je
% vetsi.

% reprezentace dat - vertex(V), edge(U,V)

% edgeG(+A,+B) - splneno, pokud hrana A-B v G
edgeG(A,B):- edge(A,B) ; edge(B,A).

% noedgeG(+A,+B) - splneno neni-li hrana A-B v G
noedge(A,B):- \+ edgeG(A,B).

% is_vertex(+Vs,+V) - splneno, pokud Vs a take [V|Vs] nezavisle mnoziny
is_vertex([],_).                        % konec rekurze
is_vertex([Head|Tail],V):-              % prvek lze pridat do nezavisle mnoziny
noedge(Head,V),                       % pokud neexistuje hrana s hlavou
is_vertex(Tail,V).                    % a neexistuje hrana s prvkem v tele

% insetG(-IS) - IS je nezavisla mnozina G
insetG(IS):-
vertex(V),                            % vyber 1. vrchol do nezavisle mnoziny
insetG([V],IS).                       % utvor nezavislou mnozinu obsahujici
                                      % tento vrchol

% insetG(+Vs,-IS) nezavisla mnozina obsahujici vrcholy Vs
insetG(Vs,IS):-
vertex(U),                            % vyber vrchol
\+ member(U,Vs),                      % ktery jeste neni ve Vs
is_vertex(Vs,U),                      % pokud lze pridat
insetG([U|Vs],IS).                    % rekurze pro vetsi mnozinu
insetG(Vs,Vs).                          % jiz neslo pridat -> napln vystupni IS

% testovaci data

vertex(a).
vertex(b).
vertex(c).
vertex(d).
vertex(e).
vertex(f).
vertex(g).
vertex(h).

edge(a,b).
edge(a,c).
edge(a,f).
edge(b,g).
edge(c,d).
edge(c,e).
edge(c,g).
edge(d,e).

% testy
is_t1:-insetG(W),write(W).




%% 4. KARTEZSKY SOUCIN GRAFU %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Jsou dany grafy G1=(V1,E1), G2=(V2,E2), vytvorte G=(V,E)=G1*G2, tedy E=V1*V2
% a ((u1,u2),(v1,v2)) in E, jestlize (u1,v1) in E1 a (u2,v2) in E2.

% priklad:
%
% G1=({a,b,c},{(a,b),(b,c)})                G2({1,2,3,4},{(1,2),(3,4)})
%
%       a                                       1 3
%       |                                       | |
%       b-c                                     2 4
%
%
% G=({a1,b1,c1,a2,b2,c2,a3,b3,c3,a4,b4,c4},{(a1,b2),(a2,b1),(b1,c2),(b2,c1),
%     (a3,b4),(a4,b3),(b3,c4),(b4,c3)})
%
%       a  * * * *
%           X   X
%       b  * * * *
%           X   X
%       c  * * * *
%
%          1 2 3 4
%

% reprezentace dat - vertexKP(G,V), edgeKP(G,U,V)

% edgeKPG(+G,?A,?B) - splneno, pokud hrana A-B v G
edgeKPG(G,A,B):- edgeKP(G,A,B) ; edgeKP(G,B,A).

% kp(+G1,+G2,-E) vrati hrany kartezskeho soucinu G1*G2, vrcholy jsou zrejme
kp(G1,G2,E):-
kp(G1,G2,[],E).

kp(G1,G2,KPE,E):-
edgeKPG(G1,U1,V1),
edgeKPG(G2,U2,V2),
\+ member(U1*U2-V1*V2,KPE),
\+ member(U1*V2-V1*U2,KPE),
append(KPE,[U1*U2-V1*V2],KPENew),
kp(G1,G2,KPENew,E).
kp(_,_,KPE,KPE).

% testovaci data

vertexKP(g1,a).
vertexKP(g1,b).
vertexKP(g1,c).
vertexKP(g2,x1).
vertexKP(g2,x2).
vertexKP(g2,x3).
vertexKP(g2,x4).

edgeKP(g1,a,b).
edgeKP(g1,b,c).
edgeKP(g2,x1,x2).
edgeKP(g2,x3,x4).

% testy
kp_t1:-kp(g1,g2,G),write(G).




%% 5. PREVOD N-ARNI -> BINARNI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Sestavte funkci realizujici kanonickou reprezentaci obecneho stromu pomoci
% binarniho ("levy syn" = prvorozeny syn, "pravy syn" = mladsi bratr).


% reprezentace dat
%
% N-arni strom reprezentovan tN(Value,[Child]) nebo nilN
% binarni strom reprezentovan tB(Left,Value,Right) nebo nilB

% convNB(+TreeN,-TreeB) prevede N-arni strom na binarni

convNB(nilN,nilB).
convNB(TreeN,TreeB):-
convNBs([TreeN],TreeB).

convNBs([],nilB).
convNBs([tN(Value,[])],tB(nilB,Value,nilB)).

convNBs([tN(Value,Children)],tB(TreeB,Value,nilB)):-
convNBs(Children,TreeB).

convNBs([tN(Value,Children)|TNTail],tB(TreeB,Value,TreeB2)):-
convNBs(Children,TreeB),
convNBs(TNTail,TreeB2).


% testovaci stromy

treeN1(X):-
X=tN(10,
[
  tN(5,
  [
    tN(2,[]),
    tN(7,[])
  ]),
  tN(7,
  [
    tN(10,[])
  ]),
  tN(12,[]),
  tN(3,
  [
    tN(18,[]),
    tN(1,[]),
    tN(40,[])
  ])
]).

treeN2(X):-
X=tN(10,
[
  tN(5,
  [
    tN(4,[]),
    tN(1,[])
  ]),
  tN(7,[]),
  tN(2,[])
]).

% testy

cNB_t1:-treeN1(X),convNB(X,TB),write(TB).
cNB_t2:-treeN2(X),convNB(X,TB),write(TB).




%% 6. RIDKE POLYNOMY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Naprogramujte soucin ridkych polynomu reprezentovanych jako seznam dvojic
% prv(Koef,Exp), kde Koef je nenulovy koeficient u exponentu Exp.


% predpokladame rostouci seznam v reprezentaci polynomu

% insP(+Tuple,+List,-List2) zaradi Tuple do Listu na spravnou pozici
insP(T,[],[T]).
insP(prv(K1,E1),[prv(K2,E2)|Tail],[prv(K1,E1),prv(K2,E2)|Tail]):-
E1 P(i) }
% tzn. k P=[3,2,1,4] je O=[0,1,2,0].
% Sestavte:
%  a) predikat, ktery k dane permutaci udela vektor inverzi
%  b) predikat, ktery k vektoru inverzi udela permutaci
%  c) predikat, ktery urci, zda vektor je vektor permutace.

% countGreater(+X,+List,-Gr) spocte, kolik prvku v List je vetsich nez X
countGreater(_,[],0).
countGreater(X,[Head|Tail],Gr):-
countGreater(X,Tail,Gr1),
(
  (Head>X,!,Gr is Gr1+1)
  ;
  (Gr is Gr1)
).

% genList(+List,+From,-NumList) vygeneruje posloupnost prirozenych cisel
% od From delky Listu
genList([],_,[]).                       % konec rekurze
genList([_|Tail],From,[From|TailN]):-   % pridej prvek do hlavy
From1 is From+1,                      % s prvkem o jedna vetsim
genList(Tail,From1,TailN).            % se zarekurzi

% cast a)
% permVi(+P,-O) udela z permutace vektor inverzi
permVi(P,O):-
permVi(P,[],O).                       % zavolej verzi s prazdnym akumulatorem

permVi([],_,[]).                        % konec rekurze
permVi([HeadP|TailP],Ak,[Gr|TailO]):-   % do hlavy
countGreater(HeadP,Ak,Gr),            % spocti pocet vetsich prvku v Ak
permVi(TailP,[HeadP|Ak],TailO).       % a rekurze pro zbytek

% cast b)
% viPerm(+O,-P) udela z vektoru inverzi permutaci
viPerm(O,P):-
genList(O,1,List),                    % vygeneruj seznam 1..len(O)
reverse(List,ListR),                  % otoc jej
reverse(O,OR),                        % otoc vstupni vektor
viPerm(OR,ListR,[],P).                % zavolej verzi s prazdnym akumulatorem

viPerm([],_,Ak,Ak).
viPerm([HeadO|TailO],List,Ak,P):-
nth0(HeadO,List,X),                   % najdi odpovidajici prvek
delete(List,X,ListNew),               % vyskrtni jej ze senzamu cisel
viPerm(TailO,ListNew,[X|Ak],P).       % pridej ho k Ak a rekurze pro zbytek

% cast c)
% isPerm(+P) je splnen, pokud P je permutace
isPerm(P):-
genList(P,1,List),                    % vygeneruj cisla 1..len(P)
isPerm(P,List).                       % zavolej rozsirenou verzi

isPerm([],[]).                          % konec rekurze - uspech
isPerm([HeadP|TailP],List):-
delete(List,HeadP,ListNew),           % odeber prvni prvek permutace z Listu
isPerm(TailP,ListNew).                % a rekurze pro zbytek

% testovaci permutace

vi_p1(X):-
X=[3,2,1,4].

vi_p2(X):-
X=[5,1,6,8,2,3,7,4].

vi_v1(X):-
X=[0,1,2,0].

vi_v2(X):-
X=[0,1,0,0,3,3,1,4].

% testy

vi_t1:-vi_p1(X),permVi(X,Y),write(Y).
vi_t2:-vi_p2(X),permVi(X,Y),write(Y).
vi_t3:-vi_v1(X),viPerm(X,Y),write(Y).
vi_t4:-vi_v2(X),viPerm(X,Y),write(Y).
vi_t5:-vi_p1(X),isPerm(X).
vi_t6:-vi_p2(X),isPerm(X).
vi_t7:-isPerm([1]).
vi_t8:-isPerm([1,2,9,8,4,1,6,3,5,7]).
vi_t9:-isPerm([2]).




%% 10. PREVOD REPREZENTACE PERMUTACE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Napiste predikat k prevodu permutace reprezentovane vektorem na reprezentaci
% cykly (napr. [1,3,2,4] -> [[1],[3,2],[4]])

% genZero(+P,List) vytvori seznam nul dlouhy len(P)
genZero([],[]).                         % konec rekurze
genZero([_|Tail],[0|TailL]):-           % pridej nulu
genZero(Tail,TailL).                  % a generuj telo

% check(+X,+List,-NewList) zaskrtne (nastavi na 1) prvek na pozici X v List
check(1,[_|Tail],[1|Tail]).
check(X,[Head|Tail1],[Head|Tail2]):-
X1 is X-1,
check(X1,Tail1,Tail2).

% rpcOne(+VP,+Pos,+List,-NewLost,+OneCyk,-Cyk) projde jeden cyklus,
% ktery obsahuje prvek na pozici Pos v permutaci VP se seznamem pruchodu
% List aktualnim cyklem OneCyk
rpcOne(_,Pos,List,List,Cyk,Cyk):-
nth1(Pos,List,1),                     % konec rekurze pokud dany prvek
!.                                    % zaskrtnut

rpcOne(VP,Pos,List,NewList,OneCyk,Cyk):-
check(Pos,List,List2),                % zaskrtni navstiveny prvek
nth1(Pos,VP,X),                       % urci dalsi prvek
rpcOne(VP,X,List2,NewList,[X|OneCyk],Cyk).


% rpc(+VP,-Cyk) prevede vektor permutace na cykly
rpc(VP,Cyk):-
genZero(VP,ZeroList),                 % vygeneruj nulovy seznam
length(VP,VPLen),                     % zjisti delku vektoru
rpc(VP,1,VPLen,ZeroList,[],Cyk).      % a zavolej rozsirenou verzi predikatu

rpc(_,Pos,VPLen,_,Ak,Ak):-              % konec rekurze
Pos is VPLen+1.

rpc(VP,Pos,VPLen,List,Ak,Cyk):-
nth1(Pos,List,1),                     % pokud je prvek jiz hotov
!,
Pos1 is Pos+1,                        % jdi na nasledujici pozici
rpc(VP,Pos1,VPLen,List,Ak,Cyk).       % a rekurzi

rpc(VP,Pos,VPLen,List,Ak,Cyk):-
rpcOne(VP,Pos,List,NewList,[],NewCyk),% prvek neni hotov -> udelej cyklus
append(Ak,[NewCyk],NewAk),            % pridej cyklus do akumulatoru
Pos1 is Pos+1,                        % jdi na nasledujici pozici
rpc(VP,Pos1,VPLen,NewList,NewAk,Cyk). % a rekurzi

% testovaci permutace

rpc_p1(X):-
X=[1,3,2,4].

rpc_p2(X):-
X=[3,2,1,4].

rpc_p3(X):-
X=[5,1,6,8,2,3,7,4].


% testy

rpc_t1:-rpc_p1(X),rpc(X,Y),write(Y).
rpc_t2:-rpc_p2(X),rpc(X,Y),write(Y).
rpc_t3:-rpc_p3(X),rpc(X,Y),write(Y).




%% 11. POCET INVERSI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Sestavte predikat inv(+Sez,-PocInv), ktery spocte, kolik inverzi obsahuje
% vstupni seznam cisel Sez. Inverze je dvojice A,B, kde AHead,
!,
CntNew is CntStart+1,
gtCnt(X,Tail,CntNew,Cnt).

gtCnt(X,[_|Tail],CntStart,Cnt):-
gtCnt(X,Tail,CntStart,Cnt).

% inv(+Sez,-PocInv)
inv(Sez,PocInv):-
inv(Sez,0,PocInv).

inv([],Cnt,Cnt).
inv([HeadSez|TailSez],Cnt,PocInv):-
gtCnt(HeadSez,TailSez,Cnt,CntNew),
inv(TailSez,CntNew,PocInv).


% testy

pi_t1:-inv([1,3,2],X),write(X).
pi_t2:-inv([1,2,3,4,5],X),write(X).
pi_t3:-inv([6,1,8,2,9,60,12,3],X),write(X).

%% THE END %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%