A feladvány

A megoldandó feladat

A Prolog-eljárásnak két paramétere van. Első (bemenő) paramétere a feladványt, második (kimenő) paramétere a megoldást írja le. Az eljárásnak a visszalépések során minden megoldást pontosan egyszer kell kiadnia. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.

A Prolog-eljárás bemenő paramétere egy

satrak(Ss, Os, Fs)

• Ss a sátrak soronkénti számát tartalmazó lista,
• Os a sátrak oszloponkénti számát tartalmazó lista és
• Fs a fák sorát (i) és oszlopát (j) azonosító i-j párok lexikografikusan rendezett listája.

Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere:

satrak([1,1,0,3,0], [1,0,2,0,2], [1-2,3-3,3-5,5-1,5-5])

A Prolog-eljárás kimenő paramétere egy olyan lista, amely - a fák Fs-beli megadási sorrendjét követve - a sátrak saját fájukhoz viszonyított helyzetét írja le. Egy sátor helyzetét a megfelelő égtájat jelölő betűvel adjuk meg:

A 2. ábrán látható megoldást írja le például az alábbi lista:

[e,s,n,n,n]

Feltételezheti, hogy feladvány sorainak és oszlopainak száma legfeljebb 999 lehet.

A megírandó eljárás specifikációja

% :- type fLeiro  ---> satrak(sSzS, sSzO, list(parc)).
% :- type sSzS    == list(int).
% :- type sSzO    == list(int).
% :- type parc    == int-int.
% :- type irany   ---> n    % észak
%                 ;    e    % kelet
%                 ;    s    % dél
%                 ;    w.   % nyugat
% :- type sHelyek   == list(irany).
% :- pred satrak(fLeiro::in, sHelyek::out).

Egyéb követelmények

Megoldásában tetszőleges Prolog-könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb, chr és atts könyvtárakat: az ezeket felhasználó megoldásokat nem fogadjuk el, így a létraversenyben sem vehetnek részt, és megajánlott jegyet sem kaphatnak. Hasonlóképpen tiltott a mellékhatásos beépített eljárások, így az assert, retract, bb_put, bb_get stb. használata.

A keretprogram

Programját keretprogram segítségével próbálhatja ki. A keretprogramot a beadáskor használthoz hasonló tesztesetekkel együtt az alábbi helyről töltheti le:

• Keretprogram + tesztesetek + futási idők + README.txt (ZIP).

A ksatrak.pl Prolog-keretprogram a következő eljárásokat exportálja:

% :- pred satrak_be(file::in, sspec::out).

A megnevezett szövegfájlból beolvassa a feladványt, és visszaadja a kimenő paraméterben.

% :- pred satrak_ki(file::in, ssol::in).

A megnevezett szövegfájlba kiírja a feladvány második paraméterként átadott összes megoldását.

% :- pred megold(file::in, file::in).

Beolvas egy feladványt az első paraméterrel megnevezett szövegfájlból, és kiírja az összes megoldását a második paraméterrel megnevezett szövegfájlba. Ehhez felhasználja a satrak/2 eljárást.

% :- pred stopper(file::in, file::in).

Mint megold/2, de a végén kiírja a feladvány nevét, a megoldások számát és a futási időt is.

% :- pred teljes_teszt(int::in).

A tests könyvtárban levő összes testXXXd.txt tesztállomány esetén:

• lefuttatja a tesztet az első paraméterben megadott, másodpercben értelmezett időkorláttal,
• ellenőrzi, hogy a testXXXs.txt állományban megadott megoldáshalmazt kapta,
• olvasható formában (lásd megold/2) kiírja az eredményt a tests_out könyvtár testXXXt.txt nevű állományába.

A fenti állománynevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl. Ezt az eljárást Eisenberger András ültette át Prologra.

A keretprogram felhasználja a file típust:

% :- type file == atom.

A file típusú paraméterben a user atomot megadva a terminálról vihetünk be, ill. a terminálra írathatunk ki adatokat. Egyébként a megadott nevű fájlba írunk, ill. fájlból olvasunk.

Használat: saját programját a satrak.pl nevű fájlba tegye, különben a ksatrak.pl keretprogram nem találja meg. Ezután indítsa el a SICStus rendszert, és töltse be a keretprogramot. Példa:

| ?- [ksatrak].
% compiling /home/szeredi/tmp/ksatrak.pl...
%  module ksatrak imported into user
(...)
% compiled /home/szeredi/tmp/ksatrak.pl in module ksatrak, 30 msec 78104 bytes
yes
| ?- stopper('teszt0.txt','teszt0.sol').

A stopper/2, ill. megold/2 eljárások meghívása a satrak.pl programot automatikusan betölti (ha szükséges), ezért ennek módosításakor nem kell sem a SICStus interpretert újraindítania, sem a keretprogramot újra betöltenie.

Dokumentációs követelmények

Egyéb tudnivalók