Ujjak

A feladvány

1. Egy ujj 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, és nem valamelyik főátló irányába mutat.
2. A tábla minden 0-tól 8-ig számozott mezője felé pontosan annyi ujjnak kell mutatnia, amekkora szám áll a mezőben.
3. A 9-et tartalmazó mezők felé akárhány ujj mutathat.

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

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

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

A megoldandó feladat

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 9 közötti egész számok azonos hosszúságú listáiból álló lista, amely a tábla sorait, azon belül az egyes mezőit írja le.

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

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

A Prolog-eljárás kimenő paramétere egy u(É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 ujjak 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:

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

    [se,s,se,sw]
     \  |  \  /
[                [
se, \          - w,
se, \          \ nw,
se, \          \ nw,
e   -          - w
]                ]
     /  |  /  \
    [ne,n,ne,nw]

Az SML-függvény paramétere egy 0 és 9 közötti számjegyek 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 az SML-függvény paramétere:

[[9,4,9,3], (* a tábla első sora  *)
 [9,3,1,2],
 [2,4,9,1],
 [3,6,4,9]] (* 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 ujjak 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 ujjak/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 | 9.
% :- type sor            == list(mezo).
% :- type ujjtabla       == list(sor).

% :- type ujj          ---> s | sw | w | nw | n | ne | e | se.
% :- type ujjak          == list(ujj).
% :- type peremezes    ---> u(ujjak, ujjak, ujjak, ujjak).

% :- pred ujjak(ujjtabla::in, peremezes::out).

helyes_feladvany(Tabla) :-
        %% négyzet alakú
        length(Tabla, N),
        all_same_length(Tabla, N),
        %% nem üres
        N \= 0,
        %% nincs nem helyes eleme a Tabla ujjtá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(D) :- number(D), 0 =< D, D =< 9.

A ujjak 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 TUjjak =
struct
    type mezo         = int
    type sor          = mezo list
    type ujjtabla     = sor list
	
    datatype ujj      = s | sw | w | nw | n | ne | e | se
    type ujjak        = ujj list
    type peremezes    = ujjak * ujjak * ujjak * ujjak
end

signature Ujjak =
sig
    (* ujjak Tabla = olyan lista, amelynek az elemei (tetszőleges
       sorrendben) a Tabla ujjtábla megoldásai a fenti értelemben
     *)
    val ujjak : TUjjak.ujjtabla -> TUjjak.peremezes list
end

fun helyes_feladvany tabla =
    let
        fun helyes_mezo v = 0 <= v andalso v <= 9

        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

A keretprogramok

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 9 közötti számjegyek fordulhatnak elő, szóközökkel elválasztva (ld. 3. ábra, vö. 1. ábra).

9 4 9 3 9 3 1 2 2 4 9 1 3 6 4 9

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

helyes_feladvany(ujjtabla::in)

A fent ismertetett feladvány-ellenőrző eljárás.

ujjak_be(file::in, ujjtabla::out)

A megnevezett szöveges állományból beolvassa az ujjtáblát, és visszaadja a második argumentumban.

ujjak_ki(file::in, ujjtabla::in, peremezes::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 ujjak/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.

Használat: a saját programját a ujjak.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.11.2 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002
Licensed to BUTE DP course
| ?- [kujjak].
% consulting /home/david/uni/dp/02a/nhf/kujjak.pl...
%  module ujjak_keret imported into user
%  loading /usr/local/lib/sicstus-3.11.2/library/lists.po...
%  module lists imported into ujjak_keret
%  loaded /usr/local/lib/sicstus-3.11.2/library/lists.po in module lists, 0 msec 11656 bytes
% consulted /home/david/uni/dp/02a/nhf/kujjak.pl in module ujjak_keret, 20 msec 29168 bytes
yes
| ?- stopper(..., ...).

Az SML-keretprogram

signature KUjjak =
sig
    val helyes_feladvany : TUjjak.ujjtabla -> bool
    val ujjak_be         : string -> TUjjak.ujjtabla
    val ujjak_ki         : string * TUjjak.ujjtabla * TUjjak.peremezes list -> unit
    val megold           : string * string -> string
end

helyes_feladvany t

A fent ismertetett feladvány-ellenőrző függvény.

ujjak_be f

Az f szöveges állományból beolvasott adatokból képzett ujjtábla.

ujjak_ki(m, t, us)

A t ujjtábla us 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 Ujjak.ujjak 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.

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

mosmlc -c TUjjak.sml Ujjak.sig Ujjak.sml KUjjak.sig KUjjak.sml

Moscow ML version 2.01 (January 2004)
Enter `quit();' to quit.
- load "KUjjak";
> val it = () : unit
- open KUjjak;
> val helyes_feladvany = fn : int option list list -> bool
  val ujjak_ki = fn :
  string * int option list list *
  (ujj list * ujj list * ujj list * ujj list) list -> unit
  val megold = fn : string * string -> string
  val ujjak_be = fn : string -> int option list list
- megold (..., ...);

Dokumentációs követelmények

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:

• Követelmények elemzése
• Tervezés, az egyes eljárások, ill. függvények specifikálása
• Kódolás SML-, ill. Prolog-nyelven, az algoritmusok ismertetése
• Tesztelési megfontolások
• Kipróbálási tapasztalatok

A dokumentációt elektronikus formában adja be, HTML, PDF, 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.11.2, ill. az MOSML 2.01 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 az eredményrő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 teszteseteket úgy választottuk meg, hogy 3-4 feladatot az egyszerű, algoritmikus ötletek nélküli programok is meg tudjanak oldani.

Figyelem! A jó jegyhez gyakorlatilag elengedhetetlen a házi feladat elkészítése.

A programok és az elektronikus dokumentáció végső beadási határideje 2005. május 9-e, hétfő 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 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 legfeljebb 100 alapponton felül 15 pluszpontot kap.

A programot és dokumentációt mindenkinek saját magának kell elkészítenie. A beadott házi feladatokat gépi úton hasonlítjuk össze, másolás esetén a kódot adó és kapó hallgató sem kaphat pontot. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.