Nyilak

A feladvány

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

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])

    [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).

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 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

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

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 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

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.

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(..., ...).

Az SML-keretprogram

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.

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

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 (..., ...);

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
• Pontosított feladatspecifikáció
• 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, 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.