+#!/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:])