Deklaratív programozás

Bevezetés

A feladat a Mastermind játékhoz kapcsolódik, ezért kérjük, először olvassa el a jelen félév nagy házi feladatát.

Tekintsünk egy, a féléves nagy házi feladatban specifikált Mastermind-feladványt. Legyen Max a kódban megengedett maximális érték, H pedig a kód hossza, azaz elemeinek a száma. A feladvány megoldása során érdemes lehet nyilvántartani azt, hogy a titkos kód egyes pozícióin (a tábla oszlopaiban) milyen értékek lehetségesek még. Ennek az információnak a tárolására bevezetjük a közelítő megoldás adatstruktúrát.

Egy (Max, H) paraméterű Mastermind-feladvány esetén közelítő megoldásnak nevezünk egy olyan H hosszúságú listát, amelynek elemei az 1..Max intervallumba eső egész számokból képzett, szigorúan monoton növő listák. A közelítő megoldás i-edik eleme azokat az egész számokat tartalmazza, amelyek a titkos kód i-edik pozícióján szerepelhetnek. Tehát a közelítő megoldás elemei sorra az 1., 2., ..., H-adik pozíción lehetséges értékek halmazát írják le, rendezett lista formájában, ezért ezeket értéklistáknak nevezzük.

A lehető legáltalánosabb közelítő megoldás az a H hosszú lista, amelynek minden eleme az [1,2,...,Max] értéklista. Ez a közelítés nyilván nem tesz semmilyen megszorítást a megoldásra. A nagy házi feladat megoldása során viszont szűkíthetjük a közelítő megoldást, azaz bizonyos elemeket elhagyhatunk belőle a súgás-lista alapján. Ha például a súgás-listában van egy olyan tipp, pl. a [2,3,1], amelyhez 0 fekete válaszpálcika tartozik, akkor (a fehér válaszpálcikák számától függetlenül) biztosak lehetünk abban, hogy az első pozíción nincs 2-es, a második pozíción nincs 3-as, és a harmadik pozíción nincs 1-es érték. Tehát ezek az értékek feleslegesek, azaz elhagyhatók a közelítő megoldás adott pozícióján levő értéklistából (feltéve, hogy még benne vannak ebben a listában).

Egy közelítő megoldás érvényes, ha nincs benne üres lista.

Egy közelítő megoldás valójában titkos kódok egy halmazát határozza meg, nevezetesen azokat a kódokat, amelyeket úgy kapunk, hogy a közelítő megoldás minden egyes pozíciójáról egy elemet kiválasztunk. Például a [[3],[1,2,3,4],[1,2]] közelítő megoldás az alábbi nyolcelemű megoldáshalmazt határozza meg:

{ [3,1,1], [3,2,1], [3,3,1], [3,4,1],
  [3,1,2], [3,2,2], [3,3,2], [3,4,2] }.

Ebben a kis házi feladatban egy érvényes közelítő Mastermind-megoldást kell szűkíteni egy tipp és a hozzá tartozó fekete válaszpálcikák, azaz a pontos találatok száma alapján. Arról nincs információnk, hogy az adott tipphez hány fehér válaszpálcika tartozik, ezek száma tetszőleges lehet.

Először vizsgáljuk meg azt az esetet, amikor a [3,2,1] tipphez 1 fekete (és általunk nem ismert számú fehér) válaszpálcika tartozik. Mivel az első pozíción a kódban csak a 3 érték lehet, és a tippben is ez az érték szerepel ezen a helyen, ezért az egyetlen pontos találat az első pozíción lehet csak. Ebből következik, hogy a tippben a többi pozíción felsorolt értékek nem lehetnek pontos találatok. Így a 2. pozíción levő 2-es, és a 3. pozíción levő 1-es érték felesleges, azaz elhagyható a közelítő megoldásból. A kapott információ alapján tehát ezt a [[3],[1,3,4],[2]] közelítésre szűkíthetjük le.

Második – az előzőtől független – példánkban azt az információt kapjuk, hogy a [3,4,3] tippben 2 pontos találat van. Mivel az utolsó pozíción nem lehet pontos találat (a tippben levő 3-as szám nem szerepel a közelítő megoldás utolsó pozícióján levő értéklistában), ezért az első és a második pozíción lehetnek csak a pontos találatok, tehát a közelítő megoldást leszűkíthetjük a [[3],[4],[1,2]] listára (azaz az adott tipp-információ alapján a 2. pozíción levő 1-es, 2-es és 3-as értékek feleslegesekké válnak).

Harmadik – szintén az előzőektől független – példánkban azt az információt kapjuk, hogy a [2,2,3] tippben 2 pontos találat van. Ha összevetjük ezt a tippet a közelítő megoldással, akkor láthatjuk, hogy pontos találat nem lehetséges sem az első, sem a harmadik pozíción. Így legfeljebb egy pontos találat lehet, ami ellentmond a kapott információnak. Ezt az ellentmondást másképpen is kikövetkeztethetjük: a közelítő megoldás első pozícióján szereplő 3-as érték felesleges, hiszen ha az első helyen 3-as áll, akkor a [2,2,3] tipp esetén legfeljebb egy pontos találat lehet (a 2. pozíción). A 3-as értéket az első értéklistából elhagyva viszont egy üres listát kapunk, így az ehhez az új közelítő megoldáshoz tartozó megoldások halmaza üres.

A kis házi feladatnak jeleznie kell az ilyen jellegű ellentmondásokat, az alábbiakban részletezett (nyelvenként eltérő) módon.

A feladat

Egy adott, érvényes KM közelítő megoldásból – egy Tipp tipp és a hozzá tartozó pontos találatok P száma alapján – el kell hagyni az összes felesleges értéket. A KM lista i-edik pozícióján levő értéklista egy X eleme felesleges a Tipp-P párra nézve, ha abból, hogy a keresett titkos kód a KM-hez tartozik, és a Tipp tippre P pontos találatot ad, következik, hogy a titkos kód i-edik pozícióján nem szerepelhet az X érték. Megjegyezzük, hogy a feladat megoldásához elegendő a fenti három példában használt következtetési lépések megvalósítása, természetesen általánosított formában.

Ha egy olyan felesleges elemet kell elhagynunk, amely már csak önmagában szerepel az adott pozíción, akkor érvénytelen közelítő megoldáshoz jutunk. Könnyen belátható, hogy ebben az esetben a közelítő megoldásban szereplő összes elem felesleges, azaz az eredménynek csupa üres listából kell állnia. Ez az elfajuló eset azt jelzi, hogy ellentmondás van a közelítő megoldás és a tipp-információ között.

A másik véglet az, hogy az adott KM közelítő megoldás eleve nem tartalmaz felesleges értéket. Ilyenkor értelemszerűen a KM-ből egyetlen értéket sem kell elhagyni.

A feladat bemenetei:

• egy KM közelítő megoldás;
• egy Tipp-P pár, ahol Tipp egy tipp, P pedig a tippre vonatkozó fekete (pontos találatot jelző) válaszpálcikák száma. Itt P egy nemnegatív, a Tipp lista hosszánál kisebb vagy vele egyenlő egész szám (ezt a feltételt nem szükséges ellenőriznie).

A feladat kimenete az az UjKM érvényes közelítő megoldás, amely a KM-ből a Tipp-P párra nézve felesleges elemek elhagyásával áll elő. Ha az így előálló megoldás érvénytelen, akkor a Prolog eljárás hiúsuljon meg, az Erlang függvény pedig az invalid_approx atomot adja eredményül.

Kiegészítésül megadjuk a felesleges érték fogalmának egy másfajta, a fentivel ekvivalens meghatározását is.

A definíció megértését segíti az alábbi példa.

Legyen KM=[[3],[1,2,3,4],[1,2]]. A KM közelítő megoldáshoz tartozó titkos kódok listája a TKL=[[3,1,1], [3,2,1], [3,3,1], [3,4,1], [3,1,2], [3,2,2], [3,3,2], [3,4,2]] lista.

Nézzük a Tipp=[3,2,1] és P=1 esetet. A TKL lista elemei közül a Tipp tippre a következők adnak P darab pontos találatot: [3,1,2], [3,3,2], [3,4,2]. Felesleges tehát a 2-es érték a KM közelítő megoldás 2. értéklistájában, mert egyetlen P darab pontos találatot adó titkos kódban sem fordul elő a 2. pozícióban. Felesleges még a KM közelítő megoldás 3. értéklistájában az 1-es érték is.

Prolog-specifikációk

% :- type code          == list(int).
% :- type simple_hint ---> code-int.
% :- type approx        == list(list(int))

% :- pred szukitese(approx::in, simple_hint::in, approx::out).

% szukitese(KM0, Tipp_P, KM): A KM érvényes közelítő megoldás a KM0
% közelítésből a Tipp_P párra nézve felesleges értékek elhagyásával áll elő.

Erlang-specifikációk

-type code()            :: [integer()].
-type simple_hint()     :: {code(),integer()}.
-type approx()          :: [code()].
-type optional_approx() :: approx() | invalid_approx.

-spec khf3:szukitese(KM0::approx(), Tipp_P::simple_hint()) -> KM::optional_approx().

%% A KM közelítő megoldás a KM0 közelítésből a Tipp_P párra nézve felesleges értékek
%% elhagyásával áll elő. Ha nincs érvényes megoldás, KM értéke az invalid_approx atom.

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

Példák

Prolog

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

Erlang

1> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[3,2,1],1}).
[[3],[1,3,4],[2]]

2> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[3,4,3],2}).
[[3],[4],[1,2]]

3> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[2,2,3],2}).
invalid_approx

4> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[2,2,3],1}).
[[3],[2],[1,2]]

5> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[2,2,3],0}).
[[3],[1,3,4],[1,2]]

6> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[3,2,2],2}).
[[3],[1,2,3,4],[1,2]]

7> khf3:szukitese([[3],[1,2,3,4],[1,2]], {[3,2,1],2}).
[[3],[1,2,3,4],[1,2]]

8> khf3:szukitese([[1,2,4],[1,3,4],[1,2,3]], {[3,2,1],3}).
invalid_approx

9> khf3:szukitese([[1,2,4],[1,3,4],[1,2,3]], {[2,3,1],3}).
[[2],[3],[1]]

10> khf3:szukitese([[1,2,4],[1,3,4],[1,2,3]], {[2,3,1],0}).
[[1,4],[1,4],[2,3]]

11> khf3:szukitese([[1,2,4],[1,3,4],[1,2,3]], {[2,3,1],1}).
[[1,2,4],[1,3,4],[1,2,3]]

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 hármas számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf3.pl, ill. khf3.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.