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

Deklaratív programozás

Házi feladat, 1.5 változat

2000. május 3.

Cikcakk

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

A feladvány

Adott egy n sorból és m oszlopból álló, téglalap alakú tábla, amelynek mezői 1 és k (a maximális mezőérték) közötti egész számokat tartalmaznak. A bal felső sarokból kindulva úgy kell eljutni a jobb alsó sarokba, hogy (1) az érintett számok szakaszosan ismétlődjenek (1,2,3,...,k,1,2,...), (2) az útvonal minden mezőn pontosan egyszer haladjon át, és sehol se keresztezze saját magát.

Az 1. ábra egy feladványt, a 2. ábra pedig a négy lehetséges megoldása közül kettőt mutat. A betűk a haladási irányt jelzik: n = north (észak), e = east (kelet), s = south (dél), w = west (nyugat), ns = northeast, nw = northwest, se = southeast, sw = southwest. 

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

+---+---+---+---+---+   +---+---+---+---+---+
|se1| e3| e4| e5| s6|   | s1| e3| e4| e5| s6|
+---+---+---+---+---+   +---+---+---+---+---+
| s2| n2| s3| w2| w1|   | s2| n2| s3| w2| w1|
+---+---+---+---+---+   +---+---+---+---+---+
| s3|nw1| s4| e4| s5|   | s3| n1| s4| e4| s5|
+---+---+---+---+---+   +---+---+---+---+---+
| s4| n6| w5| n3| s6|   | s4| n6|sw5| n3| s6|
+---+---+---+---+---+   +---+---+---+---+---+
| e5| e6| e1| n2|se1|   |ne5| e6| e1| n2|se1|
+---+---+---+---+---+   +---+---+---+---+---+
1. ábra Egy feladvány (n=5, m=5, k=6) 2. ábra A négy lehetséges megoldás közül kettő

A megoldandó feladat

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

A függvény, illetve az eljárás bemenő paramétere olyan sorfolytonos alakban megadott mátrix, ahol az egyes sorokat és magát a mátrixot is listaként ábrázoljuk. A 1. ábrán látható feladvány esetén a mátrixot így adjuk meg: 

[[1, 3, 4, 5, 6],
 [2, 2, 3, 2, 1],
 [3, 1, 4, 4, 5],
 [4, 6, 5, 3, 6],
 [5, 6, 1, 2, 1]]

A feladvány egy-egy megoldását szintén sorfolytonos mátrixként kell előállítani. (A jobb alsó sarokba írt irány egyezményesen se.) Az 1. ábrán látható feladat összes megoldásának egy lehetséges permutációját tartalmazza az alábbi lista. 

[[[se,e,e,e,s], [s,n,s,w,w],   [s,nw,s,e,s], [s,n,w,n,s],  [e,e,e,n,se]],
 [[s,e,e,e,s],  [s,n,se,w,w],  [s,n,s,e,s],  [s,n,w,nw,s], [e,e,e,n,se]],
 [[s,e,e,e,s],  [s,n,s,w,w],   [s,n,s,e,s],  [s,n,sw,n,s], [ne,e,e,n,se]],
 [[s,e,e,e,s],  [ne,sw,s,w,w], [s,n,s,e,s],  [s,n,w,n,s],  [e,e,e,n,se]]]
A megoldásmátrix elemei azt írják le, hogy a feladványmátrix azonos indexű mezőiről milyen irányban kell továbbhaladni:
w - nyugat felé n - észak felé e - kelet felé s - dél felé
nw - északnyugat felé ne - északkelet felé se - délkelet felé sw - délnyugat felé

Az SML-függvény első paramétere a feladványt leíró mátrix, második paramétere a feladványban előforduló maximális mezőszám, eredménye pedig olyan lista, amely tetszőleges sorrendben tartalmazza az összes megoldást, mégpedig minden megoldást pontosan egyszer. Ha a feladványnak nincs megoldása, az eredmény az üres lista. (Vigyázat, a függvény részlegesen alkalmazható, lásd alább!)

A Prolog-eljárásnak három paramétere van. Első - bemenő - paramétere a feladványt, második - bemenő - paramétere a feladványban szereplő maximális mezőszám, harmadik - kimenő - paramétere a megoldást a megadott alakban leíró mátrix. Az eljárásnak (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 megírandó fügvény, ill. eljárás specifikációja

A cikcakk 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 TCikcakk =
struct
  type 'a row  = 'a list
  type 'a matrix  = 'a row list
  type field   = int
    (* north, east, south, west,
       northeast, northwest, southeast, southwest *)
  datatype dir = n | e | s | w | ne | nw | se | sw
end

signature Cikcakk =
sig
  (* cikcakk f k = az f feladványmátrixon keresztezés nélkül,
                   minden mezőn pontosan egyszer áthaladó élsorozatok
                   listája, ahol minden élsorozat 1-től k-ig tart  *)
  val cikcakk : TCikcakk.field TCikcakk.matrix -> int ->
                                    TCikcakk.dir TCikcakk.matrix list
end
A cikcakk/3 eljárás paramétereinek típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le. 
    % :- type row(T)    == list(T).
% :- type matrix(T) == list(row(T)).
% :- type field     == int.
% :- type dir       ---> n                % north
%                   ;    e                % east
%                   ;    s                % south
%                   ;    w                % west
%                   ;    ne               % northeast
%                   ;    nw               % northwest
%                   ;    se               % southeast
%                   ;    sw.              % southwest

% :- pred cikcakk(matrix(field)::in, int::in, matrix(dir)::out).

A keretprogram

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a specifikációs modulokkal és a beadáskor használt tesztsorral együtt letöltheti. 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 maximális mezőérték, további soraiban a feladványmátrix sorai vannak (ld. 3. ábra, vö. 1. ábra). A keretprogram kimenete a 2. ábrához hasonló tartalmú szöveges állomány. 

6
1 3 4 5 6
2 2 3 2 1
3 1 4 4 5
4 6 5 3 6
5 6 1 2 1
3. ábra Példa a bemenő állomány tartalmára
Az SML-keretprogram három függvényt exportál: 
    signature KCikcakk =
sig
    val cikcakk_in : string -> (int * TCikcakk.field TCikcakk.matrix)
    val cikcakk_out : string * TCikcakk.field TCikcakk.matrix *
                               TCikcakk.dir TCikcakk.matrix -> unit
    val solve : string * string -> string
end
cikcakk_in f
Az f szöveges állományból beolvasott maximális mezőértéket és feladványmátrixot adja eredményül.
cikcakk_out(m, fss, mss)
Az mss megoldásmátrix által lefedett fss feladványmátrixot kiírja az m szöveges állományba.
solve(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 Cikcakk.cikcakk függvényre. Eredménye a feladványmátrix nevét, a megoldásmátrix méreté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:

cikcakk_in(file::in, int::out, matrix(field)::out)
A megnevezett szöveges állományból beolvassa a maximális mezőértéket és a feladványt, és mindkettőt visszaadja a belső ábrázolásban.
cikcakk_out(file::in, matrix(field)::in, matrix(dir)::in)
Kiírja a megoldást megnevezett szöveges állományba. Ehhez felhasználja a feladványt (második argumentum) és a megoldást (harmadik argumentum).
solve(file::in, file::in)
Beolvas egy feladatot es kiírja az összes megoldást. Ehhez természetesen szüksége van a cikcakk/3 eljárásra.

A keretprogram felhasználja a file típust: 

    % :- type file      == atom.
A file típusú argumentumokban 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 ún. 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. A beadás részleteit a tárgy honlapján közöljük. A programok és az elektronikus dokumentáció beadási határideje 2000. május 15., hétfő, 24:00 óra.

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

A hibátlan nagyfeladatot határidőre beadók SML-, ill. 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 0 közötti pluszpont kapható, a féléves összpontszámhoz a kapott összegnek a negyedét adjuk hozzá. A létraversenyről az esetleges további tudnivalókat a tárgy honlapján tesszük közzé.

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