ucw/digit.c

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