/*
 * since we are looking for the maximal solution we know that the ant must start on the edge of the grid facing inwards. 
 * because the ant is invariant to grid rotations and reflections (reflection negatives actually), 
 * we only need to test half of one edge (n-floor(n/2) starting positions).
 * for each starting position we generate grid configurations as consecutive binary number, 
 * keeping track of the spatial extent of the trajectory so that we do not check every single configuration 
 * (the cells that are not visited are arbitrary). 
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define n 6 //GRID DIMENSION

void writecode(int* code, int** board){
	int st = 0;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			board[i][j] = code[st];
			st++;
		}
	}
}

void printboard(int** board){
	printf("\n\n");
	for(int i = 0; i < n; ++i){
		printf("   ");
		for(int j = 0; j < n; ++j){
			if(board[i][j] == 0) printf(" o");
			else printf(" +");
		}
		printf("\n");
	}
	printf("\n");
}
void fprintboard(FILE *f, int** board){
	fprintf(f, "\n\n");
	for(int i = 0; i < n; ++i){
		fprintf(f, "   ");
		for(int j = 0; j < n; ++j){
			if(board[i][j] == 0) fprintf(f, " o");
			else fprintf(f, " +");
		}
		fprintf(f, "\n");
	}
	fprintf(f, "\n");
}

int mod4(int x){
	if(x == 4) return 0;
	if(x == -1) return 3;
	return x;
}

int antmakestep(int** board, int *ap1, int *ap2, int *ao){
	//first find orientation
	if(board[*ap1][*ap2] == 0) *ao = mod4(*ao+1);
	else *ao = mod4(*ao-1);
	//reset the boardfield
	if(board[*ap1][*ap2] == 0) board[*ap1][*ap2] = 1;
	else board[*ap1][*ap2] = 0;
	//and now make a step
	if(*ao == 0){
		(*ap1)++;
		if(*ap1 < n) return 0;
	}
	else if(*ao == 1){
		(*ap2)++;
		if(*ap2 < n) return 0;
	}
	else if(*ao == 2){
		(*ap1)--;
		if(*ap1 >= 0) return 0;
	}
	else if(*ao == 3){
		(*ap2)--;
		if(*ap2 >= 0) return 0;
	}
	return 1; //the ant is out
}

int main(void){
	
	int **board = (int**)malloc(n*sizeof(int*));
	for(int i = 0; i < n; ++i) board[i] = (int*)malloc(n*sizeof(int));
	int **code = (int**)malloc(int(n-floor(n/2))*sizeof(int*));
	for(int i = 0; i < int(n-floor(n/2)); ++i) code[i] = (int*)malloc((n*n+1)*sizeof(int));
	for(int i = 0; i < int(n-floor(n/2)); ++i){
		for(int j = 0; j < n*n+1; ++j) code[i][j] = 0;
	}

	//solution saves
	int maxsolutions = 100; //max number of saved solutions
	int **solutionsaves = (int**)malloc(maxsolutions*sizeof(int*));
	for(int i = 0; i < maxsolutions; ++i) solutionsaves[i] = (int*)malloc((n*n+2)*sizeof(int)); 
	int solutioncounter = 0;
	
	int position_counter = 0;
	int maxsteps = 0;
	//ant orientation
	int ao0 = 2; //2 works the fastest
		int init = (n-1)*n+int(floor(n/2));
		int cap = n*n;//-int(floor(n/2));
		int addition = 1;
		for(int ap0 = init; ap0 < cap; ap0 += addition){ //ant position loop
			//printf("position: (%d, %d), orientation: %d\n", ap0/n, ap0%n, ao0);
			while(code[position_counter][n*n] != 1){
				//update code
				code[position_counter][0] += 1;
				for(int i = 0; i < n*n; ++i){
					if(code[position_counter][i] == 2){
						code[position_counter][i] = 0;
						code[position_counter][i+1] += 1;
					}
				}
				//update board
				writecode(code[position_counter], board);
				//intialize position and orientation variables
				int ap1,ap2;
				ap1 = ap0/n;
				ap2 = ap0%n;
				int ao = ao0;
				//set variables for noting the last cell visited
				int ap1min = ap1;
				int ap2min_ap1cond = ap2; //for ap1min
				int mincell = ap1*n+ap2; //the last cell (in terms of 1,2,3,...n*n) visited
				//counter and in_or_out
				int niven = 0;
				int counter = -1;
				while(niven == 0){
					if(ap1 < ap1min){
						ap1min = ap1;
						ap2min_ap1cond = ap2;
						mincell = ap1*n+ap2;
					}
					else if(ap1 == ap1min){
						if(ap2 < ap2min_ap1cond){
							ap2min_ap1cond = ap2;
							mincell = ap1*n+ap2;
						}
					}
					niven = antmakestep(board, &ap1, &ap2, &ao);
					counter++;
				}
				if(counter > maxsteps){
					maxsteps = counter;
					for(int i = 0; i < n*n; ++i) solutionsaves[0][i] = code[position_counter][i];
					solutionsaves[0][n*n] = ap0;
					solutionsaves[0][n*n+1] = ao0;
					solutioncounter = 1;
				}
				else if(counter == maxsteps && solutioncounter < maxsolutions-1){
					for(int i = 0; i < n*n; ++i) solutionsaves[solutioncounter][i] = code[position_counter][i];
					solutionsaves[solutioncounter][n*n] = ap0;
					solutionsaves[solutioncounter][n*n+1] = ao0;
					solutioncounter++;
				}
				//skip through codes that will yield the same result because some last cells were never visited
				for(int ll = 0; ll < mincell; ++ll){
					code[position_counter][ll] = 1;
				}
			}
			//increase position counter
			position_counter++;
		}

	//print
	for(int i = 0; i < solutioncounter; ++i){
		writecode(solutionsaves[i], board);
		printboard(board);
		printf("start at (%d,%d) oriented %d\n", solutionsaves[i][n*n]/n, solutionsaves[i][n*n]%n, solutionsaves[i][n*n+1]);
	}
	printf("\n\nmaxsteps = %d\nnumber of solutions = %d\n\n", maxsteps, solutioncounter);
	
	//fileprint
	FILE *f;
	char buffer[1024];
	snprintf(buffer, sizeof(buffer), "solution%d.txt", n);
	f = fopen(buffer, "wt");
	for(int i = 0; i < solutioncounter; ++i){
		writecode(solutionsaves[i], board);
		fprintboard(f, board);
		fprintf(f, "start at (%d,%d) oriented %d\n", solutionsaves[i][n*n]/n, solutionsaves[i][n*n]%n, solutionsaves[i][n*n+1]);
	}
	fprintf(f, "\n\nmaxsteps = %d\nnumber of solutions = %d\n\n", maxsteps, solutioncounter);
	fclose(f);
	
	return 0;
	
}