7 #define SIZE (2*MATCHES+3)
9 typedef char conf[SIZE][SIZE];
11 static void print(conf c)
13 for (int i=0; i<SIZE; i++)
15 for (int j=0; j<SIZE; j++)
19 putchar((i%2) ? '|' : '-');
35 static void norm(conf from, conf to)
38 for (int i=0; i<SIZE; i++)
39 for (int j=0; j<SIZE; j++)
45 ASSERT(ii < SIZE && jj < SIZE);
47 int di = 2 - (ii & ~1U);
48 int dj = 2 - (jj & ~1U);
50 bzero(to, sizeof(conf));
51 for (int i=ii; i<SIZE; i++)
52 for (int j=jj; j<SIZE; j++)
57 ASSERT(fi >= 0 && fj >= 0 && fi < SIZE && fj < SIZE);
62 static void mirror(conf from, conf to)
64 for (int i=0; i<SIZE; i++)
65 for (int j=0; j<SIZE; j++)
66 to[i][j] = from[j][i];
69 static void rotate(conf from, conf to)
71 for (int i=0; i<SIZE; i++)
72 for (int j=0; j<SIZE; j++)
73 to[j][SIZE-1-i] = from[i][j];
76 static int rr(conf c, int i, int j)
78 if (i < 0 || i >= SIZE || j < 0 || j >= SIZE)
84 static int has_neighbor(conf c, int i, int j)
86 if ((i%2) ? (rr(c, i-2, j) || rr(c, i+2, j))
87 : (rr(c, i, j-2) || rr(c, i, j+2)))
89 if (rr(c, i-1, j-1) || rr(c, i-1, j+1) ||
90 rr(c, i+1, j-1) || rr(c, i+1, j+1))
104 #define MAXSTATES 1000
106 static struct state states[MAXSTATES];
109 static struct state *lookup_direct(conf c)
113 for (int i=0; i<wi; i++)
114 if (!memcmp(states[i].c, n, sizeof(conf)))
119 static struct state *lookup_rot(conf c)
122 memcpy(d[0], c, sizeof(conf));
123 for (int i=0; i<4; i++)
125 struct state *s = lookup_direct(d[i]);
129 rotate(d[i], d[i+1]);
134 static struct state *lookup(conf c)
136 struct state *s = lookup_rot(c);
142 return lookup_rot(d);
148 static void generate(void)
150 conf c = { [2][5] = 1 };
151 norm(c, states[0].c);
152 states[0].matches = 1;
158 struct state *s = &states[ri++];
160 memcpy(to, s->c, sizeof(conf));
161 printf("### State %d (%d matches) ###\n", s->id, s->matches);
163 if (s->matches < MATCHES)
165 for (int i=0; i<SIZE; i++)
166 for (int j=1-(i%2); j<SIZE; j+=2)
167 if (!to[i][j] && has_neighbor(to, i, j))
170 struct state *t = lookup(to);
175 t->matches = s->matches+1;
178 if (t->from != s->id)
180 printf("-> %d\n", t->id);
188 printf("Degree: %d in, %d out, from=%d\n\n", s->indegree, s->outdegree, s->from);