#!/usr/bin/env python
-import sys, subprocess, math
+import sys, subprocess, math, getopt
from fractions import Fraction
+import bounds
+
+verbose = False
def vprint(*args):
# In verbose mode, print diagnostics.
- pass # FIXME: implement verbose mode
+ if verbose:
+ sys.stdout.write(" ".join(map(str,args)) + "\n")
def find_partitions(n, minfrag, maxfrag=None, prefix=(), ret=None):
"""Find all partitions of n into integer pieces at least minfrag.
# 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):
+ 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():
- m, n = sorted(map(int,sys.argv[1:3]))
+ global verbose
+ opts, args = getopt.gnu_getopt(sys.argv[1:], "v")
+ for opt, val in opts:
+ if opt == "-v":
+ verbose = True
+ else:
+ assert False, "unrecognised option '%s'" % opt
+ m, n = sorted(map(int,args[:2]))
search_and_report(n, m)
if __name__ == "__main__":