/* See https://www.iwriteiam.nl/D2407.html#7 */ #include #include #define SIZE 19 #define CENTER 9 int sides[5][4] = { { 0, 5, 1, 4 }, { 11, 6, 10, 5 }, { 3, 7, 2, 6 }, { 8, 4, 9, 7 }, { 10, 2, 9, 1 } }; int dir[4][2] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } }; #define SWAP(T, A, B) { T h = A; A = B; B = h; } int main(int argc, char *argv[]) { if (argc == 2 && strcmp(argv[1], "-p") == 0) { // transform the output lines into a visible representation char buffer[200]; while (fgets(buffer, 199, stdin)) { char *s = strstr(buffer, "\""); if (s == 0) continue; for (s++; *s != '"'; s++) if (*s == '|') printf("\n"); else if (*s == 'x') printf(" "); else printf("%c", *s); printf("\n"); } return 0; } // Initialize finding all 5 out of 12 combinations int s[12]; for (int i = 0; i < 12; i++) s[i] = i < 5 ? 1 : 0; for (;;) { // Check for some impossible combinations of sides if ( s[ 0] + s[ 1] + s[ 2] + s[ 3] < 4 && s[ 4] + s[ 5] + s[ 6] + s[ 7] < 4 && s[ 0] + s[ 4] + s[ 8] < 3 && s[ 0] + s[ 5] + s[11] < 3 && s[ 0] + s[ 5] + s[11] < 3 && s[ 1] + s[ 4] + s[ 9] < 3 && s[ 1] + s[ 5] + s[10] < 3 && s[ 2] + s[ 6] + s[10] < 3 && s[ 2] + s[ 7] + s[ 9] < 3 && s[ 3] + s[ 6] + s[11] < 3 && s[ 3] + s[ 7] + s[ 8] < 3) { // Place one face on the 'field' char field[SIZE][SIZE]; for (int i = 0; i < SIZE; i++) for (int j = 0; j < SIZE; j++) field[i][j] = ' '; field[CENTER][CENTER] = 'x'; field[CENTER][CENTER-1] = 'a' + 3; field[CENTER+1][CENTER] = 'a' + 11; field[CENTER][CENTER+1] = 'a' + 0; field[CENTER-1][CENTER] = 'a' + 8; field[CENTER-1][CENTER-1] = '+'; field[CENTER-1][CENTER+1] = '+'; field[CENTER+1][CENTER-1] = '+'; field[CENTER+1][CENTER+1] = '+'; // Make a copy of the selected sides, bool s2[12]; for (int i = 0; i < 12; i++) s2[i] = s[i] == 1; bool face_placed[5] = { false, false, false, false, false }; bool combination_possible = true; // Loop five times to place a face for (int n = 0; n < 5; n++) { // Find which sides already occur in the field int occur[12]; for (int i = 0; i < 12; i++) occur[i] = 0; for (int j = 0; j < SIZE; j++) for (int i = 0; i < SIZE; i++) { char ch = field[i][j]; if ('a' <= ch && ch <= 'a' + 11) occur[ch - 'a']++; } // Check if there is at least one more side along which // the 'brick' needs to be flattened and check if all // sides that still need to be flattened only occur at // most once. int one_possible = false; for (int i = 0; i < 12; i++) if (s2[i]) { if (occur[i] >= 2) combination_possible = false; else if (occur[i] == 1) one_possible = true; } if (combination_possible && !one_possible) { combination_possible = false; } if (!combination_possible) break; // Loop over the faces that have not been placed yet for (int p = 0; p < 5; p++) if (!face_placed[p]) { // Check if it can be placed bool found = false; int i; int j; int k; for (i = 0; i < SIZE && !found; i++) for (j = 0; j < SIZE && !found; j++) for (k = 0; k < 4 && !found; k++) found = (field[i][j] == 'a' + sides[p][k]) && s2[field[i][j] - 'a']; i--; j--; k--; if (found) { // Determine where it needs to be placed char match = field[i][j]; s2[match - 'a'] = false; if (field[i+1][j] == 'x') i--; else if (field[i-1][j] == 'x') i++; else if (field[i][j-1] == 'x') j++; else if (field[i][j+1] == 'x') j--; else { printf("Error 1\n"); return 0; } // Determine the orienation for (int l = 0; l < 4; l++) if (field[i + dir[l][0]][j + dir[l][1]] == match) { field[i][j] = 'x'; field[i-1][j-1] = '+'; field[i-1][j+1] = '+'; field[i+1][j-1] = '+'; field[i+1][j+1] = '+'; for (int m = 0; m < 4; m++) field[i + dir[(l+m)%4][0]][j + dir[(l+m)%4][1]] = 'a' + sides[p][(k+m)%4]; break; } face_placed[p] = true; break; } } } if (combination_possible) { // If the combination is possible, copy the placement where all // sides with the same orientation are given the same value. int min_i = SIZE + 10, max_i = 0, min_j = SIZE + 10, max_j = 0; for (int j = 0; j < SIZE; j++) for (int i = 0; i < SIZE; i++) if (field[i][j] != ' ') { if (i < min_i) min_i = i; if (i > max_i) max_i = i; if (j < min_j) min_j = j; if (j > max_j) max_j = j; } char f1[SIZE][SIZE]; for (int j = 0; j < SIZE; j++) for (int i = 0; i < SIZE; i++) f1[i][j] = ' '; for (int j = min_j; j <= max_j; j++) for (int i = min_i; i <= max_i; i++) if (field[i][j] == '+' || field[i][j] == ' ' || field[i][j] == 'x') f1[i - min_i][j - min_j] = field[i][j]; else f1[i - min_i][j - min_j] = 'a' + (field[i][j] - 'a') / 4; // Find a minimal solution, trying all eight orientations char min_f1[SIZE][SIZE]; for (int j = 0; j < SIZE; j++) for (int i = 0; i < SIZE; i++) min_f1[i][j] = f1[i][j]; int i_last = max_i - min_i; int j_last = max_j - min_j; int min_i_last = i_last; int min_j_last = j_last; int nr_sym = 1; int min_rot = 0; for (int rot = 1; rot < 8; rot++) { if (rot % 2 == 0) { for (int j = 0; j < SIZE; j++) for (int i = j + 1; i < SIZE; i++) SWAP(char, f1[i][j], f1[j][i]) SWAP(int, i_last, j_last) } else { for (int j1 = 0, j2 = j_last; j1 < j2; j1++, j2--) for (int i = 0; i < SIZE; i++) SWAP(char, f1[i][j1], f1[i][j2]) } int cmp = i_last - min_i_last; for (int j = 0; j < SIZE && cmp == 0; j++) for (int i = 0; i < SIZE && cmp == 0; i++) cmp = f1[i][j] - min_f1[i][j]; if (cmp == 0) nr_sym++; else if (cmp < 0) { for (int j = 0; j < SIZE; j++) for (int i = 0; i < SIZE; i++) min_f1[i][j] = f1[i][j]; nr_sym = 1; min_i_last = i_last; min_j_last = j_last; min_rot = rot; } } // Output the minimal solution, starting with a string that can be sorted printf("/*"); for (int j = 0; j <= min_j_last; j += 2) { for (int i = 0; i <= min_i_last; i += 2) printf("%c", min_f1[i][j] == '+' ? 'b' : 'a'); printf("c"); } printf("*/ \""); for (int i = 0; i <= min_i_last; i++) { for (int j = 0; j <= min_j_last; j++) printf("%c", min_f1[i][j]); printf("|"); } printf("\",\n"); } } // Find next 5 out of 12 combination, and quit the loop if the last has been reaced. int m = 0; int j = 11; for (; s[j] == 1; j--) { m++; s[j] = 0; } if (m == 5) break; while (s[j] == 0) j--; s[j++] = 0; for (int i = 0; i <= m; i++) s[j+i] = 1; } }