tut6.pl

maptree(_, nil).
maptree(P, b(L, X, R)) :-
    call(P, X), maptree(P, L), maptree(P, R).

size(nil, 0, -1).
size(b(L, _, R), S, H) :-
    SP is S - 1, between(0, SP, SL), SR is S - SL - 1,
    HP is H - 1, (HL = HP, between(-1, HP, HR); between(-1, HP, HL), HR = HP, HL \= HR),
    size(L, SL, HL),
    size(R, SR, HR).

decode_char(Key, A, B) :- B is ((A - 97 + Key) mod 26) + 97.

decode_string(_, _, [], []).
decode_string(Key1, Key2, [A|As], [B|Bs]) :-
    decode_char(Key1, A, B),
    decode_string(Key2, Key1, As, Bs).

decode(K1, K2, S1, S2) :-
    string_codes(S1, C1),
    decode_string(K1, K2, C1, C2),
    string_codes(S2, C2).

somewhere(A, B) :- member(B, A).

decrypt(Line, Dict, R) :-
    split_string(Line, " ", " ", Words),
    between(0, 25, Key1),
    between(0, 25, Key2),
    maplist(decode(Key1, Key2), Words, Decoded),
    maplist(somewhere(Dict), Decoded),
    atomics_to_string(Decoded, " ", R).

% V Prologu můžeme definovat vlastní operátory:
% :- op(Prec,Fixity,Name)
%
% Kde Prec je priorita operátoru (menší hodnota = váže více),
% Fixity udává typ a asociativitu
%   fx, fy - prefix
%   xf, yf - postfix
%   xfx    - infix, bez asoc.
%   xfy    - infix, asoc. vpravo
%   yfx    - infix, asoc. vlevo

:- op(550, xfx, ekv).
:- op(500, xfy, imp).
:- op(450, xfy, or).
:- op(400, xfy, and).
:- op(350,  fx, non).

% Do prefixové notace můžeme převést pomocí predikátu display/1
%
% display(1+2*3).
% +(1,*(2,3))
% true.

% Korektně zadaná formule.
correct(X) :- ground(X), correct_(X).

correct_(X) :- atom(X).
correct_(F ekv G) :- correct_(F), correct_(G).
correct_(F imp G) :- correct_(F), correct_(G).
correct_(F or  G) :- correct_(F), correct_(G).
correct_(F and G) :- correct_(F), correct_(G).
correct_(  non G) :-              correct_(G).

% Chceme zjistit, jestli je daná formule F splnitelná.
%
% Idea:

sat(F) :-
  correct(F),
  vars(F, Vars),
  genModel(Vars, Model),
  eval(F, Model, true).

% Kde vars najde všechny proměnné, genModel na základě těchto proměnných
% (nedeterministicky) vytvoří model a pak jen zkusíme, jestli je F
% pravdivá v tomto modelu.

% Slévání seznamů, které vyhazuje duplikátní prvky.
mergeU(XS, [], XS) :- !.
mergeU([], YS, YS) :- !.
mergeU([X|XS], [Y|YS], R) :-
  ( X @< Y -> mergeU(XS, [Y|YS], S), R = [X|S]
  ; X == Y -> mergeU(XS, YS, S), R = [X|S]  % Takto vypadá "else-if" v Prologu.
  ; mergeU([X|XS], YS, S), R = [Y|S]
  ).

vars(X, [X]) :- atom(X).
vars(non F, R) :- vars(F, R).
vars(F, RR) :-
  F =.. [H, L, R],  % Lze splnit pouze pokud F byl (binární) složený term. Viz níže.
  member(H, [ekv, imp, or, and]),  % H je hlava složeného termu F.
  vars(L, R1),  % L je první argument.
  vars(R, R2),  % R je druhý argument.
  mergeU(R1, R2, RR).