Initial Query

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.

LLM Generation

Query

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.

Output

Okay, let's plan and implement the C program to count unholy 8x8 matrices using dynamic programming and bit arithmetic. **1. Plan** 1. **Data Representation:** * Use `unsigned long long` (guaranteed to be at least 64 bits) to represent the entire 8x8 matrix. Let's call this type `Matrix`. * Map the matrix cells `(r, c)` (row `r`, column `c`, 0-indexed) to bit positions `r * 8 + c`. * Use `unsigned char` (8 bits) to represent a single row of the matrix. Let's call this type `Row`. 2. **`is_unholy` Function:** * Input: `Matrix m`. * Output: `bool` (true if unholy, false otherwise). * Logic: * Calculate a mask representing all positions that are neighbors (up, down, left, right) of *any* 1 in the matrix `m`. * `neighbors_up = m << 8` * `neighbors_down = m >> 8` * `neighbors_left = (m << 1) & ~0x0101010101010101ULL` (Mask out wraps from col 7 to col 0) * `neighbors_right = (m >> 1) & ~0x8080808080808080ULL` (Mask out wraps from col 0 to col 7) * `all_neighbors = neighbors_up | neighbors_down | neighbors_left | neighbors_right` * Identify isolated 1s: These are bits that are 1 in `m` but 0 in `all_neighbors`. * `isolated_ones = m & (~all_neighbors)` * The matrix is unholy if `isolated_ones == 0`. 3. **Dynamic Programming:** * **State:** `dp[r][row_r][row_{r-1}]` = Number of ways to fill the first `r+1` rows (0 to `r`) such that all 1s in rows 0 to `r-1` are *not* isolated (considering neighbors up to row `r`), and the last two rows added are `row_{r-1}` (at index `r-1`) and `row_r` (at index `r`). * **Dimensions:** `r` from 1 to 7. `row_r` and `row_{r-1}` are `Row` types (0-255). So, `dp[8][256][256]`. The values will be counts, so use `unsigned long long`. * **Helper Function `check_middle_row(Row current, Row prev, Row next)`:** Checks if any 1 in `current` row is isolated, considering `prev` as the row above and `next` as the row below. * `ones_in_current = current` * `neighbors_in_prev = prev` * `neighbors_in_next = next` * `neighbors_horizontal = ((current << 1) & 0xFE) | ((current >> 1) & 0x7F)` // Mask LSB/MSB for shifts * `all_neighbors = neighbors_in_prev | neighbors_in_next | neighbors_horizontal` * `isolated = ones_in_current & (~all_neighbors)` * Return `isolated == 0`. * **Base Case (r=1):** Fill `dp[1][row1][row0]`. * Iterate through all possible `row0` (0-255) and `row1` (0-255). * Check if `row0` is valid considering `row1` as the row below it (and no row above). This is like `check_middle_row` but with `prev_row = 0`. * Helper `check_first_row(Row r0, Row r1)`: * `ones = r0` * `neighbors_down = r1` * `neighbors_horizontal = ((r0 << 1) & 0xFE) | ((r0 >> 1) & 0x7F)` * `all_neighbors = neighbors_down | neighbors_horizontal` * `isolated = ones & (~all_neighbors)` * Return `isolated == 0`. * If `check_first_row(row0, row1)` is true, set `dp[1][row1][row0] = 1`. * **Transition (r from 1 to 6):** Calculate `dp[r+1][row_{r+1}][row_r]`. * Iterate `row_prev` (0-255), `row_curr` (0-255). * If `dp[r][row_curr][row_prev] == 0`, continue. * Iterate `row_next` (0-255). * Check if `row_curr` is valid given `row_prev` and `row_next` using `check_middle_row(row_curr, row_prev, row_next)`. * If valid, `dp[r+1][row_next][row_curr] += dp[r][row_curr][row_prev]`. * **Final Calculation:** Sum results after computing `dp[7][...]`. * Initialize `total_unholy_count = 0`. * Iterate `row6` (0-255), `row7` (0-255). * If `dp[7][row7][row6] == 0`, continue. * Check if the last row (`row7`) is valid, considering `row6` as the row above it (and no row below). This is like `check_middle_row` but with `next_row = 0`. * Helper `check_last_row(Row r7, Row r6)`: * `ones = r7` * `neighbors_up = r6` * `neighbors_horizontal = ((r7 << 1) & 0xFE) | ((r7 >> 1) & 0x7F)` * `all_neighbors = neighbors_up | neighbors_horizontal` * `isolated = ones & (~all_neighbors)` * Return `isolated == 0`. * If `check_last_row(row7, row6)` is true, add `dp[7][row7][row6]` to `total_unholy_count`. * Return `total_unholy_count`. 4. **Main Function:** * Allocate the DP table. * Run the base case calculation. * Run the transition loops. * Run the final calculation. * Print the result. * Include necessary headers (`stdio.h`, `stdint.h`, `stdbool.h`, `stdlib.h` for potential allocation if needed, though static should be fine). **2. C 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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h> // For memset

// Define types for clarity
typedef uint64_t Matrix;
typedef uint8_t Row;

// Constants
#define SIZE 8
#define NUM_ROWS (1 << SIZE) // 2^8 = 256

// DP table: dp[row_index][current_row][previous_row]
// row_index goes from 1 to SIZE-1 (7)
// We use SIZE instead of SIZE-1 for indexing convenience (1 to 7)
unsigned long long dp[SIZE][NUM_ROWS][NUM_ROWS];

// --- is_unholy Function (as requested, not used in DP) ---

// Checks if a full 8x8 matrix represented by a 64-bit integer is unholy.
bool is_unholy(Matrix m) {
    if (m == 0) return true; // Matrix with all 0s has no isolated 1s

    // Calculate neighbors for all bits simultaneously
    Matrix neighbors_up = m << SIZE;
    Matrix neighbors_down = m >> SIZE;
    // Mask to prevent wrap-around during horizontal shifts
    Matrix left_mask = 0xFEFEFEFEFEFEFEFEULL; // ~0x0101...
    Matrix right_mask = 0x7F7F7F7F7F7F7F7FULL; // ~0x8080...
    Matrix neighbors_left = (m << 1) & left_mask;
    Matrix neighbors_right = (m >> 1) & right_mask;

    Matrix all_neighbors = neighbors_up | neighbors_down | neighbors_left | neighbors_right;

    // Isolated ones are those present in m but not in all_neighbors
    Matrix isolated_ones = m & (~all_neighbors);

    return isolated_ones == 0;
}

// --- Helper functions for DP ---

// Checks if row 0 (r0) has any isolated 1s, considering row 1 (r1) below it.
bool check_first_row(Row r0, Row r1) {
    if (r0 == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_down = r1;
    Row neighbors_horizontal = ((r0 << 1) & 0xFE) | ((r0 >> 1) & 0x7F);
    Row all_neighbors = neighbors_down | neighbors_horizontal;
    Row isolated = r0 & (~all_neighbors);
    return isolated == 0;
}

// Checks if the middle row (current) has isolated 1s, given rows above (prev) and below (next).
bool check_middle_row(Row current, Row prev, Row next) {
    if (current == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_up = prev;
    Row neighbors_down = next;
    Row neighbors_horizontal = ((current << 1) & 0xFE) | ((current >> 1) & 0x7F);
    Row all_neighbors = neighbors_up | neighbors_down | neighbors_horizontal;
    Row isolated = current & (~all_neighbors);
    return isolated == 0;
}

// Checks if the last row (r7) has isolated 1s, considering row 6 (r6) above it.
bool check_last_row(Row r7, Row r6) {
    if (r7 == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_up = r6;
    Row neighbors_horizontal = ((r7 << 1) & 0xFE) | ((r7 >> 1) & 0x7F);
    Row all_neighbors = neighbors_up | neighbors_horizontal;
    Row isolated = r7 & (~all_neighbors);
    return isolated == 0;
}


int main() {
    // Initialize DP table to 0
    memset(dp, 0, sizeof(dp));

    printf("Calculating unholy matrices count...\n");

    // --- Base Case (r=1): Fill dp[1][row1][row0] ---
    printf("Processing base case (rows 0 and 1)...\n");
    for (Row r0 = 0; ; ++r0) {
        for (Row r1 = 0; ; ++r1) {
            if (check_first_row(r0, r1)) {
                dp[1][r1][r0] = 1;
            }
            if (r1 == 255) break; // Avoid infinite loop for unsigned char
        }
         if (r0 == 255) break; // Avoid infinite loop for unsigned char
    }

    // --- DP Transitions (r from 1 to SIZE-2, i.e., 1 to 6) ---
    // Calculate dp[r+1] based on dp[r]
    for (int r = 1; r < SIZE - 1; ++r) {
        printf("Processing row %d...\n", r + 1);
        for (Row row_prev = 0; ; ++row_prev) {
            for (Row row_curr = 0; ; ++row_curr) {
                if (dp[r][row_curr][row_prev] == 0) {
                     if (row_curr == 255) break;
                     continue; // No paths lead to this state
                }

                // Current count for the state ending in row_prev, row_curr
                unsigned long long current_count = dp[r][row_curr][row_prev];

                // Iterate through all possible next rows
                for (Row row_next = 0; ; ++row_next) {
                    // Check if placing row_next makes row_curr valid
                    if (check_middle_row(row_curr, row_prev, row_next)) {
                        dp[r + 1][row_next][row_curr] += current_count;
                    }
                     if (row_next == 255) break;
                }
                 if (row_curr == 255) break;
            }
             if (row_prev == 255) break;
        }
    }

    // --- Final Calculation ---
    printf("Calculating final sum...\n");
    unsigned long long total_unholy_count = 0;
    // We need dp[SIZE-1], which corresponds to index r = 7
    int final_r = SIZE - 1; // r = 7
    for (Row row6 = 0; ; ++row6) {
        for (Row row7 = 0; ; ++row7) {
            if (dp[final_r][row7][row6] > 0) {
                 // Check if the last row (row7) is valid given row6
                 if (check_last_row(row7, row6)) {
                     total_unholy_count += dp[final_r][row7][row6];
                 }
            }
             if (row7 == 255) break;
        }
         if (row6 == 255) break;
    }

    printf("\nTotal number of unholy 8x8 matrices: %llu\n", total_unholy_count);

    // Example usage of is_unholy (optional)
    // Matrix test_matrix = 0; // All zeros - unholy
    // printf("Is 0x0 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 1ULL; // Single 1 at (0,0) - holy
    // printf("Is 0x1 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 3ULL; // Two 1s at (0,0) and (0,1) - unholy
    // printf("Is 0x3 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 0x0101000000000000ULL; // Two 1s at (0,0) and (1,0) - unholy
    // printf("Is 0x0101... unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
     // test_matrix = 0x0000020502000000ULL; // A 1 at (2,1) isolated by 0s around it - holy
     // printf("Is matrix with isolated 1 at (2,1) unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");


    return 0;
}
**Explanation:** 1. **Types and Constants:** `Matrix` (uint64_t), `Row` (uint8_t), `SIZE` (8), `NUM_ROWS` (256) are defined. 2. **DP Table:** `dp[SIZE][NUM_ROWS][NUM_ROWS]` is declared globally (or could be allocated). `SIZE` is used for the first dimension for convenience, indexing from `dp[1]` to `dp[7]`. 3. **`is_unholy`:** Implemented as described in the plan using bit shifts and masks on the full 64-bit matrix. It correctly identifies isolated 1s. 4. **DP Helper Functions:** * `check_first_row`: Checks validity of row 0 given row 1. * `check_middle_row`: Checks validity of a row `r` (1 <= r <= 6) given rows `r-1` and `r+1`. * `check_last_row`: Checks validity of row 7 given row 6. * All these use bitwise operations on `Row` (uint8_t) types to find horizontal and vertical neighbors and check for isolated 1s within that specific row context. 5. **`main` Function:** * Initializes the `dp` table. * **Base Case:** Populates `dp[1][r1][r0]` by iterating through all `r0`, `r1` pairs and calling `check_first_row`. * **Transitions:** Loops from `r = 1` to `6`. Inside, it iterates through `row_prev` (`r-1`) and `row_curr` (`r`). If `dp[r][row_curr][row_prev]` is non-zero, it iterates through `row_next` (`r+1`), checks if `row_curr` is valid in this context using `check_middle_row`, and updates `dp[r+1][row_next][row_curr]`. * **Final Sum:** Iterates through all final states `dp[7][row7][row6]`. For each non-zero state, it calls `check_last_row` to ensure the last row itself doesn't contain isolated 1s, and if valid, adds the count to `total_unholy_count`. * Prints the final result. * The loops iterating through `Row` types use the `for (Row r = 0; ; ++r) { ... if (r == 255) break; }` pattern to correctly iterate from 0 to 255 for unsigned chars. This program structure follows the plan and uses the specified techniques (bit arithmetic, `unsigned long long`, DP by rows considering two at a time) to solve the problem. The time complexity is dominated by the transition step, roughly O(SIZE * NUM_ROWS^3), which is O(8 * 256^3) ≈ 1.3 x 10^8 operations, feasible within a reasonable time (likely a few seconds to a minute depending on the machine). The memory complexity is O(SIZE * NUM_ROWS^2) for the DP table, which is about 4MB.

Extract Code

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h> // For memset

// Define types for clarity
typedef uint64_t Matrix;
typedef uint8_t Row;

// Constants
#define SIZE 8
#define NUM_ROWS (1 << SIZE) // 2^8 = 256

// DP table: dp[row_index][current_row][previous_row]
// row_index goes from 1 to SIZE-1 (7)
// We use SIZE instead of SIZE-1 for indexing convenience (1 to 7)
unsigned long long dp[SIZE][NUM_ROWS][NUM_ROWS];

// --- is_unholy Function (as requested, not used in DP) ---

// Checks if a full 8x8 matrix represented by a 64-bit integer is unholy.
bool is_unholy(Matrix m) {
    if (m == 0) return true; // Matrix with all 0s has no isolated 1s

    // Calculate neighbors for all bits simultaneously
    Matrix neighbors_up = m << SIZE;
    Matrix neighbors_down = m >> SIZE;
    // Mask to prevent wrap-around during horizontal shifts
    Matrix left_mask = 0xFEFEFEFEFEFEFEFEULL; // ~0x0101...
    Matrix right_mask = 0x7F7F7F7F7F7F7F7FULL; // ~0x8080...
    Matrix neighbors_left = (m << 1) & left_mask;
    Matrix neighbors_right = (m >> 1) & right_mask;

    Matrix all_neighbors = neighbors_up | neighbors_down | neighbors_left | neighbors_right;

    // Isolated ones are those present in m but not in all_neighbors
    Matrix isolated_ones = m & (~all_neighbors);

    return isolated_ones == 0;
}

// --- Helper functions for DP ---

// Checks if row 0 (r0) has any isolated 1s, considering row 1 (r1) below it.
bool check_first_row(Row r0, Row r1) {
    if (r0 == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_down = r1;
    Row neighbors_horizontal = ((r0 << 1) & 0xFE) | ((r0 >> 1) & 0x7F);
    Row all_neighbors = neighbors_down | neighbors_horizontal;
    Row isolated = r0 & (~all_neighbors);
    return isolated == 0;
}

// Checks if the middle row (current) has isolated 1s, given rows above (prev) and below (next).
bool check_middle_row(Row current, Row prev, Row next) {
    if (current == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_up = prev;
    Row neighbors_down = next;
    Row neighbors_horizontal = ((current << 1) & 0xFE) | ((current >> 1) & 0x7F);
    Row all_neighbors = neighbors_up | neighbors_down | neighbors_horizontal;
    Row isolated = current & (~all_neighbors);
    return isolated == 0;
}

// Checks if the last row (r7) has isolated 1s, considering row 6 (r6) above it.
bool check_last_row(Row r7, Row r6) {
    if (r7 == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_up = r6;
    Row neighbors_horizontal = ((r7 << 1) & 0xFE) | ((r7 >> 1) & 0x7F);
    Row all_neighbors = neighbors_up | neighbors_horizontal;
    Row isolated = r7 & (~all_neighbors);
    return isolated == 0;
}


int main() {
    // Initialize DP table to 0
    memset(dp, 0, sizeof(dp));

    printf("Calculating unholy matrices count...\n");

    // --- Base Case (r=1): Fill dp[1][row1][row0] ---
    printf("Processing base case (rows 0 and 1)...\n");
    for (Row r0 = 0; ; ++r0) {
        for (Row r1 = 0; ; ++r1) {
            if (check_first_row(r0, r1)) {
                dp[1][r1][r0] = 1;
            }
            if (r1 == 255) break; // Avoid infinite loop for unsigned char
        }
         if (r0 == 255) break; // Avoid infinite loop for unsigned char
    }

    // --- DP Transitions (r from 1 to SIZE-2, i.e., 1 to 6) ---
    // Calculate dp[r+1] based on dp[r]
    for (int r = 1; r < SIZE - 1; ++r) {
        printf("Processing row %d...\n", r + 1);
        for (Row row_prev = 0; ; ++row_prev) {
            for (Row row_curr = 0; ; ++row_curr) {
                if (dp[r][row_curr][row_prev] == 0) {
                     if (row_curr == 255) break;
                     continue; // No paths lead to this state
                }

                // Current count for the state ending in row_prev, row_curr
                unsigned long long current_count = dp[r][row_curr][row_prev];

                // Iterate through all possible next rows
                for (Row row_next = 0; ; ++row_next) {
                    // Check if placing row_next makes row_curr valid
                    if (check_middle_row(row_curr, row_prev, row_next)) {
                        dp[r + 1][row_next][row_curr] += current_count;
                    }
                     if (row_next == 255) break;
                }
                 if (row_curr == 255) break;
            }
             if (row_prev == 255) break;
        }
    }

    // --- Final Calculation ---
    printf("Calculating final sum...\n");
    unsigned long long total_unholy_count = 0;
    // We need dp[SIZE-1], which corresponds to index r = 7
    int final_r = SIZE - 1; // r = 7
    for (Row row6 = 0; ; ++row6) {
        for (Row row7 = 0; ; ++row7) {
            if (dp[final_r][row7][row6] > 0) {
                 // Check if the last row (row7) is valid given row6
                 if (check_last_row(row7, row6)) {
                     total_unholy_count += dp[final_r][row7][row6];
                 }
            }
             if (row7 == 255) break;
        }
         if (row6 == 255) break;
    }

    printf("\nTotal number of unholy 8x8 matrices: %llu\n", total_unholy_count);

    // Example usage of is_unholy (optional)
    // Matrix test_matrix = 0; // All zeros - unholy
    // printf("Is 0x0 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 1ULL; // Single 1 at (0,0) - holy
    // printf("Is 0x1 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 3ULL; // Two 1s at (0,0) and (0,1) - unholy
    // printf("Is 0x3 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 0x0101000000000000ULL; // Two 1s at (0,0) and (1,0) - unholy
    // printf("Is 0x0101... unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
     // test_matrix = 0x0000020502000000ULL; // A 1 at (2,1) isolated by 0s around it - holy
     // printf("Is matrix with isolated 1 at (2,1) unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");


    return 0;
}

Run Code Interpreter

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h> // For memset

// Define types for clarity
typedef uint64_t Matrix;
typedef uint8_t Row;

// Constants
#define SIZE 8
#define NUM_ROWS (1 << SIZE) // 2^8 = 256

// DP table: dp[row_index][current_row][previous_row]
// row_index goes from 1 to SIZE-1 (7)
// We use SIZE instead of SIZE-1 for indexing convenience (1 to 7)
unsigned long long dp[SIZE][NUM_ROWS][NUM_ROWS];

// --- is_unholy Function (as requested, not used in DP) ---

// Checks if a full 8x8 matrix represented by a 64-bit integer is unholy.
bool is_unholy(Matrix m) {
    if (m == 0) return true; // Matrix with all 0s has no isolated 1s

    // Calculate neighbors for all bits simultaneously
    Matrix neighbors_up = m << SIZE;
    Matrix neighbors_down = m >> SIZE;
    // Mask to prevent wrap-around during horizontal shifts
    Matrix left_mask = 0xFEFEFEFEFEFEFEFEULL; // ~0x0101...
    Matrix right_mask = 0x7F7F7F7F7F7F7F7FULL; // ~0x8080...
    Matrix neighbors_left = (m << 1) & left_mask;
    Matrix neighbors_right = (m >> 1) & right_mask;

    Matrix all_neighbors = neighbors_up | neighbors_down | neighbors_left | neighbors_right;

    // Isolated ones are those present in m but not in all_neighbors
    Matrix isolated_ones = m & (~all_neighbors);

    return isolated_ones == 0;
}

// --- Helper functions for DP ---

// Checks if row 0 (r0) has any isolated 1s, considering row 1 (r1) below it.
bool check_first_row(Row r0, Row r1) {
    if (r0 == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_down = r1;
    Row neighbors_horizontal = ((r0 << 1) & 0xFE) | ((r0 >> 1) & 0x7F);
    Row all_neighbors = neighbors_down | neighbors_horizontal;
    Row isolated = r0 & (~all_neighbors);
    return isolated == 0;
}

// Checks if the middle row (current) has isolated 1s, given rows above (prev) and below (next).
bool check_middle_row(Row current, Row prev, Row next) {
    if (current == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_up = prev;
    Row neighbors_down = next;
    Row neighbors_horizontal = ((current << 1) & 0xFE) | ((current >> 1) & 0x7F);
    Row all_neighbors = neighbors_up | neighbors_down | neighbors_horizontal;
    Row isolated = current & (~all_neighbors);
    return isolated == 0;
}

// Checks if the last row (r7) has isolated 1s, considering row 6 (r6) above it.
bool check_last_row(Row r7, Row r6) {
    if (r7 == 0) return true; // No 1s, so no isolated 1s
    Row neighbors_up = r6;
    Row neighbors_horizontal = ((r7 << 1) & 0xFE) | ((r7 >> 1) & 0x7F);
    Row all_neighbors = neighbors_up | neighbors_horizontal;
    Row isolated = r7 & (~all_neighbors);
    return isolated == 0;
}


int main() {
    // Initialize DP table to 0
    memset(dp, 0, sizeof(dp));

    printf("Calculating unholy matrices count...\n");

    // --- Base Case (r=1): Fill dp[1][row1][row0] ---
    printf("Processing base case (rows 0 and 1)...\n");
    for (Row r0 = 0; ; ++r0) {
        for (Row r1 = 0; ; ++r1) {
            if (check_first_row(r0, r1)) {
                dp[1][r1][r0] = 1;
            }
            if (r1 == 255) break; // Avoid infinite loop for unsigned char
        }
         if (r0 == 255) break; // Avoid infinite loop for unsigned char
    }

    // --- DP Transitions (r from 1 to SIZE-2, i.e., 1 to 6) ---
    // Calculate dp[r+1] based on dp[r]
    for (int r = 1; r < SIZE - 1; ++r) {
        printf("Processing row %d...\n", r + 1);
        for (Row row_prev = 0; ; ++row_prev) {
            for (Row row_curr = 0; ; ++row_curr) {
                if (dp[r][row_curr][row_prev] == 0) {
                     if (row_curr == 255) break;
                     continue; // No paths lead to this state
                }

                // Current count for the state ending in row_prev, row_curr
                unsigned long long current_count = dp[r][row_curr][row_prev];

                // Iterate through all possible next rows
                for (Row row_next = 0; ; ++row_next) {
                    // Check if placing row_next makes row_curr valid
                    if (check_middle_row(row_curr, row_prev, row_next)) {
                        dp[r + 1][row_next][row_curr] += current_count;
                    }
                     if (row_next == 255) break;
                }
                 if (row_curr == 255) break;
            }
             if (row_prev == 255) break;
        }
    }

    // --- Final Calculation ---
    printf("Calculating final sum...\n");
    unsigned long long total_unholy_count = 0;
    // We need dp[SIZE-1], which corresponds to index r = 7
    int final_r = SIZE - 1; // r = 7
    for (Row row6 = 0; ; ++row6) {
        for (Row row7 = 0; ; ++row7) {
            if (dp[final_r][row7][row6] > 0) {
                 // Check if the last row (row7) is valid given row6
                 if (check_last_row(row7, row6)) {
                     total_unholy_count += dp[final_r][row7][row6];
                 }
            }
             if (row7 == 255) break;
        }
         if (row6 == 255) break;
    }

    printf("\nTotal number of unholy 8x8 matrices: %llu\n", total_unholy_count);

    // Example usage of is_unholy (optional)
    // Matrix test_matrix = 0; // All zeros - unholy
    // printf("Is 0x0 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 1ULL; // Single 1 at (0,0) - holy
    // printf("Is 0x1 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 3ULL; // Two 1s at (0,0) and (0,1) - unholy
    // printf("Is 0x3 unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
    // test_matrix = 0x0101000000000000ULL; // Two 1s at (0,0) and (1,0) - unholy
    // printf("Is 0x0101... unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");
     // test_matrix = 0x0000020502000000ULL; // A 1 at (2,1) isolated by 0s around it - holy
     // printf("Is matrix with isolated 1 at (2,1) unholy? %s\n", is_unholy(test_matrix) ? "Yes" : "No");


    return 0;
}
And got the output: Calculating unholy matrices count... Processing base case (rows 0 and 1)... Processing row 2... Processing row 3... Processing row 4... Processing row 5... Processing row 6... Processing row 7... Calculating final sum... Total number of unholy 8x8 matrices: 1121231537486377866

Substring Evaluation

Testing if the previous output contains the string 1121231537486377866: True