A feladat egy térbeli kirakós játékot vizsgál. A játék célja, hogy egy henger alakú kukoricacsutkára összetapadt kukoricaszemekből álló elemeket helyezzük el úgy, hogy a csutka minden részét pontosan egyszer fedjük be.
A játékot egy olyan n×m méretű, azaz n sorból és m oszlopból álló négyzetráccsal modellezhetjük, ahol az oszlopindexet modulo m értelmezzük. Így például egy 4×5 méretű csutkán a 2-0 és 2-5 párok ugyanazt a mezőt jelölik.
Az összetapadt kukoricaszemekből álló elemekre a következő jelölést vezetjük be: ha az elem belefér egy k×l méretű négyzetrácsba, akkor egy k elemű, egyenként l karakteres atomból álló listával ábrázoljuk. Az atomok kizárólag a 0'. (pont), 0'O, 0'X karakterekből állnak.
Ezeknek a jelentése az alábbi:
0'. karakterek az üres helyeket jelölik, ahol nincs kukoricaszem.0'O karakterek a kukoricaszemeket jelölik. Feltételezheti, hogy a kukoricaszemek összefüggő elemet alkotnak.0'O karakter helyett 0'X karakterrel van megjelölve. Ez a referencia-kukoricaszem. Amikor azt mondjuk, hogy az elemet a csutkán az i-j mezőre helyeztük, akkor a referencia-kukoricaszem a csutka i. sorában és j. oszlopában foglal helyet.Mivel a csutka hengeres, az elemek is egy hengerpalástra illeszkednek. Ezért az elemeket csak 0 vagy 180 fokkal forgathatjuk el. Ha az elem a csutkán az atomok listájával leírt elrendezésben található meg, azt mondjuk, hogy 0 fokkal van elforgatva. A másik lehetséges elforgatás a referencia-kukoricaszem körül történő 180 fokos elforgatás (azaz középpontos tükrözés).
| Prolog-kód | Elhelyezés, 0° | Elhelyezés, 180° | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
elem = [ 'X.', 'O.', 'OO' ] |
|
|
A feladat célja egy olyan lefedheto/5 eljárás készítése, amely egy részben lefedett, és lehetséges referenciákat tartalmazó csutka esetény megállapítja, mely mezők fedhetők le
melyik referenciaszem által. A részben lefedett, és lehetséges referenciákat tartalmazó csutka az 5. kisházi feladatban eredményül kapott struktúrájú, azaz
egy olyan n×m méretű rács, ahol a lefedett mezőkön az ott levő elem sorszáma található. A nem fedett mezőkön, pedig a fedettekhez képest ütközésmentesen
lehelyezhető referenciaszem sorszáma és forgatása.
% lefedheto(+N, +M, +Elemek, +Csutka, -Fedheto):
% Az N sorból és M oszlopból álló Fedheto rácsra megállapítja a már
% fedett mezőket, és a Csutka rácson megjelölt referenciaszemek által
% lefedhető mezőket. Csutka formátuma megegyezik az 5. kisházi kimeneti
% változójának formátumával.
% Fedheto egy N elemű lista, aminek minden eleme egy M elemű lista.
% Az M elemű lista minden eleme a csutka egy mezőjét reprezentálja.
% Egy mező pontosan akkor fedett, ha a megfelelő listaelem pontosan egy
% egész számot tartalmaz. Ezek megegyeznek a Csutka paraméterben fedett elemekkel.
% A nem fedett mezők vagy üres listák vagy forras(Sorszam,I-J,Forgat)
% struktúrák listája, ahol Sorszam annak az elemnek a sorszáma, ami a mezőt fedheti,
% I és J a referenciaszem sora illetve oszlopa és Forgat true vagy false, az elem
% forgatását jelzi.
Az eljárás paraméterei a következők:
N száma, ahol 0 < N.M száma, ahol 0 < M.Elemek listája. Minden elemet egy elem(Sorok) összetett kifejezés ír le,
amelyben a Sorok lista egyforma hosszú atomokból áll, és az elem elforgatás nélküli (0 fokos) alakját írja le.
Csutka listák listája. A lista minden eleme egy lista, ami egy sort reprezentál.
A sorokat reprezentáló listák minden eleme vagy egy egész szám, ami a fedett elemeket jelöli, vagy egy lista.
A lista vagy üres, vagy Elem-Forgatás párokat tárol, ahol Elem az egy, a mezőre Forgatás forgatással, ütközés nélkül lehelyezhető elem sorszáma.
A számozás 0-val kezdődik.
Fedheto listák listája. A lista minden eleme egy lista, ami egy sort reprezentál.
A sorokat reprezentáló listák minden eleme vagy egy egész szám, ami a fedett elemeket jelöli, vagy egy lista.
A lista vagy üres, vagy forras(Sorszam,I-J,Forgat) összetett kifejezéseket tárol, ahol Sorszam annak az elemnek a sorszáma, ami a
mezőt az I-J helyen található referenciaszemmel, Forgatas forgatással le tudja fedni.
A forras kifejezések sorrendje a listán belül tetszőleges.
A lefedheto/5 eljárás minden helyes bemenetre sikeresen lefut.
lefedheto/5 eljárás paramétereinek típusát a következő – megjegyzésként megadott – Prolog-típusdefiníciók írják le.% :- type sorSzam == integer. % a csutka sorainak a száma % :- type oszlopSzam == integer. % a csutka oszlopainak a száma % :- type sorszam == integer. % az elem bemeneti listában elfoglalt (nullával kezdődő) sorszáma % :- type forgatas ---> false % nincs forgatás % ; true. % van forgatás % :- type sorok == list(atom). % egy elem szöveges leírása % :- type elemek == list(elem(sorok)). % :- type mezo ---> integer % ; list(sorszam-forgatas) % :- type csutka == list(list(mezo)). % a csutka leírása % :- type fedheto_m ---> integer % a fedhető rács egy mezője % ; list(forras(sorszam, % sorSzam-oszlopSzam % forgatas)). % :- type fedheto == list(list(fedheto_m)) % a fedhető rács leírása % :- pred referencia_lehet(sorSzam::in, % N % oszlopSzam::in, % M % elemek::in, % Elemek % csutka::in, % Csutka % fedheto::out). % Fedheto
A beadott programokat Linux környezetben SWI Prolog (10.1.13) rendszerrel teszteljük.
?- lefedheto(3, 3,
[elem(['OX']),
elem(['OXO'])],
[[2 , 3 , 4 ],
[[], [], []],
[[], [], []]], Fedheto).
Fedheto = [[2 , 3 , 4 ],
[[], [], []],
[[], [], []]] ;
false
?- lefedheto(3, 3,
[elem(['OX']),
elem(['OXO'])],
[[2 , 3 , 4 ],
[[] , [0-false,0-true], []],
[[0-false,1-true], [] , []]], Fedheto).
Fedheto = [[2 , 3 , 4 ],
[[forras(0,1-1,false)] , [forras(0,1-1,true), forras(0,1-1,false)], [forras(0,1-1,true)] ],
[[forras(1,2-0,true), forras(0,2-0,false)], [forras(1,2-0,true)] , [forras(1,2-0,true), forras(0,2-0,false)]]] ;
false
?- lefedheto(4, 4,
[elem(['.O.','OXO']),
elem(['O..','XOO'])],
[[2 , [], [0-true], []],
[2 , 2 , [] , 3 ],
[[] , 3 , 3 , 3 ],
[[1-false], [], [] , 3 ]], Fedheto).
Fedheto = [[2 , [forras(0,0-2,true)] , [forras(0,0-2,true)] , [forras(0,0-2,true)]],
[2 , 2 , [forras(0,0-2,true)] , 3 ],
[[forras(1,3-0,false)], 3 , 3 , 3 ],
[[forras(1,3-0,false)], [forras(1,3-0,false)], [forras(1,3-0,false)], 3 ]] ;
false
| DP Admin: dvacakrobotjaitoknakpadm@dp.iit.bme.hu | Vissza az elejére / Back to the top |