Lépegető

A feladvány

? - - - - - - - - - ? - - ? - - - - ? - - - - - - - - - - - - - ? - - ?		5 - - - - - - - - - 3 - - 2 - - - - 1 - - - - - - - - - - - - - 4 - - 6
1. ábra. Egy feladvány		2. ábra. A feladvány (egyetlen) megoldása

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 Sor-Oszlop párokból álló lista, amelynek elemei egy-egy kitöltendő rácspont (kérdőjel) helyét adják meg. A listáról feltételezhető, hogy az elemei lexikografikusan növekvő sorrendben vannak. Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere:

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

A Prolog-eljárás kimenő paramétere egy olyan - az előbbivel megegyező hosszúságú - lista, amely minden egyes koordinátához hozzárendeli a megfelelő rácspontba írandó számot. A 2. ábrán látható megoldást írja le például az alábbi lista:

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

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

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

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

% :- type koord      ---> int-int.
% :- type racspontok == list(koord).
% :- type kitoltes   == list(int).
% :- pred lepeget(racspontok::in, kitoltes::out).

A lepeget eljárás paraméterének és eredményének típusát a következő SML-típusdefiníciók írják le.

structure TLepeget =
struct
      type koord      = int * int
      type racspontok = koord list
      type kitoltes   = int list
end

signature Lepeget =
sig
  (* lepeget Rs = az 1..n számok összes olyan permutációja listaként
       ábrázolva, amelynek elemeit rendre egy rács Rs-beli rácspontjaiba
       írva a megadott távolságkritériumnak eleget tevő elrendezést kapunk
  *)
  val lepeget : TLepeget.racspontok -> TLepeget.kitoltes list
end

A keretprogram

A keretprogram bemenete egy olyan szöveges állomány, amelynek egyetlen sorában a rács kitöltendő rácspontjainak koordinátái állnak (Sor, Oszlop) alakban, egy-egy szóközzel elválasztva, lexikografikusan növekvő sorrendben.

(1,1) (2,5) (3,2) (4,1) (6,3) (6,6)

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ó felépítésű szöveges állomány.

A Prolog-keretprogram három eljárást exportál:

lepeget_be(file::in, racspontok::out)

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

lepeget_ki(file::in, racspontok::in, kitoltes::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 lepeget/2 eljárásra.

A keretprogram felhasználja a file típust:

% :- type file == atom.

Az SML-keretprogram három eljárást exportál:

signature KLepeget =
sig
    val lepeget_be : string -> TLepeget.racspontok
    val lepeget_ki : string * TLepeget.racspontok * TLepeget.kitoltes list -> unit
    val megold     : string * string -> string
end

lepeget_be f

Az f szöveges állományból beolvasott adatokból képzett feladvány.

lepeget_ki(m, fl, mss)

Az fl feladvány és az mss megoldáslista alapján az összes megoldást kiírja az m szöveges állományba.

megold(f, m)

Beolvas egy feladványt az f szöveges állományból és kiírja az összes megoldást az m szöveges állományba. Ehhez természetesen szüksége van a Lepeget.lepeget eljárásra. Eredménye az f nevet, a megoldások számát és a futási időt másodpercben tartalmazó füzér.

Dokumentációs követelmények

A két programhoz közös dokumentációt készítsen - 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 specifikálása
• Kódolás SML-, ill. Prolog-nyelven, az algoritmusok ismertetése
• Tesztelési megfontolások
• Kipróbálási tapasztalatok

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

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

A programok készülhetnek MS Windows alatt, de Linux alatt is működniük kell (ügyeljen a fájlnevekben a kis- és nagybetűk használatára!). A beadott programokat Linux környezetben SICStus Prolog 3.12.2, ill. MOSML 2.01 fordítóprogramokkal teszteljük.

A programokat és az elektronikus dokumentációt a webes felületen keresztül lehet külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. Programját egy 10-elemű tesztsorozattal automatikusan futtatjuk, és az eredményről válaszlevélben értesítjük. A beadást többször is megismételheti, a legutolsóként beadott megoldást értékeljük.

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ó beadási határideje 2005. december 15-e, csütörtök 24h.

Az értékelés a beadási tesztsorozathoz hasonló nehézségű tesztesetekkel történik. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk. A 10 futásra ö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 legfeljebb 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.