BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus alapszak
Nappali tagozat
2018/2019-es tanév, őszi félév

Deklaratív programozás

2. kis házi feladat: Egyszerűsített Mastermind játék

1.0 változat
Kiadás: 2018-10-05
A beadási határidők a főoldalon nézhetők meg.

A feladat

A feladat egy egyszerűsített Mastermind játék megoldása. Kérjük, először olvassa el a jelen félév nagy házi feladatát, mivel ez a kis házi feladat kapcsolódik hozzá.

Írjon tipp_kod néven olyan Erlang-függvényt, ill. Prolog-eljárást, amely egy tipp és a hozzá tartozó egyszerűsített válasz alapján megadja az ezeknek megfelelő titkos kódokat! A nagy házi feladat válaszával ellentétben az egyszerűsített válasz itt egyetlen szám, a tippre adott összes (fehér és fekete) válaszpálcika száma.

A feladat bemenetei:

Az Erlang-függvény, ill. Prolog-eljárás állítsa elő az összes olyan K kódot, amely a bemenő adatoknak megfelel, azaz

  1. a K kódlista hossza egyezzen meg az T tipplista hosszával;
  2. a K kódlista csak az 1..Max egész számokat tartalmazza;
  3. a K kódlista esetén a T tippre a Mastermind szabályai szerint adott összes válaszpálcika száma (vagyis az egyszerűsített válasz) S legyen.

Az Erlang-függvény eredménye az összes 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 pontosan egyszer; a felsorolás sorrendje itt is érdektelen. Értelemszerűen, ha nincs megfelelő kód, akkor az Erlang-függvény üres listával tér vissza, a Prolog-eljárás pedig meghiúsul.

A teljesség kedvéért a feladatot a fentitől eltérő módon, a Mastermind játéktől függetlenül is leírjuk. Ehhez felhasználjuk az 1. kis házi feladatban is ismertett zsák (multihalmaz) fogalmát, valamint a zsákokon értelmezett metszet műveletet. Az A és B zsákok metszete az a zsák, amely A és B közös elemeit tartalmazza, és amelyben egy elem multiplicitása az adott elem A és B-beli multiplicitása közül a kisebbik. Egy zsák elemszáma értelemszerűen az elemei multiplicitásának az összege.

A zsák fogalmának felhasználásával a Max és (T,S) bemenő adatokra vonatkozó 3. megfelelési feltételt a következőképpen írhatjuk le:

  1. a zsáknak tekintett T és K listák metszetének elemszáma S.

Prolog-specifikációk

Írjon Prolog-eljárást tipp_kod/3 néven egy adott Max paraméternek és egy Tipp-S párnak megfelelő kódok előállítására.
% :- type code          == list(int).
% :- type simple_hint ---> code-int.

% :- pred tipp_kod(int::in, simple_hint::in, code::out).

% tipp_kod(Max, Tipp-S, Kod): Kod a Max paraméternek és a Tipp-S párnak megfelel.

Erlang-specifikációk

Írjon Erlang-függvényt tipp_kod/2 néven egy adott Max paraméternek és egy {Tipp,S} párnak megfelelő kódok előállítására.
-type code()        :: [integer()].
-type simple_hint() :: {code(),integer()}.

-spec khf2:tipp_kod(Max::integer(), Tipp_S::simple_hint()) -> Kodok::[code()].

%% A Max paraméternek és a Tipp_S párnak megfelelő kódok listája Kodok.
A programot tartalmazó modul attribútumai ezek legyenek ('email@unit.org.hu' helyébe a saját email-címét, 'year-mm-dd' helyébe a beadás napját írja be, exportálni csak a 'tipp_kod/2' függvényt exportálja, a '-compile(export_all)' attribútumot kommentezze ki vagy törölje):
-module(khf2).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([tipp_kod/2]).
%-compile(export_all).

Példák

Prolog

| ?- tipp_kod(3, [1,2]-0, K).
K = [3,3] ? ;
no
| ?- tipp_kod(4, [1,2]-0, K).
K = [3,3] ? ;
K = [3,4] ? ;
K = [4,3] ? ;
K = [4,4] ? ;
no
| ?- tipp_kod(2, [1,2]-0, K).
no
| ?- tipp_kod(3, [1,2]-1, K).
K = [1,1] ? ;
K = [1,3] ? ;
K = [2,2] ? ;
K = [2,3] ? ;
K = [3,1] ? ;
K = [3,2] ? ;
no
| ?- tipp_kod(3, [1,2]-2, K).
K = [1,2] ? ;
K = [2,1] ? ;
no
| ?- tipp_kod(2, [1,2,2]-2, K).
K = [1,1,2] ? ;
K = [1,2,1] ? ;
K = [2,1,1] ? ;
K = [2,2,2] ? ;
no

Erlang

1> khf2:tipp_kod(3, {[1,2],0}).
[[3,3]]
2> khf2:tipp_kod(4, {[1,2],0}).
[[3,3],[3,4],[4,3],[4,4]]
3> khf2:tipp_kod(2, {[1,2],0}).
[]
4> khf2:tipp_kod(3, {[1,2],1}).
[[1,1],[1,3],[2,2],[2,3],[3,1],[3,2]]
5> khf2:tipp_kod(3, {[1,2],2}).
[[1,2],[2,1]]
6> khf2:tipp_kod(2, {[1,2,2],2}).
[[1,1,2],[1,2,1],[2,1,1],[2,2,2]]

Tudnivalók a beadásról

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.4, ill. az Erlang/OTP R16A rendszerekkel teszteljük.

Ennek a kis házi feladatnak a beadása ugyan nem kötelező, azonban a félévközi követelmények teljesítéséhez a félév során legalább három kisházifeladat-megoldást – közülük legalább egyet Prolog és legalább egyet Erlang nyelven – sikeresen be kell adni. Sikeres az a megoldás, amelyik az összes tesztesetre helyes választ ad. Ha ezt a kis házi feladatot mindkét nyelven sikeresen beadja, az természetesen két megoldásnak számit.

A programot az Elektronikus Tanársegéd (ETS) segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a kettes számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf2.pl, ill. khf2.erl néven tárolja el és hivatkozik rá. (A feltöltendő állomány neve tetszőleges lehet, az ETS átnevezi.)

Az osztályzat megállapításakor a határidőre beadott, minden tesztesetre helyesen működő feladatmegoldásért plusz 1-1 pont jár.

DP Admin $LastChangedDate: 2018-10-18 12:58:28 +0200 (Thu, 18 Oct 2018) $ Vissza az elejére / Back to the top