search in order by max hamming weight

[matchsticks-search.git] / main.c

diff --git a/main.c b/main.c
index e093311d63ea31e18909fdc7a7f71c6d409318bb..15b534bd3bc3c9eb0447b059e5bf013de4969b44 100644 (file)
--- a/main.c
+++ b/main.c
@@ -4,6 +4,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
+#include <stdbool.h>
 #include <inttypes.h>
 
 #include <publib.h>
@@ -12,7 +13,7 @@
 typedef uint32_t AdjWord;
 #define PRADJ "08"PRIx32
 
-static int n, m;
+static int n, m, maxhamweight;
 static AdjWord *adjmatrix;
 static AdjWord adjall;
 
@@ -53,8 +54,12 @@ static void optimise(int doprint) {
  retry_with_print:
 #define PRINTF if (!doprint) ; else printf /* bodgy */
 
+  PRINTF("%2d ", maxhamweight);
+
+  bool had_max = 0;
   for (i=0, totalfrags=0; i<n; i++) {
     int frags = count_set_adj_bits(adjmatrix[i]);
+    had_max += (frags == maxhamweight);
     totalfrags += frags;
     PRINTF("%"PRADJ" ", adjmatrix[i]);
     double maxminsize = (double)m / frags;
@@ -63,6 +68,10 @@ static void optimise(int doprint) {
       goto out;
     }
   }
+  if (!had_max) {
+    PRINTF(" nomaxham");
+    goto out;
+  }
 
   /*
    * We formulate our problem as an LP problem as follows.
@@ -236,14 +245,25 @@ static void iterate_recurse(int i, AdjWord min) {
   for (adjmatrix[i] = min;
        ;
        adjmatrix[i]++) {
+    if (count_set_adj_bits(adjmatrix[i]) > maxhamweight)
+      goto again;
+
     iterate_recurse(i+1, adjmatrix[i]);
+
+  again:
     if (adjmatrix[i] == adjall)
       return;
   }
 }
 
 static void iterate(void) {
-  iterate_recurse(0, 1);
+  for (maxhamweight=1; maxhamweight<=m; maxhamweight++) {
+    double maxminsize = (double)m / maxhamweight;
+    if (maxminsize <= best)
+      continue;
+
+    iterate_recurse(0, 1);
+  }
 }
 
 int main(int argc, char **argv) {