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.
One acceptable answer was to “dynamicâ€program†over the rows. In our solution the idea is that an 8×8 binary matrix is “unholy†if every 1 has at least one 1 in one of the four “cardinal†directions. (Note that on a border cell there is no “up†(for the top row) or “down†(for the bottom row) neighbor so a 1 there must get help from left/right or – for the top row – its cell immediately below.) In our approach we “fill in†the matrix one row at a time. (There are 2^64 matrices in all—but by “passing along†just a pair of rows (the “previous†row and the “current†row) we can use a recurrence whose state size is only 256×256.) One key observation is that if a row’s 1 appears “by itself†horizontally (that is, if in its row the 1 does not have a 1 immediately to its left or right) then to avoid being isolated it must have a 1 either immediately above it or immediately below it. (For the very first row there is no “aboveâ€, so every horizontally isolated 1 there must be “rescued†by the row below.) Thus if we denote a row by an 8–bit mask we can “pre–compute†which bits are isolated. (One may show that the “isolated–bit mask†for an 8–bit row is simply   iso = row & ~(row<<1 | row>>1) (with appropriate masking on the left and right ends).) Now suppose we label the rows 0 ... 7 and denote by U the “upperâ€neighbor row†(row i–1), by P the “current†row (row i) and by Q the “next†row (row i+1). Then the condition needed for P (when 0 < i < 7) is that “every 1 that is isolated in P gets help from at least one vertical neighbor†– that is, for each column c for which P has a 1 and its left and right neighbors are 0 we must have   U[c]==1 OR Q[c]==1. For the top row (i = 0) there is no row U so every isolated 1 must have Q[c]==1, and in the last row (i = 7) every isolated 1 must have come from above (i.e. from row 6). Our dynamic programming is then best described by “states†consisting of two consecutive rows. We use a two–dimensional dp array dp[A][B] (of type unsigned long long) that counts how many ways there are to fill rows so that the last two rows in the partial matrix are A (the previous row) and B (the current row) and such that the isolation condition has already been “checked†for the previous row. (When transitioning from state (A,B) to the next state (B,Q) we will “check†that B is acceptable with help from its above–row A and the soon–to–be–chosen row Q.) For example, when we “start†we choose two rows: for every pair (a,b) (with a and b from 0 to 255) we require that in the top row a every isolated 1 is “rescued†by the row below – that is,   if (iso(a) & ~b)==0 then we set dp[a][b]++; Then we iterate for rows 1 to 6. When in state (A, B) (that is, the previous row was A and the current row is B) and about to choose row Q to be the next row we require that every isolated 1 in B is supported by A (above) or by Q (below). That is, we require   if (iso(B) & ~(A | Q))==0 we add dp[A][B] to the new state (B, Q). Finally, at the last row (row 7) there is no row below so the condition is that every isolated 1 in row 7 must have come from above (i.e. from row 6). That is, if we are in state (A,B) (where B is row 7) and   if (iso(B) & ~A)==0 then we add dp[A][B] to our final answer. The complete C program below is one acceptable answer. (Note that although there are 2^64 possible matrices, this DP runs in time roughly proportional to 256^3 which is very reasonable.) Below is the full source code: ----------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define ROWS 8 #define MASKS 256 // Compute the isolated mask for a given row mask. // A bit in 'mask' is considered isolated horizontally if its immediate // left and right bits are zero. (We take care at the boundaries.) static inline int isolated_mask (int mask) { // For an 8-bit number, we must make sure that shifting does not // bring in bits from outside. int left = (mask << 1) & 0xFF; // shifted left; bit0 becomes 0. int right = (mask >> 1); return mask & ~(left | right); } int main(void) { // dp[A][B] will hold the number of ways to fill the matrix // so far such that the previous row is A and the current row is B. // (A and B are in the range 0 .. 255.) unsigned long long dp[MASKS][MASKS] = {0}; unsigned long long new_dp[MASKS][MASKS] = {0}; unsigned long long result = 0; // Precompute the isolated-bit mask for each possible row. int iso[MASKS]; for (int mask = 0; mask < MASKS; mask++) { iso[mask] = isolated_mask(mask); } // Initialize: rows[0] = a, rows[1] = b, where row0 has no upper row. // For row 0, any 1 that is isolated horizontally must be rescued by row1. for (int a = 0; a < MASKS; a++) { for (int b = 0; b < MASKS; b++) { // For row0 (a), if a bit is isolated (i.e. in iso[a]), // then row1 (b) MUST provide a 1 in that position. if ((iso[a] & ~b) == 0) { dp[a][b]++; // one valid way. } } } // Process rows 2 through 7. // Currently dp[A][B] represents that we've filled rows 0..(r), // with (r-1) = A and r = B. // We will now choose row Q to be the next row (r+1), for r=1..6. for (int row = 1; row < ROWS-1; row++) { // Clear new_dp. for (int i = 0; i < MASKS; i++) { for (int j = 0; j < MASKS; j++) { new_dp[i][j] = 0; } } // For each state (A, B) in dp: for (int A = 0; A < MASKS; A++){ for (int B = 0; B < MASKS; B++){ if (dp[A][B] == 0) continue; // We want to pick a row Q (0..255) for the next row such that // every isolated 1 in row B is “rescued†by either the above row (A) // or by the new row Q (i.e. condition: iso(B) is a subset of A|Q). for (int Q = 0; Q < MASKS; Q++){ if ((iso[B] & ~(A | Q)) == 0) { new_dp[B][Q] += dp[A][B]; } } } } // Copy new_dp into dp. for (int i = 0; i < MASKS; i++){ for (int j = 0; j < MASKS; j++){ dp[i][j] = new_dp[i][j]; } } } // Now, our dp[A][B] represents that rows 0..7 have been set, // where row6 is A and row7 is B. There is no row 8, so for row7 // every isolated 1 must have a 1 in row6. for (int A = 0; A < MASKS; A++){ for (int B = 0; B < MASKS; B++){ if (dp[A][B] == 0) continue; if ((iso[B] & ~A) == 0){ result += dp[A][B]; } } } printf("The number of unholy 8x8 matrices is: %llu\n", result); return 0; } ----------------------------------------------------------- Explanation of the code: 1. The function isolated_mask(mask) computes which bits in a row are “isolated†(that is, a 1 that does not have a 1 immediately to its left or right). (Notice that we take care to keep things within 8 bits.) 2. We use a two–dimensional dp array. The state dp[A][B] means that the “previous row†was A and the “current row†is B and that the isolation–condition for the previous row has been satisfied. 3. For the very first row (row 0) there is no row above so any isolated 1 must be “rescued†by row1. Hence we initialize dp[a][b] to 1 if (iso(a) must be a subset of b). 4. Then for rows 1 through 6 we “extend†the matrix. If our current state is (A,B) then we choose a candidate new row Q (which will be the next row) provided that every isolated 1 in B is ‘saved’ by having either a 1 above (in A) or a 1 in the new row Q. 5. After we have filled in row 7 the condition for that last row is that any isolated 1 (with no row below) must have been “rescued†by row 6. 6. Finally, we sum up all dp[A][B] states that meet this final condition, and print the result. Any C program that “counts†the number of unholy matrices and uses a state–space of size 256×256 (with roughly 256^3 iterations overall) is acceptable. This is one correct answer to the problem.
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 | #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define ROWS 8 #define MASKS 256 // Compute the isolated mask for a given row mask. // A bit in 'mask' is considered isolated horizontally if its immediate // left and right bits are zero. (We take care at the boundaries.) static inline int isolated_mask (int mask) { // For an 8-bit number, we must make sure that shifting does not // bring in bits from outside. int left = (mask << 1) & 0xFF; // shifted left; bit0 becomes 0. int right = (mask >> 1); return mask & ~(left | right); } int main(void) { // dp[A][B] will hold the number of ways to fill the matrix // so far such that the previous row is A and the current row is B. // (A and B are in the range 0 .. 255.) unsigned long long dp[MASKS][MASKS] = {0}; unsigned long long new_dp[MASKS][MASKS] = {0}; unsigned long long result = 0; // Precompute the isolated-bit mask for each possible row. int iso[MASKS]; for (int mask = 0; mask < MASKS; mask++) { iso[mask] = isolated_mask(mask); } // Initialize: rows[0] = a, rows[1] = b, where row0 has no upper row. // For row 0, any 1 that is isolated horizontally must be rescued by row1. for (int a = 0; a < MASKS; a++) { for (int b = 0; b < MASKS; b++) { // For row0 (a), if a bit is isolated (i.e. in iso[a]), // then row1 (b) MUST provide a 1 in that position. if ((iso[a] & ~b) == 0) { dp[a][b]++; // one valid way. } } } // Process rows 2 through 7. // Currently dp[A][B] represents that we've filled rows 0..(r), // with (r-1) = A and r = B. // We will now choose row Q to be the next row (r+1), for r=1..6. for (int row = 1; row < ROWS-1; row++) { // Clear new_dp. for (int i = 0; i < MASKS; i++) { for (int j = 0; j < MASKS; j++) { new_dp[i][j] = 0; } } // For each state (A, B) in dp: for (int A = 0; A < MASKS; A++){ for (int B = 0; B < MASKS; B++){ if (dp[A][B] == 0) continue; // We want to pick a row Q (0..255) for the next row such that // every isolated 1 in row B is “rescued†by either the above row (A) // or by the new row Q (i.e. condition: iso(B) is a subset of A|Q). for (int Q = 0; Q < MASKS; Q++){ if ((iso[B] & ~(A | Q)) == 0) { new_dp[B][Q] += dp[A][B]; } } } } // Copy new_dp into dp. for (int i = 0; i < MASKS; i++){ for (int j = 0; j < MASKS; j++){ dp[i][j] = new_dp[i][j]; } } } // Now, our dp[A][B] represents that rows 0..7 have been set, // where row6 is A and row7 is B. There is no row 8, so for row7 // every isolated 1 must have a 1 in row6. for (int A = 0; A < MASKS; A++){ for (int B = 0; B < MASKS; B++){ if (dp[A][B] == 0) continue; if ((iso[B] & ~A) == 0){ result += dp[A][B]; } } } printf("The number of unholy 8x8 matrices is: %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 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 | #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define ROWS 8 #define MASKS 256 // Compute the isolated mask for a given row mask. // A bit in 'mask' is considered isolated horizontally if its immediate // left and right bits are zero. (We take care at the boundaries.) static inline int isolated_mask (int mask) { // For an 8-bit number, we must make sure that shifting does not // bring in bits from outside. int left = (mask << 1) & 0xFF; // shifted left; bit0 becomes 0. int right = (mask >> 1); return mask & ~(left | right); } int main(void) { // dp[A][B] will hold the number of ways to fill the matrix // so far such that the previous row is A and the current row is B. // (A and B are in the range 0 .. 255.) unsigned long long dp[MASKS][MASKS] = {0}; unsigned long long new_dp[MASKS][MASKS] = {0}; unsigned long long result = 0; // Precompute the isolated-bit mask for each possible row. int iso[MASKS]; for (int mask = 0; mask < MASKS; mask++) { iso[mask] = isolated_mask(mask); } // Initialize: rows[0] = a, rows[1] = b, where row0 has no upper row. // For row 0, any 1 that is isolated horizontally must be rescued by row1. for (int a = 0; a < MASKS; a++) { for (int b = 0; b < MASKS; b++) { // For row0 (a), if a bit is isolated (i.e. in iso[a]), // then row1 (b) MUST provide a 1 in that position. if ((iso[a] & ~b) == 0) { dp[a][b]++; // one valid way. } } } // Process rows 2 through 7. // Currently dp[A][B] represents that we've filled rows 0..(r), // with (r-1) = A and r = B. // We will now choose row Q to be the next row (r+1), for r=1..6. for (int row = 1; row < ROWS-1; row++) { // Clear new_dp. for (int i = 0; i < MASKS; i++) { for (int j = 0; j < MASKS; j++) { new_dp[i][j] = 0; } } // For each state (A, B) in dp: for (int A = 0; A < MASKS; A++){ for (int B = 0; B < MASKS; B++){ if (dp[A][B] == 0) continue; // We want to pick a row Q (0..255) for the next row such that // every isolated 1 in row B is “rescued†by either the above row (A) // or by the new row Q (i.e. condition: iso(B) is a subset of A|Q). for (int Q = 0; Q < MASKS; Q++){ if ((iso[B] & ~(A | Q)) == 0) { new_dp[B][Q] += dp[A][B]; } } } } // Copy new_dp into dp. for (int i = 0; i < MASKS; i++){ for (int j = 0; j < MASKS; j++){ dp[i][j] = new_dp[i][j]; } } } // Now, our dp[A][B] represents that rows 0..7 have been set, // where row6 is A and row7 is B. There is no row 8, so for row7 // every isolated 1 must have a 1 in row6. for (int A = 0; A < MASKS; A++){ for (int B = 0; B < MASKS; B++){ if (dp[A][B] == 0) continue; if ((iso[B] & ~A) == 0){ result += dp[A][B]; } } } printf("The number of unholy 8x8 matrices is: %llu\n", result); return 0; } |
The number of unholy 8x8 matrices is: 1121231537486377866
Testing if the previous output contains the string 1121231537486377866: True
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.
One acceptable answer was to “build†the 8×8 matrix rowâ€byâ€row using dynamic programming. One may show that a valid (or “unholyâ€) matrix is one in which every 1 has at least one neighboring 1 in one of the four “cardinal†directions. (A 1 in the top row, for example, has no “upâ€neighborâ€. So if its only 1 is in its own row it must get a neighbor to its left or right, or else the row below must “rescue†it.) One way to “prove†our algorithm works is to note that if we assign the rows 0,…,7 one at a time then when we finish row i (0 ≤ i ≤ 7) we can “validate†row i–1: any 1 in row i–1 that did not have a horizontal neighbor or an upward neighbor must have a 1 below it – i.e. in row i. (For row 0 there is no upward neighbor, so its 1’s must either come in pairs (or blocks) horizontally or be “rescued†by row 1.) One correct solution was to do the following: 1. For each row (there are 8 columns so 2^8 = 256 possible bitâ€masks) we “preâ€compute†a bitmask req that indicates, for every 1 in that row that is “lonely†(that is, it has no 1 immediately to its left or right – and if the row is not the first then a 1 immediately above “saves†it), that it will require a 1 in the next row (directly below) in that column. 2. We then use dynamic programming where the state is (row, previous–row–mask, req–mask from the previous row). When we add a new candidate row we must have that every bit that was “required†by the previous row is set in the new candidate row. 3. In the candidate row the “lonely†bits are computed by checking whether: • The cell to its left or right is 1 OR • (if it is not the first row) the cell immediately above is 1. If neither is true, the cell is “lonely†and so we mark that column in the req–mask for the current row (meaning the next row must “rescue†that one). Finally, when we finish row 7 the req–mask must be all zeros (since there is no row 8 to “rescue†any lonely 1’s). One acceptable C solution is given below. (Any correct solution – for example ones using recursion with memoization – is acceptable.) Below is one complete C program that uses a 3–dimensional DP array (indexed by the row number, the previous row’s bitmask, and the “req†bitmask for that row) to obtain the final count. (Note: the number of unholy matrices is huge; the program below uses the non–standard C type “unsigned __int128†to hold very large numbers and then prints them out in decimal.) ------------------------------------------------ /* unholy.c */ #include <stdio.h> #include <stdlib.h> #define ROWS 8 #define COLS 8 #define MASKS (1 << COLS) typedef unsigned __int128 uint128; // A helper function to print an unsigned __int128 in decimal. void print128(uint128 n) { if(n == 0) { printf("0"); return; } char buffer[100]; int pos = 0; while(n > 0) { buffer[pos++] = '0' + (int)(n % 10); n /= 10; } // The digits are in reverse order. for (int i = pos - 1; i >= 0; i--) putchar(buffer[i]); } // // Given a row candidate (an 8-bit mask) and the bitmask of the previous row (prev), // and given the row number (row; note row==0 means first row), // compute the “req†mask for the current row. A bit j in the req mask is 1 if: // the current row has a 1 at column j, AND // it does NOT have a horizontal neighbor (i.e. column j–1 or j+1 is 1) AND // (if row>0) does NOT have a 1 directly above (i.e. in prev at column j). // For row 0 there is no row above so the horizontal condition is all that matters. unsigned int compute_req(unsigned int cur, unsigned int prev, int row) { unsigned int req = 0; for (int j = 0; j < COLS; j++) { if (cur & (1 << j)) { int safe = 0; // Check left and right neighbors: if (j > 0 && (cur & (1 << (j-1)))) safe = 1; if (j < COLS - 1 && (cur & (1 << (j+1)))) safe = 1; // Check upward neighbor (if not first row): if (row > 0 && (prev & (1 << j))) safe = 1; // If not safe then we require a vertical rescue in the next row. if (!safe) req |= (1 << j); } } return req; } int main(void) { // dp[row][prev_row][req] = number of ways to fill rows 0..(row-1) // (row runs from 0 to ROWS, so dp[ROWS] corresponds to having filled all rows) // Note: since we only use 8-bit masks (0..255), we make arrays of size MASKS. static uint128 dp[ROWS+1][MASKS][MASKS] = {{{0}}}; // Base case: before any row is placed, there is no previous row. // We now “choose†row 0. for (unsigned int candidate = 0; candidate < MASKS; candidate++) { // For row 0, there is no upward neighbor, so a 1 is safe only if it has a horizontal neighbor. unsigned int req = compute_req(candidate, 0, 0); dp[1][candidate][req] += 1; } // Now fill rows 1 ... 7. for (int row = 1; row < ROWS; row++) { for (unsigned int prev = 0; prev < MASKS; prev++) { for (unsigned int prev_req = 0; prev_req < MASKS; prev_req++) { uint128 ways = dp[row][prev][prev_req]; if(ways == 0) continue; // When we choose the current row "cur", we must have that // every column that was required by the previous row is 1 in cur. for (unsigned int cur = 0; cur < MASKS; cur++) { if ((prev_req & ~cur) != 0) continue; // some required column is missing in cur. // Now compute the new req for cur. unsigned int new_req = compute_req(cur, prev, row); dp[row+1][cur][new_req] += ways; } } } } // Finally, after filling row 7, we have a state dp[ROWS][prev][req]. // But now row = 8 means that row 7’s lonely ones must have already been “rescued†// (since there is no row 8). Thus we must require req==0. uint128 ans = 0; for (unsigned int prev = 0; prev < MASKS; prev++) { ans += dp[ROWS][prev][0]; } printf("The total number of unholy 8x8 matrices is:\n"); print128(ans); printf("\n"); return 0; } ------------------------------------------------ Explanation: 1. We preâ€compute the “req†mask for each row. For row 0, a 1 is “safe†only if it has a horizontal neighbour; for later rows a 1 is safe if it has a horizontal neighbour or if there is already a 1 immediately above. 2. We initialize dp[1][candidate][req] for every candidate for row 0. 3. For every subsequent row (from 1 to 7), we require that the candidate row “rescue†every lonely 1 from the previous row (i.e. every column where prev_req is 1). 4. After placing the 8th row the req mask must be 0. 5. The final answer is accumulated and printed. Any solution that correctly counts the matrices is acceptable. (Note: Since the number of such matrices is enormous, other methods for bigâ€integer arithmetic might also be used.)
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 | /* unholy.c */ #include <stdio.h> #include <stdlib.h> #define ROWS 8 #define COLS 8 #define MASKS (1 << COLS) typedef unsigned __int128 uint128; // A helper function to print an unsigned __int128 in decimal. void print128(uint128 n) { if(n == 0) { printf("0"); return; } char buffer[100]; int pos = 0; while(n > 0) { buffer[pos++] = '0' + (int)(n % 10); n /= 10; } // The digits are in reverse order. for (int i = pos - 1; i >= 0; i--) putchar(buffer[i]); } // // Given a row candidate (an 8-bit mask) and the bitmask of the previous row (prev), // and given the row number (row; note row==0 means first row), // compute the “req†mask for the current row. A bit j in the req mask is 1 if: // the current row has a 1 at column j, AND // it does NOT have a horizontal neighbor (i.e. column j–1 or j+1 is 1) AND // (if row>0) does NOT have a 1 directly above (i.e. in prev at column j). // For row 0 there is no row above so the horizontal condition is all that matters. unsigned int compute_req(unsigned int cur, unsigned int prev, int row) { unsigned int req = 0; for (int j = 0; j < COLS; j++) { if (cur & (1 << j)) { int safe = 0; // Check left and right neighbors: if (j > 0 && (cur & (1 << (j-1)))) safe = 1; if (j < COLS - 1 && (cur & (1 << (j+1)))) safe = 1; // Check upward neighbor (if not first row): if (row > 0 && (prev & (1 << j))) safe = 1; // If not safe then we require a vertical rescue in the next row. if (!safe) req |= (1 << j); } } return req; } int main(void) { // dp[row][prev_row][req] = number of ways to fill rows 0..(row-1) // (row runs from 0 to ROWS, so dp[ROWS] corresponds to having filled all rows) // Note: since we only use 8-bit masks (0..255), we make arrays of size MASKS. static uint128 dp[ROWS+1][MASKS][MASKS] = {{{0}}}; // Base case: before any row is placed, there is no previous row. // We now “choose†row 0. for (unsigned int candidate = 0; candidate < MASKS; candidate++) { // For row 0, there is no upward neighbor, so a 1 is safe only if it has a horizontal neighbor. unsigned int req = compute_req(candidate, 0, 0); dp[1][candidate][req] += 1; } // Now fill rows 1 ... 7. for (int row = 1; row < ROWS; row++) { for (unsigned int prev = 0; prev < MASKS; prev++) { for (unsigned int prev_req = 0; prev_req < MASKS; prev_req++) { uint128 ways = dp[row][prev][prev_req]; if(ways == 0) continue; // When we choose the current row "cur", we must have that // every column that was required by the previous row is 1 in cur. for (unsigned int cur = 0; cur < MASKS; cur++) { if ((prev_req & ~cur) != 0) continue; // some required column is missing in cur. // Now compute the new req for cur. unsigned int new_req = compute_req(cur, prev, row); dp[row+1][cur][new_req] += ways; } } } } // Finally, after filling row 7, we have a state dp[ROWS][prev][req]. // But now row = 8 means that row 7’s lonely ones must have already been “rescued†// (since there is no row 8). Thus we must require req==0. uint128 ans = 0; for (unsigned int prev = 0; prev < MASKS; prev++) { ans += dp[ROWS][prev][0]; } printf("The total number of unholy 8x8 matrices is:\n"); print128(ans); printf("\n"); 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 | /* unholy.c */ #include <stdio.h> #include <stdlib.h> #define ROWS 8 #define COLS 8 #define MASKS (1 << COLS) typedef unsigned __int128 uint128; // A helper function to print an unsigned __int128 in decimal. void print128(uint128 n) { if(n == 0) { printf("0"); return; } char buffer[100]; int pos = 0; while(n > 0) { buffer[pos++] = '0' + (int)(n % 10); n /= 10; } // The digits are in reverse order. for (int i = pos - 1; i >= 0; i--) putchar(buffer[i]); } // // Given a row candidate (an 8-bit mask) and the bitmask of the previous row (prev), // and given the row number (row; note row==0 means first row), // compute the “req†mask for the current row. A bit j in the req mask is 1 if: // the current row has a 1 at column j, AND // it does NOT have a horizontal neighbor (i.e. column j–1 or j+1 is 1) AND // (if row>0) does NOT have a 1 directly above (i.e. in prev at column j). // For row 0 there is no row above so the horizontal condition is all that matters. unsigned int compute_req(unsigned int cur, unsigned int prev, int row) { unsigned int req = 0; for (int j = 0; j < COLS; j++) { if (cur & (1 << j)) { int safe = 0; // Check left and right neighbors: if (j > 0 && (cur & (1 << (j-1)))) safe = 1; if (j < COLS - 1 && (cur & (1 << (j+1)))) safe = 1; // Check upward neighbor (if not first row): if (row > 0 && (prev & (1 << j))) safe = 1; // If not safe then we require a vertical rescue in the next row. if (!safe) req |= (1 << j); } } return req; } int main(void) { // dp[row][prev_row][req] = number of ways to fill rows 0..(row-1) // (row runs from 0 to ROWS, so dp[ROWS] corresponds to having filled all rows) // Note: since we only use 8-bit masks (0..255), we make arrays of size MASKS. static uint128 dp[ROWS+1][MASKS][MASKS] = {{{0}}}; // Base case: before any row is placed, there is no previous row. // We now “choose†row 0. for (unsigned int candidate = 0; candidate < MASKS; candidate++) { // For row 0, there is no upward neighbor, so a 1 is safe only if it has a horizontal neighbor. unsigned int req = compute_req(candidate, 0, 0); dp[1][candidate][req] += 1; } // Now fill rows 1 ... 7. for (int row = 1; row < ROWS; row++) { for (unsigned int prev = 0; prev < MASKS; prev++) { for (unsigned int prev_req = 0; prev_req < MASKS; prev_req++) { uint128 ways = dp[row][prev][prev_req]; if(ways == 0) continue; // When we choose the current row "cur", we must have that // every column that was required by the previous row is 1 in cur. for (unsigned int cur = 0; cur < MASKS; cur++) { if ((prev_req & ~cur) != 0) continue; // some required column is missing in cur. // Now compute the new req for cur. unsigned int new_req = compute_req(cur, prev, row); dp[row+1][cur][new_req] += ways; } } } } // Finally, after filling row 7, we have a state dp[ROWS][prev][req]. // But now row = 8 means that row 7’s lonely ones must have already been “rescued†// (since there is no row 8). Thus we must require req==0. uint128 ans = 0; for (unsigned int prev = 0; prev < MASKS; prev++) { ans += dp[ROWS][prev][0]; } printf("The total number of unholy 8x8 matrices is:\n"); print128(ans); printf("\n"); return 0; } |
The total number of unholy 8x8 matrices is:
1121231537486377866
Testing if the previous output contains the string 1121231537486377866: True