From: Ian Jackson <ijackson@chiark.greenend.org.uk>
Date: Sun, 9 Mar 2014 12:29:12 +0000 (+0000)
Subject: minimum output match hamming weight; enforce argument ordering
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=matchsticks-search.git;a=commitdiff_plain;h=4612c66ee3e04a8a29a4752de8b658759b77e70f

minimum output match hamming weight; enforce argument ordering

This seems to provide a very dramatic speedup.
---

diff --git a/main.c b/main.c
index 57a9796..97b4bbb 100644
--- a/main.c
+++ b/main.c
@@ -5,7 +5,9 @@
  *
  * Invoke as   ./main n m
  *
- * The algorithm is faster if the arguments are ordered so that n > m.
+ * The arguments must be ordered so that n > m:
+ *   n is the number of (more, shorter) input matches of length m
+ *   m is the number of (fewer, longer) output matches of length n
  */
 
 /*
@@ -84,7 +86,10 @@
  *
  * We further winnow the set of possible adjacency matrices, by
  * ensuring the same bit is not set in too many entries of adjmatrix
- * (ie, as above, only considering output sticks).
+ * (ie, as above, only considering output sticks); and by ensuring
+ * that it is not set in too few: each output stick must consist
+ * of at least two fragments since the output sticks are longer than
+ * the input ones.
  *
  * And, we want to do the search in order of increasing maximum
  * hamming weight.  This is because in practice optimal solutions tend
@@ -453,6 +458,13 @@ static void optimise(bool doprint) {
   if (!ok)
     goto out;
 
+  for (j=0; j<m; j++)
+    if (weight[j] < 2) {
+      PRINTF(" nominham");
+      goto out;
+    }
+
+
   /*
    * We formulate our problem as an LP problem as follows.
    * In this file "n" and "m" are the matchstick numbers.
@@ -712,6 +724,7 @@ int main(int argc, char **argv) {
   assert(argc==3);
   n = atoi(argv[1]);
   m = atoi(argv[2]);
+  assert(n > m);
 
   prep();