Az I. 513. feladat (2020. május)

I. 513. (É). A sejtautomata elnevezés Neumann Jánostól származik az 1940-es évek elejéről, aki az önmagát reprodukáló gép logikáját, létrehozásának lehetőségeit vizsgálta. A leghíresebb sejtautomata a John Horton Conway által kitalált életjáték. Conway egy hónappal ezelőtt, 2020 áprilisában halt meg, így ezzel a feladattal rá is emlékezünk.

A Conway-féle életjátékban sejtek élnek egy kétdimenziós világban. A sejtek egy képzeletbeli táblázat egy-egy cellájában találhatók. Viselkedésüket az határozza meg, hogy az őket tartalmazó cella 8 szomszédja közül hányban található sejt. Ha egy sejt szomszédos cellái közül kettőnél kevesebb vagy háromnál több tartalmaz sejtet, akkor a sejt elpusztul, egyébként életben marad. Ha egy cella üres, de a szomszédos cellák közül pontosan háromban van sejt, akkor az üres cellában új sejt születik. A leírt változások nem folyamatosan, hanem lépésekben (generációkban) történnek. Kezdetben az élettér bizonyos celláiban vannak sejtek, míg a többi cellában nincsenek.

Például egy \(\displaystyle 6\times 6\)-os élettér hat egymást követő állapota (a szürke cellákban vannak sejtek, a sötétebbek új sejtek helyét mutatják):

Készítsünk programot sejtautomata néven egy \(\displaystyle 50\times 50\)-es négyzethálós életjátékhoz és oldjuk meg a következő feladatokat. A megoldások során a mintához hasonlóan valósítsuk meg a felhasználóval történő kommunikációt (az ékezetmentes kiírás is elfogadott).

1. Olvassuk be az élettér kezdeti állapotát a conway.txt szöveges állományból és tároljuk el az adatokat úgy, hogy a szimulációhoz használni tudjuk őket. A szöveges állomány 50 sorból áll, melyek mindegyikében 50 karakter található. Az állomány \(\displaystyle i\)-edik sorának \(\displaystyle k\)-adik karaktere az élettér \(\displaystyle i\)-edik sorának \(\displaystyle k\)-adik oszlopában lévő cella kezdeti tartalmát mutatja: szóköz esetén a cella üres, s betű esetén a cellában sejt van.

2. Adjuk meg, hogy összesen hány sejt található az élettérben.

3. Készítsünk függvényt szomszed néven, amelynek bemeneti paramétere \(\displaystyle i\) és \(\displaystyle k\), amelyek az élettér \(\displaystyle i\)-edik sorát és \(\displaystyle k\)-adik oszlopát jelentik. A függvény számítsa ki és adja vissza a megfelelő cella szomszédjaiban található sejtek számát. Kérjük be a felhasználótól egy oszlop és egy sor értékét, és adjuk meg, hogy az adott cellában van-e sejt, illetve azt, hogy a cella szomszédjaiban hány sejt található.

4. Készítsünk eljárást egylepes néven, amely elvégez egy szimulációs lépést. Vegyünk fel az eredeti élettér mellé még egy átmeneti tárolót, amely az élettér állapotát mutatja majd a következő generációban. Vizsgáljuk meg az élettér celláit a fenti leírásnak megfelelően, majd ez alapján adjunk értéket a most létrehozott átmeneti tárolónak. Az eljárás végén a kiszámított új élettér értékei kerüljenek a tárolóból az eredeti élettérbe.

5. Számítsuk ki, hogy hány olyan sejt van az élettérben, amely életben marad egy szimulációs lépés megtétele után, majd az eredményt jelenítsük meg.

6. Végezzük el a szimuláció \(\displaystyle n\) lépését az egylepes alprogram meghívásával, ahol \(\displaystyle n\) értékét a felhasználótól kérjük be.

7. Adjuk meg, hogy az eddig elvégzett \(\displaystyle n\) lépés után most hány sejt fog születni a következő szimulációs lépésben.

8. Adjunk statisztikát a szimuláció következő 100 lépésében az élettér állapotáról. Írjuk a statisztika.txt szöveges állomány egy-egy sorába az élettérben lévő sejtek, a következő szimulációs lépésben elpusztuló és születő sejtek számát egy-egy szóközzel elválasztva. Ha az élettér üres, tehát a sejtek kihalnak, akkor az állományba 0 0 0 tartalmú sorokat ne írjunk, hanem helyette a következő sor jelenjen meg: ,,A szimuláció 34. lépése után az élettér már nem tartalmaz sejteket.'' A szimulációs lépések közé a 6. feladatban végrehajtott \(\displaystyle n\) lépés is beleszámít.

Példa a be/kimenetre:

Letölthető állomány: conway.txt

(10 pont)

A beküldési határidő 2020. június 10-én LEJÁRT.

Mintamegoldásként Mócsy Mátyás 10. osztályos, budapesti diák Java nyelvű megoldását (Sejtautomata.java), valamint Nagy Márton váci, 12. évfolyamos tanuló C#-ban írt megoldását (i513.cs) adjuk közre.

Statisztika:

12 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Mócsy Mátyás, Nagy 793 Márton, Ürmössy Dorottya, Vörös 314 László.
8 pontot kapott:	2 versenyző.
7 pontot kapott:	2 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.

A KöMaL 2020. májusi informatika feladatai