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