import sys, subprocess, math, getopt
from fractions import Fraction
+import bounds
+
verbose = False
def vprint(*args):
# In verbose mode, print diagnostics.
# Trivial special case.
return (m, 1, {(m,):n}, {(m,)*(n/m):m})
best = (0,)
+ bound, _ = bounds.upper_bound(n, m)
for d in xrange(1, n+1):
- for k in xrange(m*d/2, int(math.ceil(best[0]*d))-1, -1):
+ for k in xrange(int(bound*d), int(math.ceil(best[0]*d))-1, -1):
result = try_one_minfrag(n, m, k, d)
if result is not None:
best = (Fraction(k, d), d) + result
break
+ if best == bound:
+ break # terminate early if we know it's the best answer
return best
def search_and_report(n, m):
d = best[1]
print "%d into %d best min fragment found: %s" % (n, m, best[0])
print " Cut up %d sticks of length %d like this:" % (n, m)
- for row, count in sorted(best[2].items(), reverse=True):
+ for row, count in sorted(best[3].items(), reverse=True):
print " %d x (%s)" % (count, " + ".join([str(Fraction(k,d)) for k in row]))
print " Reassemble as %d sticks of length %d like this:" % (m, n)
- for col, count in sorted(best[3].items(), reverse=True):
+ for col, count in sorted(best[2].items(), reverse=True):
print " %d x (%s)" % (count, " + ".join([str(Fraction(k,d)) for k in col]))
def main():