2. nagy házi feladat (Prolog): Sátrak

1.0 változat — $LastChangedDate: 2022-11-06 22:18:20 +0100 (Sun, 06 Nov 2022) $
Kiadás: 2022-10-20
Beadási határidő a honlapon.

A feladvány

A megoldandó feladat

Írjon satrak néven olyan Prolog-eljárást, amely egy feladvány összes megoldását előállítja!

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)
felépítésű struktúra, ahol

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:

w (west) - a sátor a saját fájától nyugatra áll, n (north) - a sátor a saját fájától északra áll,
e (east) - a sátor a saját fájától keletre áll, s (south) - a sátor a saját fájától délre áll.

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

A satrak/2 Prolog-eljárás paramétereinek típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le.
% :- 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

A beadott programot Linux környezetben a SICStus Prolog 4 rendszerrel teszteljük.

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:

A nagy házi feladatok teszteléséhez és értékeléséhez a keretprogrammal azonos specifikációjú programokat fogunk használni. Olvassa el a README.txt-t!

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: 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

DP Admin: dvacakrobotjaitoknakp@iit.bme.hu Vissza az elejére / Back to the top