# FLP -- Prolog
## 2024/25
1. Vytvorte predikát `transp(+InMat,-OutMat)`, ktorý transponuje zadanú maticu. Bolo uvedených zopár príkladov použitia.
```prolog
transp( [[H|T]|LS], [[H|TT]|XS] ) :-
cont(LS,TT,Rests),
transp2( [T|Rests], XS ).
cont( [], [], [] ).
cont( [[H|T]|LS], [H|TT], [T|TTS] ) :-
cont( LS, TT, TTS ).
transp2( [[]|_], [] ). % :-
transp2( [[H|T]|LS], [[H|TT]|XS] ) :-
cont(LS,TT,Rests),
transp2( [T|Rests], XS ).
```
2. Definujte predikát `isMatOK(+Mat)`. Predikát skončí úspešne, pokiaľ má vstupná matica v každom riadku a v každom stĺpci práve jednu hodnotu 1, ostatné hodnoty 0.
```prolog
isMatOK(M) :-
tst(M),
transp(M,NT),
tst(NT).
tst( [] ).
tst( [L|LS] ) :-
isLineOK(L),
tst(LS).
isLineOK( [1|R] ) :- null(R).
isLineOK( [0|R] ) :- isLineOK(R).
null( [] ).
null( [0|R] ) :- null(R).
```
3. Vytvorte predikát `fs(+N,-Mat)`, ktorý pre daný rozmer šachovnice `NxN` nájde také šachovnice `M`, kde bude rozmiestnených `N` dám. Dámy musia byť umiestnené tak, aby sa vzájomne neohrozovali. Môžete použiť predikáty s predošlých úloh, kľúčove slovo `is`, základnú konštrukciu zoznamov, `append`, číselné operácie a predikát `isDiagOk(M)`, ktorý skontroluje či sa žiadne 2 dámy neohrozujú po diagonále.
```prolog
fs(N,M) :-
prep(1,N,SM),
varm(SM, M),
isMatOK(M),
isDiagOK(M).
gen(0,[]).
gen(N,[0|R]) :-
N>0, NN is N-1,
gen(NN,R).
varm( [], [] ).
varm( [L|LS], [NL|NLS] ) :-
varm(LS,NLS),
append(S,[_|R],L),
append(S,[1|R],NL).
prep(N,N,[L]) :- gen(N,L).
prep(X,N,[L|LS]) :- gen(N,L),
X<N, XX is X+1,
prep(XX,N,LS).
```
## 2023/2024
### 1. opravný termín
Pozn. na začátku každého úkolu je napsáno: "V holém jazyku Prolog -- tedy jen termy, predikáty, unifikace (nikoliv negace unifikace) -- ..."
1. /2b/ Definujte predikáty `ser(+R1, +R2, -Rser)` a `parR(+R1, +R2, -Rpar)`, které spočtou odpor sériového a paralelního zapojení resistorů -- `Rser = R1 + R2` a `Rpar = 1/((1/R1) + (1/R2))`. Nad holý Prolog použijte operace nad čísly a operátor is.
```prolog
serR(R1,R2,R) :- R is R1+R2.
parR(R1,R2,R) :-
R is 1/((1/R1)+(1/R2)).
```
2. /5b/ Definujte termy pro složení libovolného sériového/paralelního/sério-paralelního zapojení resistorů libovolné velikosti a složitosti a popište je. S využitím predikátů z předchozího příklad (pokud je nemáte, jako byste měli). Definujte predikát `resistance(+Zapojeni, -Odpor)`, který pro zadané zapojení resistorů spočte jejich odpor. Krom vlastního predikátu `resistance` a těch z předchozího příkladu nic jiného použít nesmíte, tedy až na termy definované v tomtu příkladu pro popis zapojení.
```prolog
% res(Ohm) - resistor
% serial(R1,R2) - seriove zapojeni
% paralel(R1,R2) - paralelni zapojeni
resistance(res(O),O).
resistance(serial(R1,R2),R) :-
resistance(R1,O1), resistance(R2,O2),
serR(O1,O2,R).
resistance(paralel(R1,R2),R) :-
resistance(R1,O1), resistance(R2,O2),
parR(O1,O2,R).
```
3. /6b/ Definujte predikát `bagdiff(+Bag1, +Bag2, -BagR)`, který pro zadané dvě multimnožiny `+Bag1` a `+Bag2` spočte jejich multimnožinový rozdíl a unifikuje do výstupního parametru `BagR`. Predikát pracuje jako funkce. Multimnožiny jsou reprezentovány seznamem.
```prolog
bagdiff([], _, []).
bagdiff(R, [], R).
bagdiff(Bag1, [Bag2H|Bag2T], Bagr) :-
member(Bag2H, Bag1),!,
remove(Bag1, Bag2H, Res),
bagdiff(Res, Bag2T, Bagr).
bagdiff(Bag1, [_|Bag2T], Bagr) :-
bagdiff(Bag1, Bag2T, Bagr).
remove([],_, []).
remove([H|T], H, T):- !.
remove([H|T], S, [H|Res]):-
remove(T, S, Res).
member(S, [S|_]).
member(S, [_|Rest]):-
member(S, Rest).
```
4. /6b/ Definujte predikát `getRes(+BagRes, -ConRes, -RemainingBag)` který pro zadanou multimnožinu `BagRes` (zadanou seznamem) hodnot odporu jednotlivých resistorů postupně unifikuje (přes zpětné navracení) do parametru `ConRes` buďto ty odpory jako samotné, nebo ve všech kombinacích sériového a paralelního zapojení (jen jedna úroveň). K tomu použijte termy (pro ten `ConRes`) pro reprezentaci zapojení z předchozího příkladu. Do parametru `RemainingBag` se unifikuje multimnožina (jako seznam) hodnot odporu neužitých v zapojení `ConRes`.
```prolog
getRes(List,res(Val),NL) :-
append(_,[Val|_],List),
remove(List,Val,NL).
getRes(List,serial(res(R1),res(R2)),NL) :-
append(_,[R1|_],List),
remove(List,R1,L1),
append(_,[R2|_],L1),
remove(L1,R2,NL).
getRes(List,paralel(res(R1),res(R2)),NL) :-
append(_,[R1|_],List),
remove(List,R1,L1),
append(_,[R2|_],L1),
remove(L1,R2,NL).
```
5. /11b/ Definujte predikát `getAny(+BagRes, +Res, -Connection)`, který pro zadanou multimnožinu odporů (jako seznam) `BagRes` a hodnotu požadovaného odporu `Res` (desetinné či celé kladné číslo) vyhledá z odporů v multimnožine `BagRes` takové zapojení, aby dávalo požadovaný odpor. Nad holý Prolog můžete použít základní práci se seznamy, operátor `is`, operace nad čísly, `assert*`, `retract*`, a predikáty a termy z předchozích příkladů. Pozn: Po nutné úpravě je možné úspešně využít schéma z přednášky. Navíc není nutné, aby dodávané výsledky byly dodávany nějak bez opakování -- viz dodatkový list.
```prolog
getAny(List,Val,Res) :-
getCon(List,Wal,Res,_),
Rval is Val*1.0,
Rwal is Wal*1.0,
Rwal=Rval.
con(R1,V1,R2,V2,serial(R1,R2),Val) :-
serR(V1,V2,Val).
con(R1,V1,R2,V2,paralel(R1,R2),Val) :-
parR(V1,V2,Val).
getCon(List,Val,Res,Rem) :-
getRes(List,Res,Rem),
resistance(Res,Val).
getCon(List,_,_,_) :-
par(List),!,fail.
getCon(List,Val,Res,Rem) :-
assert(par(List)),
getCon(List,V1,R1,Rest1),
getCon(Rest1,V2,R2,Rem),
con(R1,V1,R2,V2,Res,Val).
getCon(List,_,_,_) :-
retract(par(List)),!,fail.
```
### Řádný termín
1. Navrhni dátovú štruktúru reprezentujúcu zásobník a na ňom operácie `empty/1, push/3, pop/3, top/2, size/2` tak, aby pracovali v konštantnom čase (aj `size` !). (Pozn. prve 4 úlohy spolu súvisia)
```prolog
% zasobnik: st(pocet polozek, polozky v seznamu)
% st(count,[vals])
empty(st(0,[])).
push(st(C,S),V,st(CC,[V|S])) :- CC is C+1.
pop(st(C,[V|S]),V,st(CC,S)) :- CC is C-1.
top(st(_,[V|_]),V).
size(st(C,_),C).
```
2. Predikát `pp/3`, `pp(?Stack, ?Item, ?Stack)`, ktorý podľa toho, či bude vľavo alebo vpravo daný zásobník, sa bude správať aj ako push (vľavo vstupný zás. a item, vpravo po pushi) aj ako pop (vpravo vstupný zásobník, vľavo popnutný zásobník, v strede popnutý item). (nemožno použiť push a pop z predošlej úlohy, možno použiť `nonvar` a aritmetické operácie).
```prolog
pp(In,V,Res) :-
nonvar(In),!,In=st(C,S),
CC is C+1, Res = st(CC,[V|S]).
pp(In,V,st(CC,[V|S])) :-
C is CC-1, In = st(C,S).
```
3. Predikát `pushStr/3`, `popStr/3`, ktorý dokáže pushnúť viacero prvkov naraz. `popStr` bude zároveň vedieť kontrolovať, či sekvencia, ktorá sa popuje, sedí s tým, čo je na vrchole zásobníka - ak nie, tak failne.
```prolog
pushStr(Stack,[],Stack).
pushStr(Stack,[X|XS],NewStack) :-
pushStr(Stack,XS,SubStack),
push(SubStack,X,NewStack).
popStr(Stack,[],Stack).
popStr(Stack,[X|XS],NS) :-
pop(Stack,X,RetStr),
popStr(RetStr,XS,NS).
```
4. Predikát `remN/3`, ktorý podľa zadanej hodnoty popne daný počet prvkov zo zásobníka. Ak je zadané číslo menšie rovné nule, nič sa nestane, ak je zadané číslo väčšie ako veľkosť zásobníka, predikát zlyhá.
```prolog
remN(Stack,N,Stack) :- N =< 0.
remN(Stack,N,Res) :-
N>0,
size(Stack,C),
N =< C, NN is N-1,
pop(Stack,_,NewStack),
remN(NewStack,NN,Res).
```
5. V predikáte `sum4/3` implementovať SUBSET SUM problém (pre zadaný zoznam čísel a nejakú hodnotu nájdi všetky podmnožiny, ktorých súčet sa rovná danému číslu) - predikát bude vracať všetky výsledky a potom failne. (operátor rezu možno použiť max 1x)
```prolog
% priklad pouziti:
?- sum4([1,2,3,4,5,6], 7, R).
R = [1,2,4] ;
R = [1,6] ;
R = [2,5] ;
R = [3,4] ;
false.
```
```prolog
sum4(_,0,[]) :- !.
sum4([X|XS],N,[X|Rest]) :-
X =< N,
NN is N-X,
sum4(XS,NN,Rest).
sum4([_|XS],N,Res) :-
sum4(XS,N,Res).
```
## 2022/2023
### Řádný
Implementace funkce prime/1, která ověří, že X je prvočíslo a při zadání prime(X) generuje nekonečkou posloupnost prvočísel.
```prolog
allNums(1, 1) :- !.
allNums(N, X) :- X is N - 1.
allNums(N, X) :- N2 is N - 1, allNums(N2, X).
generateinfity(1).
generateinfity(X) :- generateinfity(X2), X is X2 + 1.
generateinfity(X) :- generateinfity(X).
not_prime(X) :- allNums(X, X1), allNums(X, X2), X is X1 * X2.
prime2(X) :- not_prime(X), !, fail.
prime2(_).
prime(1).
prime(X) :- generateinfity(X), prime2(X).
% does not seem to work properly
```
alebo, funkcnejsie riesenie:
```prolog
generate_naturals(0).
generate_naturals(X) :- generate_naturals(Y), X is Y + 1.
generate_divisor(N, N) :- N > 1.
generate_divisor(N, X) :- N > 1, N1 is N - 1, generate_divisor(N1, X).
primeGen(X) :- generate_naturals(NextNumber), primeCheck(NextNumber), X is NextNumber.
primeCheck(X) :- X > 1, not((generate_divisor(X div 2, Divisor), X mod Divisor =:= 0)).
% X is integer => check if its prime
prime(X) :- integer(X), !, primeCheck(X).
% falling here means X is a variable => generate
prime(X) :- primeGen(X).
```
### Předtermín
Implementace deterministickeho Turingova stroje. Je dano `:- dynamic tol/1 tor/1 state/1 head/1.`, kde:
- `state` je predikat reprezentujici aktualni stav Turingova stroje.
- `head` obsahuje symbol pod hlavou.
- `tol` obsahuje seznam reprezentujici pasku vlevo od hlavy.
- `tor` stejne tak, ale vpravo od hlavy.
V obou pripadech je prvni prvek seznamu policko pasky nejblize hlave. Semantika TM je klasicka, tj. neni mozne se posunout doleva, pokud seznam `tol` je prazdny. Doprava je mozne se posunout vzdy (blank pod hlavou). Krok TS je reprezentovany termem
- `move(State, Symbol, Action)`, kde `State` je soucasny stav, `Symbol` symbol pod hlavou a `Action` akce, co se ma provest (viz 4).
V zadani zminoval, ze mame vzdy co nejvic vyuzivat predikaty vzdy z predchozich ukolu.
1) Implementujte predikat `shl/0`, co pokud je to mozne, pak provede posun hlavy doleva a uspeje. (7b) V dalsich prikladech muzeme predpokladat existenci predikatu
- `shr/0`, co posouva doprava,
- `wh/1`, co zapisuje pod hlavu a
- `rh/1`, co cte symbol pod hlavou.
```prolog
shl :- tol([NewHead|NewLTape]),
head(OldHead),
retract(head(_)), assertz(head(NewHead)),
retract(tol(_)), assertz(tol(NewLTape)),
tor(OldRTape),
retract(tor(_)), assertz(tor([OldHead|OldRTape])).
```
2) Implementujte predikat `ttol/1`, co do prvniho argumentu vrati obsah cele pasky (5b za "oneliner", jinak 3b)
```prolog
% this could be considered a oneliner
ttol(FullTape) :-
tol(LTape),
tor(RTape),
head(Head),
reverse(LTape, RevLTape),
append(RevLTape, [Head|RTape], FullTape).
```
3) Implementujte predikat `findmove(Moves, Action)`, co ve vstupnim seznamu `Moves` (jeho obsah jsou termy `move`) najde proveditelnou akci a zunifikuje ji do argumentu `Action`. Pak tam byla asi 4radkova poznamka o tom, ze v seznamu `Moves` muzou byt i kroky, ktery jdou provest s jakymkoliv symbolem apod, ale mame brat v potaz jen validni. Zaroven mame umoznit backtracking v pripade, ze tech validnich pohybu je vic (ze to v realu nenastane, ale mame to podporovat) (3b)
```prolog
findmove(Moves, Action) :-
member(move(State, Symbol, Action), Moves),
head(Symbol), % it would be better to use rh(Symbol) instead.
state(State).
```
4) Implementujte predikat `action/1`, ktery dostane jako argument akci a provede ji. Akce muze byt nasledujiciho tvaru (5b):
a) `act(w, Sym, State)` - zapise Sym pod hlavu a presune se do stavu State
b) `act(r, State)` - posune hlavu doprava a presune se do stavu State
c) `act(l, State)` - posune hlavu doleva a presune se do stavu State
```prolog
action(act(r, State)) :-
shr,
retract(state(_)),
assertz(state(State)).
action(act(l, State)) :-
shl,
retract(state(_)),
assertz(state(State)).
action(act(w, Sym, State)) :-
retract(head(_)),
assertz(head(Sym)), % `wh(Symbol)` would be better
retract(state(_)),
assertz(state(State)).
```
5) Implementujte predikat work(Moves, InitState, Tape, FinalStates), ktery dostane mozne prechody TS `Moves` (viz format `move`), pocatecni stav `InitState`, seznam koncovych stavu `FinalStates` a pocatecni obsah pasky `Tape` a uspeje, pokud pro tohle zadani existuje reseni. Tim, ze je to deterministicky TM, mame uvazovat, ze je mozne provest vzdy maximalne jeden krok z `Moves`, tj. neuvazovat backtracking. (10b)
```prolog
work(Moves, InitState, [InitHead|RestOfTape], FinalStates) :-
assertz(state(InitState)),
assertz(tol([])),
assertz(tor(RestOfTape)),
assertz(head(InitHead)),
doMoves(Moves, FinalStates).
isInFinal(Finals) :- state(CurrentState), member(CurrentState, Finals), !.
doMoves(Moves, FinalStates) :- isInFinal(FinalStates), !.
doMoves(Moves, FinalStates) :-
findmove(Moves, NextAction),
action(NextAction),
doMoves(Moves, FinalStates).
```
## 2021/2022
### 1. termín
1) [12b.]
Např.: [[1, 2], [2,3,4], []], [[3,4], [1], [1,2,3,4]]
Vstupem seznam množin,
Sjednocení všech množin tvoří univerzum,
Pro každou vstupní množinu vypsat doplněk vůči tomuto univerzu.
K dispozici holý prolog.
```prolog!
complements(I,O) :- % since there is only one possible "universe",
getUniverse(I,U), % there is only one correct list of differences =>
getComplements(I,U,O), !. % use cut to not search for other (wrong) answers
getComplements([],_,[]). % no input "sets" to produce complements for
getComplements([HI|TI],U,[HO|TO]) :-
getDifference(HI,U,HO), % complement = universal set \ our set
getComplements(TI,U,TO).
getDifference(U,U,[]).
getDifference(_,[],[]).
getDifference(S,[HU|SU],[HU|R]) :-
notMember(HU,S),
getDifference(S,SU,R).
getDifference(S,[_|SU],R) :-
getDifference(S,SU,R).
getUniverse([],[]).
getUniverse([H|T],U) :-
getUniverse(T,TU),
append(H,TU,U).
notMember(_,[]).
notMember(X,[H|T]) :-
notMember(X,T), % the order of these two does not matter
X \= H.
member(_,[]) :- false. % member is not used in the solution
member(X,[X|_]).
member(X,[_|T]) :- member(X,T).
append([],X,X).
append(X,[],X).
append(L1,L2,R) :-
appendInner(L1,L2,T),
removeDuplicates(T,R).
appendInner([],X,X).
appendInner(X,[],X).
appendInner([H1|T1],L,[H1|R]) :-
appendInner(T1,L,R).
removeDuplicates([],[]).
removeDuplicates([H|T],[H|R]) :-
notMember(H,T),
removeDuplicates(T,R).
removeDuplicates([_|T],R) :- removeDuplicates(T,R).
```
2) [4b.] splt
chová se jako span v Haskellu.
splt (P, A, AT, AF)
vstupem predikát P a seznam A.
Výstupem dva seznamy:
AT = souvislý prefix A, kde pro všechny prvky platí predikát P.
AF = zbytek seznamu A(od prvního prvku, kde P neplatí, do konce).
K dispozici holý prolog.
```prolog
% Pozn.: call a not nie sú v holom prológu, ale bez toho to nejde implementovať
splt(_, [], _, []).
splt(P, [H|T], N, AF) :-
call(P, H), % zavolanim P(H) zistime, ci predikat plati na H
N = [H|Rest], % (ak ano), tak ho pripojime do vysledku
splt(P, T, Rest, AF). % a pokracujeme dalej
% prvy vysledok bude prazdny iba ak predikat zlyha hned na hlave
splt(P, [H|T], [], [H|T]) :- not(call(P, H)).
% alebo ine riesenie
splt(P,[HA|TA],[HA|ATA],AF) :-
call(P, HA), !, % cut, aby vratilo len to jedine "maximalne" riesenie
splt(P,TA,ATA,AF).
splt(_,L,[],L).
```
3) [asi 6b.]
Vyhledání všech klíčů ve stromě, které se vážou k dané hodnotě.
Klíče ve stromě byly unikátní, hodnoty byly neznámého typu
```prolog
% test příslušnosti do seznamu
elem(H, [H|_]) :- !.
elem(H, [_|T]) :- elem(H, T), !.
% sjednocení množin
union([], R, R) :- !.
union(R, [], R) :- !.
union([H|T], U, R) :- elem(H, U), union(T, U, R), !.
union([H|T], U, [H|R]) :- union(T, U, R), !.
% definice stromu
% strom může být prázdný, to jsem vyjádřil predikátem myTree(stop).
myTree(stop).
% strom může mít tři položky
% -> dvojici (klíč, hodnota), to v prologu vyjádřím zápisem -(_K, _V),
% spojovník a závorky vyjadřuji, že je to dvojice,
% podtržítko na začátku vyjadřuje anonymitu.
% -> levý podstrom Left
% -> pravý podstrom Right
myTree(tree(-(_Key, _Value), Left, Right)) :-
myTree(Left),
myTree(Right). % musí nutně platit, že Left i Right jsou stromy.
% hledání klíče dle libovolné hodnoty v prázdném stromě
% vrátí prázdný seznam jako odpověď
getKeysByValue(_, myTree(stop), []) :- !.
% při hledání klíčů dle hodnoty Val naunifikuji do A, B klíče odpovídající
% hodnotě Val z podstromů Left, Right (po řadě),
% sjednotím je do R a přidám k nim Key, pokud plati,
% ze hodnota aktuálního uzlu odpovídá hledané hodnotě
getKeysByValue(Val, myTree(tree(-(Key, Value), Left, Right)), [Key|R]) :-
Val == Value,
getKeysByValue(Val, myTree(Left), A),
getKeysByValue(Val, myTree(Right), B),
union(A, B, R),
!.
% tu predtym chybalo, co sa ma stat, ak Val != Value => Key sa neprida do vysledku
getKeysByValue(_, myTree(tree(-(_Key, _Value), Left, Right)), R) :-
getKeysByValue(Val, myTree(Left), A),
getKeysByValue(Val, myTree(Right), B),
union(A, B, R),
!.
% Zkuste si třeba:
myTree(stop).
myTree(tree(-(1, 2), stop, tree(-(2, 3), stop, stop))).
getKeysByValue(2, myTree(tree(-(10,2), tree(-(1, 2), stop, stop), tree(-(100, 0), stop, tree(-(1000, 2), stop, stop)))), R).
% --Nebo-------
% To predtim mi uplne nefungovalo (uz je to fixed). Toto mi jde uz spustit:
% Dole jsou i "testy"
union([], [], []).
union([], T, T).
union([H|T], S, [H|U]) :-
\+ member(H, S),
union(T, S, U).
union([H|T], S, U) :-
member(H, S),
union(T, S, U).
myTree(stop).
myTree(tree(-(_Key, _Value), Left, Right)) :-
myTree(Left),
myTree(Right).
getKeysByValue(_, stop, []) :- !.
getKeysByValue(Val, tree(-(Key, Value), Left, Right), R) :-
getKeysByValue(Val, Left, A),
getKeysByValue(Val, Right, B),
(Val == Value -> union(A, B, AB), union(AB, [Key], R) ; union(A, B, R)),
!.
main :-
union([1,2,3], [2,3,4], U1),
format('Test 1: Union = ~w~n', [U1]),
myTree(tree(-(1, a), tree(-(2, b), stop, stop), tree(-(3, c), stop, stop))),
format('Test 2: myTree passed~n'),
getKeysByValue(a, tree(-(1, a), tree(-(2, b), stop, stop), tree(-(3, a), stop, stop)), K1),
format('Test 3: Keys = ~w~n', [K1]),
halt.
```
4) [asi 8b.]
~jsme v nekonečném stavovém prostoru, prakticky všechno je neznámé nebo dané parametrem a úkolem je udělat krok/cestu v rámci stavového prostoru ... no idea
### 1. opravný
1. vytvoriť funkciu `notelem(+Val,+List)`, ktorá failne ak sa polozka nachádza v zadanom liste. - moze sa poouzit `!, fail`
```prolog
notelem(_,[]).
notelem(X,[X|_]) :- !, fail.
notelem(X,[_|XS]) :- notelem(X,XS).
```
2. implementovat `keyval(Key, Val)` (cca 15b)
- pouzite assert, nonvar, var, !
- ak sú zadané key aj value skúsi vložiť do pamati
```prolog
keyval(1, jeden)
keyval(2, dva)
keyval(3, tri)
```
- ak sú zadany len key, nájde value z pamäti
```prolog
keyval(1, V)
V = jeden
keyval(5, V)
false.
```
- len value - nájde keys
```prolog
keyval(K, jeden)
K = [1,11]
```
- keyval(K, V) - vypíše z pamati
```prolog
K = 1
V = jeden
K = 2
V = dva
```
```prolog
:-dynamic
kvpair/2.
keyval(Key,Val) :-
var(Key), var(Val), !, kvpair(Key,Val).
keyval(Key,Val) :-
var(Val), !, kvpair(Key,Val).
keyval(Key,Val) :-
var(Key), !, collect(Key,Val).
keyval(Key,Val) :-
testOrInsert(Key,Val).
collect(Key,Val) :-
kvpair(K,Val), !,
take([K],Val,Key).
take(Keys,Val,Res) :-
kvpair(K,Val), notelem(K,Keys), !,
take([K|Keys],Val,Res).
take(Keys,_,Keys).
testOrInsert(Key,Val) :-
kvpair(Key,V), !, Val=V.
testOrInsert(Key,Val) :-
assertz(kvpair(Key,Val)).
```
3. `remKey(Key)` - odstráni Key z pamati, neuspeje ak nenájde, `remAll` - uspeje vždy raz, odstráni predikáty z pamäti
```prolog
remKey(Key) :-
kvpair(Key,Val),
retract(kvpair(Key,Val)).
remAll :-
kvpair(Key,Val), !,
retract(kvpair(Key,Val)),
remAll.
remAll.
```
4. vytvoriť zjednocovanie zanorenych listov do obycajného listu - zostanú len najvonkajšejšie zátvorky (najľavejšia+najpravejšia)
`destr([[1,[]],[2,[3],4],[[], 5]],[1,2,3,4,5])`
[tu je aj alternativne riesenie z 2017/18](https://hackmd.io/C7K8Nvc5R4uO9I0htzkC1A#%C5%98%C3%A1dn%C3%BD-term%C3%ADn2)
```prolog
destr([],[]).
destr([[]|X],Y) :- % if we encounter an empty list, we just skip it
destr(X,Y),!. % and continue with the rest
destr([[H|T]|X],Y) :- % if we encounter a list, we process its head
destr([H|[T|X]],Y),!. % and merge the tail with the rest of the input
destr([H|T],[H|TT]) :- % now we just process elements within one list
destr(T,TT).
```
### Riadny
Lambda calcul v prologu
- viz [riadny 19/20](https://hackmd.io/JB5CYyAZRoS55_WFMbdUkQ?view#riadny)
```prolog
/* 1
var(V) variable abs(f,abs(x,var(x))) ... 0
app(E1,E2) application abs(f,abs(x,app(var(f),var(x)))) ... 1
abs(V,E) abstraction abs(f,abs(x,app(var(f),app(var(f),var(x)))))
V - variable
E,E1,E2 - lambda-expression
*/
```
2 - z toho riesenia mi pride, ze uloha bola najst vsetky premenne v danom lambda vyraze
```prolog!
% find all "free" variables in a lambda expression
fv(var(V),[V]).
fv(app(E1,E2),Res) :-
fv(E1,R1), fv(E2,R2),
union(R1,R2,Res).
% \x.expr -> x is bound in expr
% so we need to remove it from the result that is propagated up
fv(abs(V,E),Res) :-
fv(E,FV),
del(FV,V,Res).
union([],L,L) :- !.
union(L,[],L) :- !.
union([X|XS],YS,Res) :-
member(X,YS), !,
union(XS,YS,Res).
union([X|XS],YS,[X|Res]) :-
union(XS,YS,Res).
% delete the first occurence of a value from a list
del([],_,[]).
del([X|XS],X,XS) :- !.
del([X|XS],V,[X|Res]) :-
del(XS,V,Res).
/* 3 */
valid(Where,What,Var) :-
fv(What,FV),
chk(Where,Var,[],FV).
chk(var(V),V,BV,FV) :-
intersect(BV,FV,I), I==[].
chk(app(E1,E2),V,BV,FV) :-
chk(E1,V,BV,FV),
chk(E2,V,BV,FV).
chk(abs(V,_),V,_,_) :- !.
chk(abs(W,E),V,BV,FV) :-
chk(E,V,[W|BV],FV).
intersect([],_,[]) :- !.
intersect(_,[],[]) :- !.
intersect([X|XS],YS,[X|RS]) :-
member(X,YS),!,
intersect(XS,YS,RS).
intersect([_|XS],YS,RS) :-
intersect(XS,YS,RS).
/* 4 */
isEta( abs( V, app(E,var(V)) ) ) :-
fv(E,FV),
not(member(V,FV)).
isEta(app(E1,E2)) :-
isEta(E1) ; isEta(E2).
isEta(abs(_,E)) :-
isEta(E).
```
<!-- ### 1. opravný -->
<!-- ### 2. opravný -->
## 2020/2021
### Řádný termín
Magicke štvorce - NxN matica s hodnotami 1,...,N^2 hodnotami
- info: 1x1 je jednoduche spravit; 2x2 nejde; 3x3 ...
- suma v riadku, stlpci a uhlopriecke je 15 (pri 3x3)
- viz http://www.mathematische-basteleien.de/magsquare.htm
8....1....6
3....5....7
4....9....2
1. spraviť reprezentaciu matice NxN `cms(+N, -M)`
- `cms(N,M)` skontroluje, že N je číslo, M je pre navrat konečnej matice Magic sqaure
- `cel(N,R)` vytvorí list riadku
- `car(N,N,M)` vytvorí výslednú maticu - list listov (list riadkov pomocou `cel`)
```Prolog
cms(N,M) :-
integer(N),
car(N,N,M).
cel(N,[_|T]) :-
N>0,
NN is N-1,
cel(NN,T).
cel(N,[]) :-
N =< 0.
car(N,A,[L|T]) :-
A>0,
cel(N,L),
AA is A-1,
car(N,AA,T).
car(_,A,[]) :-
A =< 0.
```
2. na poziciu X, Y v matici doplnit hodnotu V a vrátiť výslednú maticu - `set(X,Y,M,V,MM)`
```Prolog
set(X,Y,[H|T],V,[H|TT]) :-
X > 1, XX is X-1,
set(XX,Y,T,V,TT).
set(X,Y,[H|T],V,[HH|T]) :-
X == 1,
yset(Y,H,V,HH).
yset(Y,[H|T],V,[H|TT]) :-
Y > 1, YY is Y-1,
yset(YY,T,V,TT).
yset(Y,[_|T],V,[V|T]) :-
Y == 1.
```
3. doplniť zvyšnú maticu (pomocne funkcie - f. co ti da nevyuzite hodnoty, ...)
```Prolog
solve(N,M,M) :-
getFree(M,[]),!,
chk(N,M).
solve(N,M,Res) :-
getFree(M,Free),
concat(M,L),
assertz(size_of(N)),
step(Free,[],L,[],0,ResL),
toMS(N,ResL,Res).
solve(_,_,_) :-
retractall(size_of(_)),
!,fail.
step([],[],[],Rev,_,Res) :-
reverse(Rev,Res),
size_of(N),
toMS(N,Res,M),
chk(N,M).
step(Free,[],[X|XS],Rev,Ctr,Res) :-
integer(X),
CC is Ctr+1,
try(Free,[],XS,[X|Rev],CC,Res).
step([F|FS],WasFree,[X|XS],Rev,Ctr,Res) :-
var(X), % Try F
CC is Ctr+1,
append(FS,WasFree,Xfree),
try(Xfree,[],XS,[F|Rev],CC,Res).
step([F|FS],WasFree,[X|XS],Rev,Ctr,Res) :-
var(X), % F failed
step(FS,[F|WasFree],[X|XS],Rev,Ctr,Res).
/* rozsireni prubezny test */
try(Xfree,[],XS,Rev,Ctr,Res) :-
size_of(N),
D is Ctr div N,
M is Ctr mod N,
D > 1,
M == 0,!,
reverse(Rev,O),
check(N,D,O), /* prubezny test */
step(Xfree,[],XS,Rev,Ctr,Res).
try(Xfree,[],XS,Rev,Ctr,Res) :-
step(Xfree,[],XS,Rev,Ctr,Res).
/* .............. */
/* rozsireni o prubezny test - test */
sumupto(N,Rest,0,Rest) :- N =< 0.
sumupto(N,[X|XS],S,Rest) :-
N > 0,
N1 is N-1,
sumupto(N1,XS,Sub,Rest),
S is X+Sub.
check(N,Rows,L) :-
Rows>1,
sumupto(N,L,Val,Rest),
RR is Rows-1,
chcl(N,RR,Val,Rest).
chcl(_,Rows,_,_) :- Rows == 0.
chcl(N,Rows,Val,L) :-
Rows > 0,
sumupto(N,L,Val,Rest),
RR is Rows-1,
chcl(N,RR,Val,Rest).
/* -------------- */
/* -------------- */
/* -------------- */
/* co bylo hotove a k uziti, aby to byly komplet, tak zde */
toMS(_,[],[]).
toMS(N,L,[HH|Rest]) :-
toArray(N,L,HH,TT),
toMS(N,TT,Rest).
toArray(0,L,[],L).
toArray(N,[H|T],[H|TT],Rest) :-
N > 0,
N1 is N-1,
toArray(N1,T,TT,Rest).
/* .............. */
getFree(MS,ListN) :-
getUsed(MS,Used),
length(MS,N),
genAll(N,All),
sd(All,Used,ListN).
genAll(N,L) :-
NN is N*N,
mkl(1,NN,L).
mkl(N,M,[N|T]) :-
N < M, NN is N+1,
mkl(NN,M,T).
mkl(N,M,[M]) :-
N == M.
getUsed([],[]).
getUsed([[]|T],R) :-
getUsed(T,R).
getUsed([[H|T]|TT],R) :-
var(H),!,
getUsed([T|TT],R).
getUsed([[H|T]|TT],[H|R]) :-
getUsed([T|TT],R).
sd([],_,[]).
sd([X|XS],S,R) :-
member(X,S),!,
sd(XS,S,R).
sd([X|XS],S,[X|R]) :-
sd(XS,S,R).
/* .............. */
concat(L1,L2) :- append(L1,L2).
/* .............. */
chk(N,M) :-
integer(N),
N>0,
length(M,N),
maplist(length,M,LN),
all(N,LN),
append(M,AllVals),
genAll(N,AllPos),
vals(AllPos,AllVals),
csum(M).
all(_,[]).
all(N,[N|T]) :-
all(N,T).
vals([],[]).
vals(Pos,[X|XS]) :-
integer(X),
member(X,Pos),
delete(Pos,X,NewPos),
vals(NewPos,XS).
csum(M) :-
maplist(sum_list,M,[H|T]),
transp(M,MT),
maplist(sum_list,MT,TT),
all(H,T), all(H,TT),
cdiag(H,0,M),
maplist(reverse,M,MR),
cdiag(H,0,MR).
cdiag(H,S,[[V]]) :-
SS is S+V,
H == SS.
cdiag(H,S,[[V|_]|T]) :-
SS is S+V,
maplist(tail,T,TT),
cdiag(H,SS,TT).
tail([_|T],T).
head([H|_],H).
transp([],[]).
transp([[]|_],[]).
transp(XSS,[HHS|RT]) :-
maplist(head,XSS,HHS),
maplist(tail,XSS,TSS),
transp(TSS,RT).
```
- BONUS: definovat datovy typ obojsmerne viazany zoznam + funkciu ktora zisti dlzku zoznamu - prvky v zozname sa neopakuju
### 1. opravný
1. `genV(+Start,+End, -V)` vygenerovat hodnoty od Start do End vratane (ocakavany vstup je zadany dobre); Start, End su kladné čisla
```prolog
genV(1,3,V).
V=1
V=2
V=3
```
```prolog
genL(E,E,[E]).
genL(S,E,[S|T]) :-
S<E,
SS is S+1,
genL(SS,E,T).
genV(S,E,V) :-
genL(S,E,L),
append(_,[V|_],L).
% alebo ina verzia:
genV(S,E,S):- S < (E + 1).
genV(S, E, V):- S < (E + 1), NS is S + 1, genV(NS, E, V).
% alebo este trochu ina verzia
genV(S, E, S) :- S =< E.
genV(S, E, V) :- S < E, NS is S + 1, genV(NS, E, V).
```
2. `solve(+Xm, +Ym, -X, -Y, -Z)` vyriesit prehladavanim pre `1, ...Xm` a `1...Ym` rovnicu `x²+y²=z²`
```prolog
solve(5,5,X,Y,Z)
x=3
y=4
z=5
x=4
y=3
z=5
atd...
```
```prolog
solve(Xm,Ym,X,Y,Z) :-
genV(1,Xm,X),
genV(1,Ym,Y),
ZZ is X*X+Y*Y,
genZ(X,Y,ZZ,Z).
genZ(M1,M2,ZZ,Z) :-
max(M1,M2,S),
Zm is 2*S+1,
genV(S,Zm,Z),
Z2 is Z*Z,
Z2==ZZ.
max(X,Y,X) :- X >= Y.
max(X,Y,Y) :- X < Y.
% alebo menej komplikovane
solve(Xm, Ym, X, Y, Z) :-
genV(1, Xm, X),
genV(1, Ym, Y),
L is X * X + Y * Y,
genV(1, L, Z),
P is Z * Z,
L == P.
```
3. `resolve` ako `solve` ale zadava da lava a prava strana rovnice
```prolog
resolve(5,5,X*X*X+Y*Y*Y,Z*Z,X,Y,Z)
X = 1,
Y = 2,
Z = 3
X = 2,
Y = 1,
Z = 3
X = 2,
Y = 2,
Z = 4
```
```prolog
resolve(Xm,Ym,Xe,Ze,X,Y,Z) :-
genV(1,Xm,X),
genV(1,Ym,Y),
ZZ is Xe,
genF(ZZ,Ze,Z).
genF(ZZ,Ze,Z) :-
Zm is ZZ+1,
genV(1,Zm,Z),
Z2 is Ze,
test(Z2,ZZ). % skor tu malo byť Z2 = ZZ
% alebo menej komplikovane
resolve(Xm, Ym, Le, Pe, X, Y, Z) :-
genV(1, Xm, X),
genV(1, Ym, Y),
L is Le,
genV(1, L, Z),
P is Pe,
L == P.
```
4. `zip(L1,L2,L12)`
```prolog
zip([1,2,3,4],[a,b,c],R)
R = [(1,a),(2,b),(3,c)]
```
```prolog
zip([],_,[]):-!.
zip(_,[],[]):-!.
zip([X|XS],[Y|YS],[(X,Y)|T]) :- zip(XS,YS,T).
```
### 2. opravný termín
Definované:
```prolog
:- dynamic p/1.
node(t,c,92).
node(t,d,45).
node(t,g,71).
node(t,h,40).
node(t,p,67).
node(d,c,50).
node(d,g,42).
node(d,h,20).
node(d,p,54).
node(c,g,36).
node(c,h,54).
node(c,p,58).
node(g,h,32).
node(g,p,22).
node(h,p,36).
```
/8b/ Holý prolog + `not`, `!`, `member`, `length`. Napísať predikát `getAllNodes(+Num)`, ktorý do jediného parametru unifikuje počet jedinečných uzlov.
```prolog!
% cut prevents unnecessary backtracking and ensures that once a node has been
% added to the list of nodes (L), it is not re-added in subsequent iterations
getNodes(L,Res) :-
node(N,_,_),
not(member(N,L)),!,
getNodes([N|L],Res).
getNodes(L,Res) :-
node(_,N,_),
not(member(N,L)),!,
getNodes([N|L],Res).
getNodes(L,L). % we fall here when all node/3 are explored -> unify working L
getAllNodes(Len) :-
getNodes([],L),
length(L,Len).
```
/22b/ Travelling salesman problem. Napísať predikát `tsp`, ktorý nájde ~~najlacnejšiu trasu medzi dvoma uzlami.~~ najlacnejsiu trasu z daneho uzla cez vsetky uzly naspat do daneho uzla (a kazdy uzol okrem startu navstivime 1x).
```prolog
getlen(X,Y,L) :- node(X,Y,L); node(Y,X,L).
tsp(From,How,Price) :-
setof(J,solve(From,J),LL), % get all paths starting from our node From
best(LL,How,Price). % find the one with the best Price
% `j` functor usage is not necessary, it just improves readability
% solution is a tuple of list (describing the circular path) and price
best([j(H,P)],H,P) :- !. % there is only one solution, so we save it
best([j(_,P)|R],RH,RP) :- % there are multiple solutions
best(R,RH,RP), % so we find the best solution from the tail
RP<P, !. % and conclude that the head solution is worse
best([j(H,P)|_],H,P). % if it's not worse, then we save it
solve(From,j(How,Price)) :-
getAllNodes(LAll), % note that From node will be visited twice
getlen(From,Nxt,L), % get some neighbor node (+ its distance)
go(Nxt,From,Way,P), % 'go' is basically BFS => gets the solution's tail
length(Way,LAll), % make sure that we visited all nodes in the found path
Price is P+L, % but the solution needs to add the initial edge price
How = [From|Way]. % and the starting node
% this is basically BFS
go(T,T,[T],0) :- !.
go(F,T,[F|R],PP) :-
assertz(p(F)), % we make sure we visited F,
getlen(F,N,P), % so that when we find the neighboring node,
not(p(N)), % we can avoid cycles
go(N,T,R,PR), % and keep going,
PP is P+PR. % while keeping track of the cost of the path
go(F,_,_,_) :-
p(F), % if we reach a dead-end,
retract(p(F)), % we 'unvisit' the node
!, fail. % backtrack the whole branch until the latest decision point
```
## 2019/2020
### Predtermin
Klika - viz [popis](https://fituska.eu/download/file.php?id=13594)
1 Dána reprezentace pro neorientovaný graf na vstupu ug(vertices,edges),
uložit jako `node(uzel,-1)` a `edge(uzel,uzel)`
```prolog
:- dynamic edge/2, node/2.
insUG(ug(VS,ES)) :-
inV(VS), inE(ES).
inV([]).
inV([V|VS]) :-
assertz(node(V,-1)), inV(VS).
inE([]).
inE([p(V1,V2)|ES]) :-
assertz(edge(V1,V2)), inE(ES).
```
2 Otestovat, zda zadaná množina uzlů je klika - graf je v DB
```prolog
isC([_]) :- !.
isC([N|NS]) :-
checkE(N,NS),isC(NS).
isC([]).
checkE(_,[]).
checkE(N,[X|XS]) :-
(edge(N,X);edge(X,N)),!,
checkE(N,XS).
```
3 Doplnit stupeň uzlu ne každému, kde to ještě není nastaveno
```prolog
deg(Node,Deg) :-
findall(N, edge(Node,N), L1),
findall(N, edge(N,Node), L2),
length(L1,N1), length(L2, N2),
Deg is N1+N2.
mkDegs :-
node(V,-1),!,
deg(V,D),
retract(node(V,-1)),
assertz(node(V,D)),
mkDegs.
mkDegs.
```
4 Zkusit pro uzel N a jeho okolí Nbr najít mezi nimi co kliku velikosti D-1.
Sousedů je dostatek, nebo více, na to je spoleh.
K dipozici je take jako z Haskellu a perm pro permutace.
```prolog
tryC(D,N,Nbrs, [N|Nbrs]) :-
length(Nbrs,Len),
Len == D, !,
isC([N|Nbrs]).
tryC(D,N,Nbrs, [N|L]) :-
perm(Nbrs,NX),
take(D,NX,L),
isC([N|L]).
/* 5 */
/* Zkusit najít kliku v rozsahu (CD,D>, kde je hlavní uzel N a jeho okolí Nbrs.
Klika bude Clique, když se najde. */
repTry(CD,D,N,Nbrs,Clique) :-
D > CD,
tryC(D,N,Nbrs,Clique),!.
repTry(CD,D,N,Nbrs,Clique) :-
DD is D-1,
DD > CD,
repTry(CD,DD,N,Nbrs,Clique).
```
5 Udělat predikát, co zkusít najít větší kliku než zadanou, ideálně tu největší.
Dostane aktuální velikost kliky - 1 (`ActD`), tu kliku a nějakou vrátí (`ResClique`).
K dispozici má `getNbr`, co vrací sousedy pro uzel a `fltr`, co zjistí, jestli to má
k aktuální klice smysl v daném okolí kliku hledat a když ano, tak vrátí to okolí,
kde se to ověří.
```prolog
findC(ActD,_,ResClique) :-
node(N,D), D>ActD,
getNbr(N,AllNbrs),
fltr(D,AllNbrs,NewD,NewNbrs), NewD>ActD,
repTry(ActD,NewD,N,NewNbrs,Clique),
length(Clique,LenC),
DC is LenC - 1, DC > ActD, !,
findC(DC,Clique,ResClique).
findC(_,C,C).
/* A když to vyjde, bude toto fungovat. */
getClique(ug(VS,ES),Clique) :-
retractall(node(_,_)),
retractall(edge(_,_)),
insUG(ug(VS,ES)),
mkDegs,
node(N,_),
findC(0,[N],Clique),!.
```
### riadny
Lambda Kalkul v prologu:
- viz [riadny 21/22](https://hackmd.io/JB5CYyAZRoS55_WFMbdUkQ?both#Riadny2)
```prolog
/* 1 definicie + ako reprezentovat LE v prologu
lambda expression:
variable - var(atom)
lambda-application - app(E1,E2)
lambda-abstraction - abs(atom,E)
where E, E1, E2 are lambda expressions
atom is a name of variable
*/
/* 2 */
fv(E,Vs) :-
fv3(E,[],Vs).
fv3(var(V),Bs,[]) :-
member(V,Bs), !.
fv3(var(V),_,[V]).
fv3(app(E1,E2),Bs,Vs) :-
fv3(E1,Bs,V1),
fv3(E2,Bs,V2),
uni(V1,V2,Vs).
fv3(abs(V,E),Bs,Vs) :-
fv3(E,[V|Bs],Vs).
uni([],L, L).
uni([X|XS],L, YS) :-
member(X,L), !,
uni(XS,L, YS).
uni([X|XS],L, [X|YS]) :-
uni(XS,L, YS).
/* 3 */
subst(Where,What,Var,Res) :-
fv(What,FW),
sb(Where,What,FW,Var,[],Res).
sb(var(X),_,_,Var,_,var(X)) :- X \= Var, !.
sb(var(X),_,_,X,Bs,var(X)) :- member(X,Bs).
sb(var(X),What,FW,X,Bs,What) :- notIn(FW,Bs), !.
sb(app(E1,E2),What,FW,Var,Bs,app(R1,R2)) :-
sb(E1,What,FW,Var,Bs,R1),
sb(E2,What,FW,Var,Bs,R2).
sb(abs(V,E),What,FW,Var,Bs,abs(V,Res)) :-
sb(E,What,FW,Var,[V|Bs],Res).
notIn([],_) :- !.
notIn(_,[]) :- !.
notIn([X|_],YS) :-
member(X,YS),
!, fail.
notIn([_|XS],YS) :-
notIn(XS,YS).
/* 4 */
doBR(app(abs(Var,Where),What), Res) :- subst(Where, What, Var, Res).
doBR(app(E1,E2), app(Res,E2)) :- doBR(E1,Res).
doBR(app(E1,E2), app(E1,Res)) :- doBR(E2,Res).
doBR(abs(V,E), abs(V,Res)) :- doBR(E,Res).
/* 5 */
findR(S,S,_,[S]) :- !.
findR(_,_,N,_) :-
N > 5, !, fail.
findR(S,E,N,[S|Rest]) :-
assertz(la(S)),
doBR(S,NS),
not(la(NS)),
NN is N+1,
findR(NS,E,NN,Rest).
findR(S,_,_,_) :-
la(S),
retract(la(S)),
!, fail.
```
### 1. opravný
1.
```prolog
% kontrola ze list Y obsahuje prefix list X
isPref([], _) :-!.
isPref([X|XS],[X|YS]) :- isPref(XS,YS).
% dropuje list L, kym list X obsahuje elementy
dropL([],L,L) :- !.
dropL([_|XS],[_|YS],R) :- dropL(XS,YS,R).
```
2.
```prolog
replaceAll(Where,What,By,Res) :-
length(Where,WL),
length(What,AL),
AL =< WL, !,
doRepl(Where,What,AL,By,Res).
replaceAll(Where,_,_,Where).
doRepl([W|WS], What, AL, By, [R1|Res]) :-
isPref(What, [W|WS]), !,
dropL(What, [W|WS], Rest),
append(By, Rest, R1),
doRepl(WS, What, AL, By, SR),
prep(W, SR, Res).
doRepl(WS, _, AL, _, []) :-
length(WS, WL),
WL < AL, !.
doRepl([W|WS], What, AL, By, Res) :-
doRepl(WS, What, AL, By, SR),
prep(W, SR, Res).
prep(X, XS, [X|XS]).
```
3.
```prolog
replLines([], _,_, []).
replLines([L|LS], What,By, [RL|RLS]) :-
replaceAll(L,What,By, RL),
replLines(LS, What,By, RLS).
```
4.
```prolog
mkLines([[]|LS],RS) :- !, mkLines(LS,RS).
mkLines([LX|_],_) :- length(LX,L), L>1, !, fail.
mkLines([[L]|LS],[L|RS]) :- mkLines(LS,RS).
mkLines([],[]).
```
5.
```prolog
find(Lines1,SR,Lines2,Res) :-
assertz(done(Lines1,[])),
findP(Lines1,SR,Lines2,Res).
find(Lines1,_,_,_) :-
retract(done(Lines1,[])),
!,fail
findP(Lines1,_,Lines1,[]) :- !.
findP(Lines1,SR,Lines2,[T|TS]) :-
length(Lines2,LL2),
append(_,[T|_],SR),
not(done(_,T)),
T =.. [sr,What,By],
replLines(Lines1,What,By,LRep),
mkLines(LRep,LinesNew),
length(LinesNew,LN),
LN >= LL2,
not(done(LinesNew,_)),
asr_ret(LinesNew,T),
findP(LinesNew,SR,Lines2,TS).
asr_ret(L,T) :-
assertz(done(L,T)).
asr_ret(L,T) :-
retract(done(L,T)),
!,fail.
```
## 2018/2019
### Řádný termín
Sudoku zadani
```prolog
/* co bylo k dispozici jako hotove, pro uplnost */
newRC(R,C,R,CC) :-
C<9, !, CC is C+1.
newRC(R,9,RR,1) :-
R<9, RR is R+1.
getIth(1,[X|_],X) :- !.
getIth(N,[_|XS],X) :- N1 is N-1, getIth(N1,XS,X).
getRC(R,C,M,V) :-
getIth(R,M,L),
getIth(C,L,V).
```
1. Napsat predikaty pro zjisteni, jestli je prvek v seznamu a pro odstraneni hodnoty ze seznamu. Dat si bacha na to, ze seznam muze obsahovat nenavazane promenne a prvek se s nima nesmi zunifikovat.
```prolog!
elemNV(X,[V|_]) :- nonvar(V), V=X, !.
elemNV(X,[_|VS]) :- elemNV(X,VS).
remVals([],_,[]).
remVals([X|XS],L,R) :- elemNV(X,L), !, remVals(XS,L,R).
remVals([X|XS],L,[X|R]) :- remVals(XS,L,R).
```
2. Transpozice matice.
```prolog!
trp([[]|_],[]) :- !.
trp(XSS,[L|LS]) :- heads(XSS,L,YSS), trp(YSS,LS).
heads([[H|TS]|XSS],[H|T],[TS|YSS]) :- heads(XSS,T,YSS).
heads([],[],[]).
```
3. Predikat, ktery bere sudoku reprezentovane matici `9x9` a vytvori seznam bloku `3x3`.
```prolog!
blocks([[A,B,C|CS],[D,E,F|FS],[G,H,I|IS]|XSS],[[A,B,C,D,E,F,G,H,I]|LS]) :-
blocks([CS,FS,IS|XSS],LS).
blocks([[],[],[]|XSS],LS) :- blocks(XSS,LS).
blocks([],[]).
```
4. Predikat, ktery pro danou pozici v sudoku zjisti seznam moznych hodnot, ktere se na to policko daji doplnit. Mame k dispozici predikat `getIth(X,M,L)`, ktery z matice `M` vytahne radek `X` do seznamu `L`. A meli jsme napsane, jak se z pozice `[X,Y]` v matici urci cislo bloku.
```prolog!
valsFor(X,Y,M,[V|VS]) :-
getIth(X,M,L),
remVals([1,2,3,4,5,6,7,8,9],L,[H|T]),
trp(M,TM),
getIth(Y,TM,R),
remVals([H|T],R,[HH|TT]),
blocks(M,BM),
P is (3*((X-1)//3)) + (1+((Y-1)//3)),
getIth(P,BM,B),
remVals([HH|TT],B,[V|VS]).
```
5. Predikat `solves`, ktery s vyuzitim definovanych predikatu vyresi sudoku, ktere ma na vstupu zadane matici 9x9. Neobsazene policka jsou reprezentovana volnou promennou. Muzem pouzit `getIth`, `getRC`, ktery pro zadanou pozici a matici vrati prvek na tech souradnicich a `setRC`, ktery nastavi prvek v matici na nejakou hodnotu.
```prolog!
solves(M) :- search(1,1,M).
search(R,C,M) :-
getRC(R,C,M,V),
nonvar(V), !,
goNonvar(R,C,M).
search(R,C,M) :-
valsFor(R,C,M,VS),
testVals(R,C,M,VS).
goNonvar(9,9,_) :- !.
goNonvar(R,C,M) :-
newRC(R,C,RR,CC),
search(RR,CC,M).
testVals(9,9,M,[X]) :-
getRC(9,9,M,X), !.
testVals(R,C,M,[X|_]) :-
getRC(R,C,M,X),
newRC(R,C,RR,CC),
search(RR,CC,M).
testVals(R,C,M,[_|XS]) :-
testVals(R,C,M,XS).
```
### 1. opravny termín
Dámy
```prolog
/* -------------------------------------------------------------------- */
genAll(0,_,[]).
genAll(Size,Col,[pos(Col,Size)|Res]) :-
Size > 0,
SS is Size - 1,
genAll(SS,Col,Res).
/* -------------------------------------------------------------------- */
inConf([pos(X,_)|_], pos(X,_)) :- !.
inConf([pos(_,Y)|_], pos(_,Y)) :- !.
inConf([pos(XX,YY)|_], pos(X,Y)) :-
tst(XX,X,YY,Y), !.
inConf([_|PS], P) :-
inConf(PS,P).
tst(XX,X,YY,Y) :-
XX<X, !, tst(X,XX,YY,Y).
tst(XX,X,YY,Y) :-
YY<Y, !, tst(XX,X,Y,YY).
tst(XX,X,YY,Y) :-
XR is XX-X,
YR is YY-Y,
XR == YR.
/* -------------------------------------------------------------------- */
filterNot(_, [], []).
filterNot(Pred, [X|XS], YS) :-
call(Pred, X), !,
filterNot(Pred, XS, YS).
filterNot(Pred, [X|XS], [X|YS]) :-
filterNot(Pred, XS, YS).
/* -------------------------------------------------------------------- */
tryNext(PS,Size,Possible) :-
length(PS,LPS),
NewCol is LPS+1,
genAll(Size,NewCol,NewPs),
filterNot(inConfPS),NewPs,Possible).
/* -------------------------------------------------------------------- */
findQ(Size,PS,PS) :-
length(PS,Size),
!.
findQ(Size,PS,[]) :-
tryNext(PS,Size,[]),
!, fail.
findQ(Size,PS,Res) :-
tryNext(PS,Size,NewPS),
tryAll(Size,PS,NewPS,Res).
tryAll(_,_,[],_) :-
!, fail.
tryAll(Size,PS,[N|_],Res) :-
findQ(Size,[N|PS],Res).
tryAll(Size,PS,[_|NS],Res) :-
tryAll(Size,PS,NS,Res).
/* -------------------------------------------------------------------- */
queens(Size,Ress) :-
setof(P,findQ(Size,[],P),Ress).
/* -------------------------------------------------------------------- */
```
### 2. opravný termín
**Obchodní cestující:**
1. Definovat predikát `search (From, To, L)`, který vyhledá nejkratší cestu z `From` do `To` a vrátí její délku v `L`. Přičemž využívá `get_distance(From,To,L)`, což je predikát pro navrácení délky cesty mezi dvěma místy.
2. Definovat predikát `fsf (+From, Where, Distances)`, který vhodně navrací nejkratší vzdálenosti od `From` do všech míst z množiny `Where` v argumentu `Distances`.
3. Definovat predikát `gc (+Distances, Closest, L)`, který vybere a vrátí nejbližší bod od `From` z předchozího bodu v argumentu `Closest` a vzdálenost k němu v `L`.
4. Definovat predikát `ts (+From, +Where, -Path, -L)`, jež dostává výchozí bod a množnu dalších, které je nutné navštívit. Musí pak vybrat nejkratší cestu a vrátit ji i její délku.
## 2017/2018
### Řádný termín
1) /6b/ Flatten seznamu - vytvorit predikat e, ktery bere 2 argumenty. Prvni je seznam libovolne zanorenych seznamu (i prazdnych), napr. ``[[], [1, 2], [[[[]]],[atom, atom]]]``. Druhy argument je vysledny seznam bez zanoreni napr. `[1, 2, atom, atom]`.
```prolog
e([],[]).
e([[]|R],Res) :- !, e(R,Res).
e([[X|XS]|YS],Res) :- !, e([X,XS|YS],Res).
e([V|XS],[V|Res]) :- e(XS,Res).
/* alternative solution */
e([],[]) :- !.
e([H|T],FlatList) :- e(H, FlatH), e(T,FlatT), append(FlatH, FlatT, FlatList), !.
e(Elem, [Elem]).
append([H1|L1], L2, [H1|R]) :- append(L1, L2, R).
append([], R, R).
```
2) /7b/ Funkce XOR, ktera vraci symterickou diferenci dvou mnozin (sjednoceni mnozin bez jejich pruseciku). Bere prvni a druhy parametr mnozinu reprezentovanou seznamem, treti parametr je vysledna mnozina reprezentovana seznamem.
```prolog
xor([],L,L) :- !.
xor(L,[],L) :- !.
xor(L,R,Res) :- sub(L,R,L1),sub(R,L,R1),app(L1,R1,Res).
sub([],_,[]).
sub([X|XS],YS,RS) :- elem(X,YS),!,sub(XS,YS,RS).
sub([X|XS],YS,[X|RS]) :- sub(XS,YS,RS).
elem(X,[X|_]) :- !.
elem(X,[_|XS]) :- elem(X,XS).
app([],L,L).
app([X|XS],L,[X|RS]) :- app(XS,L,RS).
```
3) /9b/ Napisat predikat search(PocatecniPozice, SeznamCest), ktory najde vsechny cesty z dane pozice zpet do teto pozice, delky 20 az 22 kroku (netrapit se tim, jestli vracet prvni/posledni prvek ci ne). Kazdy prvok je mozne nastivit len jeden krat vyjma prveho (== posledneho). Definicia pozicie je neznama, napiste funkci nextStep(Pos, NewPos) nad neznamym a NEKONECNYM stavovym priestorom. Mozno pouzit retract*, assert*, bagof, setof, length.
```prolog
:- dynamic pos/1.
search(P,Res) :-
setof(Path,s(P,P,0,Path),Res).
s(P,P,N,[P]) :- N =< 22, N >= 20, !.
s(_,_,N,_) :- N > 22, !, fail.
s(P,P,N,_) :- N \= 0, !, fail.
s(A,P,N,[A|R]) :-
assertz(pos(A)),
NN is N+1,
nextStep(A,AA),
( not(pos(AA)) ; AA=P ) ,
s(AA,P,NN,R).
s(A,_,_,_) :-
pos(A),
retract(pos(A)),
!,fail.
nextStep(p(X,Y),p(XX,Y)) :- XX is X+1.
nextStep(p(X,Y),p(XX,Y)) :- XX is X-1.
nextStep(p(X,Y),p(X,YY)) :- YY is Y+1.
nextStep(p(X,Y),p(X,YY)) :- YY is Y-1.
```
4) /8b/ Napisat predikat lookup. Prvy arguement vhodne reprezentovana tabulka symbolov, 2-hy argument kluc, 3-ty argument hodnota. A posledny a vysledny argument je modifikovana, pripadne vstupna tabulka symbolov.
Predikat pracuje v dvoch rezimoch. Ak je zadana hodnota, tak sa prida/modifikuje zaznam (klic -> hodnota?) v tabulke symbolov. Ak nie je zadana hodnota, tak vyhladavame v tabulke hodnotu so zadanym klucom. Ak sa nemylim, tak bolo mozne pouzit vsetko zo zakladnej kniznice Prologu. Ja som pouzil `var/1`, `nonvar/1` na zistenie, ci (nie) je zadana hodnota a nemyslim si, ze by to bolo v zadani spomenute. -- priklad byl mozna lehce modifikovany?
```prolog
emptyT([]).
lookup(T,_,_,_) :- var(T), !, fail.
lookup(T,Var,Val,NT) :- nonvar(Var),nonvar(Val), !, iT(T,Var,Val,NT).
lookup(T,Var,Val,T) :- nonvar(Var), lT(T,Var,Val).
% iT = insert to Table
% we have not found pair (R,L) -> insert and end
iT([], R, L, [p(R,L)]).
% we have found matching key -> update and end
iT([p(R,_)|PS], R, L, [p(R,L)|PS]) :- !.
% iterating while keys are not matching
iT([p(RR,LL)|PS], R, L, [p(RR,LL)|PPS]) :- iT(PS,R,L,PPS).
% lT = lookup in Table
lT([p(R,L)|_],R,L) :- !.
lT([_|PS],R,L) :- lT(PS,R,L).
```
### 1. opravny termín
1. Holý Prolog. Napsat predikát `mkTrans(ListOfLists,ListOfLists)`, která dostane v 1. argumentu matici, kterou transponovanou unifikuje do 2. argumentu.
```prolog
mkTrans([],[]).
mkTrans([[]|_],[]).
mkTrans(LS,[HS|HHS]) :-
trans(LS,HS,TS),
mkTrans(TS,HHS).
trans([],[],[]).
trans([[H|T]|LS],[H|HS],[T|TS]) :-
trans(LS,HS,TS).
```
2. Holý Prolog. Napsat predikát `subseq`, který v 1. argumentu dostane seznam a do 2. argumentu unifikuje seznam všech jeho podseznamů, tedy jde tam o prefix a suffix matching.
```prolog
suff([],[[]]).
suff([H|T],[[H|T]|R]) :-
suff(T,R).
subseq(S,[[]|SS]) :-
suff(S,SUFS),
proc(SUFS,SS).
proc([],[]).
proc([S|SS],RES) :-
pref(S,[_|PS]),
proc(SS,PSS),
append(PS,PSS,RES).
pref([H|T],[[]|R]) :-
pref(T,PS),
prepAll(H,PS,R).
pref([],[[]]).
prepAll(_,[],[]).
prepAll(X,[L|LS],[[X|L]|XS]) :-
prepAll(X,LS,XS).
```
3. Prolog s `bagof, setof, assert, retract` atp. Prohledávání stavového prostoru. Napsat predikát `search(Start,Cíl, Nejkratší_cesta)`, který dostane nějakou startovní a koncovou pozici a unifikuje do 3. argumentu nejkratší cestu mezi nimi. Napsat také predikát `nextStep`, který bude vracet další novou pozici. úkolem není napsat optimální řešení, ale využít elegantnosti Prologu.
```prolog
:- dynamic pos/1. % the 1 argument is really a tuple of coordinates
search(S,E,Res) :-
retractall(pos(_)),
steptry(S,E,0,Res).
steptry(S,E,N,Res) :-
s(S,E,N,Res), !.
steptry(S,E,N,Res) :-
NN is N+1,
steptry(S,E,NN,Res).
s(E,E,0,[E]) :- !.
s(_,_,N,_) :- N < 0, !, fail.
s(A,E,N,[A|R]) :-
assertz(pos(A)),
NN is N-1,
nextStep(A,AA),
not(pos(AA)) ,
s(AA,E,NN,R).
s(A,_,_,_) :-
pos(A),
retract(pos(A)),
!,fail.
nextStep(p(X,Y),p(XX,Y)) :- XX is X+1.
nextStep(p(X,Y),p(XX,Y)) :- XX is X-1.
nextStep(p(X,Y),p(X,YY)) :- YY is Y+1.
nextStep(p(X,Y),p(X,YY)) :- YY is Y-1.
```
4. Prolog s celočíselným dělením, dělením a is. Napsat Prologovou reprezentaci racionálních čísel a operaci násobení a sčítání nad nimi.
```prolog
/* ---------------------------------- */
/* rac(numerartor,denominator) */
/* op('+',L,R).
* op('*',L,R).
* rac(N,D).
*/
gcd(N,N,N) :- !.
gcd(N,M,M) :-
N > M,
NN is mod(N,M),
NN==0, !.
gcd(N,M,D) :- % see 'euclidean algorithm'
N > M, !,
NN is mod(N,M),
gcd(M,NN,D).
gcd(N,M,N) :-
M > N,
MM is mod(M,N),
MM is 0, !.
gcd(N,M,D) :-
MM is mod(M,N),
gcd(N,MM,D).
ev(op('+',L,R),rac(NN,DD)) :-
ev(L,rac(LN,LD)),
ev(R,rac(RN,RD)),
N1 is LN*RD + RN*LD,
D1 is LD*RD,
norm(N1,D1,NN,DD).
ev(op('*',L,R),rac(NN,DD)) :-
ev(L,rac(LN,LD)),
ev(R,rac(RN,RD)),
N1 is LN*RN,
D1 is LD*RD,
norm(N1,D1,NN,DD).
ev(rac(X,Y),rac(X,Y)).
norm(N,D,NN,DD) :-
gcd(N,D,G), G>1,!,
NN is div(N,G),
DD is div(D,G).
norm(N,D,N,D).
```
## 2016/2017
### Riadny termín
1. Prohledávání stavového prostoru. Napsat predikát getPath, který má jako první parametr startovní bod a jako druhý cílový bod a do třetího unifikuje nejkratší (s nejmenší cenou) cestu mezi těmito body. Předpokládejte, že stavový prostor je konečný. Máte k dispozici predikát nextStep(X, XX, P), který jako první parametr dostane nějaký stav stavového prostoru a v druhém vrátí další stav a ve třetím bude výsledná cena tohoto kroku. (14b)
```prolog
% graph definition for testing etc.
% from: https://ibpublicimages.s3-us-west-2.amazonaws.com/tutorial/dijkstra3.png
nextStep('a', 'b', 3). nextStep('a', 'c', 2). nextStep('a', 'f', 5).
nextStep('b', 'a', 3). nextStep('b', 'c', 1). nextStep('b', 'd', 6).
nextStep('c', 'a', 2). nextStep('c', 'b', 1). nextStep('c', 'd', 4). nextStep('c', 'e', 4).
nextStep('d', 'b', 6). nextStep('d', 'c', 4). nextStep('d', 'e', 3).
nextStep('e', 'c', 4). nextStep('e', 'd', 3). nextStep('e', 'f', 2).
nextStep('f', 'a', 5). nextStep('f', 'e', 2).
:- dynamic
visited/1, % for preventing cycles
best_price/1, % when searched node is found, we save path price here for later comparison
best_path/1. % when we find some path to searched node, it is saved here
getPath(S,E,Path) :-
retractall(visited(_)),
retractall(best_price(_)),
retractall(best_path(_)),
assert(best_price(none)),
getPathHelper(S,E,Path).
% search always fails, but it keeps trying to explore all possible paths
getPathHelper(S,E,_) :- search(S,E,0,[]).
% eventually we fall here (no paths to explore) and check if we found some path
getPathHelper(S,_,[S|Path]) :- best_path(Path).
% when we reach the searched node, we check the price of our current path
search(E,E,Price,Path) :- checkP(Price, Path), fail.
% this is the base-case of the computation
search(S,E,P,TP) :-
assertz(visited(S)), % saving the visited node
nextStep(S,Nxt,SP), % find a neighbouring node and price of the edge
not(visited(Nxt)), % make sure we have not been in this node already
NP is P+SP, % add the price
append(TP,[Nxt],NTP), % add the node to our current path
search(Nxt,E,NP,NTP). % keep searching
% we fall here when we reach a dead-end = all possible neighbors have been visited
search(S,_,_,_) :-
retract(visited(S)), % we "unvisit" this dead-end node
!, fail. % and backtrack
% in this case, we have not yet found any solution
checkP(NP,Path) :-
best_price(none), % in which case this should be true
retract(best_price(none)),
assert(best_price(NP)), % so we set our price
assert(best_path(Path)). % and our path
% in this case, we have found some solution before
checkP(NP,Path) :-
best_price(P), % so we get its price
NP<P, % we make sour our current solution is better
retract(best_price(P)),
retract(best_path(_)),
assert(best_price(NP)),
assert(best_path(Path)). % and update best price, best path
```
2. Holý prolog (unifikace, základní práce se seznamy, + řez tuším). Navrhnout strukturu pro ukládání boolovských výrazů (pro and, or, not) nad proměnnými a literály true/false. Dále strukturu pro ukládání hodnot proměnných. Dále napsat predikát eval(Table, Expr, Res), která vyhodnotí daný bool výraz. V table je tabulka hodnot proměnných. Expr je vyhodnocovaný výraz. Do Res se unifikuje výsledek. (6b)
```prolog
% ground truth
eval(_,true,true).
eval(_,false,false).
% cuts are necessary, so that when a evaluation of expression gives false as a result,
% we don't explore further
eval(T,var(V),R) :- getVal(T,V,R), !.
eval(T,not(E),R) :-
eval(T,E,EvalE1),
% we use short-circuit evaluation here
% (also note that , has a higher priority than ; )
% if EvalE1 is unified with true,
% we have to also do the second part of the conjuction
% to satisfy the first part of the or (;) expression
% if EvalE1 is unified with false,
% the first part of the or (;) expression cannot be true
% because there is conjuction there, so we skip to the R=false part.
(EvalE1, eval(_, false, R); eval(_, true, R)), !.
eval(T,and(E1,E2),R) :-
eval(T,E1,EvalE1),
(EvalE1, eval(T,E2,R); eval(_,false,R)), !.
eval(T,or(E1,E2),R) :-
eval(T,E1,EvalE1),
(EvalE1, eval(_,true,R); eval(T,E2,R)), !.
% table of bool variable values is just a list of tuples
getVal([(V,Value)|_],V,Value).
getVal([_|WS],V,Value) :- getVal(WS,V,Value).
% usage examples:
% eval([(1, true), (2, false)], not(and(not(var(1)), var(2))), X).
% eval([('a', true), ('b', false)], or((var('a'), var('b')), X).
```
3. Holý prolog (unifikace, základní práce se seznamy). Implementujte predikát msort, který provádí merge sort řazení seznamu hodnot. Musí to být merge sort s jeho klasickou složitostí (ne kvadratickou...). (7b)
```prolog
merge([],L,L).
merge(L,[],L).
merge([H1|T1],[H2|T2],[H1|TT]) :- % to place H1 at the start of the result
H1 =< H2, % it has to be smaller than H2
merge(T1,[H2|T2],TT). % we then call merge on the rest
merge([H1|T1],[H2|T2],[H2|TT]) :- % other case (H2 is smaller)
H2 < H1,
merge([H1|T1],T2,TT).
msort([],[]). % list with no items is already sorted
msort([V],[V]). % list with 1 item is already sorted
msort([A,B|T],R) :-
divide(T,L1,L2), % split input list T into two equal-size lists
msort([A|L1],S1), % sort both of these lists individually
msort([B|L2],S2),
merge(S1,S2,R). % merge them together
% items with even idx (0,2,...) go to first list, odd idxs go to second
divide([],[],[]).
divide([V],[V],[]).
divide([A,B|T],[A|TA],[B|TB]) :-
divide(T,TA,TB).
```
4. Cely prolog, ale nesmi se pouzit vestaveny append a jeste 2 veci co si nepamatuju. Mame predikat, kde prvni parametr je predikat (dvouparametrovy - tedy jeden vstup a výsledek) a druhy je seznam seznamu. Z druheho parametru se postupně berou seznamy a ma se provest aplikace predikatu na vsechny hodnoty v seznamu a dat dohromady vysledky do jednoducheho seznamu (tedy ne seznam seznamu). (6b)
```prolog!
% we first recursively fall here, so the RES list is unified as []
mapOnListOfLists(_,[],[]) :- !.
% so that RES is in the correct order, we do the computation "backwards"
% we first have to get the whole result (recursively),
% and then apply F on the head list (HL) and
mapOnListOfLists(F,[HL|TL],RES) :-
mapOnListOfLists(F,TL,RT), % we perform F() on the rest first
mapOnList(F,HL,RT,RES). % then we do the head list
% once we have no more values to map a function over,
% R (3rd parameter) is unified with what was in RES (4th parameter)
mapOnList(_,[],R,R) :- !.
% base case => X contains the result with the mapped values
% it is appended to the result
mapOnList(F,[H|T],R,[X|RES]) :-
% next two lines could also be done using `call(F, H, X),`
C =.. [F,H,X], % construct a predicate F(H,X)
% we cannot do that directly since F is a variable
call(C), % call it (result is stored in X)
mapOnList(F,T,R,RES).
% example usage:
% mapOnListOfLists(abs, [[1,2,3], [-4,5,-6], [-10], []], X).
sqr(X,Y) :- Y is X*X.
% mapOnListOfLists(sqr, [[1,2,3], [-4,5,-6], [-10], []], X).
```
Sign in with Wallet
Connect another wallet