3 import sys, re, fractions
4 from fractions import Fraction
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
19 rmatrix = [[Fraction(int(round(d*x)), d)
20 for x in mrow] for mrow in matrix]
24 # Check that the dissection is still valid.
26 if sum(rmatrix[i]) != m:
32 if sum([rmatrix[i][j] for i in range(n)]) != n:
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:
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)
51 return [x for x in a if x != 0]
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.
60 sorted_row = tuple(sorted(dezero(mrow), reverse=True))
61 rows.setdefault(sorted_row, 0)
63 rowout = sorted([(rows[r], r) for r in rows])
66 sorted_col = tuple(sorted(dezero([matrix[i][j]
69 cols.setdefault(sorted_col, 0)
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)))
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" % (
85 print " Proved optimal by", reason
87 print " Best upper bound proof (%s) gives %s" % (reason, bound)
89 heading_re = re.compile(r'^(\d+) into (\d+): min fragment ([\d\.]+)')
95 match = heading_re.search(line)
97 n = int(match.group(1))
98 m = int(match.group(2))
99 minfrag = float(match.group(3))
101 # Now expect n lines of m matrix elements each.
107 mentry = mline[10*j:10*(j+1)]
108 if mentry == " " * 10:
111 mrow.append(float(mentry))
114 got(n, m, minfrag, matrix)
125 if __name__ == "__main__":