print.py

   1 #!/usr/bin/env python
   2
   3 import sys, re, fractions
   4 from fractions import Fraction
   5
   6 import bounds
   7
   8 results = {}
   9
  10 def got(n, m, minfrag, matrix):
  11     # Search for a common denominator to re-express our entire matrix
  12     # as rationals. We do this by rounding every matrix element
  13     # (fragment length) to its nearest multiple of the candidate
  14     # denominator, and seeing if the result still comes out as a legal
  15     # dissection.
  16     d = 0
  17     while True:
  18         d = d + 1
  19         rmatrix = [[Fraction(int(round(d*x)), d)
  20                 for x in mrow] for mrow in matrix]
  21
  22         ok = True
  23
  24         # Check that the dissection is still valid.
  25         for i in range(n):
  26             if sum(rmatrix[i]) != m:
  27                 ok = False
  28                 break
  29         if not ok:
  30             continue
  31         for j in range(m):
  32             if sum([rmatrix[i][j] for i in range(n)]) != n:
  33                 ok = False
  34                 break
  35         if not ok:
  36             continue
  37
  38         # Find the new minimum fragment length, and verify that it's
  39         # about the same as the old one. (Protects against the
  40         # possibility of a case where rounding every frag gives a
  41         # legal but worse dissection.)
  42         rminfrag = min([x for x in sum(rmatrix,[]) if x > 0])
  43         if abs(rminfrag / minfrag - 1) < 1e-5:
  44             break
  45
  46     # And store what we've now got, so we can later peruse our entire
  47     # data set in a sensible order.
  48     results[(n,m)] = (rminfrag, rmatrix)
  49
  50 def dezero(a):
  51     return [x for x in a if x != 0]
  52
  53 def report():
  54     for (n, m), (minfrag, matrix) in sorted(results.items()):
  55         print "%d into %d: %s" % (n, m, str(minfrag))
  56         # Reduce the matrix representation to just indicating how
  57         # everything is cut up.
  58         rows = {}
  59         for mrow in matrix:
  60             sorted_row = tuple(sorted(dezero(mrow), reverse=True))
  61             rows.setdefault(sorted_row, 0)
  62             rows[sorted_row] += 1
  63         rowout = sorted([(rows[r], r) for r in rows])
  64         cols = {}
  65         for j in range(m):
  66             sorted_col = tuple(sorted(dezero([matrix[i][j]
  67                                               for i in range(n)]),
  68                                              reverse=True))
  69             cols.setdefault(sorted_col, 0)
  70             cols[sorted_col] += 1
  71         colout = sorted([(cols[r], r) for r in cols])
  72         print "  Cut up %d sticks of length %d like this:" % (n, m)
  73         for count, row in sorted(rowout, reverse=True):
  74             print "    %d x (%s)" % (count, " + ".join(map(str,row)))
  75         print "  Reassemble as %d sticks of length %d like this:" % (m, n)
  76         for count, col in sorted(colout, reverse=True):
  77             print "    %d x (%s)" % (count, " + ".join(map(str,col)))
  78
  79         # See what our upper bound techniques have to say about this.
  80         bound, reason = bounds.upper_bound(n, m)
  81         assert bound >= minfrag, \
  82             "(%d,%d) solution %s exceeds upper bound %s" % (
  83             n, m, minfrag, bound)
  84         if bound == minfrag:
  85             print "  Proved optimal by", reason
  86         else:
  87             print "  Best upper bound proof (%s) gives %s" % (reason, bound)
  88
  89 heading_re = re.compile(r'^(\d+) into (\d+): min fragment ([\d\.]+)')
  90
  91 def read_file(f):
  92     while 1:
  93         line = f.readline()
  94         if line == "": break
  95         match = heading_re.search(line)
  96         if match:
  97             n = int(match.group(1))
  98             m = int(match.group(2))
  99             minfrag = float(match.group(3))
 100
 101             # Now expect n lines of m matrix elements each.
 102             matrix = []
 103             for i in range(n):
 104                 mline = f.readline()
 105                 mrow = []
 106                 for j in range(m):
 107                     mentry = mline[10*j:10*(j+1)]
 108                     if mentry == " " * 10:
 109                         mrow.append(0)
 110                     else:
 111                         mrow.append(float(mentry))
 112                 matrix.append(mrow)
 113
 114             got(n, m, minfrag, matrix)
 115
 116 def main(args):
 117     if len(args) == 0:
 118         read_file(sys.stdin)
 119     else:
 120         for arg in args:
 121             with open(arg) as f:
 122                 read_file(f)
 123     report()
 124
 125 if __name__ == "__main__":
 126     main(sys.argv[1:])