6. kis házi feladat (Prolog): Összegfeltételek

1.0 változat — $LastChangedDate: 2021-10-13 22:22:50 +0200 (sze, 13 okt 2021) $
Kiadás: 2021-10-27
Beadási határidő a honlapon.

A feladat

Ez a leírás a Deklaratív programozás c. tárgyból kiadott 6., Prolog nyelven megirandó kis házi feladatot ismerteti, amely a Prolog nagy házi feladathoz kapcsolódik, de itt most önállóan, a nagy házi feladattól függetlenül ismertetjük.

A Prolog nagy házi feladatban egy logikai feladványt kell megoldani:

Egy téglalap alakú kert négyzet alakú, egyforma parcellákra van felosztva, egy n sorból és m oszlopból álló mátrixot alkotva. A parcellák többsége üres, egyes parcellákon egy-egy fa áll. Az üres parcellákon – egy-egy szomszédos fához kötve – sátrakat állíthatunk fel, az alábbi feltételekkel:

  1. egy parcellán legfeljebb egy fa vagy egy sátor lehet,
  2. minden fához pontosan egy sátrat kell kötni, és minden sátor pontosan egy fához van kötve,
  3. egy sátor akkor köthető egy fához, ha a parcellák, amelyeken állnak, oldalszomszédok,
  4. olyan parcellák, amelyeken sátrak állnak, sem oldal-, sem sarokszomszédok nem lehetnek, azaz egy sátor nem érinthet egyetlen másik sátrat sem,
  5. a mátrix egyes soraira és oszlopaira előírt összegfeltételeknek teljesülnie kell, ezeket két lista formájában adjuk meg:

A fák helyzetét a mátrixbeli sor- és oszlopszámukkal adjuk meg. Egy fához tartozó sátor helyét a fához viszonyított helyzetével (észak, kelet, dél, nyugat) jellemezzük.

Az irányokat az égtájak angol nevének kezdőbetűjével jelöljük, a w, n, e, s Prolog atomok rendre a west – nyugati, north – északi, east – keleti, ill. south – déli irányt jelölik.

Iránylistának nevezünk egy a fenti égtáj-atomokból álló ismétlődésmentes, lexikografikusan rendezett listát. Minden fához egy iránylistát rendelünk, amely a fához tartozó sátor lehetséges elhelyezéseit adja meg.

Ebben a feladatban iránylisták szűkítésével foglalkozunk, összegfeltételek alapján.

Az osszeg_szukites/4 predikátum

Írjon egy osszeg_szukites(Fs, Osszegfeltetel, ILs0, ILs) Prolog-eljárást, amely egy egyetlen sorra vagy oszlopra vonatkozó Osszegfeltetel alapján végez el egy esetleges iránylista szűkítést: az ILs0 iránylista-lista egyes elemeiből elhagy olyan irányokat, amelyek választása esetén a szóbanforgó összegfeltétel biztosan nem teljesül (és a szűkített iránylista-listát ILs-ben adja vissza).

Például, ha az összegfeltétel azt írja elő, hogy az 5. oszlop összege 0, akkor a 4. oszlopban levő fák iránylistáiból a keleti irányt, a 6. oszlopban levő fák iránylistáiból a nyugati irányt, az 5. oszlopban levő fák iránylistáiból a déli és északi irányt el lehet hagyni. Hasonló szűkítést lehet elvégezni, ha pl. az 5. oszlop előírt összege 3, de már van három olyan fa, amelyeknek egyelemű az iránylistája, és ezen iránylisták szerint mindhárom fa sátra az 5. oszlopba kerül.

Egy másik fajta szűkítési példa: a 3. sor előírt összege 2, viszont csak két olyan fa van, amelyek sátra a 3. sorba kerülhet. Ebben az esetben az adott két fának az iránylistájából el kell hagyni az összes olyan irányt, amely nem a 3. sorba mutat. (Vegyük észre, hogy ez nem feltétlenül jelenti azt, hogy a két fa iránylistája egyeleművé válik: ha pl. az egyik fa a 3. sorban van, akkor itt ki tudjuk zárni az északi és déli irányt, de a keleti és a nyugati meg kell maradjon, hiszen mindkettő a 3. sorba mutat.)

Az osszeg_szukites(Fs, Osszegfeltetel, ILs0, ILs) eljárásnak három bemenő és egy kimenő paramétere van.

  1. Az Fs bemenő paraméter a kertbeli fák helyét a fenti módon leíró f hosszúságú lista.
  2. Az Osszegfeltetel bemenő paraméter alakja sor(I,Db) vagy oszl(J,Db) (1 ≤ I ≤ n, 1 ≤ J ≤ m, Db ≥ 0), az első esetben az I-edik sorra, a második esetben a J-edik oszlopra vonatkozó Db darabszámú feltétel alapján kell a szűkítést elvégezni.
  3. Az ILs0 bemenő paraméter a kertbeli fák iránylistáit tartalmazó lista.
  4. Az ILs kimenő paraméter a kertbeli fák esetlegesen szűkített iránylistáit tartalmazó lista.

Az eljárás végrehajtásának pontos leírásához bevezetjük a következő elnevezéseket:

Az osszeg_szukites/4 eljárás bemenő paraméterei által leírt minden egyes állapotban meg lehet állapítani azoknak a fáknak a számát, amelyek biztosan ill. esetleg az adott sorba/oszlopba kerülnek; jelöljük ezeket a számokat rendre b-vel ill. e-vel.

A osszeg_szukites(Fs, Osszegfeltetel, ILs0, ILs) eljáráshívás végrehajtása:

A fentiekben jeleztük, hogy a iii. eset opcionális. Ez azt jelenti, hogy a khf6 feladat beadási és éles tesztelés során a iii. eset nem fordul majd elő. Azok a hallgatók, akik programjukat felkészítik a iii. eset kezelésére, egy másik, khf6plusz nevű feladatra is adják be ugyanazt a programot mint amit a "sima" khf6 feladatra beadtak. Ennek sikeres futása esetén egy további pluszpontot kapnak.

Példák

| ?- osszeg_szukites([6-6,9-7], oszl(7,2), [[n,s,w],[e,n,s,w]], ILs).      % b = 0, e = 1, Db = 2  (i)
ILs = [] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,2), [[e,n,s,w],[e,n,s,w]], ILs).    % b = 0, e = 2, Db = 2  (ii)
ILs = [[e],[n,s]] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,2), [[e,n,s,w],[n,s]], ILs).        % b = 1, e = 1, Db = 2  (ii)
ILs = [[e],[n,s]] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,1), [[e,n,s,w],[n,s]], ILs).        % b = 1, e = 1, Db = 1  (iii)
ILs = [[n,s,w],[n,s]] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,0), [[e,n,s,w],[n,s]], ILs).        % b = 1, e = 1, Db = 0  (iv)
ILs = [] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,1), [[e,n,s,w],[e,n,s,w]], ILs).    % b = 0, e = 2, Db = 1  (meghiúsulás)
no

A beadott programokat Linux környezetben SICStus Prolog 4 rendszerrel teszteljük.


A fenti eljárások paramétereinek típusát a következő – megjegyzésként megadott – Prolog-típusdefiníciók írják le.
% :- type parcMutató ==    int-int.          % egy parcella helyét meghatározó egészszám-pár
% :- type fák ==           list(parcMutató). % a fák helyeit tartalmazó lista
% :- type irány    --->    n                 % észak 
%                        ; e                 % kelet 
%                        ; s                 % dél   
%                        ; w.                % nyugat
% :- type iránylista ==    list(irany).      % egy adott fához rendelt sátor
                                             % lehetséges irányait megadó lista
% :- type iránylisták ==   list(iránylista). % az összes fa iránylistája

% :- type összegfeltétel
                      ==   sor(int, int)     % sor(I,Db): az I-edik sorbeli sátrak száma Db
                         ; oszl(int, int).   % oszl(J,Db): a J-edik oszlopbeli sátrak száma Db

% :- pred osszeg_szukites(fák::in,           % Fs
%                         összegfeltétel::in,% Osszegfeltetel
%                         iránylisták::in,   % ILs0
%                         iránylisták::out)  % ILs

 

 

Egy teljes példasor

Az alábbiakban egy olyan példasort adunk meg, amely egy egyszerű feladvány teljes megoldási folyamatát mutatja be. Ebben felhasználjuk az 5. kis házi feladatban definiált iranylistak/3 és sator_szukites/4 eljárásokat is.

Tekintsük az alábbi, három sorból és négy oszlopból álló, három fát (F1, F2 és F3) tartalmazó feladványt, amelyben a következő összegfeltételeknek kell teljesülniük: az első sorban 2 sátor van, az első oszlopban pedig 1

                 1
               +-------------+     
             2 | .  .  F1 .  |        Fs = [1-3,2-1,3-2]
               | F2 .  .  .  |     
               | .  F3 .  .  |
               +-------------+
  1. A kezdeti iránylista előállítása:
  2. | ?- Fs=[1-3,2-1,3-2], iranylistak(3-4, Fs, ILs0).     --->  ILs0 = [[e,s,w],[e,n,s],[e,n,w]]
    
                1
              +-------------+     
            2 | .  .  F1 .  |        Fs = [1-3,    2-1,    3-2]
              | F2 .  .  .  |      ILs0 = [[e,s,w],[e,n,s],[e,n,w]]
              | .  F3 .  .  |
              +-------------+
    
    
  3. Alkalmazzunk szűkítést az 1. sorbeli összegfeltételre (b = 0, e = 2, Db = 2, ii. eset):
  4. | ?- Fs=[1-3,2-1,3-2], ILs0 = [[e,s,w],[e,n,s],[e,n,w]], 
         osszeg_szukites(Fs, sor(1,2), ILs0, ILs1).            --->  ILs1 = [[e,w],[n],[e,n,w]]
    
                1
              +-------------+     
            2 | .  .  F1 .  |        Fs = [1-3,  2-1,3-2]
              | F2 .  .  .  |      ILs1 = [[e,w],[n],[e,n,w]]
              | .  F3 .  .  |
              +-------------+
    

    Az első sorban két sátrat kell elhelyeznünk, de csak két fának lehet sátra ebben a sorban (F3 sátra nem kerülhet az 1. sorba). Emiatt az F1 fa iránylistájából elhagyjuk a déli, az F2 iránylistájából pedig a keleti és déli irányt,

    Mivel az első sorra vonatkozó összegfeltétel szűkítést váltott ki, erre a feltételre a továbbiakban nem lesz szükség. Ennek jelzésére a további ábrákon az első sor elötti 2-es darabszámot már nem is jelenítjük meg

  5. Mivel az F2 fa iránylistája egyelemű, érdemes meghívni a sator_szukites eljárást:
  6. | ?- Fs=[1-3,2-1,3-2], ILs1 = [[e,w],[n],[e,n,w]],
         sator_szukites(Fs, 2, ILs1, ILs2).                    --->  ILs1 = [[e,w],[n],[e,n,w]]
    
                1
              +-------------+     
              | N  x  F1 .  |        Fs = [1-3,2-1,3-2]
              | F2 x  .  .  |      ILs2 = [[e],[n],[e,w]]
              | .  F3 .  .  |
              +-------------+
    

    Itt most az F1 és F3 fák iránylistái szűkültek, az előbbiből a nyugati, az utóbbiból az északi irányt hagytuk el.


  7. Az F1 fa iránylistája egyelemű lett, így érdemes újra meghívni a sator_szukites eljárást, az 1-es sorszámú fára:
  8. | ?- Fs=[1-3,2-1,3-2], ILs2 = [[e],[n],[e,w]],
         sator_szukites(Fs, 1, ILs2, ILs3).                    --->  ILs3 = [[e],[n],[e,w]]
    
                1
              +-------------+     
              | N  x  F1 E  |        Fs = [1-3,2-1,3-2]
              | F2 x  x  x  |      ILs3 = [[e],[n],[e,w]]
              | .  F3 .  .  |
              +-------------+
    

    Itt most nem történt szűkítés mert az F1 fa keleti irányú sátrának szomszédos mezőin amúgy sem lehetett volna sátor.

  9. Most szűkítsünk az 1. oszlopra vonatkozó összegfeltétel szerint (b = 1, e = 1, Db = 1, iii. eset):
  10. | ?- Fs=[1-3,2-1,3-2], ILs3 = [[e],[n],[e,w]],
         osszeg_szukites(Fs, oszl(1,1), ILs3, ILs4).           --->  ILs4 = [[e],[n],[e]]
    
                1
              +-------------+     
              | N  x  F1 E  |        Fs = [1-3,2-1,3-2]
              | F2 x  x  x  |      ILs4 = [[e],[n],[e]]
              | x  F3 .  .  |
              +-------------+
    
  11. Mivel az F3 fa iránylistája egyelemű, alkalmazzuk rá a sator_szukites eljárást
    | ?- Fs=[1-3,2-1,3-2], ILs4 = [[e],[n],[e]],
         sator_szukites(Fs, 3, ILs4, ILs5).                   --->  ILs5 = [[e],[n],[e]]
                
              +-------------+     
              | N  x  F1 E  |        Fs = [1-3,2-1,3-2]
              | F2 x  x  x  |      ILs5 = [[e],[n],[e]]
              | x  F3 E  x  |
              +-------------+
    

További szűkítést nem kaptunk, de az ellentmondásre utaló ILs5 = [] választ sem, így a kapott egyelemű iránylisták az eredeti feladat egyetlen megoldását mutatják: [e,n,e]


Tudnivalók a beadásról

DP Admin: dvacakrobotjaitoknakp@iit.bme.hu Vissza az elejére / Back to the top