Bűvös csiga

A feladvány

1. Minden sorban és minden oszlopban az 1..m számok mindegyike pontosan egyszer szerepel.
2. A bal felső sarokból induló csigavonal mentén a számok rendre az 1,2,...m,1,2,...,m,... sorrendben követik egymást.

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja.

-----------------------\
                  2     |
/-------------------\   |
|     1             |   |
|   /-----------\   |   |
|   |           |   |   |
|   |   /---\   |   |   |
|   |   |       |   | 1 |
|   |   \-------/   |   |
|   |               |   |
|   \---------------/   |
|                       |
\-----------------------/

-----------------------\
  1   -   -   -   2   3 |
/-------------------\   |
| -   1   2   3   - | - |
|   /-----------\   |   |
| - | 3   1   2 | - | - |
|   |   /---\   |   |   |
| - | 2 | 3   - | - | 1 |
|   |   \-------/   |   |
| 3 | -   -   -   1 | 2 |
|   \---------------/   |
| 2   -   -   1   3   - |
\-----------------------/

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

     csiga(N, M, As)

• N a négyzetes tábla mérete, azaz sorainak, ill. oszlopainak a száma ( N >= 1);
• M a csigavonal ciklusa, azaz az egy sorban/oszlopban levő nem-üres mezők száma; minden sorban és oszlopban az 1..M számok pontosan egyszer fordulnak elő (1 <= M <= N)
• As az előre kitöltött mezőket leíró lista. A lista egyes elemei i(Sor,Oszlop,Érték) alakú struktúrák. Egy ilyen elem azt írja elő, hogy a tábla Sor számú sorának Oszlop számú oszlopában az Érték szám áll. Az As lista a (Sor,Oszlop) párok szerint lexikografikusan rendezett.

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

     csiga(6, 3, [i(1,5,2),i(2,2,1),i(4,6,1)])

A Prolog-eljárás kimenő paramétere a kitöltött tábla. Ezt sorok listájaként kell előállítani, ahol az egyes sorok egész számokból álló listák. Ez utóbbi lista minden eleme a tábla egy mezőjét írja le: a 0 számérték jelenti az üres helyet, míg a nem-nulla I érték azt jelenti, hogy az adott helyen az I szám áll.

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

     [[1,0,0,0,2,3],
      [0,1,2,3,0,0],
      [0,3,1,2,0,0],
      [0,2,3,0,0,1],
      [3,0,0,0,1,2],
      [2,0,0,1,3,0]]

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

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

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

     [[[1,0,0,0,2,3],
       [0,1,2,3,0,0],
       [0,3,1,2,0,0],
       [0,2,3,0,0,1],
       [3,0,0,0,1,2],
       [2,0,0,1,3,0]]
     ]

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

A buvos_csiga 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 TCsiga =
struct
      type meret           = int (* 0 < meret *)
      type ciklus          = int (* 0 < ciklus <= meret *)
      type sorszam         = int (* 0 < sorszam <= meret *)
      type oszlopszam      = int (* 0 < oszlopszam <= meret *)
      type ertek           = int (* 0 < ertek <= ciklus *) 
      type adott_elem      = sorszam * oszlopszam * ertek
      type feladvany_leiro = meret * ciklus * adott_elem list

      type ertek_vagy_ures = int (* ertek_vagy_ures = 0, ha ures,
                                    egyebkent 0 < ertek_vagy_ures <= ciklus *)
      type sor             = ertek_vagy_ures list
      type csigatabla      = sor list
end

signature Csiga =
sig
  (* buvos_csiga (N, M, (Sor,Oszlop,Ertek) list) = olyan lista, amelynek az
          elemei (tetszőleges sorrendben) az összes olyan N méretű,
          egymástól különböző táblák, amelyek mindegyike a felsorolt
          (Sor,Oszlop,Ertek) hármasok által meghatározott M ciklusú
          csigavonalat ír le
  *)
  val buvos_csiga : TCsiga.feladvany_leiro -> TCsiga.csigatabla list
end

load "Listsort";

fun helyes_feladvany_leiro(Meret, Ciklus, Adottak) =

    let
	fun helyes_adott_elem(Sor, Oszlop, Ertek) = 0 < Sor andalso
	      Sor <= Meret andalso 0 < Oszlop andalso Oszlop <= Meret andalso
	      0 < Ertek andalso Ertek <= Ciklus;

	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 ((x1,y1,_)::(x2y2s as (x2,y2,_)::xys)) =
	   (x1 <> x2 orelse y1 <> y2) andalso szomszedok_kulonbozok x2y2s
	  | szomszedok_kulonbozok _ = true
    in
	0 < Meret andalso 0 < Ciklus andalso Ciklus <= Meret andalso
          (* minden eleme helyes az Adottak listának: *)
        (List.all (fn x => x) (map helyes_adott_elem Adottak)) andalso
          (* az Adottak lista lexikografikusan rendezett: *)
	Listsort.sorted lexikografikusan_hasonlit Adottak andalso
	  (* Az Adottak 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 Adottak
end

A buvos_csiga/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 feladvany_leiro ---> csiga(meret, ciklus, list(adott_elem)).
% :- type meret             == integer.
% :- type ciklus            == integer.
% :- type adott_elem      ---> i(sorszam, oszlopszam, ertek).
% :- type sorszam           == integer.
% :- type oszlopszam        == integer.
% :- type ertek             == integer.
		          
% :- type csigatabla        == list(sor).
% :- type sor               == list(ertek_vagy_ures).
% :- type ertek_vagy_ures   == integer.

% :- pred buvos_csiga(feladvany_leiro::in, csigatabla::out).

helyes_feladvany_leiro(csiga(Meret,Ciklus,Adottak)) :-
	integer(Meret), integer(Ciklus),
	Meret >= 1, Ciklus >= 1,
	Ciklus =< Meret.
        % nincs nem helyes eleme az Adottak listának:
	\+ (   member(Adott, Adottak), 
	       \+ helyes_adott_elem(Meret, Ciklus, Adott)
	   ),  
	% az Adottak lista lexikografikusan rendezett:
	sort(Adottak, Adottak),
	% Az Adottak lista minden eleme különböző (Sor,Oszlop) 
	% koordinátára vonatkozik (a rendezettség miatt elegendő a
        % szomszédos elemekre kikötni ezt):
	\+ append(_, [i(S,O,_),i(S,O,_)|_], Adottak).

helyes_adott_elem(Meret, Ciklus, i(Sor,Oszlop,Ertek)) :-
	integer(Sor), integer(Oszlop), integer(Ertek),
	1 =< Sor, Sor =< Meret,
	1 =< Oszlop, Oszlop =< Meret,
	1 =< Ertek, Ertek =< Ciklus.

A keretprogram

A keretprogram bemenete egy olyan szöveges állomány, amelynek első két sora a feladványtábla mérete és a csigavonal ciklusa. Az ezt követő sorok mindegyikében három szám áll, amelyek az adott elemek sorszámát, oszlopszámát ill. értékét írják le (ld. 3. ábra, vö. 1. ábra).

6                                         
3                                        
1 5 2
2 2 1
4 6 1

A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szöveges állomány.

Az SML-keretprogram három függvényt exportál:

signature KCsiga =
sig
    val csiga_be : string -> TCsiga.feladvany_leiro
    val csiga_ki : string * TCsiga.csigatabla list -> unit
    val megold   : string * string -> string
end

csiga_be f

Az f szöveges állományból beolvasott adatokból képzett feladványleíró.

csiga_ki(m, ms)

Az ms megoldáslistá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 Csiga.buvos_csiga 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 Prolog-keretprogram három eljárást exportál:

csiga_be(file::in, feladvany_leiro::out)

A megnevezett szöveges állományból beolvassa a feladványleírót, és visszaadja a második argumentumban.

csiga_ki(file::in, csigatabla::in)

A megnevezett szöveges állományba kiírja az adott megoldást.

megold(file::in, file::in)

Beolvas egy feladványleírót 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 buvos_csiga/2 eljárásra.

A keretprogram felhasználja a file típust:

     % :- type file == atom.

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 ill. az MOSML 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 hamarosan letölthető lesz. 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. május 6-a, 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 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.