X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=matchsticks-search.git;a=blobdiff_plain;f=partition.py;h=4e2766d253c9b54bddf71fd23c5fb334c298e735;hp=c8c7db74d9dae4c188b00c193fd1a6a5bbd73bdc;hb=83522686e4bd5f0a877f3adf5d94e3b351a774f6;hpb=0917331168d079acc8bd6901289acdafe9459f56

diff --git a/partition.py b/partition.py
index c8c7db7..4e2766d 100755
--- a/partition.py
+++ b/partition.py
@@ -3,6 +3,8 @@
 import sys, subprocess, math, getopt
 from fractions import Fraction
 
+import bounds
+
 verbose = False
 def vprint(*args):
     # In verbose mode, print diagnostics.
@@ -127,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):
@@ -140,10 +145,10 @@ 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():