Deklaratív programozás

2. kis házi feladat: Értékmátrix távolságinfók szerinti részleges helyessége

1.1 változat
Utolsó módosítás: 2020-10-09
Kiadás: 2020-10-07
A beadási határidők a weboldalon olvashatók.

A feladat

A feladat a félévi nagy házi feladatban specifikált Sudoku-feladvány és egy részlegesen kitöltött értékmátrix összevetése a távolságinfók szempontjából. Pontosítva: egy adott Sudoku-feladvány és egy részlegesen kitöltött értékmátrix esetén el kell dönteni, hogy az értékmátrix teljesíti-e a feladványban szereplő távolságinfók által támasztott feltételeket.

Egy m*m méretű részlegesen kitöltött értékmátrix egy olyan értékmátrix (lásd a nagy házi feladat kiírását), amelynek mezői 0 és m = k² közé eső egész számok. Egy részlegesen kitöltött értékmátrix tehát két dologban tér el a nagy házi feladatban specifikált Sudoku-megoldástól:

0 értékek is szerepelhetnek benne, amelyek a még ki nem töltött mezőknek felelnek meg. Ha tehát egy távolságinfó által kijelölt két mező közül legalább az egyik 0, akkor az adott távolságinfót teljesültnek tekintjük.
Az értékmátrix nem feltétlenül teljesíti a nagy házi feladatban a Sudoku-megoldással szemben támasztott elvárásokat, tehát előfordulhat benne számismétlés (a nem 0 értékek esetén is), és a feladványban előírt távolságinfók sem feltétlenül teljesülnek.

Összefoglalva: egy részlegesen kitöltött értékmátrix nem teljesíti egy adott Sudoku-feladvány távolságinfói által támasztott feltételeket, ha az értékmátrixban van két nem-nulla értékű oldalszomszédos mező, amely mezőpárra

a Sudoku-feladvány előír egy távolságinfót, de a két mező értékenek távolsága nem n; vagy

a Sudoku-feladvány nem ír elő távolságinfót, de a két mező értékének távolsága n;

ahol n a Sudoku-feladványban megadott távolságkonstans.

A kisházi megoldásában a Sudoku-feladványban szereplő száminfókat figyelmen kívül kell hagynia. Emellett annak sincs jelentősége, hogy az értékmátrix (a számismétlés szempontjából) ellentmondásmentes-e vagy sem.

Erlang-specifikációk

Írjon Erlang-függvényt khf2:n_away/2 néven egy Sudoku-tábla távolságinfók szerinti részleges helyességének a megállapítására.

-type sspec() :: {dist(), board()}.
-type dist()  :: integer().
-type field() :: [info()].
-type info()  :: s | w | integer().
-type board() :: [[field()]].

-type ssol()  :: [[integer()]].

-spec khf2:n_away(SSpec::sspec(), SSol::ssol()) -> B::boolean().
%% B igaz, ha az SSol részlegesen kitöltött értékmátrix teljesíti az SSpec
%% Sudoku-feladványban szereplő távolságinfók által támasztott feltételeket.

A programot tartalmazó modul attribútumai ezek legyenek:

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

A -author(...), ill. a -vsn(...) attribútum paraméterének (Erlang atomként) a saját nevét vagy email-címét, ill. a programverzió keltét adja meg.

Prolog-specifikációk

Írjon Prolog-eljárást n_away/2 néven egy Sudoku-tábla távolságinfók szerinti részleges helyességének a megállapítására.

% :- type sspec ---> s(dist, board).
% :- type dist  == int.
% :- type field == list(info).
% :- type info ---> s; w; int.
% :- type board == list(list(field)).

% :- type ssol == list(list(int)).

% :- pred n_away(sspec::in, ssol::in).
% n_away(SSpec, SSol): Az SSol részlegesen kitöltött értékmátrix teljesíti az SSpec
% Sudoku-feladványban szereplő távolságinfók által támasztott feltételeket.

Példák

Prolog

| ?- n_away(s(1, [[[s], [],    [],[s]],
                  [ [], [],    [], []],

                  [ [],[s], [s,w], []],
                  [[4], [],   [w], []]
                 ]
             ), 
            [[ 2, 4,  1, 3],
             [ 3, 1,  4, 2],
             [ 1, 3,  2, 4],
             [ 4, 2,  3, 1]]
           ).
yes

| ?- n_away(s(1, [[[s], [],    [],[s]],
                  [ [], [],    [], []],

                  [ [],[s], [s,w], []],
                  [[4], [],   [w], []]
                 ]
             ), 
            [[ 0, 2,  0, 2],
             [ 2, 0,  0, 0],
             [ 0, 0,  2, 0],
             [ 2, 0,  3, 0]]
           ).
yes

Ebben az értékmátrixban csak egy olyan oldalszomszédos mezőpár van, amely nem-nulla értékeket tartalmaz, mégpedig a 3. sor 3. mezője és az alatta levő mező. Mivel ezen két mező értékének távolsága 1, és a Sudoku-feladvány megfelelő mezője tartalmaz egy s távolságinfót, ezért az értékmátrix teljesíti a feladvány távolságinfói által támasztott feltételeket.

| ?- n_away(s(1, [[[s], [],    [],[s]],
                  [ [], [],    [], []],

                  [ [],[s], [s,w], []],
                  [[4], [],   [w], []]
                 ]
             ), 
            [[ 2, 4,  1, 3],
             [ 3, 1,  2, 4],
             [ 1, 3,  4, 2],
             [ 4, 2,  3, 1]]
           ).
no

Az utóbbi esetben azért kapunk nemleges választ, mert például a feladvány 1. sorának 3. oszlopában nem szerepel az s távolságinfó, ugyanakkor az értékmátrix ezen mezőjében az 1 érték, míg a tőle délre levőben a 2 érték szerepel, azaz a két szomszédos mező távolsága a feladványban szereplő 1 távolságkonstans.

Erlang

khf2:n_away({1, [[[s], [],    [],[s]],
                 [ [], [],    [], []],

                 [ [],[s], [s,w], []],
                 [[4], [],   [w], []]
                ]
            }, 
            [[ 2, 4,  1, 3],
             [ 3, 1,  4, 2],
             [ 1, 3,  2, 4],
             [ 4, 2,  3, 1]]
           ).
true

khf2:n_away({1, [[[s], [],    [],[s]],
                 [ [], [],    [], []],

                 [ [],[s], [s,w], []],
                 [[4], [],   [w], []]
                ]
            }, 
            [[ 0, 2,  0, 2],
             [ 2, 0,  0, 0],
             [ 0, 0,  2, 0],
             [ 2, 0,  3, 0]]
           ).
true

khf2:n_away({1, [[[s], [],    [],[s]],
                 [ [], [],    [], []],

                 [ [],[s], [s,w], []],
                 [[4], [],   [w], []]
                ]
            }, 
            [[ 2, 4,  1, 3],
             [ 3, 1,  2, 4],
             [ 1, 3,  4, 2],
             [ 4, 2,  3, 1]]
           ).
false

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.5.x, ill. az Erlang/OTP 20 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ámít.

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.