From 8f6f32d1a355e722f434b48afe668ce656914695 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 1 Sep 2011 12:07:30 +0200
Subject: [PATCH] Digit enumerator

---
 ucw/Makefile |   6 +-
 ucw/digit.c  | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 199 insertions(+), 3 deletions(-)
 create mode 100644 ucw/digit.c

diff --git a/ucw/Makefile b/ucw/Makefile
index d14e38f..b5b0684 100644
--- a/ucw/Makefile
+++ b/ucw/Makefile
@@ -1,13 +1,13 @@
-LIBUCW:=$(shell cd ../../sh/main/run && pwd)
+LIBUCW:=$(shell cd ../../libucw/run && pwd)
 UCWCF:=$(shell PKG_CONFIG_PATH=$(LIBUCW)/lib/pkgconfig pkg-config --cflags libucw)
 UCWLF:=$(shell PKG_CONFIG_PATH=$(LIBUCW)/lib/pkgconfig pkg-config --libs libucw)
 
 CC=gcc
 LD=gcc
-CFLAGS=-O2 -Wall -W -Wno-parentheses -Wstrict-prototypes -Wmissing-prototypes -Wundef -Wredundant-decls -std=gnu99 $(UCWCF)
+CFLAGS=-O2 -Wall -W -Wno-parentheses -Wstrict-prototypes -Wmissing-prototypes -Wundef -Wredundant-decls -std=gnu99 $(UCWCF) -ggdb
 LDLIBS+=$(UCWLF)
 
-all: fit
+all: fit digit
 
 clean:
 	rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend -or -name .#*`
diff --git a/ucw/digit.c b/ucw/digit.c
new file mode 100644
index 0000000..ecc5288
--- /dev/null
+++ b/ucw/digit.c
@@ -0,0 +1,196 @@
+#include <ucw/lib.h>
+
+#include <stdio.h>
+#include <string.h>
+
+#define MATCHES 5
+#define SIZE (2*MATCHES+3)
+
+typedef char conf[SIZE][SIZE];
+
+static void print(conf c)
+{
+  for (int i=0; i<SIZE; i++)
+    {
+      for (int j=0; j<SIZE; j++)
+	if ((i%2) != (j%2))
+	  {
+	    if (c[i][j])
+	      putchar((i%2) ? '|' : '-');
+	    else
+	      putchar('.');
+	  }
+	else
+	  {
+	    if (c[i][j])
+	      putchar('?');
+	    else
+	      putchar(' ');
+	  }
+      putchar('\n');
+    }
+  // putchar('\n');
+}
+
+static void norm(conf from, conf to)
+{
+  int ii=SIZE, jj=SIZE;
+  for (int i=0; i<SIZE; i++)
+    for (int j=0; j<SIZE; j++)
+      if (from[i][j])
+	{
+	  ii = MIN(ii, i);
+	  jj = MIN(jj, j);
+	}
+  ASSERT(ii < SIZE && jj < SIZE);
+
+  int di = 2 - (ii & ~1U);
+  int dj = 2 - (jj & ~1U);
+
+  bzero(to, sizeof(conf));
+  for (int i=ii; i<SIZE; i++)
+    for (int j=jj; j<SIZE; j++)
+      if (from[i][j])
+	{
+	  int fi = i + di;
+	  int fj = j + dj;
+	  ASSERT(fi >= 0 && fj >= 0 && fi < SIZE && fj < SIZE);
+	  to[fi][fj] = 1;
+	}
+}
+
+static void mirror(conf from, conf to)
+{
+  for (int i=0; i<SIZE; i++)
+    for (int j=0; j<SIZE; j++)
+      to[i][j] = from[j][i];
+}
+
+static void rotate(conf from, conf to)
+{
+  for (int i=0; i<SIZE; i++)
+    for (int j=0; j<SIZE; j++)
+      to[j][SIZE-1-i] = from[i][j];
+}
+
+static int rr(conf c, int i, int j)
+{
+  if (i < 0 || i >= SIZE || j < 0 || j >= SIZE)
+    return 0;
+  else
+    return c[i][j];
+}
+
+static int has_neighbor(conf c, int i, int j)
+{
+  if ((i%2) ? (rr(c, i-2, j) || rr(c, i+2, j))
+	    : (rr(c, i, j-2) || rr(c, i, j+2)))
+    return 1;
+  if (rr(c, i-1, j-1) || rr(c, i-1, j+1) ||
+      rr(c, i+1, j-1) || rr(c, i+1, j+1))
+    return 1;
+  return 0;
+}
+
+struct state {
+  conf c;
+  int matches;
+  int id;
+  int from;
+  int indegree;
+  int outdegree;
+};
+
+#define MAXSTATES 1000
+
+static struct state states[MAXSTATES];
+static int ri, wi;
+
+static struct state *lookup_direct(conf c)
+{
+  conf n;
+  norm(c, n);
+  for (int i=0; i<wi; i++)
+    if (!memcmp(states[i].c, n, sizeof(conf)))
+      return &states[i];
+  return NULL;
+}
+
+static struct state *lookup_rot(conf c)
+{
+  conf d[4];
+  memcpy(d[0], c, sizeof(conf));
+  for (int i=0; i<4; i++)
+    {
+      struct state *s = lookup_direct(d[i]);
+      if (s)
+	return s;
+      if (i < 3)
+	rotate(d[i], d[i+1]);
+    }
+  return NULL;
+}
+
+static struct state *lookup(conf c)
+{
+  struct state *s = lookup_rot(c);
+#if 1
+  if (s)
+    return s;
+  conf d;
+  mirror(c, d);
+  return lookup_rot(d);
+#else
+  return s;
+#endif
+}
+
+static void generate(void)
+{
+  conf c = { [2][5] = 1 };
+  norm(c, states[0].c);
+  states[0].matches = 1;
+  states[0].id = 1;
+  wi = 1;
+
+  while (ri < wi)
+    {
+      struct state *s = &states[ri++];
+      conf to;
+      memcpy(to, s->c, sizeof(conf));
+      printf("### State %d (%d matches) ###\n", s->id, s->matches);
+      print(to);
+      if (s->matches < MATCHES)
+	{
+	  for (int i=0; i<SIZE; i++)
+	    for (int j=1-(i%2); j<SIZE; j+=2)
+	      if (!to[i][j] && has_neighbor(to, i, j))
+		{
+		  to[i][j] = 1;
+		  struct state *t = lookup(to);
+		  if (!t)
+		    {
+		      t = &states[wi++];
+		      norm(to, t->c);
+		      t->matches = s->matches+1;
+		      t->id = wi;
+		    }
+		  if (t->from != s->id)
+		    {
+		      printf("-> %d\n", t->id);
+		      t->from = s->id;
+		      t->indegree++;
+		      s->outdegree++;
+		    }
+		  to[i][j] = 0;
+		}
+	}
+      printf("Degree: %d in, %d out, from=%d\n\n", s->indegree, s->outdegree, s->from);
+    }
+}
+
+int main(void)
+{
+  generate();
+  return 0;
+}
-- 
2.39.2