Folyó

A feladvány

Nevezzünk térképnek egy n*m mezőből álló, téglalap alakú táblát, amelynek mezői az alábbi "tereptárgyak" egyikéhez tartoznak, azaz az alábbi típusúak lehetnek:

• forrás,
• tó,
• kikötő (befogadóképességét - a dokkok számát - 1 és 7 közötti számmal adjuk meg),
• rét,
• folyó.

A forrás, a tó és a tetszőleges számú kikötő mindegyike csak egyetlen mezőből állhat. A folyót egymással összefüggő mezők alkotják. A többi mező a réthez tartozik. Forrásból, tóból és folyóból csak egy, kikötőből és rétből több is lehet. A feladat az, hogy egy részlegesen kitöltött térképen (azaz amelyen nincs minden mező típusa megadva) meghatározzuk a vizes, azaz a forrás, folyó és tó típusú mezőket úgy, hogy az alábbi feltételek teljesüljenek:

1. a folyó egyetlen mezőből vagy az éleik mentén érintkező mezőkből áll, nem ágazik el, a forrásból ered és a tóba folyik bele;
2. a forrás és a tó mező élszomszédjai közül pontosan egynek-egynek kell folyó típusúnak lennie;
3. a folyó nem keresztezheti önmagát, és nem szomszédos mezői legfeljebb a sarkukkal érinthetik egymást (vagyis a folyó nem folyhat például 2 mezőt észak, azután 1-et kelet, majd ismét 1-et dél felé);
4. egy kikötő nyolc él- és sarokszomszédja közül a befogadóképességével megegyező számú mezőnek kell vizes mezőnek lennie (ez a feltétel hasonló a közismert aknakereső játékban szereplő feltételhez);
5. a forrás és a tó legfeljebb a sarkukkal érintkezhetnek (ezért nincsen 8-as befogadóképességű kikötő).

A feladványban az összes kikötő típusú mező helyét előre megadjuk, a többi mező típusát pedig vagy megadjuk, vagy nem. A feltételekből következik, hogy a megoldásban legalább három vizes mezőnek kell lennie: a forrás és a tó mellett legalább egy mezőnek a folyóhoz kell tartoznia. Minden feladványnak természetesen több megoldása is lehet.

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. Jelölések: F = forrás, T = tó, @ = folyó, számjegy = adott befogadóképességű kikötő, R = rét, üres négyzet = ismeretlen mező a feladványban, réthez tartozó mező a megoldásban.

  +---+---+---+---+---+
  |   | 3 |   |   |   |
  +---+---+---+---+---+
  | T |   |   | R |   |
  +---+---+---+---+---+
  |   |   |   |   | @ |
  +---+---+---+---+---+
  | F |   | 6 |   |   |
  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+

  +---+---+---+---+---+
  |   | 3 |   |   |   |
  +---+---+---+---+---+
  | T | @ | @ | R |   |
  +---+---+---+---+---+
  |   |   | @ | @ | @ |
  +---+---+---+---+---+
  | F | @ | 6 |   | @ |
  +---+---+---+---+---+
  |   | @ | @ | @ | @ |
  +---+---+---+---+---+

A megoldandó feladat

Írjon folyo néven olyan CLP(FD) módszereken alapuló 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

    f(S-O,MezoL)

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

• S és O a tábla mérete, azaz sorainak és oszlopainak a száma (a tábla bal felső mezője az első sor első oszlopában van).
• MezoL az ismert típusú mezők listája, ahol a lista m(Sor,Oszlop,Tipus) alakú elemekből áll. Ezek határozzák meg a mezők pozícióját és típusát. A lista lexikografikusan rendezett, Tipus lehetséges értékei pedig:
  • folyo
  • forras
  • to
  • ret
  • kikoto(N), ahol N egy 1 és 7 közötti egész szám

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

    f(5-5, [m(1,2,kikoto(3)),m(2,1,to),m(2,4,ret),m(3,5,folyo),m(4,1,forras),m(4,3,kikoto(6))])

A Prolog-eljárás kimenő paramétere a forrástól a tóig vezető vizes mezők koordinátáinak a listája (a forrást és a tavat is beleértve).

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

    [4-1,4-2,5-2,5-3,5-4,5-5,4-5,3-5,3-4,3-3,2-3,2-2,2-1]

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

A folyo/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 folyoterkep     ---> f(meret, list(mezo)).
% :- type mezo            ---> m(sor, oszlop, mezo_tipus).
% :- type mezo_tipus      ---> folyo ; forras ; to ; ret ; kikoto(dokkszam).
% :- type sor               == integer.
% :- type oszlop            == integer.
% :- type dokkszam          == integer.
% :- type pont            ---> sor-oszlop.
% :- type meret           ---> sor-oszlop.
% :- type folyovonal        == list(pont).

% :- pred folyo(folyoterkep::in, folyovonal::out).

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

helyes_feladvany(f(Meret,MezoL)) :-
    % a tábla méretezése helyes:
    helyes_pont(Meret,inf-inf),
    % nincs nem helyes eleme a MezoL listának:
    \+ ( member(Mezo, MezoL),
         \+ helyes_mezo(Mezo, Meret)
       ),
    % a forrás és a tó (ha meg vannak adva) nem lehetnek élszomszédosak,
    % azaz távolságuk nagyobb 1-nél:
    ( member(m(SF,OF,forras),MezoL),
      member(m(ST,OT,to),MezoL)
    ->
      tavolsaga(SF-OF, ST-OT, Tav),
      Tav > 1
    ; true
    ),
    % nincs két forrás a listában:
    ( select(m(_,_,forras),MezoL,MezoLF) -> \+ member(m(_,_,forras),MezoLF) 
    ; true
    ),
    % nincs két tó a listában:
    ( select(m(_,_,to),MezoL,MezoLT) -> \+ member(m(_,_,to),MezoLT) 
    ; true
    ),
    % a MezoL lista lexikografikusan rendezett:
    sort(MezoL, MezoL),
    % a MezoL lista minden eleme különböző (Sor,Oszlop)
    % koordinátára vonatkozik (a rendezettség miatt elegendő ezt a
    % szomszédos elemekre kikötni):
    \+ append(_, [p(S,O,_),p(S,O,_)|_], MezoL).
    
helyes_pont(S-O, MaxS-MaxO) :-
    integer(S), S >=1, S =< MaxS,
    integer(O), O >=1, O =< MaxO.

tavolsaga(S1-O1, S2-O2, T) :-
    T is sqrt( (S1-S2)**2 + (O1-O2)**2 ).

helyes_mezo(m(S,O,Tipus),Meret) :-
    helyes_pont(S-O,Meret),
    helyes_tipus(Tipus).
    
helyes_tipus(folyo).
helyes_tipus(forras).
helyes_tipus(to).
helyes_tipus(ret).
helyes_tipus(kikoto(N)) :-
    integer(N), N >= 1, N =< 7.

A Prolog 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 specifikációs modulokkal és egy, 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 programot fogunk használni.

A keretprogram bemenete egy olyan szöveges állomány, amelynek első sorában a tábla sorainak és oszlopainak száma szerepel, az ezt követő sorok mindegyike pedig két számmal kezdődik, amelyek az adott mező sor- és oszlopszámát adják meg. Ezután a mező típusa következik, amely a folyo, forras, to, ret vagy kikoto szavak egyike lehet. Kikötő esetében a sor végén egy további szám is áll: a kikötő befogadóképessége. A mezőkre 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 kikötők befogadóképessége 1 és 7 közé esik, és a sorok lexikografikusan rendezve vannak (ld. 3. ábra, vö. 1. ábra).

 5 5
 1 2 kikoto 3
 2 1 to
 2 4 ret
 3 5 folyo
 4 1 forras
 4 3 kikoto 6

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

A Prolog-keretprogram

A Prolog-keretprogram a következő öt eljárást exportálja:

helyes_feladvany(folyoterkep::in)

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

folyo_be(file::in, folyoterkep::out)

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

folyo_ki(file::in, folyoterkep::in, folyovonal::in)

A megnevezett szöveges állományba kiírja az adott megoldást.

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 folyo/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 folyo.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. Példa:

SICStus 3.12.2 (x86-linux-glibc2.3): Sun May 29 11:59:09 CEST 2005
Licensed to BUTE-DP-course
| ?- [kfolyo].
% consulting d:/dokumentumok/bme/deklapo/06s/kfolyo.pl...
%  module folyo_keret imported into user
%  loading e:/programozas/sicstus/library/lists.po...
%  module lists imported into folyo_keret
%  loaded e:/programozas/sicstus/library/lists.po in module lists, 15 msec 11688 bytes
% consulted d:/dokumentumok/bme/deklapo/06s/kfolyo.pl in module folyo_keret, 15 msec 29792 bytes
yes
| ?- stopper(..., ...).

A stopper/2, ill. megold/2 eljárások meghívása a folyo.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 programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövege jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások, ill. függvények feladatát és működését! Kövesse a Prolog-jegyzetben látható szövegelrendezési szokásokat! Ne írjon 72 karakternél hosszabb sorokat! Minden eljáráshoz készítsen fejkommentet!

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

Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.

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

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

A programok készülhetnek MS Windows alatt is, de Linux alatt is működniük kell. A beadott programokat Linux környezetben a SICStus Prolog 3.12.x, rendszerekkel teszteljük.

A programokat és az elektronikus dokumentációt webes felületen lehet majd külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. A beadást többször is megismételheti, az utoljára beadott megoldást tekintjük érvényesnek.

A nagy házi feladat a vizsgaidőszak végéig beadható.