ucw/digit.c

   1 /*
   2  *      Enumerate positions of the game Digit
   3  *
   4  *      Martin Mares <mj@ucw.cz>, September 2011
   5  */
   6
   7 #include <ucw/lib.h>
   8
   9 #include <stdio.h>
  10 #include <string.h>
  11
  12 #define MATCHES 5
  13 #define SIZE (2*MATCHES+5)
  14 /* +5, because possible_moves() sometimes needs to represent a disconnected 5-match configuration with 1 gap */
  15
  16 typedef char conf[SIZE][SIZE];
  17
  18 static void print(conf c)
  19 {
  20   for (int i=0; i<SIZE; i++)
  21     {
  22       for (int j=0; j<SIZE; j++)
  23         if ((i%2) != (j%2))
  24           {
  25             if (c[i][j])
  26               putchar((i%2) ? '|' : '-');
  27             else
  28               putchar('.');
  29           }
  30         else
  31           {
  32             if (c[i][j])
  33               putchar('?');
  34             else
  35               putchar(' ');
  36           }
  37       putchar('\n');
  38     }
  39   // putchar('\n');
  40 }
  41
  42 static void print_matches(conf c)
  43 {
  44   printf("@@");
  45   for (int i=0; i<SIZE; i++)
  46     for (int j=1-i%2; j<SIZE; j+=2)
  47       if (c[i][j])
  48         {
  49           if (i%2)
  50             printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2+1, j/2);
  51           else
  52             printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2, j/2+1);
  53         }
  54   putchar('\n');
  55 }
  56
  57 static void norm(conf from, conf to)
  58 {
  59   int ii=SIZE, jj=SIZE;
  60   for (int i=0; i<SIZE; i++)
  61     for (int j=0; j<SIZE; j++)
  62       if (from[i][j])
  63         {
  64           ii = MIN(ii, i);
  65           jj = MIN(jj, j);
  66         }
  67   ASSERT(ii < SIZE && jj < SIZE);
  68
  69   int di = 2 - (ii & ~1U);
  70   int dj = 2 - (jj & ~1U);
  71
  72   bzero(to, sizeof(conf));
  73   for (int i=ii; i<SIZE; i++)
  74     for (int j=jj; j<SIZE; j++)
  75       if (from[i][j])
  76         {
  77           int fi = i + di;
  78           int fj = j + dj;
  79           ASSERT(fi >= 0 && fj >= 0 && fi < SIZE && fj < SIZE);
  80           to[fi][fj] = 1;
  81         }
  82 }
  83
  84 static void mirror(conf from, conf to)
  85 {
  86   for (int i=0; i<SIZE; i++)
  87     for (int j=0; j<SIZE; j++)
  88       to[i][j] = from[j][i];
  89 }
  90
  91 static void rotate(conf from, conf to)
  92 {
  93   for (int i=0; i<SIZE; i++)
  94     for (int j=0; j<SIZE; j++)
  95       to[j][SIZE-1-i] = from[i][j];
  96 }
  97
  98 static int rr(conf c, int i, int j)
  99 {
 100   if (i < 0 || i >= SIZE || j < 0 || j >= SIZE)
 101     return 0;
 102   else
 103     return c[i][j];
 104 }
 105
 106 static int has_neighbor(conf c, int i, int j)
 107 {
 108   if ((i%2) ? (rr(c, i-2, j) || rr(c, i+2, j))
 109             : (rr(c, i, j-2) || rr(c, i, j+2)))
 110     return 1;
 111   if (rr(c, i-1, j-1) || rr(c, i-1, j+1) ||
 112       rr(c, i+1, j-1) || rr(c, i+1, j+1))
 113     return 1;
 114   return 0;
 115 }
 116
 117 struct state {
 118   conf c;
 119   int matches;
 120   int id;
 121   int from;
 122   int indegree;
 123   int outdegree;
 124 };
 125
 126 #define MAXSTATES 1000
 127
 128 static struct state states[MAXSTATES];
 129 static int ri, wi;
 130
 131 static struct state *lookup_direct(conf c)
 132 {
 133   conf n;
 134   norm(c, n);
 135   for (int i=0; i<wi; i++)
 136     if (!memcmp(states[i].c, n, sizeof(conf)))
 137       return &states[i];
 138   return NULL;
 139 }
 140
 141 static struct state *lookup_rot(conf c)
 142 {
 143   conf d[4];
 144   memcpy(d[0], c, sizeof(conf));
 145   for (int i=0; i<4; i++)
 146     {
 147       struct state *s = lookup_direct(d[i]);
 148       if (s)
 149         return s;
 150       if (i < 3)
 151         rotate(d[i], d[i+1]);
 152     }
 153   return NULL;
 154 }
 155
 156 static struct state *lookup(conf c)
 157 {
 158   struct state *s = lookup_rot(c);
 159 #if 1
 160   if (s)
 161     return s;
 162   conf d;
 163   mirror(c, d);
 164   return lookup_rot(d);
 165 #else
 166   return s;
 167 #endif
 168 }
 169
 170 static void generate(void)
 171 {
 172   conf c = { [2][5] = 1 };
 173   norm(c, states[0].c);
 174   states[0].matches = 1;
 175   states[0].id = 1;
 176   wi = 1;
 177
 178   while (ri < wi)
 179     {
 180       struct state *s = &states[ri++];
 181       conf to;
 182       memcpy(to, s->c, sizeof(conf));
 183       printf("### State %d (%d matches) ###\n", s->id, s->matches);
 184       print(to);
 185       if (s->matches < MATCHES)
 186         {
 187           for (int i=0; i<SIZE; i++)
 188             for (int j=1-(i%2); j<SIZE; j+=2)
 189               if (!to[i][j] && has_neighbor(to, i, j))
 190                 {
 191                   to[i][j] = 1;
 192                   struct state *t = lookup(to);
 193                   if (!t)
 194                     {
 195                       ASSERT(wi < MAXSTATES);
 196                       t = &states[wi++];
 197                       norm(to, t->c);
 198                       t->matches = s->matches+1;
 199                       t->id = wi;
 200                     }
 201                   if (t->from != s->id)
 202                     {
 203                       printf("-> %d\n", t->id);
 204                       t->from = s->id;
 205                       t->indegree++;
 206                       s->outdegree++;
 207                     }
 208                   to[i][j] = 0;
 209                 }
 210         }
 211       printf("Degree: %d in, %d out, from=%d\n", s->indegree, s->outdegree, s->from);
 212       print_matches(s->c);
 213       putchar('\n');
 214     }
 215 }
 216
 217 static void possible_moves(void)
 218 {
 219   puts("\n=== POSSIBLE MOVES ===\n\n");
 220
 221   for (int i=0; i<wi; i++)
 222     states[i].from = 0;
 223
 224   for (int i=0; i<wi; i++)
 225     {
 226       struct state *s = &states[i];
 227       if (s->matches < MATCHES)
 228         continue;
 229       conf c;
 230       memcpy(c, s->c, sizeof(conf));
 231
 232       printf("### State %d ###\n", s->id);
 233       print(s->c);
 234
 235       int neighbors = 0;
 236       for (int j=0; j<SIZE; j++)
 237         for (int k=0; k<SIZE; k++)
 238           if (s->c[j][k])
 239             {
 240               c[j][k] = 0;
 241               for (int p=0; p<SIZE; p++)
 242                 for (int q=0; q<SIZE; q++)
 243                   if (!c[p][q] && (p != j || q != k) && has_neighbor(c, p, q))
 244                     {
 245                       c[p][q] = 1;
 246                       struct state *t = lookup(c);
 247                       if (t && t != s && t->from != s->id)
 248                         {
 249                           t->from = s->id;
 250                           // printf("-> state %d\n", t->id);
 251                           // print(t->c);
 252                           neighbors++;
 253                         }
 254                       c[p][q] = 0;
 255                     }
 256               c[j][k] = 1;
 257             }
 258
 259       printf("=> %d neighbors\n\n", neighbors);
 260     }
 261 }
 262
 263 int main(void)
 264 {
 265   generate();
 266   possible_moves();
 267   return 0;
 268 }