Deklaratív programozás

Nagy házi feladat

Mastermind

A játék ismertetése

A játékot bizonyára mindenki jól ismeri. Színes kód- és tippbábukkal, fekete és fehér válaszpálcikákkal ketten játsszák olyan táblán, amelyen több sorban lyukak vannak. Az alapjátékban hatféle színű kód- és tippbábuból lehet választani, és mind a tipp, mind a kód négy színes bábuból áll.

Az 1. ábrán egy Mastermind játszmát mutatunk be. Itt a tippbábukat az 1..6 számok jelzik, míg a fekete, illetve fehér válaszpálcikákat a B, illetve W betűkkel jelöltük.

A passzív játékos feladata, hogy a színes bábukból tetszőleges kombinációt állítson össze. Azonos színű bábukból több is lehet a kódban. A passzív játékos e titkos kódot a másik - aktív - játékos által nem látható lyukakba helyezi, majd a valóságnak megfelelően válaszol az aktív játékos kérdéseire.

Az aktív játékos feladata a titkos kód kitalálása, a lehető legkevesebb lépésben. Minden lépésben tetszőleges kombinációt állít össze a színes bábukból, és tippjét a tábla következő üres sorába rakja. A passzív játékos mindegyik tippről közli, hogy milyen közel van a kódhoz: annyi fekete válaszpálcikát rak a táblára, ahány egyforma színű bábu van a tippben és a kódban ugyanazon a helyen, továbbá annyi fehér válaszpálcikát rak a táblára, ahány egyforma színű bábu van a tippben és a kódban különböző helyen.

Mivel a titkos kódban (és így a tippben is) ugyanaz a szín többször is előfordulhat, ezért a fehér válaszpálcika használatát pontosítani kell. Amikor a kódban többször fordul elő egy szín, akkor az adott színű bábuk közül csak annyihoz rendelhető fehér válaszpálcika, ahányszor az adott szín a tippben a nem megfelelő helyen szerepel; ugyanez a megszorítás fordítva is fennáll. A fehér válaszpálcikák számának meghatározása így pl. a következő módon történhet:

• Elhagyjuk mind a kódból, mind a tippből azokat a bábukat, amelyekre fekete pálcikával válaszoltunk.
• Minden egyes szín esetén: megszámoljuk az adott színű bábukat a kódban és a tippben, majd ezen két darabszám közül a kisebbikkel megegyező számú fehér pálcikával válaszolunk.

A válaszpálcikák elhelyezése a sorban nem hordoz információt, csak a pálcikák darabszáma számít; így nem lehet tudni, hogy pontosan mely bábukra vonatkoznak.

A játék aktív játékosként itt kipróbálható (a játékhoz Flash szükséges).

A megoldandó feladat

Írjon mmind néven olyan Erlang-függvényt, ill. Prolog-eljárást, amely a tippek és a hozzájuk tartozó válaszok egy halmazára megadja a bemeneti adatoknak megfelelő titkos kódokat!

A Mastermind-játéknak két alapparamétere van:

• Max a megengedett színek száma;
• H a kódban szereplő bábuk száma, azaz a kód hossza. (Értelemszerűen a tippek hossza is H.)

A függvénynek, illetve az eljárásnak két bemenő paramétere van. Az első a Max paraméter, azaz a kódban megengedett maximális érték. A második egy nem-üres lista, a súgás-lista, amelynek elemei a játszma egy-egy lépésének felelnek meg: egy tippet és az arra adott választ tartalmazzák. A súgás-lista elemei tehát párok, amelyek első tagja egy (megtippelt) kód, a második tagja pedig az erre kapott válasz (a fekete és a fehér válaszpálcikák száma).

A játék H (hossz) paramétere implicit módon van megadva: a (nem-üres) súgás-lista elemeiben szereplő tippek mind H hosszú listák. Nem szükséges ellenőriznie, hogy ezek a listák egyforma hosszúságúak-e.

Azt mondjuk, hogy egy titkos kód megfelel egy SL súgás-listának és egy Max meximális kódértéknek, ha

• nem tartalmaz Max-nál nagyobb értéket;
• továbbá a súgás-lista minden elemére fennáll, hogy az adott súgás-elemben megadott tippre a súgás-elemben megadott választ eredményezi.

Az Erlang-függvény kimenete az összes, a bemenetnek megfelelő kód ismétlődésmentes listája, tetszőleges sorrendben. A Prolog-eljárás kimenete egyetlen kód, azonban visszalépések során az összes megfelelő kódot elő kell állítania, mégpedig mindegyiket egyszer; a felsorolás sorrendje itt is érdektelen. Értelemszerűen, ha a súgás-lista ellentmondást tartalmaz, azaz nincs megfelelő kód, akkor az Erlang-függvény az üres listával tér vissza, a Prolog-eljárás pedig meghiúsul.

Természetesen a függvény, ill. az eljárás által visszaadott kódok hossza is H kell legyen, azaz meg kell egyezzen a bemenő paraméterben szereplő tippek hosszával.

Vegyük például a következő befejezetlen játszmát, amelyben feltesszük, hogy a passzív játékos négy színt használ:

Ennek a játszmának két megoldása van, amely megfelel a bemenetnek: [3,1,4] és [4,1,3]. A Prolog-eljárásnak ezt a két megoldást a visszalépések során fel kell felsorolnia, míg az Erlang-függvény eredményének a [[3,1,4],[4,1,3]] kételemű listának kell lennie. A játszma két megoldásának sorrendje mindkét nyelv esetén felcserélhető.

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

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

% :- type code     == list(int).
% :- type blacks   == int.
% :- type whites   == int.
% :- type answer ---> blacks/whites.
% :- type hint   ---> code-answer.

% :- pred mmind(int::in, list(hint)::in, code::out).
% mmind(Max, Hints, Code): Code egy olyan titkos kód, amely megfelel a
%    a Hints súgás-listának és a Max maximális kódértéknek.

A mmind:mmind/2 Erlang-függvény típusát a következő - megjegyzésként megadott - Erlang-típusdefiníciók írják le.

%% @type code()   = [integer()].
%% @type blacks() = integer().
%% @type whites() = integer().
%% @type answer() = {blacks(),whites()}.
%% @type hint()   = {code(),answer()}.

%% @spec mmind:mmind(Max::int(),Hints::[hint()]) -> Codes::[code()].
%% @doc  Codes a Hints súgás-listának és a Max maximális kódértéknek
%%   megfelelő összes titkos kód tetszőleges sorrendű listája.

-module(mmind).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([mmind/2]).
%-compile(export_all).

Példa

A 2. ábrán látható példa az alábbi módon adható meg a Prolog-eljárásnak, illetve az Erlang-függvénynek, és a megoldást is az itt leírt módon várjuk (de nem feltétlenül ebben a sorrendben).

Prolog

| ?- mmind(4, [[1,1,1]-1/0,
               [1,2,2]-0/1,
               [3,1,3]-2/0], Code).
Code = [3,1,4] ? ;
Code = [4,1,3] ? ;
no

Erlang

mmind:mmind(4, [{[1,1,1],{1,0}},
                {[1,2,2],{0,1}},
                {[3,1,3],{2,0}}]).
[[3,1,4],[4,1,3]]

A keretprogram

A keretprogram bemenete egy olyan szövegfájl, amelynek első sora a Max számot, azaz a kódban felhasználható legnagyobb értéket tartalmazza, minden egyes további sorában pedig egy tipp és a rá adott válasz áll. A tipp pozitív egészek egy vagy több szóközzel elválasztott sorozata. Egy vagy több szóköz után következik a válasz, amely a fekete és a fehér válaszpálcikák száma, `/' jellel elválasztva.

A 3. ábra a 2. ábrán bemutatott példát leíró bemeneti fájl tartalmát mutatja.

3. ábra: A keretprogram egy lehetséges bemenete

4   1 1 1 1/0 1 2 2 0/1 3 1 3 2/0

A fenti példa esetén a bemenetnek megfelelő megoldások: [3,1,4] és [4,1,3]. (Ezeket a Prolog-eljárásnak fel kell sorolnia, az Erlang-függvénynek listába gyűjtve vissza kell adnia. A sorrend természetesen tetszőleges.)

A Prolog-keretprogram

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

mmind_be(file::in, int::out, list(hint)::out)

A megnevezett szövegfájlból beolvassa a Mastermind-feladványt leíró maximális kódértéket és súgás-listát, és mindkettőt visszaadja.

mmind_ki(file::in, list(code)::in)

A megnevezett szövegfájlba kiírja a feladvány második paraméterként átadott összes megoldásá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 mmind/3 eljárást.

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

Mint megold/2, de a végén kiírja a feladvány nevét, a megoldások számát és 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 mmind.pl nevű fájlba tegye, különben a kmmind.pl keretprogram nem találja meg. Ezután futtassa a SICStus interpretert, és töltse be a keretprogramot. Példa:

SICStus 4.1.1 (x86-linux-glibc2.7): Tue Dec 15 16:13:21 CET 2009
Licensed to BUTE-DP-course
| ?- [kmmind].
% compiling ...
% compiled ... in module mmind_keret, 15 msec 29792 bytes
yes
| ?- stopper('teszt0.txt','teszt0.sol').

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

A kmmind.erl Erlang-keretprogram a következő négy függvényt exportálja:

@spec kmmind:mmind_be(FileIn::string()) -> MMind::{integer(),[hint()]}

MMind a FileIn szövegfájlból beolvasott, a Mastermind-feladványt leíró kódértékből és súgás-listából álló pár.

@spec kmmind:mmind_ki(FileOut::string(), Codes::[code()]) -> void()

A Codes listában átadott Mastermind-megoldásokat kiírja a FileOut szövegfájlba.

@spec kmmind:megold(FileIn::string(), FileOut::string()) -> void()

Beolvas egy feladványt a FileIn szövegfájlból és összes megoldását kiírja a FileOut szövegfájlba. Ehhez felhasználja a mmind:mmind/2 függvényt.

@spec kmmind:stopper(FileIn::string(), FileOut::string()) -> void()

Mint kmmind:megold/2, de a végén kiírja a FileIn nevét, a megoldások számát és a futási időt is.

Használat: saját mmind.erl nevű programját minden változtatás után fordítsa le, és mmind.beam néven rakja a keretprogrammal azonos mappába, különben a kmmind.erl keretprogram nem találja meg. Ezután indítsa el az Erlang értelmezőt, és töltse be a lefordított keretprogramot. Példa:

Eshell V5.7.4  (abort with ^G)
1> l(kmmind).
{module,kmmind}
2> kmmind:stopper("teszt0.txt","teszt0.sol").

A keretprogram automatikusan betölti a mmind.beam programot, feltéve, hogy a keretprogrammal azonos mappában van.

Ha a saját mmind.erl programját módosítja, a lefordítása után betöltheti az l(mmind). paranccsal, de újra betöltheti a kmmind.erl keretprogramot is, ami magával húzza a módosított programot. Időnként célszerű újraindítani az Erlang értelmezőt.

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 Erlang-diákon használt szövegelrendezési konvenciókat! 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 Erlang, 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 4.1.x, ill. az Erlang R14B rendszerekkel teszteljük.

Megoldásában tetszőleges könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb és chr Prolog-könyvtárakat: az ezeket a könyvtárakat felhasználó megoldások a létraversenyben nem vehetnek részt, és így megajánlott jegyet sem kaphatnak.

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. A teszteseteket úgy választjuk meg, hogy legalább négy feladványt a kevésbé ötletes programok is meg tudjanak oldani. Az eredményt levélben közöljük és az ETS-ben is megnézhető.

A nagy házi feladat elkészítése nem kötelező, de megoldását mindenkinek javasoljuk: ez a deklaratív nyelvek magas szintű elsajátítását nagy mértékben segíti.

• Prolog - 2010. november 29., hétfő, 24h.
• Erlang - 2010. december 06., hétfő, 24h.
• Dokumentáció - 2010. december 08., szerda, 24h.

A beadási határidő után értékeljük a programokat (ez az ún. "éles" teszt). Ehhez a beadási tesztsorozathoz hasonló nehézségű teszteseteket használunk. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk, a 10 tesztesetre tehát nyelvenként összesen maximum 5 pontot. 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 pont kapható (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az éles teszt legalább 8 feladatát helyesen és az előírt időkorláton belül megoldják, létraversenyben vesznek részt. A leggyorsabban futó Erlang-, 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.

Azok a hallgatók, akik mindkét nyelvből bejutnak a létraversenybe - a tantárgyi adatlapon leírt feltételek fennállása esetén - megajánlott jegyet kapnak.

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.