BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2000/2001-es tanév

Deklaratív programozás

Házi feladat, 1.3. változat

Sátrak

Ez a leírás a Deklaratív programozás c. tárgyból kiadott féléves házi feladatot ismerteti.

A feladvány

Egy téglalap alakú kert négyzet alakú, egyforma parcellákra van felosztva. Kezdetben 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,
  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.
Összesen n*m parcella van a kertben (hosszában n, széltében m). Ismerjük a fák pontos helyét, továbbá a sátrak számát soronként és oszloponként. A fát, amelyhez a sátor hozzá van kötve, a sátor saját fájának nevezzük. Meghatározandó a sátrak helyzete a saját fájukhoz képest. Példa:


      1 --------> m
      1  0  2  0  2 
1   +--+--+--+--+--+
  1 |  |F |  |  |  |
|   +--+--+--+--+--+
| 1 |  |  |  |  |  |
|   +--+--+--+--+--+
| 0 |  |  |F |  |F |
|   +--+--+--+--+--+
v 3 |  |  |  |  |  |
    +--+--+--+--+--+
n 0 |F |  |  |  |F |
    +--+--+--+--+--+
            


    1  0  2  0  2
  +--+--+--+--+--+
1 |  | F-S |  |  |
  +--+--+--+--+--+
1 |  |  |  |  |S |
  +--+--+--+--+|-+
0 |  |  |F |  |F |
  +--+--+|-+--+--+
3 |S |  |S |  |S |
  +|-+--+--+--+|-+
0 |F |  |  |  |F |
  +--+--+--+--+--+
1. ábra. Egy feladvány (n=5, m=5)             2. ábra. A feladvány egy megoldása

Előfordulhat, hogy egyes sorokban, ill. oszlopokban nem írjuk elő a sátrak számát: ezt a megfelelő sor, ill. oszlop elején álló negatív szám jelzi. Példa:


      1 --------> m
      1  0 -1  0  2 
1   +--+--+--+--+--+
  1 |  |F |  |  |  |
|   +--+--+--+--+--+
| 1 |  |  |  |  |  |
|   +--+--+--+--+--+
|-1 |  |  |F |  |F |
|   +--+--+--+--+--+
v 3 |  |  |  |  |  |
    +--+--+--+--+--+
n 0 |F |  |  |  |F |
    +--+--+--+--+--+

3. ábra. Negatív szám jelzi, ha nem írjuk elő a sátrak számát egy-egy sorban vagy oszlopban

A megoldandó feladat

Írjon satrak néven olyan Prolog-eljárást, ill. SML-függvényt, amely egy feladvány összes megoldását előállítja!

A Prolog-eljárásnak két paramétere van. Első (bemenő) paramétere a feladványt, második (kimenő) paramétere a megoldást írja le. Az eljárásnak a visszalépések során minden megoldást pontosan egyszer kell kiadnia. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.

A Prolog-eljárás bemenő paramétere egy 

satrak(Ss, Os, Fs)
felépítésű struktúra, ahol

Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere: 

satrak([1,1,0,3,0], [1,0,2,0,2], [1-2,3-3,3-5,5-1,5-5])
ahol az (i,j) párt i-j alakú Prolog-struktúrával írjuk le.

A Prolog-eljárás kimenő paramétere egy olyan lista, amely - a fák Fs-beli megadási sorrendjét követve - a sátrak saját fájukhoz viszonyított helyzetét írja le. Egy sátor helyzetét a megfelelő égtájat jelölő betűvel adjuk meg:

w (west) - a sátor a saját fájától nyugatra áll, n (north) - a sátor a saját fájától északra áll,
e (east) - a sátor a saját fájától keletre áll, s (south) - a sátor a saját fájától délre áll.

A 2. ábrán látható megoldást írja le például az alábbi lista: 

[e,s,n,n,n]
Az SML-függvény paramétere egy (Ss, Os, Fs) hármas, ahol Ss, Os és Fs jelentése azonos a Prolog-eljárásnál leírtakkal.

Az 1. ábrán bemutatott feladvány esetén például az SML-függvény paramétere: 

([1,1,0,3,0], [1,0,2,0,2], [(1,2),(3,3),(3,5),(5,1),(5,5)])
Az SML-függvény eredménye egy olyan lista, amely a feladvány összes megoldását tartalmazza, mégpedig minden megoldást pontosan egyszer. Ha a feladatnak nincs megoldása, az eredmény az üres lista.

A 2. ábrán látható megoldást írja le például az alábbi listák listája: 

[[e,s,n,n,n]]

A megírandó függvény, ill. eljárás specifikációja

A satrak függvény paraméterének és eredményének típusát a következő SML-típusdefiníciók írják le. 

structure TSatrak =
struct
  (* a bemenő adatokat leíró típusok *)
      	(* a sátrak száma soronként és oszloponként; negatív szám jelzi,
           ha nincs megkötve a sátrak száma egy-egy sorban vagy oszlopban *)
      type sSzS   = int list
      type sSzO   = int list
      	(* egy parcella sor- és oszlopszáma *)
      type parc   = int * int
      	(* a feladványt leíró hármas *)
      type fLeiro = sSzS * sSzO * parc list
  (* a kimenő adatokat leíró típusok *)
      	(* irány; n - észak, e - kelet, s - dél, w - nyugat *)
      datatype irany = n | e | s | w
      	(* a sátrak saját fájukhoz viszonyított helyzetének listája *)
      type sHelyek  = irany list
end

signature Satrak =
sig
  (* satrak(Ss, Os, Fs) = a kertben a sátrak saját Fs-beli fájukhoz
       viszonyított összes lehetséges helyzetét leíró listák listája
  *)
  val satrak : TSatrak.fLeiro -> TSatrak.sHelyek list
end
A satrak/2 Prolog-eljárás paramétereinek típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le. 
% :- type fLeiro  ---> satrak(sSzS, sSzO, list(parc)).
% :- type sSzS    == list(int).
% :- type sSzO    == list(int).
% :- type parc    == int-int.
% :- type irany   ---> n    % észak
%                 ;    e    % kelet
%                 ;    s    % dél
%                 ;    w.   % nyugat
% :- type sHelyek   == list(irany).
% :- pred satrak(fLeiro::in, sHelyek::out).

A keretprogram

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a specifikációs modulokkal és egy, a beadáskor használthoz hasonló tesztsorral együtt innen letöltheti (egyelőre csak 7 egyszerűbb tesztesetet adunk közre, hamarosan bővítjük a készletet). A házi feladatok teszteléséhez és értékeléséhez ezekkel kompatíbilis programokat fogunk használni.

A keretprogram bemenete egy olyan szöveges állomány, amelynek soraiban a feladványmátrix sorai vannak; az üres parcellákat "-" jel jelöli. 

  1 0 2 0 2
1 - F - - -
1 - - - - -
0 - - F - F
3 - - - - -
0 F - - - F
4. ábra. A bemenő állomány tartalma az 1. ábrán látható feladvány esetén

A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szöveges állomány.

Az SML-keretprogram három függvényt exportál: 

signature KSatrak =
sig
    val satrak_be : string -> TSatrak.fLeiro
    val satrak_ki : string * TSatrak.sHelyek list * TSatrak.fLeiro -> unit
    val megold    : string * string -> string
end
satrak_be f
Az f szöveges állományból beolvasott adatokból képzett feladványleíró.
satrak_ki(m, mss, fl)
Az mss megoldáslista és az fl feladványleíró alapján az összes megoldást kiírja az m szöveges állományba.
megold(f, m)
Beolvas egy feladványt az f szöveges állományból és kiírja az összes megoldást az m szöveges állományba. Ehhez természetesen szüksége van a Satrak.satrak függvényre. Eredménye az f nevet, a megoldások számát és a futási időt mp-ben tartalmazó füzér.
A bemenetet, ill. a kimenetet a terminálra irányíthatjuk Unix alatt a /dev/stdin, ill. a /dev/stdout, MS-DOS alatt mindkét esetben a con állománynév megadásával.

A Prolog-keretprogram három eljárást exportál:

satrak_be(file::in, fLeiro::out)
A megnevezett szöveges állományból beolvassa a feladványleírót, és visszaadja a második argumentumban.
satrak_ki(file::in, sHelyek::in, fLeiro::in)
A megnevezett szöveges állományba kiírja az adott megoldást a sátorhelyek és a feladványleíró alapján.
megold(file::in, file::in)
Beolvas egy feladványleírót az első paraméterként kapott állományból, és kiírja az ahhoz tartozó összes megoldást a második paraméterben megadott állományba. Ehhez természetesen szüksége van a satrak/2 eljárásra.

A keretprogram felhasználja a file típust: 

% :- type file == atom.
A file típusú paraméterben a user atomot megadva a terminálról vihetünk be, ill. a terminálra irathatunk ki adatokat. Egyébként a megadott nevű állományba írunk, ill. állományból olvasunk.

Dokumentációs követelmények

Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások ill. függvények feladatát és működését! Írjon minden eljáráshoz és függvényhez fejkommentet!

A két programhoz közös dokumentációt készítsen - vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:

Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.

A dokumentációt elektronikus formában adja be, HTML, esetleg ASCII formátumban.

Egyéb követelmények és tudnivalók

A programokat és az elektronikus dokumentációt tömörítve, elektronikus levélben kell elküldeni egy bash szkript szkript segítségével.

A programok és az elektronikus dokumentáció beadási határideje a létraversenyen való részvételhez 2001. május 14-e, hétfő 24h. A házi feladatok végső beadási határideje 2001. május 28-án hétfőn 24h-kor van. További feltétel, hogy a megoldást a vizsga előtt öt nappal éjfélig be kell adni (azaz a május 23-án vizsgázóknak 18-án, a május 29-én vizsgázóknak 24-én éjfélig).

A vizsgaosztályzatban a határidőre beadott nagyfeladat eredményét 15%-os súllyal vesszük figyelembe.

A hibátlan nagyfeladatot 2001. május 14-éig beadók SML- és/vagy Prolog-programjukkal létraversenyben vesznek részt. A leggyorsabban futó SML-, ill. Prolog-programokra - helyezési számuktól függően - külön-külön 30 és 2 közötti pluszpont kapható, a féléves összpontszámhoz a kapott összegnek a negyedét adjuk hozzá.

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (linux) alatt is működniük kell.

dp@inf.bme.hu
Utolsó módosítás: 2001. 04. 05.