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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
Plan for the C program: 1. Define a constant `SIZE` for the matrix dimensions (8x8). 2. Use `unsigned long long` to represent the matrix, with each bit corresponding to a cell in the matrix. The lower `SIZE` bits represent the first row, the next `SIZE` bits represent the second row, and so on. 3. Define bit masks and shifting constants for checking the neighboring cells of a given cell. 4. Implement the `is_unholy` function, which takes an `unsigned long long` matrix and returns 1 if the matrix is unholy and 0 otherwise. This function will use bit-shifting and masking to check if there are any isolated 1s in the matrix. 5. Implement a dynamic programming function `count_unholy` to count the total number of unholy matrices. a. The function will have three parameters: the current row `r`, a bit mask `allowed` representing the valid configurations for the next two rows, and a bit mask `prev` representing the lower `r` rows of the matrix. b. Base cases: If `r == SIZE`, return 1 if the entire matrix is unholy (i.e., `is_unholy(prev)`), and 0 otherwise. If `allowed == 0`, return 0, as there are no valid configurations for the next two rows. c. Recursive case: Iterate through all possible configurations for the next two rows (represented by a 32-bit integer `x`, where the lower 16 bits correspond to the first of the two rows, and the upper 16 bits to the second). i. Check if the configuration `x` is allowed by the current `allowed` mask (`(x & allowed) == x`). ii. If so, construct the bit mask `next` for the next recursive call. This will represent the lower `r+2` rows of the matrix, by combining the `prev` mask and the `x` configuration, shifted to its correct position. iii. Update the `allowed` mask for the next recursive call. This will represent the valid configurations for the two rows after the current ones, given the current configuration `x`. This step is crucial for the "isolation" property of the 1s in the matrix. iv. Make the recursive call with `r+2`, the updated `allowed` mask, and the `next` mask, and accumulate the results. 6. In the `main` function, initialize the `allowed` mask to represent all possible configurations for the first two rows of the matrix, and call the `count_unholy` function with the initial parameters (`r=0`, `allowed`, and `prev=0`). Print the resulting count of unholy matrices. Here's the C program based on the above plan:
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 | #include <stdio.h> #define SIZE 8 typedef unsigned long long ull; ull LEFT = (1ULL << (SIZE - 1)) * 2 + 1; ull RIGHT = LEFT << (SIZE - 1); ull MASK = (1ULL << SIZE) - 1; int is_unholy(ull matrix) { ull m, isolated = 0; for (int r = 0; r < SIZE; r++) { m = (matrix >> (SIZE * r)) & MASK; isolated |= (m & ~(m << 1) & ~(m >> 1) & ~(m << LEFT) & ~(m >> RIGHT))) & m; } return !isolated; } ull count_unholy(int r, ull allowed, ull prev) { if (r == SIZE) return is_unholy(prev); if (!allowed) return 0; ull res = 0, next, x; for (x = 0; x < (1ULL << 16); x++) { if ((x & allowed) == x) { next = prev | (x << (SIZE * r)) | (x << (SIZE * (r + 1))); allowed ^= (x | (x << 1) | (x >> 1)) | (x << LEFT) | (x >> RIGHT)) & MASK; allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1))); res += count_unholy(r + 2, allowed, next); allowed ^= (x | (x << 1) | (x >> 1) | (x << LEFT) | (x >> RIGHT)) & MASK; allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1))); } } return res; } int main() { ull allowed = ((1ULL << 16) - 1) | ((1ULL << 16) - 1) << (SIZE * 1); printf("Number of unholy matrices: %llu\n", count_unholy(0, allowed, 0)); 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 | #include <stdio.h> #define SIZE 8 typedef unsigned long long ull; ull LEFT = (1ULL << (SIZE - 1)) * 2 + 1; ull RIGHT = LEFT << (SIZE - 1); ull MASK = (1ULL << SIZE) - 1; int is_unholy(ull matrix) { ull m, isolated = 0; for (int r = 0; r < SIZE; r++) { m = (matrix >> (SIZE * r)) & MASK; isolated |= (m & ~(m << 1) & ~(m >> 1) & ~(m << LEFT) & ~(m >> RIGHT))) & m; } return !isolated; } ull count_unholy(int r, ull allowed, ull prev) { if (r == SIZE) return is_unholy(prev); if (!allowed) return 0; ull res = 0, next, x; for (x = 0; x < (1ULL << 16); x++) { if ((x & allowed) == x) { next = prev | (x << (SIZE * r)) | (x << (SIZE * (r + 1))); allowed ^= (x | (x << 1) | (x >> 1)) | (x << LEFT) | (x >> RIGHT)) & MASK; allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1))); res += count_unholy(r + 2, allowed, next); allowed ^= (x | (x << 1) | (x >> 1) | (x << LEFT) | (x >> RIGHT)) & MASK; allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1))); } } return res; } int main() { ull allowed = ((1ULL << 16) - 1) | ((1ULL << 16) - 1) << (SIZE * 1); printf("Number of unholy matrices: %llu\n", count_unholy(0, allowed, 0)); 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 | #include <stdio.h> #define SIZE 8 typedef unsigned long long ull; ull LEFT = (1ULL << (SIZE - 1)) * 2 + 1; ull RIGHT = LEFT << (SIZE - 1); ull MASK = (1ULL << SIZE) - 1; int is_unholy(ull matrix) { ull m, isolated = 0; for (int r = 0; r < SIZE; r++) { m = (matrix >> (SIZE * r)) & MASK; isolated |= (m & ~(m << 1) & ~(m >> 1) & ~(m << LEFT) & ~(m >> RIGHT))) & m; } return !isolated; } ull count_unholy(int r, ull allowed, ull prev) { if (r == SIZE) return is_unholy(prev); if (!allowed) return 0; ull res = 0, next, x; for (x = 0; x < (1ULL << 16); x++) { if ((x & allowed) == x) { next = prev | (x << (SIZE * r)) | (x << (SIZE * (r + 1))); allowed ^= (x | (x << 1) | (x >> 1)) | (x << LEFT) | (x >> RIGHT)) & MASK; allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1))); res += count_unholy(r + 2, allowed, next); allowed ^= (x | (x << 1) | (x >> 1) | (x << LEFT) | (x >> RIGHT)) & MASK; allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1))); } } return res; } int main() { ull allowed = ((1ULL << 16) - 1) | ((1ULL << 16) - 1) << (SIZE * 1); printf("Number of unholy matrices: %llu\n", count_unholy(0, allowed, 0)); return 0; } |
main.c:8:13: error: initializer element is not constant
8 | ull RIGHT = LEFT << (SIZE - 1);
| ^~~~
main.c: In function 'is_unholy':
main.c:15:75: error: expected ';' before ')' token
15 | isolated |= (m & ~(m << 1) & ~(m >> 1) & ~(m << LEFT) & ~(m >> RIGHT))) & m;
| ^
| ;
main.c:15:75: error: expected statement before ')' token
main.c: In function 'count_unholy':
main.c:28:72: error: expected ';' before ')' token
28 | allowed ^= (x | (x << 1) | (x >> 1)) | (x << LEFT) | (x >> RIGHT)) & MASK;
| ^
| ;
main.c:28:72: error: expected statement before ')' token
main.c:29:131: error: expected ';' before ')' token
29 | allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1)));
| ^
| ;
main.c:29:131: error: expected statement before ')' token
main.c:32:131: error: expected ';' before ')' token
32 | allowed ^= ((x << (SIZE + 1)) | (x << (SIZE - 1)) | (x << (SIZE + LEFT)) | (x << (SIZE - RIGHT)) & MASK) << (SIZE * (r + 1)));
| ^
| ;
main.c:32:131: error: expected statement before ')' token
main.sh: line 2: ./a.out: No such file or directory
Testing if the previous output contains the string 1121231537486377866: False
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
Plan for the C program: 1. Define a constant `SIZE` for the matrix dimensions (8x8). 2. Use an `unsigned long long` to represent the binary matrix, with each row consisting of `SIZE` bits. 3. Write a helper function `get_row` to extract a specific row from the matrix representation. 4. Write a helper function `set_row` to set a specific row in the matrix representation. 5. Write a function `is_unholy` to check if a given matrix is unholy. This function should use bit-shifting and masking to check for any isolated 1s in the matrix. 6. Write a recursive function `count_unholy_matrices` to count the total number of unholy matrices. This function should recurse on the number of rows processed so far and enumerate all 2^16 (or 2^(2*SIZE) in general) possibilities for the next two rows. 7. In the `main` function, initialize the matrix to all 0s, call `count_unholy_matrices` with the initialized matrix and 0 rows processed, and print the resulting count. Here's the C program based on the above plan:
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 | #include <stdio.h> #include <stdbool.h> #define SIZE 8 #define ALL_ONES (((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1) typedef unsigned long long matrix_t; matrix_t get_row(matrix_t mat, int row) { return (mat >> (row * SIZE)) & ((1ULL << SIZE) - 1); } matrix_t set_row(matrix_t mat, int row, matrix_t row_val) { return (mat & ~((((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1)) << (row * SIZE))) | (row_val << (row * SIZE)); } bool is_unholy_row(matrix_t row) { return !(row & (row >> 1)) & ALL_ONES && !(row & (row << 1)) & ALL_ONES); } bool is_unholy(matrix_t mat, int rows) { if (rows == 0) return true; matrix_t prev_row = get_row(mat, rows - 1); for (int row = 0; row < rows; ++row) { matrix_t curr_row = get_row(mat, row); if (!is_unholy_row(curr_row) || (row > 0 && is_unholy_row(prev_row & curr_row)) || (row < rows - 1 && is_unholy_row(prev_row & curr_row))) ) return false; prev_row = curr_row; } return true; } long long count_unholy_matrices(matrix_t mat, int rows) { if (rows == SIZE) { if (is_unholy(mat, rows)) return 1; else return 0; } long long count = 0; for (matrix_t next_two_rows = 0; next_two_rows < (1ULL << (2 * SIZE)); ++next_two_rows) { matrix_t new_mat = set_row(set_row(mat, rows, next_two_rows & ((1ULL << SIZE) - 1)), rows + 1, (next_two_rows >> SIZE) & ((1ULL << SIZE) - 1)); count += count_unholy_matrices(new_mat, rows + 2); } return count; } int main() { matrix_t empty_mat = 0; long long num_unholy_matrices = count_unholy_matrices(empty_mat, 0); printf("Number of unholy 8x8 matrices: %lld\n", num_unholy_matrices); 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 | #include <stdio.h> #include <stdbool.h> #define SIZE 8 #define ALL_ONES (((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1) typedef unsigned long long matrix_t; matrix_t get_row(matrix_t mat, int row) { return (mat >> (row * SIZE)) & ((1ULL << SIZE) - 1); } matrix_t set_row(matrix_t mat, int row, matrix_t row_val) { return (mat & ~((((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1)) << (row * SIZE))) | (row_val << (row * SIZE)); } bool is_unholy_row(matrix_t row) { return !(row & (row >> 1)) & ALL_ONES && !(row & (row << 1)) & ALL_ONES); } bool is_unholy(matrix_t mat, int rows) { if (rows == 0) return true; matrix_t prev_row = get_row(mat, rows - 1); for (int row = 0; row < rows; ++row) { matrix_t curr_row = get_row(mat, row); if (!is_unholy_row(curr_row) || (row > 0 && is_unholy_row(prev_row & curr_row)) || (row < rows - 1 && is_unholy_row(prev_row & curr_row))) ) return false; prev_row = curr_row; } return true; } long long count_unholy_matrices(matrix_t mat, int rows) { if (rows == SIZE) { if (is_unholy(mat, rows)) return 1; else return 0; } long long count = 0; for (matrix_t next_two_rows = 0; next_two_rows < (1ULL << (2 * SIZE)); ++next_two_rows) { matrix_t new_mat = set_row(set_row(mat, rows, next_two_rows & ((1ULL << SIZE) - 1)), rows + 1, (next_two_rows >> SIZE) & ((1ULL << SIZE) - 1)); count += count_unholy_matrices(new_mat, rows + 2); } return count; } int main() { matrix_t empty_mat = 0; long long num_unholy_matrices = count_unholy_matrices(empty_mat, 0); printf("Number of unholy 8x8 matrices: %lld\n", num_unholy_matrices); 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 | #include <stdio.h> #include <stdbool.h> #define SIZE 8 #define ALL_ONES (((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1) typedef unsigned long long matrix_t; matrix_t get_row(matrix_t mat, int row) { return (mat >> (row * SIZE)) & ((1ULL << SIZE) - 1); } matrix_t set_row(matrix_t mat, int row, matrix_t row_val) { return (mat & ~((((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1)) << (row * SIZE))) | (row_val << (row * SIZE)); } bool is_unholy_row(matrix_t row) { return !(row & (row >> 1)) & ALL_ONES && !(row & (row << 1)) & ALL_ONES); } bool is_unholy(matrix_t mat, int rows) { if (rows == 0) return true; matrix_t prev_row = get_row(mat, rows - 1); for (int row = 0; row < rows; ++row) { matrix_t curr_row = get_row(mat, row); if (!is_unholy_row(curr_row) || (row > 0 && is_unholy_row(prev_row & curr_row)) || (row < rows - 1 && is_unholy_row(prev_row & curr_row))) ) return false; prev_row = curr_row; } return true; } long long count_unholy_matrices(matrix_t mat, int rows) { if (rows == SIZE) { if (is_unholy(mat, rows)) return 1; else return 0; } long long count = 0; for (matrix_t next_two_rows = 0; next_two_rows < (1ULL << (2 * SIZE)); ++next_two_rows) { matrix_t new_mat = set_row(set_row(mat, rows, next_two_rows & ((1ULL << SIZE) - 1)), rows + 1, (next_two_rows >> SIZE) & ((1ULL << SIZE) - 1)); count += count_unholy_matrices(new_mat, rows + 2); } return count; } int main() { matrix_t empty_mat = 0; long long num_unholy_matrices = count_unholy_matrices(empty_mat, 0); printf("Number of unholy 8x8 matrices: %lld\n", num_unholy_matrices); return 0; } |
main.c: In function 'set_row':
main.c:15:89: error: expected ';' before ')' token
15 | return (mat & ~((((1ULL << SIZE) - 1) << 1) | ((1ULL << SIZE) - 1)) << (row * SIZE)))
| ^
| ;
main.c:15:89: error: expected statement before ')' token
main.c:16:12: error: expected expression before '|' token
16 | | (row_val << (row * SIZE));
| ^
main.c: In function 'is_unholy_row':
main.c:21:45: error: expected ';' before ')' token
21 | && !(row & (row << 1)) & ALL_ONES);
| ^
main.c:21:45: error: expected statement before ')' token
main.c: In function 'is_unholy':
main.c:34:12: error: expected statement before ')' token
34 | )
| ^
main.sh: line 2: ./a.out: No such file or directory
Testing if the previous output contains the string 1121231537486377866: False
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
Plan for the C program: 1. Define a constant `SIZE` for the matrix dimensions (8x8). 2. Use `uint64_t` (unsigned 64-bit integer) to represent the binary matrix as bits. 3. Define necessary bit masks for checking the four cardinal directions. 4. Implement the `is_unholy` function to check if a matrix is unholy using bitwise operations and the pre-defined masks. 5. Implement a dynamic programming approach to count the total number of unholy matrices. a. Create a 2D array `dp` to store the number of unholy matrices for a given number of rows. b. Initialize the base case, `dp[0][0]` to 1, as there is only one empty matrix. c. Iterate through the number of rows (1 to `SIZE`). d. For each row, iterate through all possible combinations of the next two rows (2^16). e. Check if the combination is unholy by using the `is_unholy` function. f. If it is unholy, add the result from the previous iteration (`dp[row-1][combination & (uint64_t)-16]`) to the current `dp` value. g. The final result will be stored in `dp[SIZE-1][0]`. Here's the C program based on the plan:
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 | #include <stdio.h> #include <stdint.h> #define SIZE 8 uint64_t masks[] = { 0x00000000FFFFFF80, // up 0x00000000000001FF, // down 0x8080808080808000, // left 0x0001000100010001 // right }; int is_unholy(uint64_t matrix) { for (int i = 0; i < 4; ++i) { uint64_t isolated = matrix & ~(matrix | masks[i]); if (isolated != 0) return 0; } return 1; } int64_t count_unholy_matrices() { int64_t dp[SIZE][1 << 16]; dp[0][0] = 1; for (int row = 1; row < SIZE; ++row) { for (uint64_t next_rows = 0; next_rows < (1 << 16); ++next_rows) { uint64_t matrix = (next_rows << (16 * (row - 1))) | (dp[row-1][next_rows & ((uint64_t)-1 << 16)] << (16 * row)); if (is_unholy(matrix)) { dp[row][next_rows & ((uint64_t)-1 << 16)] += dp[row-1][next_rows & ((uint64_t)-1 << 16)]; } } } return dp[SIZE-1][0]; } int main() { int64_t count = count_unholy_matrices(); printf("There are %lld unholy 8x8 matrices.\n", 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 | #include <stdio.h> #include <stdint.h> #define SIZE 8 uint64_t masks[] = { 0x00000000FFFFFF80, // up 0x00000000000001FF, // down 0x8080808080808000, // left 0x0001000100010001 // right }; int is_unholy(uint64_t matrix) { for (int i = 0; i < 4; ++i) { uint64_t isolated = matrix & ~(matrix | masks[i]); if (isolated != 0) return 0; } return 1; } int64_t count_unholy_matrices() { int64_t dp[SIZE][1 << 16]; dp[0][0] = 1; for (int row = 1; row < SIZE; ++row) { for (uint64_t next_rows = 0; next_rows < (1 << 16); ++next_rows) { uint64_t matrix = (next_rows << (16 * (row - 1))) | (dp[row-1][next_rows & ((uint64_t)-1 << 16)] << (16 * row)); if (is_unholy(matrix)) { dp[row][next_rows & ((uint64_t)-1 << 16)] += dp[row-1][next_rows & ((uint64_t)-1 << 16)]; } } } return dp[SIZE-1][0]; } int main() { int64_t count = count_unholy_matrices(); printf("There are %lld unholy 8x8 matrices.\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 | #include <stdio.h> #include <stdint.h> #define SIZE 8 uint64_t masks[] = { 0x00000000FFFFFF80, // up 0x00000000000001FF, // down 0x8080808080808000, // left 0x0001000100010001 // right }; int is_unholy(uint64_t matrix) { for (int i = 0; i < 4; ++i) { uint64_t isolated = matrix & ~(matrix | masks[i]); if (isolated != 0) return 0; } return 1; } int64_t count_unholy_matrices() { int64_t dp[SIZE][1 << 16]; dp[0][0] = 1; for (int row = 1; row < SIZE; ++row) { for (uint64_t next_rows = 0; next_rows < (1 << 16); ++next_rows) { uint64_t matrix = (next_rows << (16 * (row - 1))) | (dp[row-1][next_rows & ((uint64_t)-1 << 16)] << (16 * row)); if (is_unholy(matrix)) { dp[row][next_rows & ((uint64_t)-1 << 16)] += dp[row-1][next_rows & ((uint64_t)-1 << 16)]; } } } return dp[SIZE-1][0]; } int main() { int64_t count = count_unholy_matrices(); printf("There are %lld unholy 8x8 matrices.\n", count); return 0; } |
There are 0 unholy 8x8 matrices.
main.c: In function 'main':
main.c:40:26: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Wformat=]
40 | printf("There are %lld unholy 8x8 matrices.\n", count);
| ~~~^ ~~~~~
| | |
| long long int int64_t {aka long int}
| %ld
Testing if the previous output contains the string 1121231537486377866: False
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
Plan for the C program: 1. Define a constant `SIZE` for the matrix dimensions (8x8). 2. Use `unsigned long long` to represent the binary matrix. The rightmost `SIZE` bits represent the first row, the next `SIZE` bits represent the second row, and so on. 3. Implement a function `get_row(unsigned long long mat, int idx)` that extracts and returns the `idx`-th row of the matrix `mat`. 4. Implement a function `set_row(unsigned long long *mat, int idx, unsigned long long row)` that sets the `idx`-th row of the matrix `mat` to `row`. 5. Implement a function `is_unholy_row(unsigned long long row)` that checks if a given row is unholy (no isolated 1s). 6. Implement a function `is_unholy_matrix(unsigned long long mat)` that checks if a given matrix is unholy. This function should use bit-shifting and masking to check for isolated 1s in all rows, columns, and diagonals. 7. Implement a dynamic programming function `count_unholy_matrices(int nrows)` that recursively counts the number of unholy `nrows x SIZE` matrices. The function should enumerate all `2^(2*SIZE)` possibilities for the next two rows and use the `is_unholy_matrix` function to check if the resulting matrix is unholy. 8. In the `main` function, call `count_unholy_matrices(SIZE)` to count the total number of unholy 8x8 matrices and print the result. C program implementation:
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <stdio.h> #include <stdint.h> #define SIZE 8 uint64_t get_row(uint64_t mat, int idx) { return (mat >> (idx * SIZE)) & ((1ULL << SIZE) - 1); } void set_row(uint64_t *mat, int idx, uint64_t row) { *mat &= ~((1ULL << SIZE) - 1) << (idx * SIZE); *mat |= row << (idx * SIZE); } int is_unholy_row(uint64_t row) { return !(row & (row >> 1)) & ((row << 1) | (1ULL << (SIZE - 1)))); } int is_unholy_matrix(uint64_t mat) { for (int i = 0; i < SIZE; ++i) { if (!is_unholy_row(get_row(mat, i))) { return 0; } } for (int i = 0; i < SIZE; ++i) { uint64_t col = 0; for (int j = 0; j < SIZE; ++j) { col |= (get_row(mat, j) >> i) & 1; if (j < SIZE - 1 && get_row(mat, j) >> i != get_row(mat, j + 1) >> i) { return 0; } } if (!is_unholy_row(col)) { return 0; } } for (int i = 0; i < SIZE; ++i) { if (i < SIZE - 1 && get_row(mat, i) & (1ULL << (SIZE - 1 - i)) != get_row(mat, i + 1) & (1ULL << (SIZE - 2 - i))) { return 0; } if (i < SIZE - 1 && get_row(mat, i) & (1ULL << i) != get_row(mat, i + 1) & (1ULL << (i + 1))) { return 0; } } return 1; } uint64_t dp[SIZE + 1][1 << (2 * SIZE)]; void init_dp() { for (int i = 0; i <= SIZE; ++i) { for (int j = 0; j < (1 << (2 * SIZE)); ++j) { dp[i][j] = 0; } } } uint64_t count_unholy_matrices(int nrows) { if (nrows == 0) { return 1; } if (nrows == 1) { uint64_t count = 0; for (uint64_t row = 0; row < (1 << SIZE); ++row) { if (is_unholy_row(row)) { ++count; } } return count; } for (int i = 0; i < (1 << (2 * SIZE)); ++i) { uint64_t row1 = i & ((1ULL << SIZE) - 1); uint64_t row2 = (i >> SIZE) & ((1ULL << SIZE) - 1); if (!is_unholy_row(row1) || !is_unholy_row(row2)) { continue; } uint64_t new_mat = row1 | (row2 << SIZE); uint64_t count = 0; for (uint64_t mat = 0; mat < dp[nrows - 2][1 << (2 * SIZE)]; ++mat) { set_row(&new_mat, nrows - 2, get_row(mat, nrows - 2)); set_row(&new_mat, nrows - 1, get_row(mat, nrows - 1)); if (is_unholy_matrix(new_mat)) { ++count; } } dp[nrows][i] = count; } uint64_t total_count = 0; for (int i = 0; i < (1 << (2 * SIZE)); ++i) { total_count += dp[nrows][i]; } return total_count; } int main() { init_dp(); uint64_t count = count_unholy_matrices(SIZE); printf("Number of unholy 8x8 matrices: %llu\n", 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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <stdio.h> #include <stdint.h> #define SIZE 8 uint64_t get_row(uint64_t mat, int idx) { return (mat >> (idx * SIZE)) & ((1ULL << SIZE) - 1); } void set_row(uint64_t *mat, int idx, uint64_t row) { *mat &= ~((1ULL << SIZE) - 1) << (idx * SIZE); *mat |= row << (idx * SIZE); } int is_unholy_row(uint64_t row) { return !(row & (row >> 1)) & ((row << 1) | (1ULL << (SIZE - 1)))); } int is_unholy_matrix(uint64_t mat) { for (int i = 0; i < SIZE; ++i) { if (!is_unholy_row(get_row(mat, i))) { return 0; } } for (int i = 0; i < SIZE; ++i) { uint64_t col = 0; for (int j = 0; j < SIZE; ++j) { col |= (get_row(mat, j) >> i) & 1; if (j < SIZE - 1 && get_row(mat, j) >> i != get_row(mat, j + 1) >> i) { return 0; } } if (!is_unholy_row(col)) { return 0; } } for (int i = 0; i < SIZE; ++i) { if (i < SIZE - 1 && get_row(mat, i) & (1ULL << (SIZE - 1 - i)) != get_row(mat, i + 1) & (1ULL << (SIZE - 2 - i))) { return 0; } if (i < SIZE - 1 && get_row(mat, i) & (1ULL << i) != get_row(mat, i + 1) & (1ULL << (i + 1))) { return 0; } } return 1; } uint64_t dp[SIZE + 1][1 << (2 * SIZE)]; void init_dp() { for (int i = 0; i <= SIZE; ++i) { for (int j = 0; j < (1 << (2 * SIZE)); ++j) { dp[i][j] = 0; } } } uint64_t count_unholy_matrices(int nrows) { if (nrows == 0) { return 1; } if (nrows == 1) { uint64_t count = 0; for (uint64_t row = 0; row < (1 << SIZE); ++row) { if (is_unholy_row(row)) { ++count; } } return count; } for (int i = 0; i < (1 << (2 * SIZE)); ++i) { uint64_t row1 = i & ((1ULL << SIZE) - 1); uint64_t row2 = (i >> SIZE) & ((1ULL << SIZE) - 1); if (!is_unholy_row(row1) || !is_unholy_row(row2)) { continue; } uint64_t new_mat = row1 | (row2 << SIZE); uint64_t count = 0; for (uint64_t mat = 0; mat < dp[nrows - 2][1 << (2 * SIZE)]; ++mat) { set_row(&new_mat, nrows - 2, get_row(mat, nrows - 2)); set_row(&new_mat, nrows - 1, get_row(mat, nrows - 1)); if (is_unholy_matrix(new_mat)) { ++count; } } dp[nrows][i] = count; } uint64_t total_count = 0; for (int i = 0; i < (1 << (2 * SIZE)); ++i) { total_count += dp[nrows][i]; } return total_count; } int main() { init_dp(); uint64_t count = count_unholy_matrices(SIZE); printf("Number of unholy 8x8 matrices: %llu\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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <stdio.h> #include <stdint.h> #define SIZE 8 uint64_t get_row(uint64_t mat, int idx) { return (mat >> (idx * SIZE)) & ((1ULL << SIZE) - 1); } void set_row(uint64_t *mat, int idx, uint64_t row) { *mat &= ~((1ULL << SIZE) - 1) << (idx * SIZE); *mat |= row << (idx * SIZE); } int is_unholy_row(uint64_t row) { return !(row & (row >> 1)) & ((row << 1) | (1ULL << (SIZE - 1)))); } int is_unholy_matrix(uint64_t mat) { for (int i = 0; i < SIZE; ++i) { if (!is_unholy_row(get_row(mat, i))) { return 0; } } for (int i = 0; i < SIZE; ++i) { uint64_t col = 0; for (int j = 0; j < SIZE; ++j) { col |= (get_row(mat, j) >> i) & 1; if (j < SIZE - 1 && get_row(mat, j) >> i != get_row(mat, j + 1) >> i) { return 0; } } if (!is_unholy_row(col)) { return 0; } } for (int i = 0; i < SIZE; ++i) { if (i < SIZE - 1 && get_row(mat, i) & (1ULL << (SIZE - 1 - i)) != get_row(mat, i + 1) & (1ULL << (SIZE - 2 - i))) { return 0; } if (i < SIZE - 1 && get_row(mat, i) & (1ULL << i) != get_row(mat, i + 1) & (1ULL << (i + 1))) { return 0; } } return 1; } uint64_t dp[SIZE + 1][1 << (2 * SIZE)]; void init_dp() { for (int i = 0; i <= SIZE; ++i) { for (int j = 0; j < (1 << (2 * SIZE)); ++j) { dp[i][j] = 0; } } } uint64_t count_unholy_matrices(int nrows) { if (nrows == 0) { return 1; } if (nrows == 1) { uint64_t count = 0; for (uint64_t row = 0; row < (1 << SIZE); ++row) { if (is_unholy_row(row)) { ++count; } } return count; } for (int i = 0; i < (1 << (2 * SIZE)); ++i) { uint64_t row1 = i & ((1ULL << SIZE) - 1); uint64_t row2 = (i >> SIZE) & ((1ULL << SIZE) - 1); if (!is_unholy_row(row1) || !is_unholy_row(row2)) { continue; } uint64_t new_mat = row1 | (row2 << SIZE); uint64_t count = 0; for (uint64_t mat = 0; mat < dp[nrows - 2][1 << (2 * SIZE)]; ++mat) { set_row(&new_mat, nrows - 2, get_row(mat, nrows - 2)); set_row(&new_mat, nrows - 1, get_row(mat, nrows - 1)); if (is_unholy_matrix(new_mat)) { ++count; } } dp[nrows][i] = count; } uint64_t total_count = 0; for (int i = 0; i < (1 << (2 * SIZE)); ++i) { total_count += dp[nrows][i]; } return total_count; } int main() { init_dp(); uint64_t count = count_unholy_matrices(SIZE); printf("Number of unholy 8x8 matrices: %llu\n", count); return 0; } |
main.c: In function 'is_unholy_row':
main.c:17:69: error: expected ';' before ')' token
17 | return !(row & (row >> 1)) & ((row << 1) | (1ULL << (SIZE - 1))));
| ^
| ;
main.c:17:69: error: expected statement before ')' token
main.c: In function 'main':
main.c:102:47: warning: format '%llu' expects argument of type 'long long unsigned int', but argument 2 has type 'uint64_t' {aka 'long unsigned int'} [-Wformat=]
102 | printf("Number of unholy 8x8 matrices: %llu\n", count);
| ~~~^ ~~~~~
| | |
| | uint64_t {aka long unsigned int}
| long long unsigned int
| %lu
main.sh: line 2: ./a.out: No such file or directory
Testing if the previous output contains the string 1121231537486377866: False
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
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.To solve this question: - Use bit arithmetic and an unsigned long to represent the matrix. - Write a function is_unholy that tests if a matrix is unholy by bit-shifting and masking. Use a dynamic program to count the number of unholy matricies. - Recurse on the number of rows the matrix has. - Enumerate all 2^16 next two rows. This is enough to completely isolate the prior solutions from the next. Write out a plan for the program, and then implement the plan in C.
Plan for the C program: 1. Define a constant `SIZE` for the matrix dimensions (8x8). 2. Use `unsigned long long` to represent the binary matrix as a bit string. 3. Write a helper function `get_bit` to extract the value of a specific bit from the bit string. 4. Write a helper function `set_bit` to set the value of a specific bit in the bit string. 5. Write the function `is_unholy` that checks if a given matrix is unholy. a. Use bit-shifting and masking to check for isolated 1s in each row and column. b. If an isolated 1 is found, return 0 (false). c. If no isolated 1s are found, return 1 (true). 6. Write a recursive function `count_unholy_matrices` to calculate the total number of unholy matrices. a. Base case: if the number of rows is 0, return 1 (since an empty matrix is considered unholy). b. Iterate through all possible combinations of the next two rows (2^16). c. For each combination, set the bits in the matrix corresponding to the two rows. d. Check if the matrix is unholy using the `is_unholy` function. e. If the matrix is unholy, recursively call `count_unholy_matrices` with the reduced number of rows, and add the result to a running sum. 7. In the `main` function, initialize the matrix to all 0s, and call `count_unholy_matrices` with the initial number of rows (SIZE). 8. Print the calculated total number of unholy matrices. Here's the C program based on the given plan:
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 | #include <stdio.h> #define SIZE 8 typedef unsigned long long matrix; int get_bit(matrix m, int row, int col) { return (m >> (row * SIZE + col)) & 1; } void set_bit(matrix *m, int row, int col, int val) { if (val) *m |= (1ULL << (row * SIZE + col)); else *m &= ~(1ULL << (row * SIZE + col)); } int is_unholy(matrix m) { matrix row, col, mask; int i, j, bit; for (i = 0; i < SIZE; i++) { row = (m >> (i * SIZE)) & ((1ULL << SIZE) - 1); col = (m & ((1ULL << SIZE) - 1)) << (SIZE * (SIZE - 1 - i)); for (j = 0; j < SIZE; j++) { mask = (1ULL << j); bit = (row & mask) && (!(row & (mask << 1)) && !(row & (mask >> 1))); if (bit) return 0; bit = (col & mask) && (!(col & (mask << 1)) && !(col & (mask >> 1)); if (bit) return 0; } } return 1; } matrix count_unholy_matrices(int rows) { matrix result = 1; matrix m = 0; matrix next_rows; if (rows > 0) { for (next_rows = 0; next_rows < (1ULL << (SIZE * 2)); next_rows++) { for (int r = 0; r < 2; r++) { for (int c = 0; c < SIZE; c++) { set_bit(&m, SIZE - rows + r, c, (next_rows >> (SIZE * r + c)) & 1); } } if (is_unholy(m)) { result += count_unholy_matrices(rows - 2); } } } return result; } int main() { matrix result = count_unholy_matrices(SIZE); printf("Number of unholy matrices: %llu\n", result); 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 | #include <stdio.h> #define SIZE 8 typedef unsigned long long matrix; int get_bit(matrix m, int row, int col) { return (m >> (row * SIZE + col)) & 1; } void set_bit(matrix *m, int row, int col, int val) { if (val) *m |= (1ULL << (row * SIZE + col)); else *m &= ~(1ULL << (row * SIZE + col)); } int is_unholy(matrix m) { matrix row, col, mask; int i, j, bit; for (i = 0; i < SIZE; i++) { row = (m >> (i * SIZE)) & ((1ULL << SIZE) - 1); col = (m & ((1ULL << SIZE) - 1)) << (SIZE * (SIZE - 1 - i)); for (j = 0; j < SIZE; j++) { mask = (1ULL << j); bit = (row & mask) && (!(row & (mask << 1)) && !(row & (mask >> 1))); if (bit) return 0; bit = (col & mask) && (!(col & (mask << 1)) && !(col & (mask >> 1)); if (bit) return 0; } } return 1; } matrix count_unholy_matrices(int rows) { matrix result = 1; matrix m = 0; matrix next_rows; if (rows > 0) { for (next_rows = 0; next_rows < (1ULL << (SIZE * 2)); next_rows++) { for (int r = 0; r < 2; r++) { for (int c = 0; c < SIZE; c++) { set_bit(&m, SIZE - rows + r, c, (next_rows >> (SIZE * r + c)) & 1); } } if (is_unholy(m)) { result += count_unholy_matrices(rows - 2); } } } return result; } int main() { matrix result = count_unholy_matrices(SIZE); printf("Number of unholy matrices: %llu\n", result); 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 | #include <stdio.h> #define SIZE 8 typedef unsigned long long matrix; int get_bit(matrix m, int row, int col) { return (m >> (row * SIZE + col)) & 1; } void set_bit(matrix *m, int row, int col, int val) { if (val) *m |= (1ULL << (row * SIZE + col)); else *m &= ~(1ULL << (row * SIZE + col)); } int is_unholy(matrix m) { matrix row, col, mask; int i, j, bit; for (i = 0; i < SIZE; i++) { row = (m >> (i * SIZE)) & ((1ULL << SIZE) - 1); col = (m & ((1ULL << SIZE) - 1)) << (SIZE * (SIZE - 1 - i)); for (j = 0; j < SIZE; j++) { mask = (1ULL << j); bit = (row & mask) && (!(row & (mask << 1)) && !(row & (mask >> 1))); if (bit) return 0; bit = (col & mask) && (!(col & (mask << 1)) && !(col & (mask >> 1)); if (bit) return 0; } } return 1; } matrix count_unholy_matrices(int rows) { matrix result = 1; matrix m = 0; matrix next_rows; if (rows > 0) { for (next_rows = 0; next_rows < (1ULL << (SIZE * 2)); next_rows++) { for (int r = 0; r < 2; r++) { for (int c = 0; c < SIZE; c++) { set_bit(&m, SIZE - rows + r, c, (next_rows >> (SIZE * r + c)) & 1); } } if (is_unholy(m)) { result += count_unholy_matrices(rows - 2); } } } return result; } int main() { matrix result = count_unholy_matrices(SIZE); printf("Number of unholy matrices: %llu\n", result); return 0; } |
main.c: In function 'is_unholy':
main.c:31:80: error: expected ')' before ';' token
31 | bit = (col & mask) && (!(col & (mask << 1)) && !(col & (mask >> 1));
| ~ ^
| )
main.c:32:31: error: expected ';' before '}' token
32 | if (bit) return 0;
| ^
| ;
33 | }
| ~
main.sh: line 2: ./a.out: No such file or directory
Testing if the previous output contains the string 1121231537486377866: False