/*	Room Assignement - 	di Enrico Sartorello	<enrico@sartorello.org>				*/
/*							<enrico@kpevillage.org				*/
/*													*/
/*	Questo programma cerca una soluzione ottimale all'assegnazione di n studenti in n/2 stanze 	*/
/*	considerando una tabella di "coefficienti d'attrito" tra i vari studenti.			*/
/*	L'algoritmo utilizzato č quello della tempratura simulata.					*/

#include <mpi.h>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>


int main (int argc, char *argv[]) {
	
	int 	N;			// numero di studenti
	int	c1,c2,			// due studenti coinvolti in un possibile scambio di stanze
		*a,			// array che conterrā l'assegnazione delle stanze agli studenti
		i,j,k=0,temp;
	float	sum=0,			// somma delle incompatibilitā di ogni coppia di studenti della migliore soluzione trovata
		new_sum,		// somma delle incompatibilitā di ogni coppia di studenti della soluzione appena generata
		t=1,			// temperatura
		**d;			// matrice N x N contenente il coefficiente d'attrito di ogni coppia di studenti
	double	elapsed_time;
	int	p,id;

	MPI_Init(&argc, &argv);
	
	MPI_Barrier(MPI_COMM_WORLD);
	elapsed_time = -MPI_Wtime();
	
	MPI_Comm_rank(MPI_COMM_WORLD, &id);
	MPI_Comm_size(MPI_COMM_WORLD, &p);
	
	
	if(argc != 2)
		{
		if (!id) printf("Command line: %s <m>\n", argv[0]);
		MPI_Finalize();
		exit(1);
		}

	N = atoi(argv[1]);
	
	a = (int *) malloc(sizeof(int *)*N);		// allocazione dinamica array
	
	d = (float**)malloc(N * sizeof(float*));	// allocazione dinamica matrice
	for(i=0;i<=N;i++)
	   {   
	   d[i]=(float*)malloc(N * sizeof(float*));
	   if (d[i] == NULL) {
	      printf("Cannot allocate enough memory\n");
	      MPI_Finalize();
	      }
	   }
     
	
	if(a == NULL || d == NULL)
		{
		printf("Cannot allocate enough memory\n");
		MPI_Finalize();
		}
	
	// soluzione iniziale scelta iterativamente
	for (i=0; i<N/2; i++) {
	   a[i]=i;
	   a[i+N/2]=i;
	   }
	   
	// generazione casuale della matrice contenente i coefficienti d'attrito   
	for (i=0; i<N-1; i++)
	   for (j=i+1; j<N; j++) {
	      d[i][j]=drand48()*10;
	      d[j][i]=d[i][j]; 
	   }
	   
	for (i=0; i<N; i++) d[i][i]=0;	// chiaramente la diagonale deve essere azzerata

	
	// funzione di valutazione
	for (i=0; i<N/2; i++)
	    for (j=0; j<N; j++) 
	       if (a[i]==a[j])
	          sum+=d[i][j];
	
	srand48(time(NULL)+id); 	// ogni processo effettua un reseed diverso, in modo tale da effettuare scambi differenti

	while (k<1000) {		// dopo 1000 iterazioni prive di nuove soluzioni migliori l'esecuzione viene fermata
	   new_sum=0;

	   do {
	      c1= drand48()*N;		// scelta casuale di due studenti che verranno scambiati di stanza
	      c2= drand48()*N;
	   } while (a[c1] == a[c2]);
	   
	   temp=a[c1];
	   a[c1]=a[c2];			// scambio effettivo
	   a[c2]=temp;
	   	   
	   for (i=0; i<N/2; i++)
	       for (j=0; j<N; j++) 	// valutazione della nuova funzione ottenuta
	          if (a[i]==a[j])
	             new_sum+=d[i][j];
		    
	   if ((new_sum<sum) || (drand48() <= pow(2.718,(sum-new_sum)/t))) {
	      sum = new_sum;
	      k=0;
	   } else {
	      temp=a[c1];
	      a[c1]=a[c2];
	      a[c2]=temp;
	      k++;
	   }
	   t=0.999*t;			// la temperatura scende
	}
	
	// ogni processo manda la sua miglior soluzione, e di esse viene presa la minima
	MPI_Reduce(&sum, &new_sum, 1, MPI_FLOAT, MPI_MIN, 0, MPI_COMM_WORLD);
	
	elapsed_time += MPI_Wtime();
	if(!id) {
		printf("Sum: %10.20f\n",new_sum);
	 	printf("Total elapsed time: %10.6f\n", elapsed_time);
		}
	MPI_Finalize();
	return 0;
}