Fix a bug causing some solutions to be missed, e.g. (16,5).

[matchsticks-search.git] / partition.py

diff --git a/partition.py b/partition.py
index d0c0dd6b66f4670f2683a389eef7caa47a17f390..18a3a3b09ad4f862933cd19e48459d5f7f80e996 100755 (executable)
--- a/partition.py
+++ b/partition.py
@@ -1,11 +1,13 @@
 #!/usr/bin/env python
 
-import sys, subprocess, math
+import sys, subprocess, math, getopt
 from fractions import Fraction
 
+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.
@@ -126,7 +128,7 @@ def search(n, m):
         return (m, 1, {(m,):n}, {(m,)*(n/m):m})
     best = (0,)
     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(m*d/2, 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
@@ -145,7 +147,14 @@ def search_and_report(n, m):
         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__":