BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2001/2002-es tanév, őszi félév

Deklaratív programozás

Házi feladat, 1.0 változat

Nyilak

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*n mezőből álló négyzet alakú tábla, amelynek minden mezőjében egy 0 és 8 közötti szám vagy egy kérdőjel áll. A feladat az, hogy a tábla szélein (északon, keleten, délen és nyugaton) a sarkok kivételével a tábla belsejébe mutató nyilakat helyezzünk el úgy, hogy az alábbi feltételek teljesüljenek:
  1. Egy nyíl a nyolc alapirány (két vízszintes, két függőleges és négy átlós) bármelyikébe mutathat, feltéve, hogy a táblának legalább egy mezőjére rámutat.
  2. A tábla minden számozott (azaz nem kérdőjeles) mezője felé pontosan annyi nyílnak kell mutatnia, amekkora szám áll a mezőben.
  3. A kérdőjeles mezők felé akárhány nyíl mutathat.

A nyilakat a karakteres ábrákon a | \ - / karakterekkel jelöljük. (Ezek jelentése mindig egyértelmű, mivel a nyilak csak a tábla belsejébe mutathatnak.)

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek megoldásait mutatja.

  +---+---+---+---+
  | ? | 4 | ? | 3 |
  +---+---+---+---+
  | ? | 3 | 1 | 2 |
  +---+---+---+---+
  | 2 | 4 | ? | 1 |
  +---+---+---+---+
  | 3 | 6 | 4 | ? |
  +---+---+---+---+

           
    \   |   \   /           \   |   \   /    
  +---+---+---+---+       +---+---+---+---+  
\ | ? | 4 | ? | 3 | -   \ | ? | 4 | ? | 3 | -
  +---+---+---+---+       +---+---+---+---+  
\ | ? | 3 | 1 | 2 | \   / | ? | 3 | 1 | 2 | \
  +---+---+---+---+       +---+---+---+---+  
\ | 2 | 4 | ? | 1 | \   \ | 2 | 4 | ? | 1 | \
  +---+---+---+---+       +---+---+---+---+  
- | 3 | 6 | 4 | ? | -   - | 3 | 6 | 4 | ? | -
  +---+---+---+---+       +---+---+---+---+  
    /   |   /   \           /   |   \   \    
1. ábra. Egy feladvány (n=4)   2. ábra. A feladvány megoldásai

A megoldandó feladat

Írjon nyilak 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 0 és 8 közötti egész számok, valamint ? atomok azonos hosszúságú listáiból álló lista, amely a tábla sorait, azon belül az egyes mezőit adja meg.

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

[[?,4,?,3],   % a tábla első sora
 [?,3,1,2],
 [2,4,?,1],
 [3,6,4,?]]   % a tábla utolsó sora

A Prolog-eljárás kimenő paramétere egy ny(Észak, Kelet, Dél, Nyugat) struktúra, amelynek argumentumai listák, és rendre a tábla északi, keleti, déli és nyugati szélén elhelyezett nyilak irányát adják meg. Az egyes irányokat az s, sw, w, nw, n, ne, e, se atomokkal írjuk le, ezek jelentése rendre dél, délnyugat, nyugat, északnyugat, észak, északkelet, kelet, délkelet.

A 2. ábrán látható első megoldást írja le az alábbi kifejezés:

ny([se,s,se,sw],[w,nw,nw,w],[ne,n,ne,nw],[se,se,se,e])
Szemléletesen:
    [se,s,se,sw]
     \  |  \  /
[                [
se, \          - w,
se, \          \ nw,
se, \          \ nw,
e   -          - w
]                ]
     /  |  /  \
    [ne,n,ne,nw]

Az SML-függvény paramétere egy SOME v és NONE értékek (0 <= v <= 8) azonos hosszúságú listáiból álló lista, amely a tábla sorait, azon belül az egyes mezőit adja meg. A mezők esetében SOME v egy v értékű számot, NONE pedig egy kérdőjelet jelent.

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

[[NONE,   SOME 4, NONE,   SOME 3], (* a tábla első sora  *)
 [NONE,   SOME 3, SOME 1, SOME 2],
 [SOME 2, SOME 4, NONE,   SOME 1],
 [SOME 3, SOME 6, SOME 4, NONE  ]] (* a tábla utolsó sora *)

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 feladványnak nincs megoldása, az eredmény az üres lista. Egy megoldást egy (eszak,kelet,del,nyugat) négyes ír le, ahol eszak, kelet, del és nyugat rendre a tábla északi, keleti, déli és nyugati szélén elhelyezett nyilak irányát adja meg. Az egyes irányokat az s, sw, w, nw, n, ne, e, se állandókkal írjuk le, ezek jelentése azonos a Prolog-eljárás specifikációjában megadottakkal.

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

[ ([se,s,se,sw],[w,nw,nw,w],[ne,n,ne,nw],[se,se,se,e]) ,
  ([se,s,se,sw],[w,nw,nw,w],[ne,n,nw,nw],[se,ne,se,e]) ]

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

A nyilak/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 mezo            ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ?.
% :- type sor               == list(mezo).
% :- type nyiltabla         == list(sor).

% :- type nyil            ---> s | sw | w | nw | n | ne | e | se.
% :- type nyilak            == list(nyil).
% :- type nyilazas        ---> ny(nyilak, nyilak, nyilak, nyilak).

% :- pred nyilak(nyiltabla::in, nyilazas::out).
A nyilak/2 eljárás első, nyiltabla típusú paramétere kielégíti az alábbi feltételt:
helyes_feladvany(Tabla) :-
        %% négyzet alakú
        length(Tabla, N),
        all_same_length(Tabla, N),
        %% nem üres
        N \= 0,
        %% nincs nem helyes eleme a Tabla nyiltáblának
        \+ (   member(Sor, Tabla),
               member(Mezo, Sor),
               \+ helyes_mezo(Mezo)
           ).

% all_same_length(Ls, L): az Ls elemei listák, hosszuk azonosan L.
all_same_length([], _).
all_same_length([L|Ls], N) :-
        length(L, N),
        all_same_length(Ls, N).

% helyes_mezo(+Mezo): Mezo egy helyes mezőt ír le
helyes_mezo(?).
helyes_mezo(D) :- number(D), 0 =< D, D =< 8.
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 nyilak SML-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 TNyilak =
struct
 (* datatype 'a option = NONE | SOME of 'a *) (* emlékeztetőül *)
    type mezo          = int option
    type sor           = mezo list
    type nyiltabla     = sor list
	
    datatype nyil      = s | sw | w | nw | n | ne | e | se
    type nyilak        = nyil list
    type nyilazas      = nyilak * nyilak * nyilak * nyilak
end

signature Nyilak =
sig
    (* nyilak Tabla = olyan lista, amelynek az elemei (tetszőleges
       sorrendben) a Tabla nyíltábla megoldásai a fenti értelemben
     *)
    val nyilak : TNyilak.nyiltabla -> TNyilak.nyilazas list
end
A Nyilak.nyilak függvény nyiltabla típusú paramétere kielégíti az alábbi feltételt:
fun helyes_feladvany tabla =
    let
        fun helyes_mezo  NONE    = true
          | helyes_mezo (SOME v) = 0 <= v andalso v <= 8

        val n = length tabla
    in
	(* négyzet alakú *)
	List.all (fn ls => n = length ls) tabla andalso
        (* nem üres *)
        n <> 0 andalso
        (* minden mezője helyes *)
        List.all (List.all helyes_mezo) tabla
    end
Az SML megoldásában tehát feltételezheti, hogy a bemenő argumentumra a helyes_feladvany függvény igazat ad eredményül (csak ilyen adattal teszteljük majd a programot).

A keretprogramok

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 minden sora a tábla egy-egy sorát írja le. Ezekben a sorokban 0 és 8 közötti számok, valamint a ? karakter fordulhat elő, szóközökkel elválasztva (ld. 3. ábra, vö. 1. ábra).
 ? 4 ? 3
 ? 3 1 2
 2 4 ? 1
 3 6 4 ?
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(nyiltabla::in)
A fent ismertetett feladvány-ellenőrző eljárás.
nyilak_be(file::in, nyiltabla::out)
A megnevezett szöveges állományból beolvassa a nyíltáblát, és visszaadja a második argumentumban.
nyilak_ki(file::in, nyiltabla::in, nyilazas::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 nyilak/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 nyilak.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.9.1 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002
Licensed to BUTE DP course
| ?- [knyilak].
% consulting /home/david/uni/dp/02a/nhf/knyilak.pl...
%  module nyilak_keret imported into user
%  loading /usr/local/lib/sicstus-3.9.1/library/lists.po...
%  module lists imported into nyilak_keret
%  loaded /usr/local/lib/sicstus-3.9.1/library/lists.po in module lists, 0 msec 11656 bytes
% consulted /home/david/uni/dp/02a/nhf/knyilak.pl in module nyilak_keret, 20 msec 29168 bytes
yes
| ?- stopper(..., ...).
A stopper/2, ill. megold/2 eljárások meghívása a nyilak.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 KNyilak =
sig
    val helyes_feladvany : TNyilak.nyiltabla -> bool
    val nyilak_be        : string -> TNyilak.nyiltabla
    val nyilak_ki        : string * TNyilak.nyiltabla * TNyilak.nyilazas list -> unit
    val megold           : string * string -> string
end
helyes_feladvany t
A fent ismertetett feladvány-ellenőrző függvény.
nyilak_be f
Az f szöveges állományból beolvasott adatokból képzett nyíltábla.
nyilak_ki(m, t, nyk)
A t nyíltábla nyk 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 Nyilak.nyilak 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 nyilak függvényt megvalósító Nyilak.sml nevű saját programját is az alábbi paranccsal:

mosmlc -c TNyilak.sml Nyilak.sig Nyilak.sml KNyilak.sig KNyilak.sml
Ezután töltse be az interpreterbe és nyissa meg a KNyilak modult:
Moscow ML version 2.00 (June 2000)
Enter `quit();' to quit.
- load "KNyilak";
> val it = () : unit
- open KNyilak;
> val helyes_feladvany = fn : int option list list -> bool
  val nyilak_ki = fn :
  string * int option list list *
  (nyil list * nyil list * nyil list * nyil list) list -> unit
  val megold = fn : string * string -> string
  val nyilak_be = fn : string -> int option list list
- megold (..., ...);
A saját programja módosításakor elegendő a Nyilak.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! Használja a Prolog ill. SML jegyzetekben látható formázási konvenciókat, ne írjon 80 karakternél hosszabb sorokat! Minden eljáráshoz és függvényhez készítsen 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 programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (linux) alatt is működniük kell. A beadott programok tesztelése Unix környezetben a SICStus Prolog 3.9.1 ill. az MOSML 2.00 rendszerekkel történik. A programokat és az elektronikus dokumentációt tömörítve, elektronikus levélben kell elküldeni egy bash szkript segítségével, amely letölthető innen. Programját egy 10-tagú 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 2002. december 15-e, vasárnap 24h.

Az értékelés a beadási tesztsorozathoz hasonló nehézségű tesztesetekkel történik. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk. A 10 futásra ö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 100 pontos alappontszámnak).

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 pontos alappontszámon felül 15 pluszpontot kap.


dp@inf.bme.hu
Utolsó módosítás: 2002. 11. 4.