BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus szak
Nappali tagozat
2017/2018-es tanév, tavaszi félév

Nagyhatékonyságú deklaratív programozás

Nagy házi feladat

1.0 változat
Utolsó módosítás: 2019-04-28

Mastermind

A játék ismertetése

A Mastermind játékot 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. A játék közismert változatában mind a tipp, mind a kód négy színes bábuból áll, a bábuk hatféle színűek lehetnek.

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.

Kód- és tippbábuk Válaszpálcikák
Titkos kód: ? ? ? ?
1. tipp és válasz: 1 2 1 2 W      
2. tipp és válasz: 5 1 3 5 W      
3. tipp és válasz: 2 3 4 4 B B    
4. tipp és válasz: 2 3 6 6 B W    
5. tipp és válasz: 2 6 4 5 B B W W
6. tipp és válasz: 2 6 5 4 B B B B
7. tipp és válasz helye:                
8. tipp és válasz helye:                

1. ábra: A Mastermind-játék alapelrendezése

Definíciók és jelölések

A passzív játékos feladata, hogy a színes bábukból tetszőleges variációt állítson össze, melyet titkos kódnak nevezünk (röviden kód). Azonos színű bábukból több is lehet a kódban. A passzív játékos e 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. Azt mondjuk, hogy a tipp egy bábuja és a kód egy bábuja ugyanazon a helyen vannak, ha a tábla ugyanazon oszlopában vannak, egyébként azt mondjuk, hogy különböző helyen vannak.

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 variációt állít össze a színes bábukból, melyet tippnek nevezünk, é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:

  1. Elhagyjuk mind a kódból, mind a tippből azokat a bábukat, amelyekre fekete pálcikával válaszoltunk.
  2. 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. Ennek megfelelően a fekete és fehér pálcikák számából alkotott számpárt válasznak nevezzük. A válasz tehát egy titkos kódhoz és egy tipphez rendelt érték, amely a két bábu-variáció távolságát jellemzi (a 4 fekete és 0 fehér pálcika jelenti azt, hogy a tipp azonos a titkos kóddal).

Az alábbi jelöléseket és adatstruktúrákat használjuk a fenti fogalmakhoz kapcsolódóan: Megjegyzés: a fenti adatstruktúrák esetén a kód és a tipp egy-egy bábuja pontosan akkor vannak ugyanazon a helyen, ha a listabeli sorszámuk megegyezik.

Írjon mmind néven olyan CLPFD alapú Prolog-eljárást, amely a tippek és a hozzájuk tartozó válaszok egy halmazára előállítja a bemeneti adatoknak megfelelő titkos kódokat!

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 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 K titkos kód megfelel egy SL súgás-listának és egy Max maximális kódértéknek (színszámnak), ha

A megirandó 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 érdektelen. Értelemszerűen, ha a súgás-lista ellentmondást tartalmaz, azaz nincs megfelelő kód, akkor a Prolog-eljárás meghiúsul.

Természetesen az eljárás által előállítottott 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 négy szín használható:

Kód- és tippbábuk Válaszpálcikák
Titkos kód: ? ? ?
1. tipp és válasz: 1 1 1 B    
2. tipp és válasz: 1 2 2 W    
3. tipp és válasz: 3 1 3 B B  

2. ábra: Példajátszma

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 sorolnia (tetszőleges sorrendben).

A megírandó 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.

Példa

A 2. ábrán látható példa az alábbi módon adható meg a Prolog-eljárásnak, é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

A keretprogram

Programját keretprogram segítségével próbálhatja ki. A keretprogramot a specifikációs modulokkal és egy tesztsorral együtt innen letöltheti. A házi feladatok teszteléséhez és értékeléséhez ezekkel kompatibilis programokat fogunk használni.

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.
4         
1 1 1  1/0
1 2 2  0/1
3 1 3  2/0
3. ábra: A keretprogram egy lehetséges bemenete

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

[[3,1,4],[4,1,3]].
4. ábra: A keretprogram egy lehetséges kimenete

A kmmind.pl Prolog-keretprogram a következő eljárásokat exportálja exportálja:

% :- pred 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.
% :- pred 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.
% :- pred 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.
% :- pred 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.
% :- pred teljes_teszt(int::in).
A tests könyvtárban levő összes testXXXd.txt tesztállomány esetén: A fenti állománynevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl.
Ezt az eljárást Eisenberger András ültette át Prologra.

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 Prolog rendszert, és töltse be a keretprogramot. Példa:

SICStus 4.3.5 ...
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.

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 feladatát és működését! Kövesse a diákon használt szövegelrendezési konvenciókat! 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:

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.x.y, rendszerrel 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.