BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2002/2003-as tanév, tavaszi félév

Deklaratív programozás

Házi feladat, 1.4 változat

Kígyó

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

Adott egy n*m mezőből álló, téglalap alakú tábla, amelynek egyes mezőin 0 és 7 közötti számok szerepelnek. A feladat az, hogy egy olyan kígyót rajzoljunk a táblára, amelyre az alábbi feltételek teljesülnek:
  1. A kígyó az éleik mentén érintkező mezőkből áll, amelyek az előre meghatározott kezdőpontot és végpontot kötik össze.
  2. A számozott mezők nyolc él- és sarokszomszédja közül pontosan annyi mezőnek kell a kígyóhoz tartoznia, amekkora szám szerepel az adott mezőn. (Ez a feltétel hasonló a közismert aknakereső feladványban szereplő feltételhez.)
  3. Számmal jelzett mezőn nem lehet kígyó.
  4. A kígyó nem keresztezheti önmagát. A kígyóhoz tartozó, nem szomszédos mezők legfeljebb a sarkukkal érinthetik egymást, az éleik nem lehetnek közösek. (Tehát a kígyó nem teheti meg, hogy például megy felfele 2 mezőt, azután 1-et jobbra, majd 1-et lefele.)
  5. A kezdő- és a végpont is csak a sarkukkal érintkezhetnek, emiatt nem szerepelhet 8-as a mezőkben.
Egy feladványnak természetesen több megoldása is lehet.

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. (K: Kezdőpont, V: Végpont, @: a kígyó további mezői.) 

  +---+---+---+---+---+
  | K |   | V |   |   |
  +---+---+---+---+---+
  |   |   | 5 |   |   |
  +---+---+---+---+---+
  | 4 |   |   |   |   |
  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+
  |   |   |   | 3 |   |
  +---+---+---+---+---+
            
  +---+---+---+---+---+
  | K |   | V | @ |   |
  +---+---+---+---+---+
  | @ | @ | 5 | @ | @ |
  +---+---+---+---+---+
  | 4 | @ |   |   | @ |
  +---+---+---+---+---+
  |   | @ | @ | @ | @ |
  +---+---+---+---+---+
  |   |   |   | 3 |   |
  +---+---+---+---+---+
1. ábra. Egy feladvány (n=5, m=5)             2. ábra. A feladvány megoldása

A megoldandó feladat

Írjon kigyo 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 

    k(S-O,KS-KO,VS-VO,RefPL)
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: 

    k(5-5, 1-1, 1-3, [p(2,3,5),p(3,1,4),p(5,4,3)])

A Prolog-eljárás kimenő paramétere a kezdőponttól a végpontig vezető mezők koordinátáinak a listája (a kezdő és a végpontokat is beleértve).

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

    [1-1,2-1,2-2,3-2,4-2,4-3,4-4,4-5,3-5,2-5,2-4,1-4,1-3]
Az SML-függvény paramétere egy ((S,O), (KS,KO), (VS,VO), RefPL) négyes, ahol S, O, KS, KO, VS és VO jelentése azonos a Prolog-eljárásnál leírtakkal, míg RefPL egy lista, amelynek elemei (Sor,Oszlop,Érték) alakú hármasok, amelyek jelentése szintén 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: 

    ((5,5), (1,1), (1,3), [(2,3,5),(3,1,4),(5,4,3)])
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. Egy megoldást a koordinátapárok (kettesek) listájaként kell megadni, a Prolog-megoldáshoz hasonlóan.

A 2. ábrán látható megoldást írja le például az alábbi (egyelemű) megoldás-lista: 

    [[(1,1),(2,1),(2,2),(3,2),(4,2),(4,3),(4,4),(4,5),(3,5),(2,5),(2,4),(1,4), (1,3)]]

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

A kigyo/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 kigyotabla      ---> k(meret, pont, pont, list(ref_pont)). 
% :- type ref_pont        ---> p(sor, oszlop, ertek). 
% :- type sor               == integer. 
% :- type oszlop            == integer. 
% :- type ertek             == integer. 
% :- type pont            ---> sor-oszlop.
% :- type meret           ---> sor-oszlop.
% :- type kigyovonal        == list(pont).

% :- pred kigyo(kigyotabla::in, kigyovonal::out).
 A kigyo/2 eljárás első, kigyotabla típusú paramétere mindenképpen kielégíti az alábbi feltételt: 
helyes_feladvany(k(Meret,KPont,VPont,RefPL)) :-
	% a tábla mérete helyes:
	helyes_pont(Meret,inf-inf),
	% a kezdő és a végpont helyesek:
	helyes_pont(KPont, Meret),
	helyes_pont(VPont, Meret),
	% a kezdő és a végpont nem lehet ugyanaz a pont,
	% és nem lehetnek élszomszédosak sem,
	% azaz távolságuk nagyobb 1-nél
	tavolsaga(KPont, VPont, Tav), Tav > 1,
        % nincs nem helyes eleme a RefPL listának:
 	\+ (   member(Ref, RefPL),  
	       \+ helyes_referencia(Ref, Meret) 
	   ),   
	% a RefPL lista lexikografikusan rendezett:
 	sort(RefPL, RefPL), 
	% A RefPL lista minden eleme különböző (Sor,Oszlop)
  	% koordinátára vonatkozik (a rendezettség miatt elegendő ezt a
        % szomszédos elemekre kikötni):
 	\+ append(_, [i(S,O,_),i(S,O,_)|_], RefPL). 
 
helyes_pont(S-O, MaxS-MaxO) :-
	integer(S), S >=1, S =< MaxS,
	integer(O), O >=1, O =< MaxO.

tavolsaga(S1-O1, S2-O2, T) :-
	T is sqrt( (S1-S2)**2 + (O1-O2)**2 ).

helyes_referencia(p(Sor,Oszlop,Ertek), Meret) :-
	helyes_pont(Sor-Oszlop, Meret),
	0 =< Ertek, Ertek =< 7.
A Prolog megoldásában tehát feltételezheti, hogy a bemenő argumentumra a helyes_feladvany/1 eljárás sikeresen lefut (csak ilyen adattal teszteljük majd a programot).

A kigyo 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 TKigyo = 
struct 
      type sor        = int (* 0 < sor         *)
      type oszlop     = int (* 0 < oszlop      *)
      type ertek      = int (* 0 <= ertek <= 7 *)
      type pont       = sor * oszlop
      type meret      = sor * oszlop
      type refpont    = sor * oszlop * ertek
      type kigyotabla = meret * pont * pont * refpont list
      type kigyovonal = pont list
end

signature Kigyo = 
sig 
  val kigyo : TKigyo.kigyotabla -> TKigyo.kigyovonal list
end
A Kigyo.kigyo függvény TKigyo.kigyotabla típusú paramétere mindenképpen kielégíti az alábbi feltételt: 
app load ["Listsort", "Math"];

fun helyes_feladvany (Meret, Kpont, Vpont, RefPL) = 
    let 
	val (MaxS, MaxO) = Meret 
	fun helyes_pont (Sor, Oszlop) = 
              1 <= Sor andalso 1 <= Oszlop andalso
              Sor <= MaxS andalso Oszlop <= MaxO
	fun helyes_ref_pont (Sor, Oszlop, Ertek)  =
              helyes_pont (Sor, Oszlop) andalso
	      0 <= Ertek andalso Ertek <= 7;
	fun tavolsag ((S1, O1), (S2, O2)) = 
	      Math.sqrt(Math.pow(real(S1)-real(S2),2.0)+
                        Math.pow(real(O1)-real(O2),2.0))

	fun lexikografikusan_hasonlit ((x1,y1,_), (x2,y2,_)) = 
	      if      x1 < x2 orelse x1 = x2 andalso y1 < y2 then LESS
	      else if x1 > x2 orelse x1 = x2 andalso y1 > y2 then GREATER
	      else EQUAL 
	fun szomszedok_kulonbozok (rp1::(rps as rp2::_)) = 
	      lexikografikusan_hasonlit (rp1, rp2) <> EQUAL
	      andalso szomszedok_kulonbozok rps
	  | szomszedok_kulonbozok _ = true
    in 
          (* a tábla méretezése, a kezdő- és végpontok megadása helyes: *)
	1 <= MaxS andalso 1 <= MaxO andalso
	helyes_pont Kpont andalso
	helyes_pont Vpont andalso
	  (* a kezdő- és végpont is csak a sarkukkal érintkezhetnek: *)
    	tavolsag(Kpont, Vpont) > 1.0 andalso
          (* a RefPL lista minden eleme helyes: *) 
        (List.all (fn x => x) (map helyes_ref_pont RefPL)) andalso 
          (* a RefPL lista lexikografikusan rendezett: *) 
	Listsort.sorted lexikografikusan_hasonlit RefPL andalso 
	  (* A RefPL lista minden eleme különböző (Sor,Oszlop)  
	     koordinátára vonatkozik (a rendezettség miatt elegendő 
             ezt a szomszédos elemekre kikötni): *) 
	szomszedok_kulonbozok RefPL 
end
Az SML megoldásában tehát feltételezheti, hogy a bemenő argumentumra a helyes_feladvany predikátum igazat ad eredményül (csak ilyen adattal teszteljük majd a programot).

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 letöltheti innen. 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 első sorában a sor- és oszlopszám szerepel, második sorában a kezdősor és kezdőoszlop, harmadik sorában a végsor és végoszlop. Az ezt követő sorok mindegyikében három szám áll, amelyek az adott referenciapont sor- és oszlopszámát, valamint értékét adják meg. Ezekre a számokra a már fent említett korlátok vonatkoznak, tehát a sor- és oszlopszámok a táblán belüli mezőt azonosítanak, a referenciapont értéke pedig 0 és 7 közé esik (ld. 3. ábra, vö. 1. ábra).

 5 5
 1 1
 1 3
 2 3 5
 3 1 4
 5 4 3
3. á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.

A Prolog-keretprogram

A Prolog-keretprogram öt eljárást exportál:
helyes_feladvany(kigyotabla::in)
A fent ismertetett feladványellenőrző eljárás.
kigyó_be(file::in, kigyotabla::out)
A megnevezett szöveges állományból beolvassa a kígyótáblát, és visszaadja a második argumentumban.
kigyo_ki(file::in, kigyotabla::in, kigyovonal::in)
A megnevezett szöveges állományba kiírja az adott megoldást.
megold(file::in, file::in)
Beolvas egy feladványt 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 kigyo/2 eljárásra.
stopper(file::in, file::in)
Mint megold/2, de a futás végén kiírja a futási időt is.

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.

Használat: a saját programját a kigyo.pl nevű állományba tegye, különben a keretprogram nem találja meg. Ezután futtassa a SICStus interpretert, és töltse be a keretprogramot: 

SICStus 3.10.0 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002
Licensed to BUTE DP course
| ?- [kkigyo].
% consulting /home/david/uni/dp/03s/nhf/kkigyo.pl...
%  module kigyo_keret imported into user
%  loading /usr/local/lib/sicstus-3.9.1/library/lists.po...
%  module lists imported into kigyo_keret
%  loaded /usr/local/lib/sicstus-3.9.1/library/lists.po in module lists, 0 msec 11656 bytes
% consulted /home/david/uni/dp/03s/nhf/kkigyo.pl in module kigyo_keret, 20 msec 29168 bytes
yes
| ?- stopper(..., ...).
A stopper/2, ill. megold/2 eljárások meghívása a kigyo.pl programot automatikusan betölti (ha szükséges), ezért ennek módosításakor nem kell sem a SICStus interpretert újraindítania, sem a keretprogramot újra betöltenie.

Az SML-keretprogram

Az SML-keretprogram négy függvényt exportál: 
signature KKigyo =
sig
    val helyes_feladvany : TKigyo.kigyotabla -> bool

    val kigyo_be         : string -> TKigyo.kigyotabla
    val kigyo_ki         : string * TKigyo.kigyotabla * TKigyo.kigyovonal list -> unit

    val megold           : string * string -> string
end
helyes_feladvany t
A fent ismertetett feladványellenőrző függvény.
kigyo_be f
Az f szöveges állományból beolvasott adatokból képzett kígyótábla.
kigyo_ki(m, kt, kvk)
A kt kígyótábla kvk megoldáslistáját olvasható formában 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 Kigyo.kigyo 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.

Használat: először fordítsa le az összes modult, belértve a kigyo függvényt megvalósító Kigyo.sml nevű saját programját is az alábbi paranccsal: 

mosmlc -c TKigyo.sml Kigyo.sig Kigyo.sml KKigyo.sig KKigyo.sml
Ezután töltse be az interpreterbe és nyissa meg a KKigyo modult: 
Moscow ML version 2.00 (June 2000)
Enter `quit();' to quit.
- load "KKigyo";
> val it = () : unit
- open KKigyo;

> val helyes_feladvany = fn : TKigyo.kigyotabla -> bool
  val kigyo_ki = fn : string * TKigyo.kigyotabla * TKigyo.kigyovonal -> unit
  val megold = fn : string * string -> string
  val kigyo_be = fn : string -> TKigyo.kigyotabla
- megold (..., ...);
A saját programja módosításakor elegendő a Kigyo.sml állományt újrafordítani, és célszerű az SML értelmezőt újraindítani.

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! Kövesse a Prolog, ill. SML jegyzetben látható szövegelrendezési szokásokat! Ne írjon 72 karakternél hosszabb sorokat! Minden eljáráshoz és függvényhez készítsen fejkommentet!

A két programhoz készítsen közös dokumentációt; 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 alakban adja be, HTML, esetleg ASCII formátumban.

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

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (linux) alatt is működniük kell. A beadott programokat Unix környezetben a SICStus Prolog 3.9.1, ill. az MOSML 2.00 rendszerekkel teszteljük. A programokat és az elektronikus dokumentációt a webes felületen keresztül lehet külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. Programját egy 10-elemű tesztsorozattal automatikusan futtatjuk, és erről válaszlevélben értesítjük. A beadást többször is megismételheti, a legutolsóként beadott megoldást értékeljük.

A házi feladat beadása nem kötelező, de a DP nyelvek magasszintű elsajátításához nagy segítséget ad. Ezért javasoljuk, hogy a házi feladatot mindkét nyelven készítsék el és adják be. Mindazonáltal elfogadunk csak SML, ill. csak Prolog nyelven készült megoldásokat, értelemszerűen felére csökkentett pontszámmal.

A programok és az elektronikus dokumentáció végső beadási határideje 2003. május 5., hétfő, 24h.

Az értékeléshez a beadási tesztsorozathoz hasonló nehézségű teszteseteket fogunk használni. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk. A 10 tesztesetre összesen tehát nyelvenként maximum 5 pontot kaphat. Ezen felül a dokumentációt, a programkód olvashatóságát, kommentezettségét is értékeljük, nyelvenként maximum 2,5 ponttal. Ha mindkét nyelvből beadja a házi feladatot, akkor tehát maximum 15 pontot kaphat (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az alapteszt minden feladatát helyesen és az előírt időkorláton belül megoldják, 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 7,5 és 0,5 közötti pluszpont kapható. Ha valaki tehát mindkét nyelvből a leggyorsabb programot írja meg, akkor a 100 alapponton felül 15 pluszpontot kap.

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