X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?a=blobdiff_plain;f=partition.py;h=4e2766d253c9b54bddf71fd23c5fb334c298e735;hb=1c6c1326518318174cab24aee1e00f3a6273284f;hp=d0c0dd6b66f4670f2683a389eef7caa47a17f390;hpb=2b68e0812cdf71031274fe1883a8857479a390a0;p=matchsticks-search.git

diff --git a/partition.py b/partition.py
index d0c0dd6..4e2766d 100755
--- a/partition.py
+++ b/partition.py
@@ -1,11 +1,15 @@
 #!/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.
@@ -125,12 +129,15 @@ def search(n, m):
         # 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):
@@ -138,14 +145,21 @@ 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__":