Game of Life - README

Descriere generală

Acest proiect implementează o versiune avansată a jocului "Game of Life". Programul simulează evoluția unei colonii de celule pe o grilă,
aplicând reguli precise pentru a determina supraviețuirea, moartea sau nașterea celulelor. Proiectul este împărțit în mai multe taskuri,
fiecare adăugând funcționalitate și complexitate față de cel precedent.


TASK1:Simularea generațiilor și afișarea acestora
Reguli aplicate (Conway's Game of Life)

Celulă vie ('X') cu mai puțin de 2 sau mai mult de 3 vecini moare.

Celulă vie ('X') cu 2 sau 3 vecini supraviețuiește.

Celulă moartă ('+') cu exact 3 vecini devine vie ('X').

Funcții importante

-citire_matrice(...) – citește configurația inițială din fișier, împreună cu dimensiunile și numărul de generații (K).

-next_gen(...) – aplică regulile jocului și generează următoarea stare a matricii. Se folosește o matrice temporară pentru a nu modifica
 matricea originală în timp ce se face calculul.

-afisare_generatii(...) – scrie în fișier toate cele K+1 generații (inclusiv generația inițială).


TASK2: Optimizarea jocului prin stocarea diferentelor de la o generatie la aplicate(stiva cu liste)

Structuri de date

celula: păstrează linia și coloana unei celule(a unui element din matricea originală) care s-a modificat.

generatie: o listă de celule modificate într-o singură generație.

stiva: o stivă de generații, implementată cu liste înlănțuite.

Functii importante

-citirea si calcularea urmatoarelor generatii: sunt in mare la fel ca la primul task, doar ca acum nu se mai modifica elementele propriu-zise ale matricei ,
ci se creaza o lista(generatie) cu fiecare celula modificata,urmand sa fie inserata intr o stiva
-sorteaza_celule: sorteaza lista de celule modificate dupa linie si coloana(pozitia lor in matricea originala)
-scrie_stiva: face scrierea in fisierul de output a stivei cu schimbarile pe generatii


TASK3: Crearea unui arbore binar (2 reguli)

Regula nouă: o celulă moartă cu exact 2 vecini vii devine vie.
Regula veche (clasică): celulele urmează regulile din Task 1.

Structuri de date:

nod: reprezintă un nod al arborelui binar și conține o matrice, nivelul din arbore și legături către stânga și dreapta.
celula: utilizată pentru a urmări celulele modificate între stări (necesare la aplicarea regulilor).

Funcții importante

regula_noua(...): aplică regula alternativă și returnează noua matrice + lista de modificări.

regula_veche(...): aplică regula clasică.

copiere_matrice: se foloseste pentru ca se aplica 2 reguli diferite pe aceeasi matrice, deci nu se poate modifica cea de baza

creare_arbore(...): funcție recursivă care construiește arborele binar până la nivelul K.

  Pentru fiecare nod: se aplică regula nouă (stânga) și regula veche (dreapta).
  Se reține doar matricea, nu și lista de modificări.

parcurgere_pre(...): scrie în fișier stările matricei din arbore în preordine.


TASK4: Gasirea celui mai lung lant Hamiltonian

Structuri de date
varf: struct care reține poziția celulelor vii.

Functii importante:
regula_noua si regula_veche: s au modificat din cauza input-urilor mari ,incercandu-se o modalitate mai optimizata;acum fiecare celula
 se retine intr o structura (pozitia ei in matrice si numarul de vecini in viata),astfel se calculeaza numarul de vecini ai fiecarei
 celule si se actualizeaza generatia in functie de numarul de vecini 
extrage_varfuri(...): Caută toate celulele vii dintr-o matrice și salvează coordonatele lor într-un vector varf[].
construieste_matrice_adiacenta(...): Verifică pentru fiecare pereche de celule vii dacă sunt vecine (inclusiv pe diagonală).
dfs_componente(...) și start_dfs_componente(...): Determină care celule fac parte din același grup (componentă conexă).
                                        DFS merge dintr-o celulă vie în vecinii ei și îi marchează ca făcând parte din același grup.
                                    Dacă o celulă nu e conectată cu altele, formează un grup separat.
dfs_lant(...): Caută toate lanțurile posibile care trec prin fiecare celulă o singură dată.
            Reține cel mai lung drum pe care îl poate construi pornind dintr-un punct.
lant_max(...): Pentru o componentă conexă, caută toate lanțurile posibile pornind din fiecare celulă vie din acea componentă.
            Salvează cel mai lung dintre ele.
compara_lungime(...): Dacă două lanțuri au aceeași lungime, îl alege pe cel care începe mai sus și mai la stânga în matrice.            
parcurgere_pre_task4(...): Parcurge arborele (copacul cu stări) în preordine: rădăcină → stânga → dreapta.
                      Extrage celulele vii.
                    Construieste graful.
                Găsește cel mai lung lanț Hamiltonian din cea mai mare componentă.
            Scrie lanțul în fișier (sau -1 dacă nu există lanț valid).