A binary 8x8 matrix is 'unholy' if there are no isolated 1s. A 1 is isolated if there isn't another 1 in any of the 4 direct cardinal directions. Write a C program that counts the total number of unholy 8x8 matricies.
A binary 8x8 matrix is 'unholy' if there are no isolated 1s. A 1 is isolated if there isn't another 1 in any of the 4 direct cardinal directions. Write a C program that counts the total number of unholy 8x8 matricies.
Here's a C program to count the total number of unholy 8x8 matrices. This program uses a recursive approach to generate all possible binary 8x8 matrices and checks each one for isolated 1s.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <stdio.h> #include <stdbool.h> // Structure to represent an 8x8 matrix typedef struct { int matrix[8][8]; } Matrix; // Function to check if a 1 is isolated in the given matrix bool isIsolated(Matrix matrix, int row, int col) { // Check all four direct cardinal directions int directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i = 0; i < 4; i++) { int newRow = row + directions[i][0]; int newCol = col + directions[i][1]; // Check if the new position is within the matrix bounds if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8) { // If there's a 1 in any of the four directions, the 1 is not isolated if (matrix.matrix[newRow][newCol] == 1) { return false; } } } // If no 1 is found in any of the four directions, the 1 is isolated return true; } // Function to check if a matrix is unholy bool isUnholy(Matrix matrix) { // Check all elements in the matrix for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // If a 1 is isolated, the matrix is not unholy if (matrix.matrix[i][j] == 1 && isIsolated(matrix, i, j)) { return false; } } } // If no isolated 1s are found, the matrix is unholy return true; } // Function to generate all possible binary 8x8 matrices and count the unholy ones long long countUnholyMatrices(int row, int col, Matrix matrix) { // Base case: if all elements have been filled if (row == 8) { // Check if the matrix is unholy if (isUnholy(matrix)) { return 1; } else { return 0; } } // Recursive case: try both 0 and 1 for the current element long long count = 0; for (int val = 0; val <= 1; val++) { matrix.matrix[row][col] = val; // Move to the next element if (col == 7) { count += countUnholyMatrices(row + 1, 0, matrix); } else { count += countUnholyMatrices(row, col + 1, matrix); } } return count; } int main() { Matrix matrix; // Initialize all elements to 0 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { matrix.matrix[i][j] = 0; } } long long count = countUnholyMatrices(0, 0, matrix); printf("Total number of unholy 8x8 matrices: %lld\n", count); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include <stdio.h> #include <stdbool.h> #include <gmp.h> // Structure to represent an 8x8 matrix typedef struct { int matrix[8][8]; } Matrix; // Function to check if a 1 is isolated in the given matrix bool isIsolated(Matrix matrix, int row, int col) { // Check all four direct cardinal directions int directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i = 0; i < 4; i++) { int newRow = row + directions[i][0]; int newCol = col + directions[i][1]; // Check if the new position is within the matrix bounds if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8) { // If there's a 1 in any of the four directions, the 1 is not isolated if (matrix.matrix[newRow][newCol] == 1) { return false; } } } // If no 1 is found in any of the four directions, the 1 is isolated return true; } // Function to check if a matrix is unholy bool isUnholy(Matrix matrix) { // Check all elements in the matrix for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // If a 1 is isolated, the matrix is not unholy if (matrix.matrix[i][j] == 1 && isIsolated(matrix, i, j)) { return false; } } } // If no isolated 1s are found, the matrix is unholy return true; } // Function to generate all possible binary 8x8 matrices and count the unholy ones void countUnholyMatrices(int row, int col, Matrix matrix, mpz_t count) { // Base case: if all elements have been filled if (row == 8) { // Check if the matrix is unholy if (isUnholy(matrix)) { mpz_add_ui(count, count, 1); } return; } // Recursive case: try both 0 and 1 for the current element for (int val = 0; val <= 1; val++) { matrix.matrix[row][col] = val; // Move to the next element if (col == 7) { countUnholyMatrices(row + 1, 0, matrix, count); } else { countUnholyMatrices(row, col + 1, matrix, count); } } } int main() { Matrix matrix; // Initialize all elements to 0 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { matrix.matrix[i][j] = 0; } } mpz_t count; mpz_init(count); countUnholyMatrices(0, 0, matrix, count); gmp_printf("Total number of unholy 8x8 matrices: %Zd\n", count); mpz_clear(count); return 0; } |
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <stdio.h> #include <stdbool.h> // Structure to represent an 8x8 matrix typedef struct { int matrix[8][8]; } Matrix; // Function to check if a 1 is isolated in the given matrix bool isIsolated(Matrix matrix, int row, int col) { // Check all four direct cardinal directions int directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i = 0; i < 4; i++) { int newRow = row + directions[i][0]; int newCol = col + directions[i][1]; // Check if the new position is within the matrix bounds if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8) { // If there's a 1 in any of the four directions, the 1 is not isolated if (matrix.matrix[newRow][newCol] == 1) { return false; } } } // If no 1 is found in any of the four directions, the 1 is isolated return true; } // Function to check if a matrix is unholy bool isUnholy(Matrix matrix) { // Check all elements in the matrix for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // If a 1 is isolated, the matrix is not unholy if (matrix.matrix[i][j] == 1 && isIsolated(matrix, i, j)) { return false; } } } // If no isolated 1s are found, the matrix is unholy return true; } // Function to generate all possible binary 8x8 matrices and count the unholy ones long long countUnholyMatrices(int row, int col, Matrix matrix) { // Base case: if all elements have been filled if (row == 8) { // Check if the matrix is unholy if (isUnholy(matrix)) { return 1; } else { return 0; } } // Recursive case: try both 0 and 1 for the current element long long count = 0; for (int val = 0; val <= 1; val++) { matrix.matrix[row][col] = val; // Move to the next element if (col == 7) { count += countUnholyMatrices(row + 1, 0, matrix); } else { count += countUnholyMatrices(row, col + 1, matrix); } } return count; } int main() { Matrix matrix; // Initialize all elements to 0 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { matrix.matrix[i][j] = 0; } } long long count = countUnholyMatrices(0, 0, matrix); printf("Total number of unholy 8x8 matrices: %lld\n", count); return 0; } |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <stdio.h> #include <stdbool.h> // Structure to represent an 8x8 matrix typedef struct { int matrix[8][8]; } Matrix; // Function to check if a 1 is isolated in the given matrix bool isIsolated(Matrix matrix, int row, int col) { // Check all four direct cardinal directions int directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i = 0; i < 4; i++) { int newRow = row + directions[i][0]; int newCol = col + directions[i][1]; // Check if the new position is within the matrix bounds if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8) { // If there's a 1 in any of the four directions, the 1 is not isolated if (matrix.matrix[newRow][newCol] == 1) { return false; } } } // If no 1 is found in any of the four directions, the 1 is isolated return true; } // Function to check if a matrix is unholy bool isUnholy(Matrix matrix) { // Check all elements in the matrix for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // If a 1 is isolated, the matrix is not unholy if (matrix.matrix[i][j] == 1 && isIsolated(matrix, i, j)) { return false; } } } // If no isolated 1s are found, the matrix is unholy return true; } // Function to generate all possible binary 8x8 matrices and count the unholy ones long long countUnholyMatrices(int row, int col, Matrix matrix) { // Base case: if all elements have been filled if (row == 8) { // Check if the matrix is unholy if (isUnholy(matrix)) { return 1; } else { return 0; } } // Recursive case: try both 0 and 1 for the current element long long count = 0; for (int val = 0; val <= 1; val++) { matrix.matrix[row][col] = val; // Move to the next element if (col == 7) { count += countUnholyMatrices(row + 1, 0, matrix); } else { count += countUnholyMatrices(row, col + 1, matrix); } } return count; } int main() { Matrix matrix; // Initialize all elements to 0 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { matrix.matrix[i][j] = 0; } } long long count = countUnholyMatrices(0, 0, matrix); printf("Total number of unholy 8x8 matrices: %lld\n", count); return 0; } |
Timeout: function took too long to complete
Testing if the previous output contains the string 1121231537486377866
: False