-
Notifications
You must be signed in to change notification settings - Fork 0
/
compute_cycles.c
133 lines (113 loc) · 4.14 KB
/
compute_cycles.c
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
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include "dots.h"
/* Find all the dots encircled by a cycle by doing a flood fill from the outside. */
mask_t get_encircled_dots(mask_t mask) {
mask_t outside = EMPTY_MASK;
int i, stack_size = 0, stack[NUM_DOTS] = {0};
#define ADD_TO_OUTSIDE(j) { \
if (!MASK_CONTAINS(outside, j)) { \
/* Mark the dot as being on the outside. */ \
outside = ADD_TO_MASK(outside, j); \
/* Don't flood past the mask, which is the boundary between outside and in. */ \
if (!MASK_CONTAINS(mask, j)) { \
stack[stack_size++] = j; \
} \
} \
}
/* Add the whole outside border to the stack. */
for (i = 0; i < NUM_ROWS; i++) {
ADD_TO_OUTSIDE(MASK_INDEX(i, 0));
ADD_TO_OUTSIDE(MASK_INDEX(i, NUM_COLS - 1));
}
for (i = 1; i < NUM_COLS - 1; i++) {
ADD_TO_OUTSIDE(MASK_INDEX(0, i));
ADD_TO_OUTSIDE(MASK_INDEX(NUM_ROWS - 1, i));
}
while (stack_size) {
int row, r, r0, r1, col, c, c0, c1;
i = stack[--stack_size];
row = INDEX_ROW(i);
col = INDEX_COL(i);
/* Bounds checking */
r0 = (row == 0) ? row : row - 1;
r1 = (row == NUM_ROWS - 1) ? row : row + 1;
c0 = (col == 0) ? col : col - 1;
c1 = (col == NUM_COLS - 1) ? col : col + 1;
/* Flood in all directions, including diagonally. */
for (r = r0; r <= r1; r++) {
for (c = c0; c <= c1; c++) {
int j = MASK_INDEX(r, c);
if (i != j) {
ADD_TO_OUTSIDE(j);
}
}
}
}
/* Everything that isn't on the outside, is on the inside! */
return ~outside & ALL_DOTS;
}
int main() {
int i, col, row;
for (col = 0; col < NUM_COLS - 1; col++) {
for (row = 0; row < NUM_ROWS - 1; row++) {
mask_t square = EMPTY_MASK;
square |= ((mask_t)3) << MASK_INDEX(row, col);
square |= ((mask_t)3) << MASK_INDEX(row, col + 1);
printf("%" PRId64 " %" PRId64 "\n", square, EMPTY_MASK);
}
}
/* Try each permuation of the center 16 dots that could be encircled by a cycle. */
for (i = 1; i < (1 << 16); i++) {
mask_t encircled_dots, mask, inside_dots;
int j;
/* Skip the two disconnected masks:
*
* X X X X X X
* X X X X
* X X X and X X X
* X X X X X X
* X X X X
* X X X X X X
*/
if (i == ((1<< 0)|(1<<15)) || i == ((1<<4)|(1<<12))) {
continue;
}
/* Move the 16 bits into the center 16 dots of a mask. */
encircled_dots = EMPTY_MASK;
encircled_dots |= ((i >> 0) & 15) << 7;
encircled_dots |= ((i >> 4) & 15) << 13;
encircled_dots |= ((i >> 8) & 15) << 19;
encircled_dots |= ((i >> 12) & 15) << 25;
/* Mask a 3x3 square around each of the encircled dots, and then negate the encircled dots.
* This leaves behind just the potential cycle.
*/
mask = EMPTY_MASK;
for (j = 0; j < NUM_DOTS; j++) {
if (MASK_CONTAINS(encircled_dots, j)) {
mask |= (mask_t)7 << (j - 1 - NUM_ROWS);
mask |= (mask_t)7 << (j - 1);
mask |= (mask_t)7 << (j - 1 + NUM_ROWS);
}
}
mask &= ~encircled_dots & ALL_DOTS;
/* Disregard moves that have extraneous dots on the inside. For example:
*
* X X X X X X X X X X X X
* X X X X
* X X and X X
* X X X X
* X X X X X X
* X X X X X X X X X X X X
*
* are equivalent, so disregard the first one.
*/
inside_dots = get_encircled_dots(mask);
if (inside_dots != encircled_dots) {
continue;
}
printf("%" PRId64 " %" PRId64 "\n", mask, mask | inside_dots);
}
return 0;
}