-#!/usr/bin/env python
-
-import sys, re, fractions
-from fractions import Fraction
-
-import bounds
-
-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)))
-
- # See what our upper bound techniques have to say about this.
- bound, reason = bounds.upper_bound(n, m)
- assert bound >= minfrag, \
- "(%d,%d) solution %s exceeds upper bound %s" % (
- n, m, minfrag, bound)
- if bound == minfrag:
- print " Proved optimal by", reason
- else:
- print " Best upper bound proof (%s) gives %s" % (reason, bound)
-
-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:])