#include<stdio.h>
#include<stdlib.h>
#include <time.h>
typedef struct train
{ int ends[2];
} train;

int** allocate(int n)
{ int k,i;
  k=n;
  int **c=(int **)malloc(k*sizeof(int*));
  for( i=0;i<k;i++)
    { c[i] = (int *)malloc(k*sizeof(int));
    }
  return c;
}

int*** allocatethreed(int n,int x,int y)
{ int i,j;
  int *allElements = malloc(x * y * n * sizeof(int));
  int ***array3D = malloc(x * sizeof(int **));
  for(i = 0; i < x; i++)
  {
    array3D[i] = malloc(y* sizeof(int *));
    for(j = 0; j < y; j++)
    {
        array3D[i][j] = allElements + (i * y * n) + (j * n);
    }
  }
return array3D;

}

void initialize( int ***timegraph, int **graph,int n)
{
	int i,j,k;
	for(i=0;i<n;i++)
	{ for(j=0;j<n;j++)
		{ for(k=0;k<(n*n/4);k++)
			{	timegraph[k][i][j]=graph[i][j];
			}
		//printf(" %d ",graph[i][j]);
		}
	    // printf("\n");
	}
}

//int readint(const char* file_name)
void ReadFromFile (const char* file_name,int *length,train ** to,int *tot,int ***graph)
{
	FILE* file = fopen (file_name, "r");
	int i,j;
	fscanf (file, "%d",length);
	*graph = allocate(*length);
	for(i = 0; i < *length; i++)
	{	for(j = 0; j < *length; j++)
	        {	fscanf (file, "%d",(*(*graph+i)+j));
		}
	}
	fscanf (file, "%d",tot);
	train *t = (train *)malloc((*tot) *sizeof(train));
	for(i=0;i<*tot;i++)
	{	for(j=0;j< 2;j++)
		        {	fscanf(file, "%d", &(t[i].ends[j]));
			}
	}
	*to=t;
	fclose (file);
}

void printmatrix(int** p,int x,int y)              // to print matrice
{ int i,j;
  for( i=0;i<x;i++)
   { for(j=0;j<y;j++)
       { printf(" %d ",p[i][j]);
       }
     printf("\n");
   }
}
int isNotIn(int *t, int num,int n)
{ int i;
 //printf(" %d",num);
  for(i=0;i<n;i++)
	{ if(t[i] == num)
		{ return 0;
		}
	}
 return 1;

}

int findpath(int ***timegraph,int i,int j,int k,int *path,int tot,int num,int **graph)
{ int pathfound=0;
	// printf(" ddd");
while(pathfound == 0 ) {
	printf(" ccc");
	 if(timegraph[k][i][j] == 1 )
	{	path[k]=j;
		timegraph[k][i][j]=1;
		path[k+1]=-1;
		pathfound=1;
	}
	  else
	{	//srand ( time(NULL) );
		int n = rand()%num;
		// printf(" ");
		int cond=0;
		if ( timegraph[k][i][n] == 1)
		{	if( isNotIn(path,n,k) == 1)
			{	cond = 1;
			}
		}
		int count = 0;
		while( cond != 1 && count <(2*num))
			{	//srand ( time(NULL) );
				 n = rand()%num;
				if ( timegraph[k][i][n] == 1)
				{	if( isNotIn(path,n,k) == 1)
					{	cond = 1;
					}
				}

			}
		 if(cond =0 )
		{	if( isNotIn(graph[i],1,n) )		//no path from i to k exists;change i
 			{	pathfound =0;
				path[k-1]=0;
				// printf(" aaa");
				return pathfound;
			}
			else
			{	path[k]=i;			//path from i to k exists but is already occupied
			 	pathfound =findpath(timegraph,i,j,k+1,path,tot,num,graph);
			}
		}
		 else
		{	 path[k]=n;
			 timegraph[k][i][n]=1;
			 pathfound =findpath(timegraph,n,j,k+1,path,tot,num,graph);
			 printf(" bbb");
		}
	 }
	}
return pathfound;

}
int allowed(int *route, int ***timegraph,int n)
{ int i;
  for(i=0;i<n;i++)
	{	if(timegraph[i][route[i]][route[i+1]] == 1)
		{	return 0;
		}
	}
  return 1;
}

void copy(int* dest,int * source,int n)
{  int i;
  for(i=0;i<n;i++)
	{dest[i]=source[i];
	}
}
void update(int ***timegraph,int *route,int n)
{ int i;
  for(i=0;i<n;i++)
	{	timegraph[i][route[i]][route[i+1]] = 1;
	}
}


void crossover(int ** graph,int*** paths,float prob,int n,int tot,int size,int*** children,train* t)
{ int i;
  for(i =0;i<size;i++)
	{
		  float random = (float)(rand()%10)/10;
		printf("%f ", random);
		  if(random < prob )		//crossover
		   {	printf(" bbb ");
			int ***timegraph;
		  	timegraph=allocatethreed(n,(n*n/4),n);
		 	initialize(timegraph,graph,n);
			int first = rand()%size;
			int second= rand()%size;
			int j;
			for(j=0;j< tot; j++)
			{	int bin = rand()%2;
				if(bin == 1)
				{ 	if( allowed(paths[first][j],timegraph,n))
					{	 copy(children[i][j],paths[first][j],n);
					 	 update(timegraph,paths[first][j],n);
					}
				 	else
					{	 if( allowed(paths[second][j],timegraph,n))
						{	 copy(children[i][j],paths[second][j],n);
							  update(timegraph,paths[second][j],n);
						}
						 else
						{	findpath(timegraph,t[j].ends[0],t[j].ends[1],0,children[i][j],tot,n,graph);
						}
					}
				}
				else
				{ 	if( allowed(paths[second][j],timegraph,n))
					{	 copy(children[i][j],paths[second][j],n);
					 	 update(timegraph,paths[second][j],n);
					}
					else
					{	 if( allowed(paths[first][j],timegraph,n))
						{	copy(children[i][j],paths[first][j],n);
							update(timegraph,paths[first][j],n);
						}
						 else
						{	findpath(timegraph,t[j].ends[0],t[j].ends[1],0,children[i][j],tot,n,graph);
						}
					}
				}
			}
		}
	else				// no crossover;just copy a random string
	{	printf("aaa");
		int p = rand()%size,l;
		for(l=0;l<tot;l++)
		{	copy(children[i][l],paths[p][l],n);
		}
	}
   }
}
int fitness(int** solution,int tot)
{	int i,j,sum=0;
	for(i=0;i<tot;i++)
	{	j=0;
		while(solution[i][j] >0)
		{	sum = sum+1;
			j++;
		}
	}
	return sum;
}
void reproduction(int*** parents,int ***children,int tot,int size)
{	int *far = (int *)malloc(k*sizeof(int));
	for(i=0;i<size;i++)
	{	far[i]=fitness(parents[i],tot);
	}


int main()
{
	int **graph;
	int ***timegraph;
	int n,tot,i,j,size=8;
	train *t;
	//int length;
	ReadFromFile("input.txt",&n,&t,&tot,&graph);
	//printmatrix(graph,n);
	/*for(i=0;i<tot;i++)
	{	for(j=0;j< 2;j++)
		        {	printf("%d ", t[i].ends[j]);
			}
	     printf("\n");
	}*/
	timegraph=allocatethreed(n,(n*n/4),n);
	initialize(timegraph,graph,n);
	srand ( time(NULL) );
	int ***paths= allocatethreed(n,size,tot);
	for(i=0;i<size;i++)
	{	for(j=0;j<tot;j++)
		{	findpath(timegraph,t[j].ends[0],t[j].ends[1],0,paths[i][j],tot,n,graph);
		}
	printmatrix(paths[i],tot,n);
	printf("-----------\n");
	}
	int ***children= allocatethreed(n,size,tot);
	crossover(graph,paths,0.8,n,tot,size,children,t);
	printf("Children are \n");
	for(i=0;i<size;i++)
	{	printmatrix(children[i],tot,n);
		int sum =fitness(children[i],tot);
		printf("Fitness : %d \n",sum);
		printf("----------\n");
	}
	return 0;
}