From: Simon Tatham <anakin@pobox.com>
Date: Sat, 8 Mar 2014 14:10:06 +0000 (+0000)
Subject: Check max Hamming weight in the other direction.
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=matchsticks-search.git;a=commitdiff_plain;h=ea5f3526c7c05c153a9c7c49e91c9ac649560fba

Check max Hamming weight in the other direction.

Once we've already got a solution, we can further winnow the set of
possible adjacency matrices, by ensuring the same bit is not set in
too many entries of adjmatrix (since if it were, some length-n stick
would have to be divided into enough pieces to make one at most the
already-known best result). This adds complexity to each step of the
recursion over possible matrices, but by early pruning it seems to cut
down the number of steps by rather more; I estimate a factor of four
speedup in pursuit of (n,m)=(10,7).
---

diff --git a/Makefile b/Makefile
index 5c571d2..225239d 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-CFLAGS += -Wall -Wwrite-strings -Wstrict-prototypes -g -O2
+CFLAGS += -Wall -Wwrite-strings -Wstrict-prototypes -g -O2 --std=gnu99
 LC_CTYPE=C
 LDLIBS = -lpub -lglpk
 
diff --git a/main.c b/main.c
index 6f0df72..3c1b123 100644
--- a/main.c
+++ b/main.c
@@ -86,6 +86,9 @@ static double best;
 static glp_prob *best_prob;
 static AdjWord *best_adjmatrix;
 
+static int n_over_best;
+static int *weight;
+
 static unsigned printcounter;
 
 static AdjWord *xalloc_adjmatrix(void) {
@@ -96,6 +99,9 @@ static void prep(void) {
   adjall = ~((~(AdjWord)0) << m);
   adjmatrix = xalloc_adjmatrix();
   glp_term_out(GLP_OFF);
+  n_over_best = n / best;
+  weight = (int *)malloc(m*sizeof(int));
+  for (int j = 0; j < m; j++) weight[j] = 0;
 }
 
 static AdjWord one_adj_bit(int bitnum) {
@@ -300,6 +306,7 @@ static void optimise(int doprint) {
   HAVE_PRINTED;
 
   best = got;
+  n_over_best = n / best;
 
   if (best_prob) glp_delete_prob(best_prob);
   best_prob = prob;
@@ -331,9 +338,20 @@ static void iterate_recurse(int i, AdjWord min) {
       goto again;
     if (i == 0 && (adjmatrix[i] & (1+adjmatrix[i])))
       goto again;
+    for (int j = 0; j < m; j++)
+      if (adjmatrix[i] & (1 << j))
+        weight[j]++;
+    for (int j = 0; j < m; j++)
+      if (weight[j] >= n_over_best)
+        goto takeout;
 
     iterate_recurse(i+1, adjmatrix[i]);
 
+   takeout:
+    for (int j = 0; j < m; j++)
+      if (adjmatrix[i] & (1 << j))
+        weight[j]--;
+
   again:
     if (adjmatrix[i] == adjall)
       return;