| BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak |
Nappali tagozat
2000/2001. tanév
|
A passzív játékos feladata, hogy a színes bábukból tetszőleges kombinációt állítson össze, e titkos kódot a másik játékos által nem látható lyukakba helyezze, és a valóságnak megfelelően válaszoljon a kérdéseire. (Azonos színű bábukból több is lehet a kódban.)
Az aktív játékos feladata a titkos kód kitalálása. 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álaszbábut 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álaszbábut rak a táblára, ahány egyforma színű bábu van a tippben és a kódban különböző helyen.
A válaszról nem lehet tudni, hogy pontosan mely bábukra vonatkozik. Az aktív játékos célja természetesen az, hogy a lehető legkevesebb lépésben kitalálja a kódot.
A játék aktív játékosként itt kipróbálható.
Írjon mmind néven olyan SML függvényt, ill. Prolog
eljárást, amely tippek és a hozzájuk tartozó válaszok egy halmazához
megadja a lehetséges titkos kódokat! A kódokat pozitív egész számok
listájaként ábrázoljuk.
A függvénynek, illetve az eljárásnak 2 bemenő paramétere van. Az első egy szám, amely megadja, hogy a kódban maximálisan mekkora érték fordulhat elő. A második egy nemüres lista, a súgás-lista, amelynek elemei a játék egy fordulójának 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álaszbábuk száma). Egy titkos kódot lehetségesnek nevezünk egy adott bemenetre nézve, ha nem tartalmaz a megadott maximumnál nagyobb kódot és a súgás-lista minden elemének megfelel, azaz a megadott kód-tippre a megadott választ eredményezi.
Az SML függvény kimenete az összes lehetséges kód (ismétlődésmentes) listája. A Prolog eljárás kimenete egyetlen kód, azonban visszalépések során az összes lehetséges kódot elő kell állítania, mégpedig mindegyiket egyszer. Lehetetlen kódot nem szabad előállítania.
Természetesen a függvény, ill. az eljárás által kiszámított kódok hossza azonos kell legyen a bemenő paraméterben szereplő kódok hosszával.
Ha a bemenetben különböző hosszúságú kódok szerepelnek, akkor a Prolog eljárás hiúsuljon meg, az SML függvény adjon vissza üres listát!
mmind függvény paraméterének és eredményének típusát a
következő SML-típusdefiníciók írják le.
structure TMMind =
struct
type code = int list
type blacks = int
type whites = int
type answer = blacks * whites
type hint = code * answer
end
signature MMind =
sig
(* mmind (m, l) = az m maximális kódérték és l súgás-lista
esetén lehetséges kódok listája *)
val mmind : int * TMMind.hint list -> TMMind.code list
end
Az mmind/3 eljárás paramétereinek 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).
A keretprogram bemenete egy olyan szöveges állomány, amelynek első sora a
kódban felhasználható legnagyobb számot tartalmazza, az összes többi sora
pedig egy tippet és a rá adott választ tartalmazza. A tipp nemnegatív
egészek üres karakterekkel elválasztott sorozata. Ezt követi a válasz, amely
a fekete és a fehér válaszbábuk száma `/' jellel elválasztva.
Az 1. ábra egy lehetséges bemeneti állomány tartalmát mutatja.
4 1 1 1 1/0 1 2 2 0/1 3 1 3 2/0 |
| 1. ábra: A keretprogram egy lehetséges bemenete |
A fenti példa esetén a lehetséges megoldások: [3,1,4] és
[4,1,3]. (Ezeket a Prolog eljárásnak fel kell sorolnia, az
SML függvénynek listába gyűjtve vissza kell adnia. A sorrend természetesen
tetszőleges.)
Az SML-keretprogram három függvényt exportál:
signature FMMind =
sig
val mmind_in : string -> (int * TMMind.hint list)
val mmind_out : string * TMMind.code list -> unit
val solve : string * string -> string
end
mmind_in f
f szöveges állományból beolvasott maximális
kódértéket és a súgás-listát adja eredményül.
mmind_out (m, cs)
cs kódlistát kiírja az m szöveges
állományba.
solve (f, m)
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 az MMind.mmind függvényre.
Eredménye a feladvány nevét, a kód hosszát és a
futási időt mp-ben tartalmazó füzér.
/dev/stdin, ill. a /dev/stdout, MS-DOS alatt
mindkét esetben a con állománynév megadásával.
A Prolog-keretprogram három eljárást exportál:
mmind_in(file::in, int::out, list(hint)::out)
mmind_out(file::in, list(code)::in)
solve(file::in, file::in)
mmind/3 eljárásra.
A keretprogram felhasználja a file típust:
% :- type file == atom.
file típusú argumentumokban a user atomot
megadva a terminálról vihetünk be, ill. a terminálra irathatunk ki
adatokat. Egyébként a megadott nevű állományba írunk, ill. állományból
olvasunk.
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:
A dokumentációt elektronikus formában adja be, HTML, esetleg ASCII formátumban.
A vizsgaosztályzatban a határidőre beadott nagyfeladat eredményét 15%-os súllyal vesszük figyelembe.
A hibátlan nagyfeladatot határidőre beadók SML-, ill. Prolog-programjukkal 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 30 és 2 közötti pluszpont kapható, a féléves összpontszámhoz a kapott összegnek a negyedét adjuk hozzá. A létraversenyről az esetleges további tudnivalókat a tárgy honlapján tesszük közzé.
A programoknak mind Unix, mind Linux operációs rendszer alatt működniük kell a tantárgy honlapján megadott rendszereket használva.