/* * 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 #include #include #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; }