Written a post-analyser for the search output.

[matchsticks-search.git] / print.py

diff --git a/print.py b/print.py
new file mode 100755 (executable)
index 0000000..d59c5e2
--- /dev/null
+++ b/print.py
@@ -0,0 +1,114 @@
+#!/usr/bin/env python
+
+import sys, re, fractions
+from fractions import Fraction
+
+results = {}
+
+def got(n, m, minfrag, matrix):
+    # Search for a common denominator to re-express our entire matrix
+    # as rationals. We do this by rounding every matrix element
+    # (fragment length) to its nearest multiple of the candidate
+    # denominator, and seeing if the result still comes out as a legal
+    # dissection.
+    d = 0
+    while True:
+        d = d + 1
+        rmatrix = [[Fraction(int(round(d*x)), d)
+                for x in mrow] for mrow in matrix]
+
+        ok = True
+
+        # Check that the dissection is still valid.
+        for i in range(n):
+            if sum(rmatrix[i]) != m:
+                ok = False
+                break
+        if not ok:
+            continue
+        for j in range(m):
+            if sum([rmatrix[i][j] for i in range(n)]) != n:
+                ok = False
+                break
+        if not ok:
+            continue
+
+        # Find the new minimum fragment length, and verify that it's
+        # about the same as the old one. (Protects against the
+        # possibility of a case where rounding every frag gives a
+        # legal but worse dissection.)
+        rminfrag = min([x for x in sum(rmatrix,[]) if x > 0])
+        if abs(rminfrag / minfrag - 1) < 1e-5:
+            break
+
+    # And store what we've now got, so we can later peruse our entire
+    # data set in a sensible order.
+    results[(n,m)] = (rminfrag, rmatrix)
+
+def dezero(a):
+    return [x for x in a if x != 0]
+
+def report():
+    for (n, m), (minfrag, matrix) in sorted(results.items()):
+        print "%d into %d: %s" % (n, m, str(minfrag))
+        # Reduce the matrix representation to just indicating how
+        # everything is cut up.
+        rows = {}
+        for mrow in matrix:
+            sorted_row = tuple(sorted(dezero(mrow), reverse=True))
+            rows.setdefault(sorted_row, 0)
+            rows[sorted_row] += 1
+        rowout = sorted([(rows[r], r) for r in rows])
+        cols = {}
+        for j in range(m):
+            sorted_col = tuple(sorted(dezero([matrix[i][j]
+                                              for i in range(n)]),
+                                             reverse=True))
+            cols.setdefault(sorted_col, 0)
+            cols[sorted_col] += 1
+        colout = sorted([(cols[r], r) for r in cols])
+        print "  Cut up %d sticks of length %d like this:" % (n, m)
+        for count, row in sorted(rowout, reverse=True):
+            print "    %d x (%s)" % (count, " + ".join(map(str,row)))
+        print "  Reassemble as %d sticks of length %d like this:" % (m, n)
+        for count, col in sorted(colout, reverse=True):
+            print "    %d x (%s)" % (count, " + ".join(map(str,col)))
+
+heading_re = re.compile(r'^(\d+) into (\d+): min fragment ([\d\.]+)')
+
+def read_file(f):
+    while 1:
+        line = f.readline()
+        if line == "": break
+        match = heading_re.search(line)
+        if match:
+            n = int(match.group(1))
+            m = int(match.group(2))
+            minfrag = float(match.group(3))
+
+            # Now expect n lines of m matrix elements each.
+            matrix = []
+            for i in range(n):
+                mline = f.readline()
+                mrow = []
+                for j in range(m):
+                    mentry = mline[10*j:10*(j+1)]
+                    if mentry == " " * 10:
+                        mrow.append(0)
+                    else:
+                        mrow.append(float(mentry))
+                matrix.append(mrow)
+
+            got(n, m, minfrag, matrix)
+
+def main(args):
+    if len(args) == 0:
+        read_file(sys.stdin)
+    else:
+        for arg in args:
+            with open(arg) as f:
+                read_file(f)
+    report()
+
+if __name__ == "__main__":
+    main(sys.argv[1:])