// three_switch is left to reader as an exercise

#define T 17
#define ITERATIONS 20						// Number of runs

int d[T][T];

2lp_main()
{
int tour[T];
int best_tour[T];
int best_distance;

	seed(2981);			// Seed random number generator
	best_distance = 1e6;	// Initialize to very high value
	data();

	and(int i=0;i<ITERATIONS;i++) {
		get_next_random_tour(tour);				// Generate random tour
		apply_hillclimb(tour);					// Reach local optimum
		compare(tour,best_distance,best_tour);		//Record best
	}
	printf("The best we found was %d\n",best_distance);
}

data()
{
	d =	{0,633,257,91,412,150,80,134,259,505,353,324,70,211,268,246,121, 
		633,0,390,661,227,488,572,530,555,289,282,638,567,466,420,745,518,
		257,390,0,228,169,112,196,154,372,262,110,437,191,74,53,472,142,
		91,661,228,0,383,120,77,105,175,476,324,240,27,182,239,237,84,
		412,227,169,383,0,267,351,309,338,196,61,421,346,243,199,528,297,
		150,488,112,120,267,0,63,34,264,360,208,329,83,105,123,364,35,
		80,572,196,77,351,63,0,29,232,444,292,297,47,150,207,332,29,
		134,530,154,105,309,34,29,0,249,402,250,314,68,108,165,349,36, 
		259,555,372,175,338,264,232,249,0,495,352,95,189,326,383,202,236,
		505,289262,476,196,360,444,402,495,0,154,578,439,336,240,685,390,
		353,282,110,324,61,208,292,250,352,154,0,435,287,184,140,542,238,
		324,638,437,240,421,329,297,314,95,578,435,0,254,391,448,157,301,
		70,567,191,27,346,83,47,68,189,439,287,254,0,145,202,289,55,
		211,466,74,182,243,105,150,108,326,336,184,391,145,0,57,426,96,
		268,420,53,239,199,123,207,165,383,240,140,448,202,57,0,483,153,
		246,745,472,237,528,364,332,349,202,685,542,157,289,426,483,0,336, 
		121,518,142,84,297,35,29,36,236,390,238,301,55,96,153,336,0 };
}

find_next_random_sequence(int q[], int n)
{
int temp, rand;

	and(int i=0;i<n;i++) 
		q[i] = i;
	and(int i=0;i<n;i++) {
		rand = random()*n-i; 		// random integer 
								// between 0 and n-i-1
		temp = q[i+rand];
		q[i+rand] = q[i];
		q[i] = temp;
	} 
}

#define VENICE 0
get_next_random_tour(int q[])
{
	find_next_random_sequence(q[1],T-1);		// From above
	and(int c=1;c<T;c++)					// Add one to eliminate 0
		q[c] = q[c] + 1;
	q[0] = VENICE;							// We’re opening in Venice
}

#define fail 0==1
two_switch(int path[])
{
int temp1,temp2;
                                  
	and(int i=0;i<T-3;i++)
		and(int j=i+2;j<T-1;j++){
			temp1=d[path[i]][path[i+1]]+
					d[path[j]][path[j+1]];
			temp2=d[path[i]][path[j]]+
					d[path[i+1]][path[j+1]];
			if temp1 > temp2;
			then {
				switch_2(i,j,path);
				return;
			}
		}
	fail;
}

switch_2(int i,int j,path[])				// Switch between cities i and j
{
int m,temp;
	m = j;
	and(int n=i+1;n<m;n++){
		temp=path[n];
		path[n]=path[m];
		path[m]=temp;
		m = m-1;
	}
}

apply_hillclimb(int tour[])
{
	and(;;)
		c_either three_switch(tour);
		or two_switch(tour);
		or break;				// Local optimum reached
}

compare(int tour[], & best_distance,best_tour[])
{
int dist;
	
	dist = 0;
	and(int c=1;c<T;c++)
			dist = dist + d[tour[c-1]][tour[c]];
	dist = dist + d[T-1][0];
	if dist < best_distance;
	then {
		best_distance = dist;
		and(int c=0;c<T;c++)
			best_tour[c] = tour[c];
	}
}
 