#include <stdlib.h>
#include <stdio.h>
// #include <conio.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define MAX_NODES 2200			// maximalni pocet uzlu (2188 zadano)

FILE *src,*dest;

int countNodes=0;	// pocet uzlu
short track[MAX_NODES];		// posloupnost hamiltnovi kruznice
short matrix[MAX_NODES][MAX_NODES];		// matice sousednosti
bool isInTrack[MAX_NODES];		// je uz v tracku?

//--------------------------------------------------------------------
//-- init a utils ----------------------------------------------------
//--------------------------------------------------------------------
void Reset()
{
	for(int i=0; i<MAX_NODES; i++)
	{
		{
			isInTrack[i]=false;
			track[i]=false;
		}
	}
}

int Random(int max)
{
	int rnd;
	rnd=rand();
	return ((int)((max*rnd)/RAND_MAX));
}

int TrackLength(void)
{
	int length=0;
	int act;
	for (int i=0; i<(countNodes-1); i++)
	{
		act=matrix[track[i]][track[i+1]];
		if (act<=0)
			return -1;	// tak to preci jen neni cesta
		length=length+act;
	}
	return length;
}

void LoadData(short inexistEdgeMode=0)		// ulozeni grafu do matice
{
	char c, jmeno[30];
	short x,y;
	x=0; y=0;
	fscanf(src,"%s\n",jmeno);	// jmeno zahodit
	while (!feof(src))
	{
		c=fgetc(src);
		if (c=='\n')
		{
			if (y==0)
				countNodes=x;
			x=0; y=y+1;
			continue;
		}
		else if ((c>='1') && (c<='9')) matrix[x][y]=c-'0'; 
		else if ((c>='A') && (c<='Z')) matrix[x][y]=c-'A'+10;
		else if (c=='0' && x!=y)
		{
			matrix[x][y]=inexistEdgeMode; // nahrada neexistujicich hran
		} else	// na diagonalu nulu
		{
			matrix[x][y]=0;
		}
		x++;
	}
	for (int i=0; i<countNodes; i++)
		track[i]=-1;
}

//--------------------------------------------------------------------
//-- posovo heurestika -----------------------------------------------
//--------------------------------------------------------------------
int lastTrack=0;	// posledni uzel v tracku

bool Extension()	// pridani uzlu
{
	for (int i=0; i<countNodes; i++)
	{
		if (isInTrack[i]==false && matrix[i][track[lastTrack]]>0)		// jeste neni v ceste a jde spojit s poslednim
		{
			track[++lastTrack]=i;
			isInTrack[i]=true;
			return true;	// neco jsem pridal
		}
	}
	return false;	// uz nic nepridam
}

void Swap(int l, int r)	// obrati poradi mezi l a r
{
	static swap=0;
	swap++;
	int tmp, cykl;
	cykl=(int) (r-l+1)/2;		// pocet prohazovani
	for (int i=0; i<cykl; i++)
	{
		tmp=track[l+i];
		track[l+i]=track[r-i];
		track[r-i]=tmp;
	}
}

int Modify(int x)	// x spojit s poslednim a x+1 se stava poslednim
{
	while (x<lastTrack)		// zkusime projit az do konce tracku
	{
		if (matrix[track[x]][track[lastTrack]]>0)	// je cesta z x do posledniho
		{
			Swap(x+1,lastTrack);	// prohodit poradi
			return ++x;	// od priste modifujem od x+1
		}
		x++;
	}
	return -1;
}

bool PosovHeuristics(int startNode)	// hledani prvniho reseni tsp
{
	int change=1;	// prohazovat s poslednim
	int iter=0;
	const maxIter=countNodes*500;

	track[0]=startNode;	// prvni v tracku je startovni mesto
	isInTrack[startNode]=true;
	lastTrack=0;
	while (iter<maxIter)
	{
		while (Extension()) {};	// dokud jde prodluzovat prodluzuj
		if (lastTrack==countNodes-1 && matrix[track[lastTrack]][track[0]]>0)	// je track uz hamilton? (je track plnej a existuje cesta z posledniho do prvniho?)
		{
			return true;
		} else // neni - zkusime modifikovat
		{
			change=Modify(change);
			if (change==-1)	// nejde modifikovat
				change=Modify(0);	// zkusim od zacatku
			if (change==-1)	// fakt nejde
			{
				printf("posov neexistuje\n");
				return false;	// hamilton nebude
			}
		}
		iter++;
	}
	printf("hodnekrat posov\n");
	return false;
}

//--------------------------------------------------------------------
//-- simulovane ochlazovani ------------------------------------------
//--------------------------------------------------------------------
double temp;	// teplota
int price;	// cena

void SimulatedCooling()
{
//	int iter;
	int delta, a, b;
	double proc=0;
	int nove=0;
	int stare=0;
	double rnd;
	int zlepseni=0;
	int zlepseniStejneCount=0;
	int zlepseniOld=0;
	int zhorseni=0;
	int sqrCountNodes=countNodes*countNodes;
	temp=50;
	while (temp>0.07 && zlepseniStejneCount<5)
	{
//		iter=0;
//		while (iter<countNodes)	// equilibrium
		{
//			iter++;
			for (a=0; a<countNodes-1; a++)
			{
				for (b=a+2; b<countNodes-1; b++)
				{
//			a=Random(countNodes-1);
//			b=Random(countNodes-1);
					if (matrix[track[a]][track[b]]>0 && matrix[track[a+1]][track[b+1]]>0)	// vede cesta
					{
						stare=matrix[track[a]][track[a+1]]+matrix[track[b]][track[b+1]];
						nove=matrix[track[a]][track[b]]+matrix[track[a+1]][track[b+1]];
						delta=stare-nove;
						if (delta>0)	//	nalezene je lepsi - prijmout
						{
							Swap(a+1,b);
							zlepseni++;
//							iter=0;	// pri nalezeni vynulujem equilibrium
//							printf("nalezeno lepsi stare: %d nove: %d\n",stare,nove);
						} else	if (delta<0) // nalezene je horsi
						{
							proc=exp(delta/temp);	// proc=e^(-|delta|/temp)
							rnd=(double)rand()/RAND_MAX;
							if (proc>rnd)	// stejne prijmem
							{
								Swap(a+1,b);
								zhorseni++;
							}
						}
					}
				}
			}
		}
		temp=temp*0.95;	// cooling
		printf("temp %f, len: %d proc: %f zlep: %d zhor: %d\n",temp,TrackLength(),proc,zlepseni,zhorseni);
		if (zlepseni==zlepseniOld)	// pokud se dlouho nezlepsil, zastavim vypocet
			zlepseniStejneCount++;
		else
			zlepseniStejneCount=0;
		zlepseniOld=zlepseni;
	}
	printf("finished lentgh %d\n",TrackLength());
}

//--------------------------------------------------------------------
//-- backtracking ----------------------------------------------------
//--------------------------------------------------------------------
/*
int trackLength=0;	// delka kruznice
int trackBestLength=0;
int startNode=0;	// startovni uzel
short trackBest[MAX_NODES];	// zatim nejlepsi kruznice
void BackTracking(int openNode, int trackNodes)	// rekurzivni backtracking (prohledani do hloubky)
{
	if (trackNodes==countNodes-1 && track[openNode]==-1 && matrix[openNode][startNode]>0)	// nalezen hamilton
	{
		trackLength=trackLength+matrix[openNode][startNode];
		track[openNode]=startNode;
		if (trackLength<trackBestLength || trackBestLength<0)	// zatim nejlepsi reseni ulozit
		{
			trackBestLength=trackLength;
			for (int i=0; i<countNodes; i++)
			{
				trackBest[i]=track[i];
			}
		}
		trackLength=trackLength-matrix[openNode][startNode];
		track[openNode]=-1;
		return;	// uz byly vsechny uzly, netreba for
	}
	for (int i=0; i<countNodes; i++)
	{
		if (openNode!=i && track[i]==-1 && matrix[openNode][i]>0)
		{
			trackLength=trackLength+matrix[openNode][i];
			track[openNode]=i;
			if (trackLength<trackBestLength || trackBestLength<0)	// muze bejt lepsi?
				BackTracking(i, trackNodes+1);
			trackLength=trackLength-matrix[openNode][i];
			track[openNode]=-1;
		}
	}
}
*/

//--------------------------------------------------------------------
//-- main ------------------------------------------------------------
//--------------------------------------------------------------------
int main(int argc, char *argv[])
{
	short method=0;	
	short inexistRep=0;
  	char str[30];
	char strin[30];

	printf("Travelling Salesman Problem 2005 by GS.\n");
	printf("Usage: 5tsp.exe inputfile [inexistEdgeReplace=0]\n");
	printf("Output file: out_'inexistEdgeReplace'_'inputfile'\n");
	printf("\n");

	if (argc>1) 
		strcpy(strin,argv[1]);
	else 
		return EXIT_SUCCESS;

	if ((src=fopen(strin,"r"))==NULL) 
	{
		printf(" Error opening %s input file.\n",strin);
		return EXIT_FAILURE;
	}
    sprintf(str,"out_%d_%s",inexistRep,strin);
    if ((dest=fopen(str,"w"))==NULL) {
			printf("Error opening %s output file.\n",str);
      fclose(src);
      return EXIT_FAILURE;
    }
	if (argc>2) inexistRep=atoi(argv[2]);
	printf("  inexist edge replace with %d selected. Working.....\n\n",inexistRep);

	srand((unsigned)time(NULL));
	LoadData(inexistRep);
/*
	//backtracking
	startNode=0;
	BackTracking(startNode, 0);
	fprintf(dest,"%d\n\n",trackBestLength);
	fprintf(dest,"%d",trackBest[0]);
	for (int i=1; i<countNodes; i++) 
		fprintf(dest,",%d",trackBest[i]);
*/
/*	for (int i=1; i<10000; i=i*10)
	{
		printf("e: %f (i=%d)\n",exp((float)-10/i),i);
	}
	system("PAUSE");
	*/
	fprintf(dest,"pocet mest: %d\n",countNodes);
	fprintf(dest,"0 v matici nahrazena %d\n",inexistRep);
	fprintf(dest,"\n");

	for (int i=0; i<3; i++)
	{
		Reset();
		if (PosovHeuristics(Random(countNodes)))
		{
			fprintf(dest,"delka prvni nalezene kruznice: %d\n",TrackLength());
			printf("initial track length: %d\n",TrackLength());
			SimulatedCooling();
			fprintf(dest,"konecna delka: %d\n",TrackLength());
			fprintf(dest,"\n");
/*		fprintf(dest,"cesta:\n");
		fprintf(dest,"%d",track[0]);
		for (int i=1; i<countNodes; i++) 
			fprintf(dest,",%d",track[i]);
*/		}
		else 
		{
		fprintf(dest,"nenalezl jsem kruznici\n");
		}
	}
	printf("\n  ....................done.\n\n");  
	fclose(dest); 
	fclose(src);
	system("PAUSE");
	return EXIT_SUCCESS;
}