/* Out of time!!!
 * The program is not complete, so only the solving decision works. :-(
 */

#include <ctype.h>
#include <stdio.h>
#include <string.h>

#define SWAP(A,B) do { (A)^=(B); (B)^=(A); (A)^=(B); } while (0)

unsigned char 	SolveFlag = 0,
		ShowFlag = 0,

		FinalPermutation [16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ,15 ,16 },
		SourcePermutation [16],
		PermutationFilter [17],
		InversedFilter [17],
		CurrentPermutation[16],
		PtrIndex[16],
		CycleSize[16],
		FlagField[16],
		FlagField2[16],

		Solution[2048][2];
unsigned long   SolCnt = 0;
int             SpaceX, SpaceY;

void Read16 (char *filename, unsigned char *permutation)
{
	FILE *f;
	char  temp_str[10],
	      ReadFlag[15],
	      XFlag = 0;
	int   ret,
	      i;

	if ( !(f = fopen (filename, "rt")) ) {
		fprintf (stderr, "Error: Cannot read the file `%s'.\n", filename);
		exit (-1);
	}
	/* Clear the reading flags. */
	for ( i = 0; i < 16; i++ )
		ReadFlag[i] = 0;

	/* Read the file */
	for ( i = 0; i < 16; i++ ) {
		ret = fscanf (f, "%s", temp_str);
		if (ret != 1) {
			fprintf (stderr, "Error: Unexpected error occured while reading `%s'.\n",
				 filename);
			exit (-1);
		}
		/* Decide whether it is an `X' character */
		if (!XFlag && strlen(temp_str) == 1 && toupper(temp_str[0]) == 'X') {
			permutation[i] = 16;
			ReadFlag[15] = 1;
			XFlag = 1;
		} else { /* It should be a number from {1,...,15} */
			permutation[i] = ret = atoi (temp_str);
			if (ret > 15 || !ret) {
				fprintf (stderr, "Error: Wrong entry in file `%s' [%s].\n", filename, temp_str);
				exit (-1);
			}
			if (ReadFlag[ret-1]) {
				fprintf (stderr, "Error: Number %d read twice.\n", ret);
				exit (-1);
			}
			ReadFlag[ret-1] = 1;
		}

	}

	/* Check if the permutation is complete. */
	for ( i = 0; i < 16; i++ )
		if ( !ReadFlag[i] ) {
			fputs("Error: Not all of the numbers were read.\n", stderr);
			exit(-1);
		}
}

/* Converts the axes coordinate system into the linear index */
int XYtoI(int x, int y)
{
	return (y<<2+x);
}

int ItoX(int i)
{
	return (i&3);
}

int ItoY(int i)
{
	return (i>>2);
}

void MoveSpace (int destx, int desty, int leavex, int leavey)
{
	int i, m, n, j, c;
	int Pos[17];
	int Pos2[17];
	char pass = 1;

	int p, p2, level;

	j = XYtoI(destx, desty);
	/* Copy the FlagField */
	for (i = 0; i < 16; i++)
		FlagField2[i] = (FlagField[i]) ? (FlagField[i]+16) : 0;
	/* Add the one member, we don't want to move with */
	FlagField2[XYtoI(leavex, leavey)] = 17;
	p = 1;
	Pos[0] = XYtoI (SpaceX, SpaceY);

	/* Do the level analysis. */
	level = 0;
	while (pass) {
		p2 = 0;
		for ( i = 0; i < p; i++ ) {
			if (Pos[i] == j) {
				pass = 0;
				break;
			}
			m = ItoX(Pos[i]);
			n = ItoY(Pos[i]);
			if (m>0 && !FlagField2[XYtoI(m-1,n)]) {
				FlagField2[XYtoI(m-1,n)] = XYtoI(m,n);	/* go left */
				Pos2[p2++]=XYtoI(m-1,n);
			}
			if (m<3 && !FlagField2[XYtoI(m+1,n)]) {
				FlagField2[XYtoI(m+1,n)] = XYtoI(m,n);	/* go right */
				Pos2[p2++]=XYtoI(m+1,n);
			}
			if (n>0 && !FlagField2[XYtoI(m,n-1)]) {
				FlagField2[XYtoI(m,n-1)] = XYtoI(m,n);	/* go up */
				Pos2[p2++]=XYtoI(m,n-1);
			}
			if (n<3 && !FlagField2[XYtoI(m,n+1)]) {
				FlagField2[XYtoI(m,n+1)] = XYtoI(m,n);	/* go down */
				Pos2[p2++]=XYtoI(m,n+1);
			}
		}
		level++;
		p = p2;
		for (i = 0; i < p2; i++)
			Pos[i] = Pos2[i];
	}

	/* Path found! Store it into solutions. And then apply it on the current permutation. */
	c = j;
	for (i = SolCnt+level-2; i >= SolCnt; i--) {
		Solution[i][0] = c;
		Solution[i][1] = c = FlagField2[c];
	}
	for (i = SolCnt; i <= SolCnt+level-2; i++)
		SWAP(CurrentPermutation[Solution[i][0]],CurrentPermutation[Solution[i][1]]);
	SolCnt += level-1;
	SpaceX = destx;
	SpaceY = desty;
}

void MoveLeft (int *x, int *y)
{
	MoveSpace (*x-1, *y, *x, *y);
	Solution[SolCnt][0] = XYtoI(*x, *y);
	Solution[SolCnt++][1] = XYtoI(--*x, *y);
}

void MoveRight (int *x, int *y)
{
	MoveSpace (*x+1, *y, *x, *y);
	Solution[SolCnt][0] = XYtoI(*x, *y);
	Solution[SolCnt++][1] = XYtoI(++*x, *y);
}

void MoveUp (int *x, int *y)
{
	MoveSpace (*x, *y-1, *x, *y);
	Solution[SolCnt][0] = XYtoI(*x, *y);
	Solution[SolCnt++][1] = XYtoI(*x, --*y);
}

void MoveDown (int *x, int *y)
{
	MoveSpace (*x, *y+1, *x, *y);
	Solution[SolCnt][0] = XYtoI(*x, *y);
	Solution[SolCnt++][1] = XYtoI(*x, ++*y);
}

/* It's not debugged yet. :-( */
void Move (unsigned char number, unsigned char dest_pos)
{
	int i, x, y, dest_x, dest_y;

	/* Find the current position of the number. */
	for ( i = 0; i < 16 && CurrentPermutation[i] != number; i++ );

	if (dest_pos == i+1)	/* The number already at the position. */
		return;

	dest_x = ItoX(dest_pos-1);
	dest_y = ItoY(dest_pos-1);
	x = ItoX(i);
	y = ItoY(i);

	while (i+1 != dest_pos) {
		if (dest_x = x) {
			if (dest_y < y)
				MoveUp(&x, &y);
			else
				MoveDown(&x, &y);
		} else if (dest_x < x) {
			if (dest_y == y)
				MoveLeft(&x, &y);
			else if (dest_y > y) {
				if (!FlagField[XYtoI(x-1,y)])
					MoveLeft(&x, &y);
				else
					MoveDown(&x, &y);
			} else {
				if (!FlagField[XYtoI(x-1,y)])
					MoveLeft(&x, &y);
				else
					MoveUp(&x, &y);
			}
		} else {
			if (dest_y == y)
				MoveRight(&x, &y);
			else if (dest_y > y) {
				if (!FlagField[XYtoI(x+1,y)])
					MoveRight(&x, &y);
				else
					MoveDown(&x, &y);
			} else {
				if (!FlagField[XYtoI(x+1,y)])
					MoveRight(&x, &y);
				else
					MoveUp(&x, &y);
			}
		}
	}
}

int main (int argc, char **argv)
{
	int i, j, count;
	unsigned char CycleNumber;
	char InifileRead   = 0,	/* Decides whether an inifile was already read. */
	     FinalfileRead = 0; /* decides whether a finalfile was already read. */

	if (argc<2) {
		/* If no arguments are given, write just some help */
		printf ("Game-16 (c) 1998 by (03) at ICP'98\n"
			"Usage:\n\tg03game.exe [-solve] [-show] <inifile>"
			"[<finalfile>]\n");
		return 0;
	}

	fputs ("----------------------------------\n", stderr);

	/* Parse the arguments */
	for ( i = 1; i < argc; i++ )
		if (argv[i][0] == '-') {
			/* The argument is a switch */
			if (!stricmp (argv[i]+1, "solve")) {
				SolveFlag = 1;
				fputs ("`-solve' flag enabled.\n", stderr);
			}
			else if (!stricmp (argv[i]+1, "show")) {
				ShowFlag = 1;
				fputs ("`-show' flag enabled.\n", stderr);
			}
		} else {
			if (InifileRead && !FinalfileRead) {
				/* Read the source permutation. */
				Read16 (argv[i], FinalPermutation);
				fputs("Final permutation read.\n", stderr);
				FinalfileRead = 1;
			} else if (!InifileRead) {
				/* Read the final permutation. */
				Read16 (argv[i], SourcePermutation);
				fputs("Source permutation read.\n", stderr);
				InifileRead = 1;
			} else {
				fprintf (stderr, "Error: Unexpected file \"%s\".\n",
					 argv[i]);
			}
		}

	fputs("Source: ", stderr);
	for (i = 0; i<16; i++)
		fprintf(stderr, "%d ", SourcePermutation[i]);
	fputs("\nFinal: ", stderr);
	for (i = 0; i<16; i++)
		fprintf(stderr, "%d ", FinalPermutation[i]);
	fputs("\n", stderr);

	/* Build the filter. */
	for ( i = 1; i <= 16; i++ )
		PermutationFilter[i] = FinalPermutation[i-1];

	/* Build the inversed filter */
	for ( i = 1; i <= 16; i++ )
		InversedFilter[PermutationFilter[i]] = i;

	/* Copy the Source perm. into the Current perm. and
	   apply the inversed filter on the Current perm. */
	for ( i = 0; i < 16; i++ )
		CurrentPermutation[i] = InversedFilter[SourcePermutation[i]];

	/* Now we can work with the Current perm. as if we would like
	   to reach the standatd permutation (1, ..., 16). */

	/*
	 * 	Decide whether the solution can be reached.
	 */

	/* Create the cycles (components of the graph). */

	for ( i = 0; i < 16; i++ )
		CycleSize[i] = PtrIndex[i] = 0; /* Initiate the cycles (no cycles) */

	CycleNumber = 1;	/* There must be at least one cycle. */

	for ( i = 0; i < 16; i++ ) {
		if (!PtrIndex[i]) {
			/* This member is not in any cycle yet. So add it. */
			PtrIndex[i] = CycleNumber;
			CycleSize[i]++;
			/* Go through all the cycle (it must be a closed component) */
			for ( j = i; CurrentPermutation[j]-1 != i; ) {
				j = CurrentPermutation[j]-1;
				PtrIndex[j] = CycleNumber;
				CycleSize[i]++;
			}
			CycleNumber++;
		}
	}

	/* Count the number of the cycles that pass the condition CountSize&1==1.
	   Sorry I wrote it so stupidly, but I'm not sure whether these are called
	   `odd' or `even'. It's those which cannot be divided by 2 in integers. */
	for ( count = i = 0; i < 16; )
		if (CycleSize[i++] & 1)
			count++;

	/* When the `count' (See previous comment) value is a multiple of 2,
	   the problem CAN BE SOLVED, because the game 16 has 16 fields
	   and that is a multiple of 2 and so the final permutation should
	   have 16 cycles, which means that it will be an identical
	   permutation. */
	fputs (" !!!! The problem CAN", stderr);
	if ( count & 1 )
		fputs("NOT", stderr);
	fputs (" BE SOLVED !!!!\n", stderr);

	if (!SolveFlag && !ShowFlag)
		return 0;

	/*
	 *	Solve it
	 */

	/* Clear te flag field before beginning. */
	for ( i = 0; i < 16; i++ )
		Solution[i][0] = Solution[i][1] = FlagField[i] = 0;
	for ( ; i < 2048; i++ )
		Solution[i][0] = Solution[i][1] = 0;

	/* Find the current position of the space. */
	for ( i = 0; i < 16 && CurrentPermutation[i] != 16; i++ );
	SpaceX = ItoX(i);
	SpaceY = ItoY(i);

#if 0
	Move(1, 1);
	Move(2, 2);
	Move(3, 3);
	Move(4, 12);
	/* Manually move 4->[4] without changing placed. */
	...
	Move(5, 5);
	Move(9, 9);
	Move(13, 15);
	/* Manually move 13->[13] without changing placed. */
	...
	Move(6, 6);
	Move(7, 7);
	Move(8, 16);
	/* Manually move 8->[8] without changing placed. */
	...
	Move(10, 10);
	Move(11, 16);
	/* Manually move 11->[11] without changing placed. */
	...
	/* Shift the four left members around, while they're not on the right place. */
	...

	/* Apply the filter. */
	...
	/* Optimize the solution */
	...
	/* Write the solution */
	...
	/* Display the solution */
	...
	/* end */

	fputs("Current: ", stderr);
	for (i = 0; i<16; i++)
		fprintf(stderr, "%d ", CurrentPermutation[i]);
	fputs("\n", stderr);

	fputs("O.K.\n", stderr);
#endif
	return 0;
}