Report the bounds along with the search results.

[matchsticks-search.git] / print.py

diff --git a/print.py b/print.py
index d59c5e2f90f9c00831527d06c7652761283d7648..f7015c73e4d09d7f41d554c671c67ae15cf1dbba 100755 (executable)
--- a/print.py
+++ b/print.py
@@ -3,6 +3,8 @@
 import sys, re, fractions
 from fractions import Fraction
 
+import bounds
+
 results = {}
 
 def got(n, m, minfrag, matrix):
@@ -74,6 +76,16 @@ def report():
         for count, col in sorted(colout, reverse=True):
             print "    %d x (%s)" % (count, " + ".join(map(str,col)))
 
+        # See what our upper bound techniques have to say about this.
+        bound, reason = bounds.upper_bound(n, m)
+        assert bound >= minfrag, \
+            "(%d,%d) solution %s exceeds upper bound %s" % (
+            n, m, minfrag, bound)
+        if bound == minfrag:
+            print "  Proved optimal by", reason
+        else:
+            print "  Best upper bound proof (%s) gives %s" % (reason, bound)
+
 heading_re = re.compile(r'^(\d+) into (\d+): min fragment ([\d\.]+)')
 
 def read_file(f):