Deklaratív programozás

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:

• a Mastermind feladványban szereplő színek száma (a Mastermind játék Max paramétere);
• egy (T,S) pár, ahol T egy tipp, S pedig a tippre vonatkozó (fehér és fekete) válaszpálcikák összesített száma. Itt S egy nem-negatív, a T lista hosszánál kisebb vagy vele egyenlő egész szám (ezt a feltételt nem szükséges ellenőriznie).

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:

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

Prolog-specifikációk

% :- 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

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

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

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.