conway game of life

[•hory0603]

pornind de la acest "joc" http://en.wikipedia.org/wiki/Conway's_Game_of_Life , am intalnit o problema care suna cam asa :

avand data o matrice (m*n) de cel mult 1000/1000 si o configuratie initiala a acesteia (vezi regulile jocului) cu celule vii, respectiv moarte, sa se afiseze matricea dupa generatia cu nr T (nu si generatiile intermediare).
problema de care m-am lovit este faptul ca acest T este putin cam mare (1.000.000) iar un algoritm de complexitate T*m*n ruleaza cam....mult  . pe google am dat doar de simulatoare,nu si de o sursa care sa-mi afiseze doar ultima configuratie.
daca s-a mai lovit cineva de pb asta si are o solutie,o sursa sau macar o idee, va rog sa-mi spuneti si mie. multumesc.

[•Cosmin]

Poti sa zici sursa problemei?

Proiectul asta http://golly.sourceforge.net/ are algoritmi rapizi de generare a configuratiilor din jocul mentionat de tine.

Este si un articol cu algoritmul in dr dobb's http://www.ddj.com/hpc-high-performance-computing/184406478 e scris de radeye (veteranii pe topcoder il stiu).

[•hory0603]

Uite enuntul original al problemei. (La asta te-ai referit cand ai cerut sursa problemei nu?)

[•Cosmin]

Nu, intrebam de la ce concurs e. Sper ca nu e unul in desfasurare ...

[•hory0603]

aa  ...nu e vorba despre niciun concurs . e una dintre aplicatiile primite la facultate (sunt student in anul 1 la automatica)

[•Cosmin]

Misto, deci nu e un concurs e tema si eu care credeam ca vrei sa te ajut la ceva pt care trebuie sa te descurci singur

Oricum cerinta cu afisat pe ecran si citit de la tastatura pare sa faca limitele impuse putin dubioase .

[•hory0603]

chestia cu cititu de la tastatura e practic de forma (pentru ca inca nu s-a predat lucrul cu fisiere)..insa datele vor fi citite fortat dintr-un fisier (din command prompt : sursa.exe <fisier.txt ). so, exista vreo idee de la care sa plec pentru o rezolvare eficienta (=cu complexitate mai mica decat t*m*n) ?

[•svalentin]

Pana la urma ce algoritm ai implementat?
Dupa ce se corecteaza, sa ne spui si noua, poate ii ajuta si pe altii

[•lache92]

asa ceva se face la facultate... eu am facut-o in clasa a 9-a fara vreo problema majora.....

Cod:

#include <fstream.h>
#include <stdlib.h>
#include <conio.h>

void citeste_fisier(int &, int &, int[20][20], int[20][20]);
void arata(int [20][20], int ,int);
void schimbare(int[20][20], int[20][20], int, int);

int main()
{
      int M[20][20], MOD[20][20];char x='n';
      register int c = 0;
      int i, y, n, m;
      citeste_fisier(n, m, M, MOD);
      arata(M, n, m);
      cout<<"Iesiti? (d/n) ";
      x = getche();
      cout<<'\n'<<'\n'<<'\n'<<'\n';
      if(x == 'd')
           return 0;
      while(x != 'd') {
              schimbare(M, MOD, n, m);
              arata(M, n, m);
              cout<<"Iesiti? (d/n) ";
              x = getche(); cout<<'\n';
              for(int lol = 0; lol < 3; lol++)
              cout<<'\n';
      }


      return 0;
}
void citeste_fisier(int & a, int & b, int M[20][20], int MOD[20][20]) {
     fstream f("start.in", ios::in);
     f>>a>>b;
     for (int i = 0; i < a; i++)
         for(int y = 0; y < b; y++) {
                 f>>M[i][y]; MOD[i][y] = M[i][y];
         }
     }

void arata(int M[20][20], int n, int m) {
     char x;
     static int contor = 0;

     cout<<"Pasul t + "<<contor<<"."<<'\n';
     for(int i = 0; i < n; i++) {
             for(int y = 0; y < m; y++)
                     cout<<M[i][y];
             cout<<'\n';
     }
     contor++;
     }

void schimbare(int M[20][20], int MOD[20][20], int n, int m) {
     int nr = 0;
     for(int i = 0; i < n; i++)
             for( int y = 0; y < m; y++) {
                  if(M[i-1][y-1] == 1)
                                 nr++;
                  if(M[i-1][y] == 1)
                                 nr++;
                  if(M[i-1][y+1] == 1)
                                 nr++;
                  if(M[i][y-1] == 1)
                                 nr++;
                  if(M[i][y+1] == 1)
                                 nr++;
                  if(M[i+1][y-1] == 1)
                                 nr++;
                  if(M[i+1][y] == 1)
                                 nr++;
                  if(M[i+1][y+1] == 1)
                                 nr++;
                  if(M[i][y] == 1) {
                             if (nr<2 || nr >3)
                                MOD[i][y] = 0; }
                  if (M[i][y] == 0)
                     if (nr==3)
                        MOD[i][y] = 1;
                  nr = 0;
               }

     for(int i = 0; i < n; i++)
             for(int y = 0; y < m; y++)
                     M[i][y] = MOD[i][y];
     }

afiseaza ceva de genul:
pasul t + x;
aici este matricea.
Doriti sa continuati? (d/n)

samd.

[•devilkind]

da pai algoritmul tau are complexitate o(N*M*T) ceea ce e prea mare ptr restrictiile problemei.

[•lache92]

dar avand in vedere ca e spre a fi citit in consola la fiecare pas nu e nici o problema

[•skyel]

nu chiar ca si la acm citesti date din consola si asta nu afecteaza timpul de rulare...

[•bogdan2412]

chiar daca citesti de la consola se pot redirectiona fisiere in stdin

Cod:

./program < fisier.in > fisier.out

sau se pot folosi pipe-uri

Cod:

cat fisier.in | ./program

[•lache92]

ceea ce vreoiam sa zic este ca oamenii nu percep diferente in timpul re rulare de ordinul milisecundelor asa ca nu conteaza care este complexitatea.

[•DITzoneC]

Iar ce incercau Bogdan si Razvan sa zica era ca se pot sesiza aceste diferente cu ajutorul calculatorului.

Cod:

time ./program < fisier.in > fisier.out

[•devilkind]

si un program cu o complexitate aprox de 1000*1000*1000000 poate dura destul de mult, ore intregi (daca nu si mai mult).