:- module(csiga, [buvos_csiga/2]). :- use_module(library(lists), [member/2,select/3]). % Tipusok a feladat kiirasabol: % :- 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. % A csiga-feladvany megoldasa soran a csigavonal kivulrol befele valo % bejarasa soran helyezzuk el a szamokat es az ures helyeket a % tablazatban. Ekozben egy allapot adatstrukturaban tartjuk nyilvan azt, % hogy az egyes sorokban ill. oszlopokban meg milyen ertekeket kell % elhelyezni. % buvos_csiga(Feladvany, Tabla): A Feladvany csiga-feladvany megoldasa Tabla. % :- pred buvos_csiga(feladvany_leiro::in, csigatabla::out). % A fentieknek megfeleloen a feladatkiirasban szereplo tipusdefiniciokat % tovabbi adatstrukturakkal egeszitjuk ki: % A vonal_minta elemek listaja, ahol egy elem egy ismert vagy ismeretlen % tablazatmezot abrazol. Az ismeretlen mezot a '?' nevkonstans jelzi. % :- type vonal_minta == list(elem_minta). % :- type elem_minta ---> i(sorszam, oszlopszam, ertek_esetleg). % :- type ertek_esetleg == integer \/ {?}. % A vonal olyan vonal_minta, amely nem tartalmaz ismeretlen erteket. % :- type vonal == list(elem). % :- type elem ---> i(sorszam, oszlopszam, ertek_vagy_ures). % Az allapot ket reszbol all, amelyek azonos szerkezetuek. Az a/2 struktura % elso argumentuma a sorokra, a masodik az oszlopokra vonatkozo informaciot % tarolja. % :- type allapot ---> a(sorallapot, oszlopallapot). % :- type sorallapot == reszallapot. % :- type oszlopallapot == reszallapot. % A reszallapot is ket komponensbol all. Az elso mondja meg, hogy hany ures % mezo lehet meg az egyes sorokban ill. oszlopokban. A masodik komponens % azt irja le, hogy az egyes sorokban/oszlopokban milyen szamokat kell meg % elhelyezni. Mindket resz egy lista formajat olti, az i. listaelem irja le % az i. sor/oszlop allapotat. Az elso lista elemei egesz szamok (hany ures % mezot kell meg elhelyezni), a masodik lista elemei szamlistak (a meg % elhelyezendo szamok listai). % :- type reszallapot ---> list(uresek_szama)-list(megengedett_szamok). % :- type uresek_szama == integer. % :- type megengedett_szamok== list(integer). buvos_csiga(Feladvany, Tabla) :- Feladvany = csiga(Meret, Ciklus, Adottak), kezdoallapot(Feladvany, All0), % kezdoallapot eloallitasa csigavonal(1, 1, Meret, Adottak, Vonal0), % a csigavonal felepitese csigakereses(Vonal0, 1, All0, Ciklus, Vonal), % mezok kitoltese (kereses) csigatablazat(Vonal, Tabla). % a vonal tablazatta % alakitasa. % --------- Kezdoallapot --------- % kezdoallapot(Feladvany, Allapot): A Feladvany feladvanynak az Allapot % kezdoallapot felel meg. % :- pred kezdoallapot(feladvany_leiro::in, allapot::out). kezdoallapot(csiga(Meret,Ciklus,Adottak), All) :- szamsor(1, Ciklus, Szamok), % Szamok = [1,...,Ciklus] Uresek is Meret-Ciklus, lista(Meret, Uresek, UresekL), % Uresek Meret-szer ismetelve lista(Meret, Szamok, SzamokL), % Szamok Meret-szer ismetelve A = UresekL-SzamokL, % a sorok ill. oszlopok kezdoallapota All0 = a(A,A), listat_hozzavesz(Adottak, All0, All). % az elore megadott mezok feldolgozasa % listat_hozzavesz(Mezok, All0, All): A Mezok ertekenek kitoltese az All0 % allapotbol az All allapotba vezet. % :- pred listat_hozzavesz(list(elem)::in, allapot::in, allapot::out). listat_hozzavesz([], All, All). listat_hozzavesz([Mezo|Mezok], All0, All) :- hozzavesz(Mezo, All0, All1), % Mezo kitoltese az All0 -> All1 % allapotvaltozast idezi elo listat_hozzavesz(Mezok, All1, All). % --------- A csigavonal felepitese --------- % csigavonal(S, O, Meret, Adottak, Mezok): A Meret meretu % csigavonal_mintanak az (S,O) mezovel kezdodo zaroszelete Mezok. A % csigavonal_mintaban az Adottak-ban megadott mezok az ottani ertekkel, a % tobbi mezo a '?' ertekkel szerepel. % :- pred csigavonal(sorszam::in, oszlopszam::in, meret::in, % list(adott_elem)::in, vonal_minta::out). csigavonal(S, O, Meret, Adottak, [Mezo|Mezok]) :- mezo_kezdoertek(S, O, Adottak, Mezo), ( csigavonalban_kov(S, O, Meret, S1, O1) -> csigavonal(S1, O1, Meret, Adottak, Mezok) ; Mezok = [] ). % Az (S,O) helyen levo mezonek az Adottak szerint a % Mezo elem-minta felel meg. % :- pred mezo_kezdoertek(sorszam::in, oszlopszam::in, % list(adott_elem)::in, elem_minta::out). mezo_kezdoertek(S, O, Adottak, Mezo) :- Mezo = i(S,O,_), member(Mezo, Adottak), !. % ha adott, az ottani ertekkel, mezo_kezdoertek(S, O, _, i(S,O,?)). % egyebkent a '?' ertekkel % A Meret meretu csigatablazatban az (S,O) mezo rakovetkezoje (S1,O1). % :- pred csigavonalban_kov(sorszam::in, oszlopszam::in, meret::in, % sorszam::out, oszlopszam::out). csigavonalban_kov(S, O, Meret, S1, O1) :- ( O+1 >= S, O+S-1 < Meret -> S1 = S, O1 is O+1 ; O > S, O+S-1 >= Meret -> S1 is S+1, O1 = O ; O =< S, O+S-1 > Meret -> S1 is S, O1 is O-1 ; O+1 < S, O+S-1 =< Meret -> S1 is S-1, O1 = O ). % --------- A csigavonal bejarasa --------- % csigakereses(Vonal0, I, All, Ciklus, Vonal): Az All allapot altal jelzett % reszleges csigavonal kiterjesztheto egy teljes csigavonalla a Vonal0 % minta menten, ahol Ciklus a feladat ciklusa es I a Vonal0 elso % szamerteke. A kiterjesztes eredmenye a Vonal vonal. % :- pred csigakereses(vonal_minta::in, ertek::in, allapot::in, ciklus::in, % vonal::out). csigakereses([], _, _, _, []). csigakereses([Mezo0|Mezok0], I0, All0, Ciklus, [Mezo|Mezok]) :- mezo_ertek(Mezo0, I0, All0, Ciklus, Mezo, I1, All1), csigakereses(Mezok0, I1, All1, Ciklus, Mezok). % mezo_ertek(Mezo0, I0, All0, Ciklus, Mezo, I, All): A Mezo0 elem-mintanak % megfeleltetheto a Mezo elem, felteve, hogy I0 a Mezo0-ra helyezheto % ertek, All0 a korabbi elhelyezeseket tukrozo allapot, es Ciklus a % feladvany ciklusa. A Mezo0 utani mezore az I szam helyezheto el, es a % Mezo kitoltese utani allapot All lesz. % :- pred mezo_ertek(elem_minta::in, ertek::in, allapot::in, ciklus::in, % elem::out, ertek::out, allapot::out). mezo_ertek(i(S,O,E0), I0, All0, Ciklus, Mezo, I, All) :- Mezo = i(S,O,E), ( number(E0) -> I0 = E0, E = I0, kov_ertek(I0, Ciklus, I), All = All0 % Itt van a valasztasi pont: ; E = 0, % eloszor az ures mezo esetet probaljuk ki, I = I0, hozzavesz(Mezo, All0, All) ; E = I0, % majd a szamot tartalmazo mezo esetet. kov_ertek(I0, Ciklus, I), hozzavesz(Mezo, All0, All) ). % Ha Ciklus a feladvany ciklusa, akkor az I0 ertek utan az I ertek kovetkezik. % :- pred(ertek::in, ciklus::in, ertek::out). kov_ertek(I0, Ciklus, I) :- I is I0 mod Ciklus + 1. % --------- Az allapot modositasa --------- % hozzavesz(Mezo, All0, All): A Mezo ertekenek kitoltese az All0 allapotbol % az All allapotba vezet. % :- pred hozzavesz(elem::in, allapot::in, allapot::out). hozzavesz(i(S,O,E), a(SA0,OA0), a(SA,OA)) :- hozzavesz(E, S, SA0, SA), hozzavesz(E, O, OA0, OA). % hozzavesz(Ertek, Index, ReszAll0, ReszAll): Az Ertek erteknek az Index % sorszamu sorba/oszlopba valo helyezese a ReszAll0 reszallapotbol a % ReszAll reszallapotba vezet. % :- pred hozzavesz(ertek_vagy_ures::in, integer::in, % reszallapot::in, reszallapot::out). hozzavesz(0, J, UkL0-SzL, UkL-SzL) :- !, % Ures mezo esete: nedik_csere(J, UkL0, U0, UkL, U), U0 > 0, U is U0-1. % 1-gyel csokkentjuk az uresek % szamat, ha lehet. hozzavesz(E, J, UkL-SzL0, UkL-SzL) :- % Szamerteku mezo esete: nedik_csere(J, SzL0, Ek0, SzL, Ek), ( select(E, Ek0, Ek) -> true % Elhagyjuk az erteklistabol az ). % az adott erteket, ha lehet. % --------- Vonal tablazatta alakitasa --------- % Tablazat a Vonal0 elem-listanak megfelelo csiga-tablazat. % :- pred csigatablazat(vonal::in, csigatabla::out). csigatablazat(Vonal0, Tablazat) :- sort(Vonal0, Vonal), bagof(S-Sor, bagof(E, O^member(i(S,O,E), Vonal), Sor), Sorok0), sort(Sorok0, Sorok), findall(Sor, member(_-Sor, Sorok), Tablazat). % --------- Segedeljarasok --------- % L a [Min,Min+1,...., Max] szamsorozat (elofeltetel: Min =< Max). % :- pred szamsor(integer::in, integer::in, list(integer)::out). szamsor(Min, Max, L) :- Min > Max, !, L = []. szamsor(Min, Max, [Min|L]) :- Min1 is Min+1, szamsor(Min1, Max, L). % lista(N, E, L) :- Az L lista N darab azonos E elembol all. % :- pred lista(int::in, T::in, list(T):: out). lista(0, _, []) :- !. lista(N, E, [E|L]) :- N > 0, N1 is N-1, lista(N1, E, L). % nedik_csere(N, L0, X, L, Y): Ha az L0 listaban az N-edik elemet, X-t, % lecsereljuk Y-ra, akkor az L listat kapjuk. % :- pred nedik_csere(integer::in, list(T)::in, T::in, list(T)::out, T). nedik_csere(1, L0, X, L, Y) :- !, L0 = [X|LL], L = [Y|LL]. nedik_csere(N, [E|L0], X, [E|L], Y) :- N1 is N-1, nedik_csere(N1, L0, X, L, Y).