From: Simon Tatham <anakin@pobox.com>
Date: Sat, 15 Mar 2014 16:26:50 +0000 (+0000)
Subject: Output dissection in the same format as partition.py.
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=matchsticks-search.git;a=commitdiff_plain;h=9d906ac4670f3170e5cab6e1a3820fcff44867ce

Output dissection in the same format as partition.py.
---

diff --git a/main.c b/main.c
index 3ee58c5..f121961 100644
--- a/main.c
+++ b/main.c
@@ -691,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) {
@@ -704,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;
@@ -715,15 +754,101 @@ static void report(void) {
         continue;
       a[x][y] = min + glp_get_col_prim(best_prob, i);
     }
-    printf("min fragment %g   [%s]\n", min, VERSION);
-    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;
+      }
+
+      /*
+       * 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 ((double)imin / d < min)
+        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", n, m);
+        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;
+        }
       }
-      printf("\n");
+      return;
+
+     next_d:;
     }
   } else {
     printf(" none better than %9.3f    [%s]\n", best, VERSION);