Nagyhatékonyságú logikai programozás

Házi feladat, 1.0. változat

Felhők

Ez a leírás a Nagyhatékonyságú logikai programozás c. tárgyból kiadott féléves házi feladatot ismerteti.

A feladvány

Adott egy n*m mezőből álló téglalap, amely egy radarernyőt ábrázol. A radarral felhőket figyelünk meg, a radarernyő minden mezője vagy egy felhőhöz, vagy a tiszta égbolthoz tartozik. Az alábbi feltételek mindig teljesülnek:

1. A felhők téglalap alakúak, mind vízszintesen, mind függőlegesen legalább két egység hosszúak.
2. A felhők egymást még sarkosan sem érintik.

1. a radarernyő mérete,
2. egyes oszlopok és sorok esetén a felhőrészletet tartalmazó (azaz felhős) mezők száma,
3. egyes mezők esetén az is, hogy az adott mező felhőrészletet tartalmaz (azaz felhős) vagy nem tartalmaz (azaz felhőtlen).

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. Az ábrán minden sorhoz és oszlophoz megadtunk egy számot. Ha ez a szám pozitív, akkor a felhős mezők számát adja meg, míg a -1 érték azt jelzi, hogy az adott sorról, ill. oszlopról nincs információ. Jelölések: # felhős mező; . felhőtlen mező.

  +---+---+---+---+---+
  |   |   |   |   |   | 4
  +---+---+---+---+---+
  |   |   |   |   | . | 4
  +---+---+---+---+---+
  |   |   |   |   |   | 0
  +---+---+---+---+---+
  |   | # |   |   |   | -1
  +---+---+---+---+---+
  |   |   |   |   |   | 4
  +---+---+---+---+---+
    4   4  -1   4   2

     

  +---+---+---+---+---+
  | # | # | # | # | . | 4
  +---+---+---+---+---+
  | # | # | # | # | . | 4
  +---+---+---+---+---+
  | . | . | . | . | . | 0
  +---+---+---+---+---+
  | # | # | . | # | # | -1
  +---+---+---+---+---+
  | # | # | . | # | # | 4
  +---+---+---+---+---+
    4   4   -1  4   2

     

A megoldandó feladat

Írjon felhok néven olyan Prolog-eljárást, amely egy feladvány összes megoldását előállítja! A feladat megoldásában használjon korlát-logikai programozási módszereket!

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

    f(SOL, OOL, RefPL)

felépítésű struktúra, ahol

• SOL a sorösszeg-lista, azaz a tábla soraiban lévő felhős mezők száma az első sortól kezdve (hossza egyben megadja a tábla magasságát);
• OOL az oszlopösszeg-lista, azaz a tábla oszlopaiban lévő felhős mezők száma az első oszloptól kezdve (hossza egyben megadja a tábla szélességét);
• RefPL a referenciapontok (esetleg üres) listája, amelynek elemei f(Sor,Oszlop) vagy e(Sor, Oszlop) alakúak. Az első jelentése az, hogy a (Sor,Oszlop) koordinátájú mező felhős, a másodiké pedig az, hogy a mező felhőtlen (azaz ott az ég látszik, ezért használjuk a e(...) jelölést). A lista a sor-oszlop párok szerint lexikografikusan rendezve van.

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

    f([4,4,0,-1,4], [4,4,-1,4,2], [e(2,5), f(4,2)]) 

A Prolog-eljárás kimenő paramétere az eredményt egy felhőlista formájában adja meg, a lista elemei egy-egy felhőt írnak le f(KS, KO, ZS, ZO) alakban, ahol a felhő a KS..ZS sorok és a KO..ZO oszlopok metszete.

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

    [f(1,1,2,4), f(4,1,5,2), f(4,4,5,5)] 

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

A felhok/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 radarkep        ---> f(list(sorosszeg), list(oszloposszeg), list(ref_pont)).
% :- type sorosszeg         == integer.
% :- type oszloposszeg      == integer.
% :- type ref_pont        ---> f(sor, oszlop) | e(sor, oszlop).
% :- type sor               == integer.
% :- type oszlop            == integer.

% :- type felhok            == list(felho).
% :- type felho           ---> f(kezdosor, kezdooszlop, zarosor, zarooszlop).
% :- type kezdosor          == sor.
% :- type kezdooszlop       == oszlop.
% :- type zarosor           == sor.
% :- type zarooszlop        == oszlop.

% :- pred felhok(radarkep::in, felhok::out).

A felhok/2 eljárás első, radarkep típusú paramétere mindenképpen kielégíti az alábbi feltételt:

helyes_feladvany(f(SorOsszegek, OszlopOsszegek, RefPL)) :-
        length(SorOsszegek, N),
        length(OszlopOsszegek, M),
        % a referenciapontok koordinátáinak KoordL listája
        % az eredetivel azonos sorrendű, ahol minden
        % referenciapont eget vagy felhőt jelöl:
        koordinatak(RefPL, KoordL),
        % az összegek legkisebb értéke -1 lehet,
        % de nem haladhatják meg a tábla méretét:
        forall( member(S, SorOsszegek), (-1 =< S, S =< M) ),
        forall( member(O, OszlopOsszegek), (-1 =< O, O =< N) ),
        % a KoordL lista minden eleme helyes:
        forall( member(Koord, KoordL), helyes_koordinata(Koord, N-M) ),
        % a KoordL lista lexikografikusan rendezett;
        % ebből következően RefPL is:
        sort(KoordL, KoordL),
	% A KoordL lista bármely két eleme különböző; 
        % ebből következően a RefPL listában szereplő 
	% (Sor,Oszlop) koordináták is páronként különböznek
        % (a rendezettség miatt elegendő ezt a szomszédos elemekre kikötni):
        forall( append(_, [K1, K2|_], KoordL), K1 \= K2 ).

koordinatak([], []).
koordinatak([e(S,O)|RefPL], [S-O|KoordL]) :-
        koordinatak(RefPL, KoordL).
koordinatak([f(S,O)|RefPL], [S-O|KoordL]) :-
        koordinatak(RefPL, KoordL).

helyes_koordinata(S-O, MaxS-MaxO) :-
        integer(S), S > 0, S =< MaxS,
        integer(O), O > 0, O =< MaxO.

%  forall(Cél1, Cél2) : Cél1 minden megoldása teljesíti Cél2-t.
forall(Goal1, Goal2) :-
        (   Goal1, \+ Goal2 -> fail
        ;   true
        ).

Megoldásában tehát feltételezheti, hogy a bemenő argumentumra a helyes_feladvany/1 eljárás sikeresen lefut (csak ilyen adattal teszteljük majd a programot).

A keretprogram

Programját keretprogram segítségével próbálhatja ki. A keretprogramot a beadáskor használthoz hasonló tesztsorral együtt letöltheti innen. A házi feladatok teszteléséhez és értékeléséhez ezekkel kompatíbilis programokat fogunk használni.

A keretprogram bemenete egy olyan szöveges állomány, amelynek első sorában a sorösszegek szerepelnek szóközzel elválasztva, második sorában az oszlopösszegek hasonló módon. Az ezt követő sorok mindegyikében egy betű és két szám áll, amelyek az adott referenciapont típusát, valamint sor- és oszlopszámát határozzák meg. Ezekre a bejegyzésekre a már fent említett korlátok vonatkoznak, tehát a sor- és oszlopszámok a táblán belüli mezőt azonosítanak, a típust jelölő karakter pedig e vagy f (ld. 3. ábra, vö. 1. ábra).

4 4 0 -1 4
4 4 -1 4 2
e 2 5
f 4 2

3. ábra. A bemenő állomány tartalma az 1. ábrán látható feladvány esetén

A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szöveges állomány.

A keretprogram öt eljárást exportál:

helyes_feladvany(radarkep::in)

A fent ismertetett feladványellenőrző eljárás.

felhok_be(file::in, radarkep::out)

A megnevezett szöveges állományból beolvassa a radarképet, és visszaadja a második argumentumban.

felhok_ki(file::in, radarkep::in, felhok::in)

A megnevezett szöveges állományba kiírja az adott radarképhez tartozó adott megoldás szöveges alakját.

megold(file::in, file::in)

Beolvas egy feladványt az első paraméterként kapott állományból, és kiírja az ahhoz tartozó összes megoldást a második paraméterben megadott állományba. Ehhez természetesen szüksége van a felhok/2 eljárásra.

stopper(file::in, file::in)

Mint megold/2, de a futás végén kiírja a futási időt is.

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ű állományba írunk, ill. állományból olvasunk.

Használat: a saját programját a felhok.pl nevű állományba tegye, különben a keretprogram nem találja meg. Ezután futtassa a SICStus interpretert, és töltse be a keretprogramot:

SICStus 3.10.0 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002
Licensed to BUTE DP course
| ?- [kfelhok].
% consulting /home/david/uni/dp/04s/nhf/kfelhok.pl...
%  module felhok_keret imported into user
%  loading /usr/local/lib/sicstus-3.9.1/library/lists.po...
%  module lists imported into felhok_keret
%  loaded /usr/local/lib/sicstus-3.9.1/library/lists.po in module lists, 0 msec 11656 bytes
% consulted /home/david/uni/dp/04s/nhf/kfelhok.pl in module felhok_keret, 20 msec 29168 bytes
yes
| ?- stopper(..., ...).

A stopper/2, ill. megold/2 eljárások meghívása a felhok.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

A programhoz készítsen dokumentációt; vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:

• Követelmények elemzése
• Modellezés: korlát-változók és tartományaik, valamint a korlátok megválasztása
• Esetleges felhasználói korlátok (globális korlátok, FD-predikátumok) ismertetése
• Címkézési módszerek (pl. borotválás) bemutatása
• Kipróbálási tapasztalatok

A dokumentációt elektronikus alakban adja be, HTML, esetleg ASCII formátumban.

Egyéb követelmények és tudnivalók

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (linux) alatt is működniük kell. A beadott programokat Unix környezetben a SICStus Prolog 3.10.1 rendszerrel teszteljük.

A beadás módja