Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/misc

[misc.git] / ucw / digit.c

diff --git a/ucw/digit.c b/ucw/digit.c
index ecc5288d78738e75e1539ff38d68bf2e6b9752b9..7cc9867d0a823143f090a72b4a530f140f320b93 100644 (file)
--- a/ucw/digit.c
+++ b/ucw/digit.c
@@ -1,10 +1,17 @@
+/*
+ *     Enumerate positions of the game Digit
+ *
+ *     Martin Mares <mj@ucw.cz>, September 2011
+ */
+
 #include <ucw/lib.h>
 
 #include <stdio.h>
 #include <string.h>
 
 #define MATCHES 5
-#define SIZE (2*MATCHES+3)
+#define SIZE (2*MATCHES+5)
+/* +5, because possible_moves() sometimes needs to represent a disconnected 5-match configuration with 1 gap */
 
 typedef char conf[SIZE][SIZE];
 
@@ -32,6 +39,21 @@ static void print(conf c)
   // putchar('\n');
 }
 
+static void print_matches(conf c)
+{
+  printf("@@");
+  for (int i=0; i<SIZE; i++)
+    for (int j=1-i%2; j<SIZE; j+=2)
+      if (c[i][j])
+       {
+         if (i%2)
+           printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2+1, j/2);
+         else
+           printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2, j/2+1);
+       }
+  putchar('\n');
+}
+
 static void norm(conf from, conf to)
 {
   int ii=SIZE, jj=SIZE;
@@ -170,6 +192,7 @@ static void generate(void)
                  struct state *t = lookup(to);
                  if (!t)
                    {
+                     ASSERT(wi < MAXSTATES);
                      t = &states[wi++];
                      norm(to, t->c);
                      t->matches = s->matches+1;
@@ -185,12 +208,61 @@ static void generate(void)
                  to[i][j] = 0;
                }
        }
-      printf("Degree: %d in, %d out, from=%d\n\n", s->indegree, s->outdegree, s->from);
+      printf("Degree: %d in, %d out, from=%d\n", s->indegree, s->outdegree, s->from);
+      print_matches(s->c);
+      putchar('\n');
+    }
+}
+
+static void possible_moves(void)
+{
+  puts("\n=== POSSIBLE MOVES ===\n\n");
+
+  for (int i=0; i<wi; i++)
+    states[i].from = 0;
+
+  for (int i=0; i<wi; i++)
+    {
+      struct state *s = &states[i];
+      if (s->matches < MATCHES)
+       continue;
+      conf c;
+      memcpy(c, s->c, sizeof(conf));
+
+      printf("### State %d ###\n", s->id);
+      print(s->c);
+
+      int neighbors = 0;
+      for (int j=0; j<SIZE; j++)
+       for (int k=0; k<SIZE; k++)
+         if (s->c[j][k])
+           {
+             c[j][k] = 0;
+             for (int p=0; p<SIZE; p++)
+               for (int q=0; q<SIZE; q++)
+                 if (!c[p][q] && (p != j || q != k) && has_neighbor(c, p, q))
+                   {
+                     c[p][q] = 1;
+                     struct state *t = lookup(c);
+                     if (t && t != s && t->from != s->id)
+                       {
+                         t->from = s->id;
+                         // printf("-> state %d\n", t->id);
+                         // print(t->c);
+                         neighbors++;
+                       }
+                     c[p][q] = 0;
+                   }
+             c[j][k] = 1;
+           }
+
+      printf("=> %d neighbors\n\n", neighbors);
     }
 }
 
 int main(void)
 {
   generate();
+  possible_moves();
   return 0;
 }