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+3)
  14
  15 typedef char conf[SIZE][SIZE];
  16
  17 static void print(conf c)
  18 {
  19   for (int i=0; i<SIZE; i++)
  20     {
  21       for (int j=0; j<SIZE; j++)
  22         if ((i%2) != (j%2))
  23           {
  24             if (c[i][j])
  25               putchar((i%2) ? '|' : '-');
  26             else
  27               putchar('.');
  28           }
  29         else
  30           {
  31             if (c[i][j])
  32               putchar('?');
  33             else
  34               putchar(' ');
  35           }
  36       putchar('\n');
  37     }
  38   // putchar('\n');
  39 }
  40
  41 static void print_matches(conf c)
  42 {
  43   printf("@@");
  44   for (int i=0; i<SIZE; i++)
  45     for (int j=1-i%2; j<SIZE; j+=2)
  46       if (c[i][j])
  47         {
  48           if (i%2)
  49             printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2+1, j/2);
  50           else
  51             printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2, j/2+1);
  52         }
  53   putchar('\n');
  54 }
  55
  56 static void norm(conf from, conf to)
  57 {
  58   int ii=SIZE, jj=SIZE;
  59   for (int i=0; i<SIZE; i++)
  60     for (int j=0; j<SIZE; j++)
  61       if (from[i][j])
  62         {
  63           ii = MIN(ii, i);
  64           jj = MIN(jj, j);
  65         }
  66   ASSERT(ii < SIZE && jj < SIZE);
  67
  68   int di = 2 - (ii & ~1U);
  69   int dj = 2 - (jj & ~1U);
  70
  71   bzero(to, sizeof(conf));
  72   for (int i=ii; i<SIZE; i++)
  73     for (int j=jj; j<SIZE; j++)
  74       if (from[i][j])
  75         {
  76           int fi = i + di;
  77           int fj = j + dj;
  78           ASSERT(fi >= 0 && fj >= 0 && fi < SIZE && fj < SIZE);
  79           to[fi][fj] = 1;
  80         }
  81 }
  82
  83 static void mirror(conf from, conf to)
  84 {
  85   for (int i=0; i<SIZE; i++)
  86     for (int j=0; j<SIZE; j++)
  87       to[i][j] = from[j][i];
  88 }
  89
  90 static void rotate(conf from, conf to)
  91 {
  92   for (int i=0; i<SIZE; i++)
  93     for (int j=0; j<SIZE; j++)
  94       to[j][SIZE-1-i] = from[i][j];
  95 }
  96
  97 static int rr(conf c, int i, int j)
  98 {
  99   if (i < 0 || i >= SIZE || j < 0 || j >= SIZE)
 100     return 0;
 101   else
 102     return c[i][j];
 103 }
 104
 105 static int has_neighbor(conf c, int i, int j)
 106 {
 107   if ((i%2) ? (rr(c, i-2, j) || rr(c, i+2, j))
 108             : (rr(c, i, j-2) || rr(c, i, j+2)))
 109     return 1;
 110   if (rr(c, i-1, j-1) || rr(c, i-1, j+1) ||
 111       rr(c, i+1, j-1) || rr(c, i+1, j+1))
 112     return 1;
 113   return 0;
 114 }
 115
 116 struct state {
 117   conf c;
 118   int matches;
 119   int id;
 120   int from;
 121   int indegree;
 122   int outdegree;
 123 };
 124
 125 #define MAXSTATES 1000
 126
 127 static struct state states[MAXSTATES];
 128 static int ri, wi;
 129
 130 static struct state *lookup_direct(conf c)
 131 {
 132   conf n;
 133   norm(c, n);
 134   for (int i=0; i<wi; i++)
 135     if (!memcmp(states[i].c, n, sizeof(conf)))
 136       return &states[i];
 137   return NULL;
 138 }
 139
 140 static struct state *lookup_rot(conf c)
 141 {
 142   conf d[4];
 143   memcpy(d[0], c, sizeof(conf));
 144   for (int i=0; i<4; i++)
 145     {
 146       struct state *s = lookup_direct(d[i]);
 147       if (s)
 148         return s;
 149       if (i < 3)
 150         rotate(d[i], d[i+1]);
 151     }
 152   return NULL;
 153 }
 154
 155 static struct state *lookup(conf c)
 156 {
 157   struct state *s = lookup_rot(c);
 158 #if 1
 159   if (s)
 160     return s;
 161   conf d;
 162   mirror(c, d);
 163   return lookup_rot(d);
 164 #else
 165   return s;
 166 #endif
 167 }
 168
 169 static void generate(void)
 170 {
 171   conf c = { [2][5] = 1 };
 172   norm(c, states[0].c);
 173   states[0].matches = 1;
 174   states[0].id = 1;
 175   wi = 1;
 176
 177   while (ri < wi)
 178     {
 179       struct state *s = &states[ri++];
 180       conf to;
 181       memcpy(to, s->c, sizeof(conf));
 182       printf("### State %d (%d matches) ###\n", s->id, s->matches);
 183       print(to);
 184       if (s->matches < MATCHES)
 185         {
 186           for (int i=0; i<SIZE; i++)
 187             for (int j=1-(i%2); j<SIZE; j+=2)
 188               if (!to[i][j] && has_neighbor(to, i, j))
 189                 {
 190                   to[i][j] = 1;
 191                   struct state *t = lookup(to);
 192                   if (!t)
 193                     {
 194                       t = &states[wi++];
 195                       norm(to, t->c);
 196                       t->matches = s->matches+1;
 197                       t->id = wi;
 198                     }
 199                   if (t->from != s->id)
 200                     {
 201                       printf("-> %d\n", t->id);
 202                       t->from = s->id;
 203                       t->indegree++;
 204                       s->outdegree++;
 205                     }
 206                   to[i][j] = 0;
 207                 }
 208         }
 209       printf("Degree: %d in, %d out, from=%d\n", s->indegree, s->outdegree, s->from);
 210       print_matches(s->c);
 211       putchar('\n');
 212     }
 213 }
 214
 215 int main(void)
 216 {
 217   generate();
 218   return 0;
 219 }