print.py

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