use "git describe" not "git-describe"

[matchsticks-search.git] / main.c

diff --git a/main.c b/main.c
index 93dc7ebe5325269db8fda05f5fe954a081489ed3..c5a49918869d9c8c1b07d865353cb856ece2c61f 100644 (file)
--- 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
  */
 
 /*
@@ -82,6 +84,13 @@
  * than our best solution.  That is, we reject candidates where any of
  * the hamming weights of the adjacency bitmap words are too large.
  *
+ * 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); 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
  * to have low hamming weight, and having found a reasonable solution
@@ -619,6 +628,10 @@ static void iterate_recurse(int i, AdjWord min) {
   AdjWord jbit;
 
   if (i >= n) {
+    for (j=0; j<m; j++)
+      if (weight[j] < 2)
+       return;
+
     printcounter++;
     optimise(!(printcounter & 0xfff));
     return;
@@ -708,6 +721,7 @@ int main(int argc, char **argv) {
   assert(argc==3);
   n = atoi(argv[1]);
   m = atoi(argv[2]);
+  assert(n > m);
 
   prep();