X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?a=blobdiff_plain;f=main.c;h=96f945cf0efd8f91a425997222536638d75e1ef1;hb=621cca6b657fd955da0f1e309b0df5d6cf0901e7;hp=b38b0ce5e1bbe8cb4d5427dd6184447f0eb94ab8;hpb=0d60fbb2fa5f40382fa260fd039d262bf583406d;p=matchsticks-search.git

diff --git a/main.c b/main.c
index b38b0ce..96f945c 100644
--- a/main.c
+++ b/main.c
@@ -115,7 +115,7 @@ static double best;
 static glp_prob *best_prob;
 static AdjWord *best_adjmatrix;
 
-static int n_max_frags, m_max_frags;
+static int n_max_frags=INT_MAX, m_max_frags=INT_MAX;
 static int *weight;
 
 static unsigned printcounter;
@@ -147,8 +147,10 @@ static void set_best(double new_best) {
    * subtract a fudge factor from our target.
    */
   double near_best = best * 0.98 - 0.02;
-  n_max_frags = ceil(n / near_best) - 1;
-  m_max_frags = ceil(m / near_best) - 1;
+  if (near_best > 0) {
+    n_max_frags = ceil(n / near_best) - 1;
+    m_max_frags = ceil(m / near_best) - 1;
+  }
 }
 
 /*----- multicore support -----*/
@@ -263,6 +265,8 @@ static void multicore_outer_iteration(int i, AdjWord min) {
 }
 
 static void mc_iterate_worker(void) {
+  static time_t lastprint;
+
   for (;;) {
     mc_rwvsetup_outer();
     ssize_t r = readv(mc_work[0], mc_iov, mc_niovs);
@@ -272,8 +276,12 @@ static void mc_iterate_worker(void) {
     bool ok = maxhamweight_ok();
     if (!ok) continue;
 
-    ok = preconsider_ok(multicore_iteration_boundary, 1);
-    progress_eol();
+    time_t now = time(0);
+    bool doprint = now != lastprint;
+    lastprint = now;
+
+    ok = preconsider_ok(multicore_iteration_boundary, doprint);
+    if (doprint) progress_eol();
     if (!ok) continue;
 
     /* stop iterate_recurse from trying to run multicore_outer_iteration */
@@ -384,8 +392,6 @@ static void prep(void) {
   glp_term_out(GLP_OFF);
   setlinebuf(stderr);
   weight = calloc(sizeof(*weight), m);  assert(weight);
-  n_max_frags = INT_MAX;
-  m_max_frags = INT_MAX;
 }
 
 #if 0
@@ -660,7 +666,7 @@ static void iterate_recurse(int i, AdjWord min) {
       if (adjmatrix[i] & jbit)
         weight[j]++;
     for (int j = 0; j < m; j++)
-      if (weight[j] >= n_max_frags)
+      if (weight[j] > n_max_frags)
         goto takeout;
 
     iterate_recurse(i+1, adjmatrix[i]);
@@ -685,6 +691,44 @@ static void iterate(void) {
   }
 }
 
+static int gcd(int a, int b)
+{
+  assert(a>0);
+  assert(b>0);
+  while (b) {
+    int t = a % b;
+    a = b;
+    b = t;
+  }
+  return a;
+}
+
+static void print_rational(int n, int d)
+{
+  int g = gcd(n, d);
+  n /= g;
+  d /= g;
+  printf("%d", n);
+  if (d > 1)
+    printf("/%d", d);
+}
+
+#define MAKE_INT_VECTOR_COMPARATOR(thing)                               \
+  static int compare_ints_##thing(const void *av, const void *bv)       \
+  {                                                                     \
+    const int *a = (const int *)av;                                     \
+    const int *b = (const int *)bv;                                     \
+    int i;                                                              \
+    for (i = 0; i < (thing); i++)                                       \
+      if (a[i] != b[i])                                                 \
+        return a[i] > b[i] ? -1 : +1;                                   \
+    return 0;                                                           \
+  }
+/* Good grief, if only qsort let me pass a context parameter */
+MAKE_INT_VECTOR_COMPARATOR(1)
+MAKE_INT_VECTOR_COMPARATOR(m)
+MAKE_INT_VECTOR_COMPARATOR(n)
+
 static void report(void) {
   fprintf(stderr, "\n");
   if (best_adjmatrix) {
@@ -698,7 +742,8 @@ static void report(void) {
   if (best_prob) {
     double min = glp_get_obj_val(best_prob);
     double a[n][m];
-    int i, j, cols;
+    int ai[n][m];
+    int i, j, k, d, cols, imin;
     for (i = 0; i < n; i++)
       for (j = 0; j < m; j++)
         a[i][j] = 0;
@@ -709,29 +754,115 @@ static void report(void) {
         continue;
       a[x][y] = min + glp_get_col_prim(best_prob, i);
     }
-    printf("min fragment %g", min);
-    for (i = 0; i < n; i++) {
+
+    /*
+     * Try to find a denominator over which all these numbers turn
+     * sensibly into rationals.
+     */
+    for (d = 1;; d++) {
+      /*
+       * Round everything to the nearest multiple of d.
+       */
+      for (i = 0; i < n; i++)
+        for (j = 0; j < m; j++)
+          ai[i][j] = a[i][j] * d + 0.5;
+
+      /*
+       * Ensure the rows and columns add up correctly.
+       */
+      for (i = 0; i < n; i++) {
+        int total = 0;
+        for (j = 0; j < m; j++)
+          total += ai[i][j];
+        if (total != d*m)
+          goto next_d;
+      }
       for (j = 0; j < m; j++) {
-        if (a[i][j])
-          printf(" %9.3f", a[i][j]);
-        else
-          printf("          ");
+        int total = 0;
+        for (i = 0; i < n; i++)
+          total += ai[i][j];
+        if (total != d*n)
+          goto next_d;
       }
-      printf("\n");
+
+      /*
+       * Ensure we haven't rounded a good solution to a worse one, by
+       * finding the new minimum fragment and making sure it's at
+       * least the one we previously had.
+       */
+      imin = d*n;
+      for (i = 0; i < n; i++)
+        for (j = 0; j < m; j++)
+          if (ai[i][j] > 0 && ai[i][j] < imin)
+            imin = ai[i][j];
+
+      if (abs((double)imin / d - min) > 1e-10)
+        goto next_d;
+
+      /*
+       * Got it! We've found a rational-valued dissection.
+       */
+      printf("min fragment ");
+      print_rational(imin, d);
+      printf("   [%s]\n", VERSION);
+
+      /*
+       * We don't really want to output the matrix, so instead let's
+       * output the ways in which the sticks are cut up.
+       */
+      {
+        int ai2[m][n];
+        for (i = 0; i < n; i++) {
+          for (j = 0; j < m; j++)
+            ai2[j][i] = ai[i][j];
+        }
+        for (i = 0; i < n; i++)
+          qsort(ai+i, m, sizeof(int), compare_ints_1);
+        qsort(ai, n, m*sizeof(int), compare_ints_m);
+        printf("  Cut up %d sticks of length %d like this:\n", n, m);
+        for (i = 0; i < n ;) {
+          for (j = 1; i+j < n && compare_ints_m(ai+i, ai+i+j) == 0; j++);
+          printf("    %d x (", j);
+          for (k = 0; k < m && ai[i][k] > 0; k++) {
+            if (k > 0) printf(" + ");
+            print_rational(ai[i][k], d);
+          }
+          printf(")\n");
+          i += j;
+        }
+
+        for (j = 0; j < m; j++)
+          qsort(ai2+j, n, sizeof(int), compare_ints_1);
+        qsort(ai2, m, n*sizeof(int), compare_ints_n);
+        printf("  Reassemble as %d sticks of length %d like this:\n", m, n);
+        for (j = 0; j < m ;) {
+          for (i = 1; i+j < m && compare_ints_n(ai2+j, ai2+j+i) == 0; i++);
+          printf("    %d x (", i);
+          for (k = 0; k < n && ai2[j][k] > 0; k++) {
+            if (k > 0) printf(" + ");
+            print_rational(ai2[j][k], d);
+          }
+          printf(")\n");
+          j += i;
+        }
+      }
+      return;
+
+     next_d:;
     }
   } else {
-    printf(" none better than %9.3f ", best);
+    printf(" none better than %9.3f    [%s]\n", best, VERSION);
   }
-  printf("   [%s]\n", VERSION);
   if (ferror(stdout) || fclose(stdout)) { perror("stdout"); exit(-1); }
 }
  
 int main(int argc, char **argv) {
   int opt;
+  double best_to_set = -1.0; /* means 'don't' */
   while ((opt = getopt(argc,argv,"j:b:")) >= 0) {
     switch (opt) {
     case 'j': ncpus = atoi(optarg); break;
-    case 'b': set_best(atof(optarg)); break;
+    case 'b': best_to_set = atof(optarg); break;
     case '+': assert(!"bad option");
     default: abort();
     }
@@ -742,6 +873,7 @@ int main(int argc, char **argv) {
   n = atoi(argv[1]);
   m = atoi(argv[2]);
   assert(n > m);
+  if (best_to_set > 0) set_best(best_to_set);
 
   prep();