UL/FRI/UNI-RI/MOS/Izpiti/2008-09-15-prolog

Prečkati morate od orkana opustošeno mesto. Na določenih mestih se nahajajo nevarnosti (poplava, zrušena drevesa, ogenj, ..), ki se jim, če se le da, želite izogniti. Pot na sliki, v tem pogledu, ni najbolj optimalna, ker prečka nevarnost na poziciji (6,f).

Pozicijo v mestu navajamo s koordinatama (X,Y), kjer je X element množice {1,2,..,10} in Y je element množice {a,b,..,k}. Premikate se lahko le po korakih, ki so podani s predikatom premik(Od, Do), kjer sta poziciji Od in Do zapisani s koordinatama (X,Y).

(slika -> http://shrani.si/f/3L/Vu/3AisRq3Y/2008-09-15-slika.jpg)

%premik(Od, Do).
premik((2,a), (2,b)).
premik((2,b), (2,a)).
premik((2,b), (2,c)).
premik((2,c), (2,b)).
etc...
 
%nevarnost((X,Y)).
nevarnost((3,c)).
nevarnost((6,f)).
nevarnost((3,h)).
nevarnost((4,k)).

1. naloga

(25%) Napišite predikate obstajaPot(A, B, Pot), ki uspe, če obstaja pot od A do B. Argument Pot naj ustreza zeznamu pozicij, ki jih obiščemo na poti. Pozorni bodite na dejstvo da so možni cikli. Predikat naj bo napisan tako, da ne vrača poti s cikli, saj ne želimo prehoditi iste pozicije več kot enkrat.

Rešitev:

% Tole ni prava rešitev in tudi ne deluje v prologu - naj nekdo dopolni/popravi
obstajaPot(A, B, []) :-
	premik(A, X),
	obstajaPot(X, B, A).
obstajaPot(B, B, Pot) :- !.
obstajaPot(A, B, Pot) :-
	premik(A, X),
	not(member(X, [Pot])), 
	obstajaPot(X, B, [X|Pot]).

2. naloga

(30%) Napišite predikat steviloNevarnosti(A, B, Stevilo, Pot), ki prešteje koliko nevarnih pozicij (argument Stevilo) je na poti Pot med pozicijama A in B.

Rešitev:

% Pot = [(9,a), (9,b), (9,c), (9,d), (9,e), (9, f), (8,f), (7,f), (6,f), (6,g), (6,h), (5,h),(4,h), (3,h), (2,h), (2,i), (2,k)].
% problem je v tem, da ne šteje nevarnosti, če "stojimo" na njej - recimo da je OK, ker zahteva št. nevarnosti MED točkama, se pravi če sta A in B nevarnosti potem šteje samo tiste nevarnosti, ki sta med njima.
steviloNevarnosti(A, B, Stevilo, Pot) :-
	conc(_, [A|Pot1], Pot),
	conc(Pot2, [B|_], Pot1),
	findall(X, (member(X, Pot2), nevarnost(X)), Nevarnosti),
	length(Nevarnosti, Stevilo).

3. naloga

(20%) Napišite predikat varnost(Stevilo, Beseda), ki število nevarnosti pretvori v besedni opis. Pretvorba naj bo učinkovita in naj se vrši po ključu:

Število → Opisno:
0 → varna
1 → nevarna
2 ali več → smrtonosna

Rešitev:

% Tole je bolj prologovska rešitev .. če je v nalogi omenjeno "učinkovito", potem uporabimo cut.
varnost2(Stevilo, Beseda) :- Stevilo = 0, Beseda = varna, !.
varnost2(Stevilo, Beseda) :- Stevilo = 1, Beseda = nevarna, !.
varnost2(Stevilo, Beseda) :- Beseda = smrtonosna.

varnost(Stevilo, Beseda) :-
	Stevilo = 1, Beseda = nevarna,!;
	(   Stevilo < 1, Beseda = varna,!; Beseda = smrtonosna).

4. naloga

(25%) Definirajte operatorje in (nove) predikate tako, da boste lahko v "naravnem" jeziku poizvedovali o varnosti posamezne poti (namig: uporabite predikata steviloNevarnosti in varnost).

Nekaj primerov poizvedb v naravnem jeziku:

?- Pot med A in B je V.
A=(2,a), B=(2,b), Pot=[(2,a), (2,b)], V = varna ? ...

?- Pot med (2,k) in (2,h) je varna.
Pot=[(2,k), (2,j), (2,i), (2,h)] ? ...

?- Pot med (2,h) in (4,h) je Varnost.
Pot=[(2,h), (3,h), (4,h)], Varnost = nevarna ? ...

Rešitev:

% Za tole nism niti 1% prepričan da je pravilno .. naj nekdo, ki se je boljš naučil Prolog popravi zadevo.
:-op(100, xfy, in).
:-op(200, xfy, med).
:-op(300, xfx, je).
 
% sm si mal pogledal zadevo v izpitu leta 2005 (1. izpit tukaj gor) .. zgleda bi moralo kaj takega bit - spet naj raši kakšn stručko to overi in popravi.
je(PotInTocki, Beseda) :-
	PotInTocki = med(Pot, in(A,B)),
	steviloNevarnosti(A, B, Stevilo, Pot),
	varnost(Stevilo, Beseda).