Aknakereső

Ez a leírás a Deklaratív 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 alakú tábla, amelynek egyes mezőin 0 és 8 közötti számok szerepelnek. A feladat az, hogy aknákat helyezzünk el a táblára, az alábbi feltételek teljesítésével:

1. Pontosan i darab aknát használunk fel összesen.
2. A számozott mezők nyolc él- és sarokszomszédja közül pontosan annyin kell aknának lennie, amekkora az adott mező értéke.
3. Számmal jelzett mezőn nem lehet akna.
4. Egy mezőn legfeljebb egy akna lehet.

Egy feladványnak több megoldása is lehet.

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. A megoldásban * jelöli az aknákat.

  +---+---+---+---+---+
  |   |   | 0 |   |   |
  +---+---+---+---+---+
  |   |   |   |   | 1 |
  +---+---+---+---+---+
  | 3 |   | 1 |   |   |
  +---+---+---+---+---+
  |   |   |   |   | 1 |
  +---+---+---+---+---+
  |   | 1 |   |   |   |
  +---+---+---+---+---+

  +---+---+---+---+---+
  |   |   | 0 |   |   |
  +---+---+---+---+---+
  | * |   |   |   | 1 |
  +---+---+---+---+---+
  | 3 | * | 1 |   | * |
  +---+---+---+---+---+
  | * |   |   |   | 1 |
  +---+---+---+---+---+
  |   | 1 |   |   |   |
  +---+---+---+---+---+

A megoldandó feladat

Írjon aknakereso néven olyan Prolog-eljárást, ill. SML-függvényt, 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

    a(S-O,N,RefPL)

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).
• N az aknák száma.
• RefPL a referenciapontok listája, ahol a lista p(Sor,Oszlop,Érték) alakú elemekből áll. Ezek határozzák meg a számot tartalmazó mezők pozícióját és értékét. A lista lexikografikusan rendezett.

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

    k(5-5, 4, [p(1,3,0),p(2,5,1),p(3,1,3),p(3,3,1),p(4,5,1),p(5,2,1)])

A Prolog-eljárás kimenő paramétere az aknát tartalmaző mezők koordinátáinak a listája (az elemek sorrendje tetszőleges).

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

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

Az SML-függvény paramétere egy ((S,O), N, RefPL) hármas, ahol S, O és N jelentése azonos a Prolog-eljárásnál leírtakkal, míg RefPL egy lexikografikusan rendezett lista, amelynek elemei (Sor, Oszlop, Érték) alakú hármasok, a jelentésük pedig szintén azonos a Prolog-eljárásnál leírtakkal.

Az 1. ábrán bemutatott feladvány esetén például az SML-függvény paramétere:

    ((5,5), 4, [(1,3,0),(2,5,1),(3,1,3),(3,3,1),(4,5,1),(5,2,1)])

Az SML-függvény eredménye egy olyan lista, amely a feladvány összes megoldását tartalmazza, mégpedig minden megoldást pontosan egyszer. Ha a feladványnak nincs megoldása, az eredmény az üres lista. Egy megoldást a koordinátapárok (kettesek) listájaként kell megadni, a Prolog-megoldáshoz hasonlóan. Az aknák felsorolásának sorrendje tetszőleges.

A 2. ábrán látható megoldást írja le az alábbi (egyelemű) megoldás-lista:

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

A megírandó függvény, ill. eljárás specifikációja

Az aknakereso/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 tabla           ---> a(meret, aknaszam, list(ref_pont)).
% :- type ref_pont        ---> p(sor, oszlop, ertek).
% :- type sor               == integer.
% :- type oszlop            == integer.
% :- type ertek             == integer.
% :- type aknaszam          == integer.
% :- type meret           ---> sor-oszlop.
% :- type pont            ---> sor-oszlop.
% :- type aknamezo          == list(pont).

% :- pred aknakereso(tabla::in, aknamezo::out).

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

helyes_feladvany(a(Meret,Aknaszam,RefPL)) :-
        % a pálya mérete helyes:
        helyes_pont(Meret,inf-inf),
        % nincs nem helyes eleme a RefPL listának:
        \+ (   member(Ref, RefPL),  
               \+ helyes_referencia(Ref, Meret) 
           ),
        % a RefPL lista lexikografikusan rendezett:
        sort(RefPL, RefPL),
        % A RefPL lista minden eleme különböző (Sor,Oszlop)
        % koordinátájú vonatkozik (a rendezettség miatt elegendő ezt a
        % szomszédos elemekre nézni):
        \+ append(_, [p(S,O,_),p(S,O,_)|_], RefPL),
        % Elég szabad mező van az aknák számára:
        Meret = Sor-Oszlop,
        Terulet is Sor * Oszlop,
        length(RefPL, Szammezok),
        Terulet - Szammezok >= Aknaszam.

helyes_pont(S-O, MaxS-MaxO) :-
        integer(S), S >=1, S =< MaxS,
        integer(O), O >=1, O =< MaxO.

helyes_referencia(p(Sor,Oszlop,Ertek), Meret) :-
        helyes_pont(Sor-Oszlop, Meret),
        0 =< Ertek, Ertek =< 8.

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

Az aknakereso függvény paraméterének és eredményének típusát a következő SML-típusszinonimák írják le.

type sor      = int
type oszlop   = int
type ertek    = int
type aknaszam = int
type meret    = sor * oszlop
type pont     = sor * oszlop
type ref_pont = sor * oszlop * ertek
type tabla    = meret * aknaszam * ref_pont list
type aknamezo = pont list

val aknakereso : tabla -> aknamezo list

Az aknakereso függvény tabla típusú paramétere mindenképpen kielégíti az alábbi feltételt:

fun helyes_feladvany (Meret, Aknaszam, RefPL) =
    let
        val (MaxS, MaxO) = Meret
        val Terulet = MaxS * MaxO
        val RefPontSzam = length RefPL
        fun helyes_pont (Sor, Oszlop) =
              1 <= Sor andalso 1 <= Oszlop andalso
              Sor <= MaxS andalso Oszlop <= MaxO
        fun helyes_ref_pont (Sor, Oszlop, Ertek)  =
              helyes_pont (Sor, Oszlop) andalso
              0 <= Ertek andalso Ertek <= 8;

        fun lexikografikusan_hasonlit ((x1,y1,_), (x2,y2,_)) =
              if      x1 < x2 orelse x1 = x2 andalso y1 < y2 then LESS
              else if x1 > x2 orelse x1 = x2 andalso y1 > y2 then GREATER
              else EQUAL
        fun szomszedok_kulonbozok (rp1::(rps as rp2::_)) =
              lexikografikusan_hasonlit (rp1, rp2) <> EQUAL
              andalso szomszedok_kulonbozok rps
          | szomszedok_kulonbozok _ = true
    in 
        (* a tábla méretezése, az aknaszám megadása helyes: *)
        1 <= MaxS andalso 1 <= MaxO andalso
        Terulet - RefPontSzam >= Aknaszam andalso
        (* a RefPL lista minden eleme helyes: *)
        (List.all (fn x => x) (map helyes_ref_pont RefPL)) andalso
        (* a RefPL lista lexikografikusan rendezett: *)
        sorted lexikografikusan_hasonlit RefPL andalso
        (* A RefPL 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): *)
        szomszedok_kulonbozok RefPL
    end;

Az SML megoldásában tehát feltételezheti, hogy az adott paraméterre a helyes_feladvany predikátum igazat ad eredményül (csak ilyen adattal teszteljük majd a programot).

Keretprogramok

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt letöltheti innen. A házi feladatok teszteléséhez és értékeléséhez a keretprogramokkal azonos specifikációjú programokat fogunk használni.

A keretprogram bemenete egy olyan szövegfájl, amelyben az első sorban a tábla sorainak és oszlopainak száma, a második sorban az aknák száma, a következő sorok mindegyikében pedig három szám szerepel. E három szám közül az első kettő valamely mező sor- és oszlopszáma, a harmadik szám pedig e mező értéke. Az adatokra a fent említett korlátok vonatkoznak, tehát a sor- és oszlopszámok a táblán belüli mezőket azonosítanak, a mezők értéke 0 és 8 közötti szám, a sorok lexikografikusan rendezve vannak (ld. 3. ábra, vö. 1. ábra).

5 5
4
1 3 0
2 5 1
3 1 3
3 3 1
4 5 1
5 2 1

A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szövegfájl.

A Prolog-keretprogram

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

helyes_feladvany(tabla::in)

A tabla tábla helyességét vizsgáló, fent ismertetett feladványellenőrző eljárás.

aknakereso_be(file::in, tabla::out)

A file szövegfájlból beolvassa a táblát, és visszaadja a tabla kimenő paraméterben.

aknakereso_ki(file::in, tabla::in, aknamezo::in)

A file szövegfájlba kiírja a feladvány megoldását.

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

Beolvas egy feladványt a file_in szövegfájlból, és kiírja összes megoldását a file_out szövegfájlba. Ehhez természetesen szüksége van az aknakereso/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ű fájlba írunk, ill. fájlból olvasunk.

Használat: a saját programját az aknakereso.pl nevű fájlba 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.5 (x86-linux-glibc2.3): Sun Mar 12 09:39:40 CET 2006
Licensed to BUTE-DP-course
| ?- [kaknakereso].
% consulting d:/dokumentumok/bme/deklapo/06a/kaknakereso.pl...
%  module aknakereso_keret imported into user
%  loading e:/programozas/sicstus/library/lists.po...
%  module lists imported into aknakereso_keret
%  loaded e:/programozas/sicstus/library/lists.po in module lists, 15 msec 11688 bytes
% consulted d:/dokumentumok/bme/deklapo/06a/kaknakereso.pl in module aknakereso_keret, 15 msec 29792 bytes
yes
| ?- stopper(..., ...).

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

Az SML-keretprogram

Az SML-keretprogram a következő öt függvényt exportálja:

helyes_feladvany t

A t tábla helyességét vizsgáló, fent ismertetett feladványellenőrző függvény.

aknakereso_be f

Az f szövegfájlból beolvasott adatokból képzett tábla.

aknakereso_ki(m, t, mss)

A t tábla mss megoldáslistáját olvasható formában kiírja az m szövegfájlba.

megold(f, m)

Beolvas egy feladványt az f szövegfájlból és kiírja az összes megoldását az m szövegfájlba. Ehhez természetesen szüksége van a aknakereso függvényre. Eredménye az f nevet és a megoldások számát tartalmazó füzér.

stopper(f, m)

Beolvas egy feladványt az f szövegfájlból és kiírja az összes megoldását az m szövegfájlba. Ehhez természetesen szüksége van a aknakereso függvényre. Eredménye az f nevet, a megoldások számát és a futási időt mp-ben tartalmazó füzér.

A bemenetet, ill. a kimenetet a terminálra irányíthatjuk Unix alatt a /dev/stdin, ill. a /dev/stdout, MS DOS/Windows alatt mindkét esetben a con fájlnév megadásával.

Használat: olvassa be az interpreterbe a kaknakereso.sml programot, és a megfelelő paraméterekre alkalmazza a kiválasztott függvényt, például:

Moscow ML version 2.01 (January 2004)
Enter `quit();' to quit.
- use "kaknakereso.sml";
> val it = () : unit
- megold (..., ...);

A keretprogram a use "aknakereso.sml" kifejezéssel betölti a keretprogrammal azonos könyvtárban lévő aknakereso.sml programot.

Miután a saját aknakereso.sml programját módosította, betöltheti a módosított programot, de betöltheti újra a kaknakereso.sml programot is, hiszen az betölti a módosított programot is. Sokszor célszerű az SML értelmezőt is újraindítani.

Dokumentációs követelmények

Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük 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-, ill. az SML-jegyzetben látható szövegelrendezési szokásokat! Ne írjon 72 karakternél hosszabb sorokat! Minden eljáráshoz és függvényhez készítsen fejkommentet!

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

• Követelmények elemzése
• Tervezés, az egyes eljárások, ill. függvények specifikálása
• Kódolás SML-, ill. Prolog-nyelven, az algoritmusok ismertetése
• Tesztelési megfontolások
• 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, ill. az MOSML 2.01 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. Programját egy tízelemű tesztsorozattal automatikusan futtatjuk, és erről válaszlevélben értesítjük. A beadást többször is megismételheti, az utoljára beadott megoldást tekintjük érvényesnek.

A házi feladat beadása nem kötelező, de a DP nyelvek magasszintű elsajátításához nagy segítséget ad. Ezért javasoljuk, hogy a házi feladatot mindkét nyelven készítsék el és adják be. Mindazonáltal elfogadunk csak SML, ill. csak Prolog nyelven készült megoldásokat, értelemszerűen felére csökkentett pontszámmal. A teszteseteket úgy választottuk meg, hogy 3-4 feladatot az egyszerű, algoritmikus ötletek nélküli programok is meg tudjanak oldani.

Figyelem! A jó jegyhez gyakorlatilag elengedhetetlen a házi feladat elkészítése.

A programok és az elektronikus dokumentáció módosított beadási határideje 2006. december 18., hétfő, 24h (eredetileg dec. 4. volt).

Az értékeléshez a beadási tesztsorozathoz hasonló nehézségű teszteseteket fogunk használni. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk. a 10 tesztesetre összesen tehát nyelvenként maximum 5 pontot kaphat. Ezen felül a dokumentációt, a programkód olvashatóságát, kommentezettségét is értékeljük, nyelvenként maximum 2,5 ponttal. Ha mindkét nyelvből beadja a házi feladatot, akkor tehát maximum 15 pontot kaphat (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az alapteszt minden feladatát helyesen és az előírt időkorláton belül megoldják, létraversenyben vesznek részt. A leggyorsabban futó SML-, ill. Prolog-programokra - helyezési számuktól függően - külön-külön 7,5 és 0,5 közötti pluszpont kapható. Ha valaki tehát mindkét nyelvből a leggyorsabb programot írja meg, akkor a 100 alapponton felül 15 pluszpontot kap.

A programot és dokumentációt mindenkinek saját magának kell elkészítenie. A beadott házi feladatokat gépi úton hasonlítjuk össze, másolás esetén a kódot adó és kapó hallgató sem kaphat pontot. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.