Szógyűrű

A feladvány

Egy szólistából egymással az elejükön, illetve a végükön legalább i és legfeljebb j helyen átfedésben lévő szavakat kell kiválogatni, és beírni egy n cellából álló szógyűrűbe (litván versenyfeladat). Minden szó legfeljebb egyszer használható fel. Egy feladványnak több megoldása is lehet. Két megoldást ekvivalensnek tekintünk, ha egymásból ciklikus léptetéssel előállíthatók. A feladat az összes megoldás előállítása úgy, hogy az egymással ekvivalens megoldáscsoportokból csak egyet mutatunk fel.

• j ≥ i ≥ 0,
• n > 0.

Az 1. ábra egy feladvány paramétereit és szavait, a 2. ábra ennek (az ekvivalens megoldásoktól eltekintve egyetlen) megoldását mutatja többféle ábrázolásban.

1 2 24 batai samba taisykla lobis timpa senis paltai aidai tikslo imti			m b a a s t i a n i e d s a i i b m o t l i s k	batai aidai imti tikslo lobis senis samba |...
1. ábra. Egy feladvány (i=1, j=2, n=24)		2. ábra. A feladvány (egyetlen) megoldása, többféle ábrázolásban

Determinizmus, nemdeterminizmus

A minimálkövetelmények teljesítéséhez szükséges első négy tesztesetben i = j lesz, azaz e tesztek determinisztikusak lesznek.

A megoldandó feladat

Írjon wordring 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, az ekvivalens megoldások közül bármelyiket. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.

A Prolog-eljárás bemenő paramétere egy

    wr(I, J, N, W)

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

• I, illetve J az átfedésben lévő karakterek minimális, illetve maximális száma;
• N a szógyűrű celláinak a száma;
• W a használandó szavak listája.

A Prolog-eljárás kimenő paramétere egy V-C párokból álló lista, ahol a V a szógyűrű egy szava, a C pedig a V szó végén és a következő szó elején átfedésben lévő karakterek száma. A listában a V szavak a szógyűrűbeli előfordulásuk szerinti sorrendben követik egymást.

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

    wr(1, 2, 24, [batai,samba,taisykla,lobis,timpa,senis,paltai,aidai,tikslo,imti])

A 2. ábrán látható megoldást (többek között) az alábbi listával írhatjuk le:

    [batai-2,aidai-1,imti-2,tikslo-2,lobis-1,senis-1,samba-2]

Az SML-függvény paramétere egy négyes, amely a feladványt, az eredménye pedig egy lista, amely a megoldást írja le. E listának a feladvány összes megoldását tartalmaznia kell, mégpedig minden megoldást pontosan egyszer, az ekvivalens megoldások közül pedig bármelyiket. Ha a feladványnak nincs megoldása, az eredmény az üres lista.

Az SML-függvény paramétere egy (i, j, n, ws) négyes, ahol i, j, n és ws jelentése azonos a Prolog-eljárás I, J, N és W struktúraelemeinek a jelentésével.

Az SML-függvény eredménye egy olyan lista, amely (v, c) párokból álló listákat tartalmaz, ahol a v a szógyűrű egy szava, a c pedig a v szó végén és a következő szó elején átfedésben lévő karakterek száma. A (v, c) párokból álló listában a v szavak a szógyűrűbeli előfordulásuk szerinti sorrendben követik egymást.

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

    (1, 2, 24, ["batai","samba","taisykla","lobis","timpa","senis","paltai","aidai","tikslo","imti"])

A 2. ábrán látható megoldást (többek között) az alábbi (egyelemű) megoldáslistával írhatjuk le:

    [[("batai",2),("aidai",1),("imti",2),("tikslo",2),("lobis",1),("senis",1),("samba",2)]]

További példák

| ?- wordring(wr(0,8,2,[babababa]), WR).
WR = [babababa-6] ? ;
no
| ?- wordring(wr(0,8,4,[babababa]), WR).
WR = [babababa-4] ? ;
no
| ?- wordring(wr(0,8,6,[babababa]), WR).
WR = [babababa-2] ? ;
no
| ?- wordring(wr(0,8,8,[babababa]), WR).
WR = [babababa-0] ? ;
no

| ?- wordring(wr(0,1,2,[a,b,ab]), WR).
WR = [a-0,b-0] ? ;
WR = [a-1,ab-0] ? ;
WR = [a-1,ab-1,b-0] ? ;
WR = [b-0,ab-1] ? ;
WR = [ab-0] ? ;
no

| ?- wordring(wr(0,2,4,[ol,lo,lool]), WR).
WR = [ol-0,lo-0] ? ;
WR = [ol-0,lo-2,lool-2] ? ;
WR = [ol-0,lool-2] ? ;
WR = [lo-2,lool-0] ? ;
WR = [lool-0] ? ;
no

wordring(0,8,2,["babababa"]) = [[("babababa",6)]];
wordring(0,8,4,["babababa"]) = [[("babababa",4)]];
wordring(0,8,6,["babababa"]) = [[("babababa",2)]];
wordring(0,8,8,["babababa"]) = [[("babababa",0)]];

wordring(0,1,2,["a","b","ab"]) = [[("a",1),("ab",0)], [("a",1),("ab",1),("b",0)],
                                 [("a",0),("b",0)], [("b",0),("ab",1)], [("ab",0)]]

wordring(0,2,4,["ol","lo","lool"]) = [[("ol",0),("lool",2)], [("ol",0),("lo",0)],
                                     [("ol",0),("lo",2),("lool",2)], [("lo",2),("lool",0)], [("lool",0)]]

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

A wordring/2 Prolog-eljárás típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le.

% :- type wrspec      ---> wr(min_overlap, max_overlap, ring_length, list(word)).
% :- type min_overlap == int.
% :- type max_overlap == int.
% :- type ring_length == int.
% :- type word        == atom.
% :- type overlap     == int.
% :- type wopair      ---> word-overlap.
% :- type ring        == list(wopair).

% wordring(WRSPEC, RING):
% RING a WRSPEC specifikációnak megfelelő szógyűrű.
% :- pred wordring(wrspec::in, ring::out).

A wordring SML-függvény típusát a következő SML-típusszinonimák és - itt megjegyzésként megadott - típusspecifikáció írják le.

type words       = string list;
type min_overlap = int;
type max_overlap = int;
type ring_length = int;
type overlap     = int;
type ring        = (string * overlap) list;
(* wordring : min_overlap * max_overlap * ring_length * words -> ring list
*)

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 nagy 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 három egész szám van: az átfedésben lévő karakterek minimális és maximális száma, továbbá a szógyűrű celláinak a száma, a többi sor pedig a szógyűrű előállításához használandó szavakat tartalmazza (ld. 1. ábra).

A keretprogram kimenete a 2. ábrán bemutatott harmadik változathoz hasonló tartalmú szövegfájl.

A Prolog-keretprogram

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

wordring_in(file::in, wrspec::out)

A megnevezett szövegfájlból beolvassa a feladványt, és visszaadja a kimenő paraméterben.

wordring_out(file::in, ring::in, ring_length::in)

A megnevezett szövegfájlba kiírja a feladvány második paraméterként átadott összes megoldását. Ehhez felhasználja a szógyűrű harmadik paraméterként átadott méretét.

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 wordring/2 eljárást.

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: saját programját a wordring.pl nevű fájlba tegye, különben a kwordring.pl 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
| ?- [kwordring].
% consulting d:/dokumentumok/bme/deklapo/07s/kwordring.pl...
%  module wordring_frame imported into user
%  loading e:/programozas/sicstus/library/lists.po...
%  module lists imported into wordring_frame
%  loaded e:/programozas/sicstus/library/lists.po in module lists, 15 msec 11688 bytes
% consulted d:/dokumentumok/bme/deklapo/07s/kwordring.pl in module wordring_keret, 15 msec 29792 bytes
yes
| ?- stopper(..., ...).

A stopper/2, ill. megold/2 eljárások meghívása a wordring.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ő négy függvényt exportálja:

wordring_in f

Az f szövegfájlból beolvasott adatokból képzett feladványleíró négyes.

wordring_out(m, mss, r)

Az m szövegfájlba kiírja a feladványnak az mss listával átadott megoldását.

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 felhasználja a wordring függvényt. Eredménye az f nevet és a megoldások számát tartalmazó füzér.

stopper(f, m)

Mint megold, de a futási időt is visszaadja a füzérben (mp-ben).

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 kwordring.sml programot, és a megfelelő paraméterekre alkalmazza a kívánt függvényt:

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

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

Miután a saját wordring.sml programját módosította, betöltheti a módosított programot, de betöltheti újra a kwordring.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 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.

Programját egy tízelemű tesztsorozattal automatikusan futtatjuk, az eredményről válaszlevélben értesítjük, az ETS-ben pedig megnézheti. A teszteseteket úgy választjuk meg, hogy négy feladványt a kevésbé ötletes programok is meg tudjanak oldani.

A nagy házi feladat beadása, elfogadása és a tesztesetek 40%-ának sikeres megoldása az aláírás feltétele. A nagy házi feladat elfogadása azt jelenti, hogy a hallgatónak a laborgyakorlatokon, illetve a feladat beadását követő konzultáción a feladatra vonatkozó kérdések megválaszolásával, illetve módosított részfeladatok megoldásával meg kell győznie a konzulensét arról, hogy a feladatot ő készítette el, és a feladat elkészítéséhez szükséges tudás birtokában van. A nagy házi feladat megoldását azoknak is javasoljuk, akik korábban szereztek aláírást: ez a deklaratív nyelvek magasszintű elsajátítását nagymértékben segíti.

A programok és az elektronikus dokumentáció módosított beadási határideje 2007. május 18., péntek, 24h (2007. május 6., vasárnap, 24h helyett).

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. A mindkét nyelven beadott nagy házi feladatra 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 nagy 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.