Algoritmi e strutture dati/Progetti/Life/Stesura I

  /* Attention please! ;)
  * Questo software e l'annessa documentazione
  * sono distribuiti sotto la GNU policy. 
  * [se non sai cos'è, vergognati, e poi acculturati un po':
  * [1]
  *
  * Il fine della distribuzione gratuita è per combattere il
  * fiorente "mercato" dei progettini. Sei libero di prenderne
  * spunto, se hai dubbi o non capisci qualcosa, let me know!
  * bye! min:o) 
  * mail: mino@ngi.it 
  * ICQ: 57553717
  *
  * Il progetto è stato valutato 4 (cioè il massimo)
  * durante l'appello di Febbraio-Aprile 2002. 
  */
  
  #include <stdlib.h>
  #include <stdio.h>
  #define HASHTABLE_SIZE 11		// Grandezza del lato della tabella hash"
  
  struct cella {
      int x, y;				// Coordinate della cella"
  	int tempo;				// Tempo in cui e' nata la cella"
  	struct cella *next;		// Prossimo elem. nella hash"
  	struct cella *prossimo_sul_piano;	// Per la lista ordinata"
  	struct cella *prossimo_nel_blocco;	// Per i gruppi di blocchi"
  	struct blocco *padre;				// Blocco rappresentativo"
  };
  
  struct blocco {
  	int num;						// Numero di celle nel blocco"
  	struct cella *prima_cella;		// Prima cella del blocco"
  	struct blocco *prossimo_blocco;	// Puntatore al prossimo blocco"
  };
  
  typedef struct cella cella;
  typedef struct blocco blocco;
  
  int tempo = 2;					// Tempo iniziale. Lo poniamo uguale"
  								// a due per una piccola ottimizzazione"
  								// (vedere relazione)."
  int dimensione_piano = 0;		// Dimensione del piano"
  
  cella *primo_sul_piano = NULL;	// Primo elemento sul piano"
  blocco *primo_blocco = NULL;	// Primo blocco"
  int n_blocchi = 0;				// Numero di blocchi sul piano"
  cella *hashtable[HASHTABLE_SIZE][HASHTABLE_SIZE]; // Tabella Hash
  
  void crea(int n) {
  	/* Crea un piano di dimensioni n * n."
  	Dobbiamo solo verificare se un piano esiste gia', e se si', eliminarlo. */"
  	if (primo_sul_piano != NULL) {"
  		int i,j;"
  		cella *q, *p;"
  		blocco *r, *s;"
  
  		/* Passo 1) Svuota le liste della hashtable. */"
  		for (i = 0; i < HASHTABLE_SIZE; i++) {"
  			for (j = 0; j < HASHTABLE_SIZE; j++) {"
  				hashtable[i][j] = NULL;"
  			}"
  		}"
  
  		/* Passo 2) Svuota la lista prossimo_sul_piano. */"
  		q = primo_sul_piano;"
  		while(q) {"
  			p = q;"
  			q = q->prossimo_sul_piano;"
  			free(p);"
  		}	"
  		primo_sul_piano=NULL;"
  
  
  		/* Passo 3) Svuota la lista dei blocchi. */"
  		r = primo_blocco;"
  		while(r) {"
  			s = r;"
  			r = r->prossimo_blocco;"
  			free(s);"
  		}	"
  		primo_blocco=NULL;"
  
  	}	"
  	/* Infine, inizializza (o resetta) dimensione_piano, tempo"
  	e numero di blocchi. */"
  	dimensione_piano = n;"
  	tempo = 2;"
  	n_blocchi = 0;"
  }
  int hash(int key) {
  	/* Calcola l'hash di x (usando il metodo del resto). */"
  	return (key % HASHTABLE_SIZE);"
  }
  
  cella *cerca(int x, int y, int t) {
  	/* Restituisce un puntatore alla cella di coordinate (x, y) viva al tempo t."
  	Se il parametro t e' -1, il tempo non viene considerato nella ricerca. */"
  	cella *p = hashtable[hash(x)][hash(y)], *q = NULL;"
  	while (p && (p->x < x || (p->x == x && p->y < y))) {"
  		q = p;"
  		p = p->next;"
  	}		"
  	"
  	if (p && p->x==x && p->y == y && ((t!=-1 && p->tempo <= t) || t==-1))"
  		return p;		// trovata!"
  	else"
  		return NULL;	// non esiste!"
  }
  
  void crea_blocco(cella *origine) {
  	/* Crea un nuovo blocco con la cella puntata da origine. */"
  	blocco *r;"
  	/* Passo 1) Alloca la memoria. */"
  	r = calloc(1,sizeof(blocco));"
  	if(!r) {"
  		fprintf(stderr,""Errore nella creazione del blocco.\n"");"
  		exit(-1);	"
  	}"
  	"
  	/* Passo 2) Inizializza le variabili. */"
  	origine->prossimo_nel_blocco=NULL;"
  	origine->padre = r;"
  	r->num = 1;"
  	r->prima_cella = origine;"
  	r->prossimo_blocco = NULL;"
  	"
  	/* Passo 3) Inserisce nella lista dei blocchi. */"
  	if (!primo_blocco)"
  		primo_blocco = r;"
  	else {"
  		r->prossimo_blocco = primo_blocco;"
  		primo_blocco = r;"
  	}"
  
  	/* Il tempo e' negativo se la cella era parte di un blocco"
  	cancellato in precedenza. In tal caso lo ""resettiamo"". */"
  	if (origine->tempo < 0)"
  		origine->tempo = origine->tempo * (-1);"
  
  	/* Passo 4) Aggiorniamo il numero di blocchi sul piano */"
  	n_blocchi++;"
  }
  
  void cancella_blocco(blocco *eliminare) {
  	/* Cancella il blocco specificato dalla lista dei blocchi. */"
  	blocco *t = primo_blocco;"
  	blocco *s = NULL;"
  	"
  	/* Passo 1) Cancella dalla lista dei blocchi. */"
  	if (t == eliminare)	{"
  		primo_blocco = eliminare->prossimo_blocco;"
  	} else {"
  		while (t != eliminare) {"
  			s = t;"
  			t = t->prossimo_blocco;"
  		}"
  		s->prossimo_blocco = t->prossimo_blocco;"
  	}"
  	"
  	/* Passo 2) Liberiamo la memoria. */"
  	free(eliminare);"
  	"
  	/* Passo 3) Aggiorniamo il numero di blocchi sul piano. */"
  	n_blocchi--;"
  }
  void unisci_blocchi(cella *uno, cella *due) {
  	/* Unisce i blocchi a cui appartengono le celle uno e due."
  	Come ottimizzazione, uniamo sempre il blocco piu' piccolo a"
  	quello piu' grande. */"
  	cella *p;"
  	blocco *eliminare;"
  	if (uno->padre->num > due->padre->num) {"
  		/* Passo 1) Aggiorniamo il numero di celle nel blocco. */"
  		(uno->padre->num) += (due->padre->num);"
  		eliminare = due->padre;				"
  		p = uno->padre->prima_cella;"
  		"
  		/* Passo 2) Aggiungiamo le nuove celle in coda. */"
  		while (p->prossimo_nel_blocco) {"
  			p=p->prossimo_nel_blocco;"
  		}"
  		p->prossimo_nel_blocco = due->padre->prima_cella;"
  		p = due->padre->prima_cella;"
  		"
  		/* Passo 3) Aggiorniamo il puntatore ""padre"". */"
  		while (p) {"
  			p->padre = uno->padre;"
  			p=p->prossimo_nel_blocco;"
  		}"
  
  		/* Passo 4) Eliminiamo il blocco. */"
  		cancella_blocco(eliminare);"
  	} else {"
  		/* Passo 1) Aggiorniamo il numero di celle nel blocco. */"
  		(due->padre->num) += (uno->padre->num);"
  		eliminare = uno->padre;				"
  		p = due->padre->prima_cella;"
  				"
  		/* Passo 2) Aggiungiamo le nuove celle in coda. */"
  		while (p->prossimo_nel_blocco) {"
  			p=p->prossimo_nel_blocco;"
  		}"
  		p->prossimo_nel_blocco = uno->padre->prima_cella;"
  		p = uno->padre->prima_cella;"
  				"
  		/* Passo 3) Aggiorniamo il puntatore ""padre"". */"
  		while (p) {"
  			p->padre = due->padre;"
  			p=p->prossimo_nel_blocco;"
  		}"
  		"
  		/* Passo 4) Eliminiamo il blocco. */"
  		cancella_blocco(eliminare);"
  	}"
  }
  
  void rimuovi_cella_dal_blocco(cella *eliminare) {
  	/* Cancella la cella dal blocco. */"
  	cella *p, *q;"
  	blocco *b;"
  	int dx, dy;"
  	"
  	/* Caso 1) Se e' l'unica cella del blocco allora dobbiamo "
  	eliminare anche il blocco stesso. */"
  	if (eliminare->padre->num <= 1)"
  		cancella_blocco(eliminare->padre);"
  	"
  	/* Caso 2) Se nel blocco ci sono due celle (ovvero se la cella"
  	ha solo un vicino) possiamo semplicemente rimuoverla dal blocco. */"
  	if (eliminare->padre->num == 2) {"
  		if(eliminare->padre->prima_cella == eliminare)	// e' la prima."
  			eliminare->padre->prima_cella = eliminare->prossimo_nel_blocco;"
  		else											// e' la seconda."
  			eliminare->padre->prima_cella->prossimo_nel_blocco = NULL;"
  		eliminare->padre->num=1;"
  	}"
  
  	/* Caso 3) Altrimenti cancello il blocco e lo ricreo partendo da"
  	ogni vicino della cella da eliminare ed effettuando una visita "
  	in profondita' in cui unisco i blocchi adiacenti. */"
  	if (eliminare->padre->num > 2) {"
  		b = eliminare->padre;"
  		q = NULL;"
  
  		/* Passo 1) Per marcare le celle del blocco da ricalcolare, rendo"
  		// il tempo negativo e azzero il puntatore ""padre"". */"
  		for(p = b->prima_cella; p; p = p->prossimo_nel_blocco) {"
  			p->tempo = p->tempo * (-1);"
  			p->padre = NULL; "
  		}"
  		"
  		/* Passo 2) Cancello il blocco originale. */"
  		cancella_blocco(b);"
  
  		/* Passo 3) Per ogni p appartenente alla lista delle celle nel blocco... */"
  		for(p = primo_sul_piano; p; p = p->prossimo_sul_piano) {"
  			if(p->tempo > 0) continue;"
  			if(p->x==eliminare->x && p->y==eliminare->y) continue;"
  			crea_blocco(p);"
  
  			/* ...per ogni q vicino di p... */"
  			for (dx=p->x-1 ; dx<=p->x+1 ; dx++) {"
  				if (dx<0 || dx>dimensione_piano) continue;"
  				for (dy=p->y-1 ; dy<=p->y+1 ; dy++) {"
  					if (dx==p->x && dy==p->y) continue;"
  					if (dy<0 || dy>dimensione_piano) continue;"
  					q=cerca(dx, dy, -1);"
  					if (q && q->padre!=p->padre) {"
  						if (q->tempo < 0) crea_blocco(q);"
  						/* ...unisci i blocchi di p e q. */"
  						unisci_blocchi(p,q);"
  					}"
  				}"
  			}"
  		}"
  	}"
  }
  
  void inserisci(int x, int y, int t) {
  	/* Inserisce una cella di coordinate (x, y). */"
  	cella *p = hashtable[hash(x)][hash(y)];"
  	cella *q = NULL, *r;"
  	int dx, dy;"
  
  	/* Passo 1) Calcola il valore della hash e scorre la lista ordinata"
  	fino a trovare un elemento maggiore della cella. */"
  	while (p && (p->x < x || (p->x == x && p->y < y))) {"
  		q = p;"
  		p = p->next;"
  	}"
  
  	/* Passo 2) Se la cella esiste gia', esce. */"
  	if (p && p->x==x && p->y==y) {"
  		return;"
  	}"
  
  	/* Passo  3) Alloca la cella. */"
  	r = calloc(1,sizeof(cella));"
  	if(!r) {"
  		fprintf(stderr,""Errore nell'inserimento della cella.\n"");"
  		exit(-1);	"
  	}"
  
  	/* Passo 4) Inizializza alcune variabili. */"
  	r->x = x;"
  	r->y = y;"
  	r->tempo = t;"
  	r->prossimo_nel_blocco=NULL;"
  	r->padre=NULL;"
  	r->prossimo_sul_piano=NULL;"
  	r->next = p;"
  
  	/* Passo 5) La inserisce nella lista, spostando i puntatori. */"
  	if (q == NULL) {"
  		hashtable[hash(x)][hash(y)] = r;"
  	}"
  	else {"
  		q->next = r;"
  	}"
  	"
  	/* Passo 6) La inserisce nella lista prossimo_sul_piano. */"
  	p = primo_sul_piano;"
  	q = NULL;"
  
  	while (p && (p->x < x || (p->x == x && p->y < y))) {"
  		q = p;"
  		p = p->prossimo_sul_piano;"
  	}"
  
  	if (q == NULL) {"
  		r->prossimo_sul_piano = primo_sul_piano;"
  		primo_sul_piano = r;"
  	}"
  	else {"
  		q->prossimo_sul_piano = r;"
  		r->prossimo_sul_piano = p;"
  	}"
  
  
  	/* Passo 7) Controlla se ha vicini e, se si', si aggiunge ai loro blocchi. */"
  	q = NULL;"
  	crea_blocco(r);"
  	for (dx=x-1 ; dx<=x+1 ; dx++) {"
  		if (dx<0 || dx>dimensione_piano) continue;"
  		for (dy=y-1 ; dy<=y+1 ; dy++) {"
  			if (dy<0 || dy>dimensione_piano) continue;"
  			if (dx==x && dy==y) continue;"
  			q = cerca(dx, dy, -1);"
  			if (q && q->padre != r->padre) {"
  				unisci_blocchi(r,q);"
  			}"
  		}"
  	}"
  }
  
  void cancella(int x, int y) {
  	/* Cancella la cella di coordinate (x,y). */"
  	cella *p, *q;"
  
  	/*	Passo 1) Cancella dalla lista nell'hashtable. */"
  	p = hashtable[hash(x)][hash(y)];"
  	q = NULL;"
  	while (p && (p->x < x || (p->x == x && p->y < y))) {"
  		q = p;"
  		p = p->next;"
  	}"
  
  	if (!(p && p->x==x && p->y == y)) {"
  		return;			// se la cella non esiste, esce."
  	}"
  
  	if (q==NULL) "
  		hashtable[hash(x)][hash(y)] = p->next;"
  	else"
  		q->next = p->next;"
  
  	/*	Passo 2)  Cancella dalla lista prossimo_sul_piano. */"
  	p = primo_sul_piano;"
  	q = NULL;"
  
  	while (p && (p->x < x || (p->x == x && p->y < y))) {"
  		q = p;"
  		p = p->prossimo_sul_piano;"
  	}"
  	"
  	if (!(p && p->x==x && p->y == y)) {"
  		return;			// se la cella non esiste, esce."
  	}"
  
  	if (primo_sul_piano == p) "
  		primo_sul_piano = p->prossimo_sul_piano;"
  	else"
  		q->prossimo_sul_piano = p->prossimo_sul_piano;"
  
  	/*	Passo 3)  La rimuove dal suo blocco. */"
  	rimuovi_cella_dal_blocco(p);"
  
  	/*	Passo 4)  Dealloca la memoria. */"
  	free(p);"
  }
  
  void listacelle() {
  	/* Stampa la lista delle celle in un ordine non decrescente,"
  	prima secondo le x poi le y. In questa implementazione e' "
  	sufficiente scorrere la lista prossimo_sul_piano. */"
  	cella *q = primo_sul_piano;"
  
  	while(q) {"
  		printf(""%d %d\n"", q->x, q->y);	"
  		q = q->prossimo_sul_piano;"
  	}"
  }
  
  void maxdimblocco() {
  	/* Stampa la dimesione del massimo blocco, scorrendo la "
  	lista dei blocchi, cercando il valore massimo del campo num. */"
  	int max = 0;"
  	blocco *p;"
  
  	for (p=primo_blocco; p; p=p->prossimo_blocco) {"
  		if (p->num > max)"
  			max = p->num;"
  	}"
  	printf(""m %d\n"",max);"
  }
  
  void evolvi(int steps) {
  	/* Calcola la situazione del piano dopo ""steps"" generazioni. */"
  	cella *p = primo_sul_piano;"
  	int x, y, dx, dy, ddx, ddy, i, j;"
  	"
  	while(steps > 0) {"
  		/* Per ogni cella p (usando la lista prossimo_sul_piano): */"
  		while(p) {"
  			if (p->tempo > tempo) {	// E' una cella appena nata, e non va"
  				p = p->prossimo_sul_piano; // quindi considerata."
  				continue;"
  			}"
  			y = p->y;"
  			x = p->x;"
  			j = 0;"
  			"
  			/* Per cella (viva o morta) vicina. */"
  			for (dx=x-1 ; dx<=x+1 ; dx++) {"
  				if (dx<0 || dx>dimensione_piano) continue;"
  				for (dy=y-1 ; dy<=y+1 ; dy++) {"
  					i = 0;"
  					if (dx==x && dy==y) continue;"
  					if (dy<0 || dy>dimensione_piano) continue;"
  
  					/* Per ogni vicino (vivo o morto) dei suoi vicini. */"
  					for (ddx=dx-1 ; ddx<=dx+1 ; ddx++) {"
  						if (ddx<0 || ddx>dimensione_piano) continue;"
  						for (ddy=dy-1 ; ddy<=dy+1 ; ddy++) {"
  							if (ddx==dx && ddy==dy) continue;"
  							if (ddy<0 || ddy>dimensione_piano) continue;"
  							"
  							/* Conta quanti ""vicini-dei-vicini"" son vivi */"
  							if (cerca(ddx, ddy, tempo)) i++;"
  						}"
  					}"
  					/* La cella (dx, dy) nasce */"
  					if (i==3) inserisci(dx, dy, tempo+1);"
  					"
  					/* Conta quanti ""vicini"" son vivi */"
  					if (cerca(dx, dy, tempo)) j++;"
  				}"
  			}"
  		"
  			/* Se una cella va eliminata, la segno come ""morta"","
  			ponendo il tempo uguale a uno. */"
  			if (j <= 1 || j >= 4) cerca(x,y,-1)->tempo=1;"
  			p = p->prossimo_sul_piano;			"
  		}"
  	"
  		/* Elimino le celle segnate come ""morte"". */"
  		p = primo_sul_piano;"
  		while(p) {"
  			x = p->x;"
  			y = p->y;"
  			i = p->tempo;"
  			p=p->prossimo_sul_piano;"
  			if (i==1) cancella(x,y);"
  		}"
  		steps--;	"
  		tempo++;"
  		p = primo_sul_piano;"
  	}"
  }
  
  int main(void) {
  	char input;"
  	int x,y;"
  
  	while (scanf(""%c"",&input) != -1) 	{"
  		switch(input) {"
  			case 'c':"
  				/* Crea il piano */"
  				scanf(""%d"",&x);"
  				crea(x);"
  				break;"
  
  			case 'i':				"
  				/* Inserisce nel piano una cella di coord (x,y) */"
  				scanf(""%d %d"",&x,&y);"
  				if (dimensione_piano > 0 && x >= 0 && y >= 0 && x <= dimensione_piano && y <= dimensione_piano)"
  					inserisci(x,y,tempo);"
  				break;"
  
  			case 'e':"
  				/* Evolve lo stato del piano di x passi. */"
  				scanf(""%d"",&x);"
  				if (dimensione_piano > 0 && x > 0) {"
  					evolvi(x);"
  					printf(""e %d\n"",x);"
  				}"
  				break;"
  
  			case 'l':"
  				/* Lista le celle del piano. */"
  				printf(""l\n"");"
  				listacelle(); "
  				printf(""-1\n"");"
  				break;"
  
  			case 'b':"
  				/* Stampa il numero di blocchi. */"
  				printf(""b %d\n"",n_blocchi);"
  				break;"
  				"
  			case 'm':"
  				/* Stampa la dimensione del massimo blocco. */"
  				maxdimblocco(); "
  				break;"
  			"
  			case 'f':"
  				/* Fine del programma. */"
  				printf(""f\n"");"
  				return 0;			"
  				break;"
  		}"
  	}"
  	return 0;"
  }
  
  
  /* è tutto, semplice no? */