X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?a=blobdiff_plain;f=tabulate.py;h=79d615320d7fe5d16a39aaf520c5022930cc0fc5;hb=621cca6b657fd955da0f1e309b0df5d6cf0901e7;hp=d06e18694d586f68438d3d1c8db2e88132c7bf1d;hpb=810c83b263fae9142eb50ce5ef45db5ce876c189;p=matchsticks-search.git

diff --git a/tabulate.py b/tabulate.py
index d06e186..79d6153 100755
--- a/tabulate.py
+++ b/tabulate.py
@@ -41,7 +41,51 @@ def verify(n, m, dissection):
     assert total == n
     assert collections[0] == collections[1]
 
-def read(n,m):
+def factor_dissector(n,m):
+    ret = []
+    gcd = fractions.gcd(n,m)
+    for i in range(1, gcd+1):
+        if gcd % i != 0: continue
+        prev = dissections[n/i, m/i]
+        ret.append(([[(i*count, [piece*i for piece in pieces])
+                      for count, pieces in prev[0]],
+                     [(i*count, [piece*i for piece in pieces])
+                      for count, pieces in prev[1]]],
+                    "multiply solution for (%d,%d) by %d" % (n/i, m/i, i)))
+
+def add_m_dissector(n,m):
+    if n <= 2*m:
+        return []
+    prev = dissections[(n-m, m)]
+    ret = [prev[0][:], prev[1][:]]
+    for i in range(len(ret[0])):
+        ret[0][i] = (ret[0][i][0], ret[0][i][1] + [m])
+    ret[1].append((m, (m,)))
+    return [(ret, "extend solution for (%d,%d) by %d" % (n-m, m, m))]
+
+def gcd_dissector(n,m):
+    gcd = fractions.gcd(n,m)
+    return [([[(m, (gcd,) * (n/gcd))],
+              [(n, (gcd,) * (m/gcd))]], "trivial gcd solution")]
+
+def invent_dissection(n,m):
+    # Try to come up with a dissection by assorted simple methods.
+    best = 0
+    for dissector in [gcd_dissector, add_m_dissector]:
+        for dissection, this_reason in dissector(n, m):
+            if dissection is None: continue
+            verify(n, m, dissection)
+            this_best = find_min_frag(dissection)
+            if best < this_best:
+                best, best_reason = this_best, this_reason
+    assert best > 0
+    return dissection, this_reason
+
+details = {} # maps (n,m) to a snippet of HTML
+
+def read_and_build_table_cell(n,m):
+    ret = ""
+
     best = 0
 
     # Look for appropriate file(s).
@@ -79,6 +123,14 @@ def read(n,m):
                     best = this_best
                     best_nature = nature
 
+    if best == 0:
+        # We don't have a stored solution at all, so make up something
+        # plausible if we can.
+        dissection, auto_reason = invent_dissection(n, m)
+        best = find_min_frag(dissection)
+        dissections[(n,m)] = dissection
+        best_nature = 'a'
+
     bound, bound_type = bounds.upper_bound(n, m)
 
     if best == bound:
@@ -92,54 +144,70 @@ def read(n,m):
         show_bound = ""
     else:
         tdclass = "range"
-        show_bound = " &ndash; %s"
-    sys.stdout.write("<td class=\"%s\">" % tdclass)
-    sys.stdout.write(str(best))
+        show_bound = "&nbsp;&ndash;&nbsp;%s"
+    ret += "<td class=\"%s\"><a href=\"#details_%d_%d\">" % (tdclass, n, m)
+    ret += str(best)
     if show_bound != "":
-        sys.stdout.write(show_bound % str(bound))
-    sys.stdout.write("</td>\n")
+        ret += show_bound % str(bound)
+    ret += "</a></td>\n"
+
+    dump = "<h3><a name=\"details_%d_%d\">n=%d, m=%d</a></h3>\n" % (n, m, n, m)
+    dump += "<p>Best dissection known for %d into %d: minimum fragment is %s.\n" % (n, m, str(best))
+    dump += "<ul><li>Cut up %d sticks of length %d as follows:<ul>\n" % (m, n)
+    for count, pieces in dissection[0]:
+        dump += "<li>%d &times; (%s)\n" % (count, " + ".join(map(str, pieces)))
+    dump += "</ul><li>Reassemble as %d sticks of length %d as follows:<ul>\n" % (n, m)
+    for count, pieces in dissection[1]:
+        dump += "<li>%d &times; (%s)\n" % (count, " + ".join(map(str, pieces)))
+    dump += "</ul></ul>\n"
+    if best == bound:
+        dump += "<p>This dissection is confidently believed optimal because an upper bound proof (%s) matches it.\n" % bound_type
+    elif best_nature == 'e':
+        dump += "<p>This dissection is believed optimal because it was found by an exhaustive search program, although the best upper bound proof (%s) gives an upper bound of %s.\n" % (bound_type, bound)
+        tdclass = "believed"
+        show_bound = ""
+    elif best_nature == 'p':
+        dump += "<p>This dissection was found by a search program which may not be exhaustive (if the conjectured denominator bound is false) and hence may not be optimal, though we think it <em>probably</em> is. The best upper bound proof (%s) gives an upper bound of %s.\n" % (bound_type, bound)
+    else:
+        dump += "<p>This dissection was found "
+        if best_nature == 'm':
+            dump += "by hand"
+        else:
+            dump += "by a simplistic automated method (%s)" % auto_reason
+        dump += ", and is not known to be optimal. The best upper bound proof (%s) gives an upper bound of %s.\n" % (bound_type, bound)
+
+    details[(n, m)] = dump
+
+    return ret
 
 def main(args):
-    limit = 18 # FIXME: configurable
-    sys.stdout.write("""\
-<html>
-<head>
-<title>Known bounds for stick-dissecting problem</title>
-<style type="text/css">
-table, td, th {
-    border: 1px solid black;
-    border-collapse: collapse;
-}
-td.known {
-    background-color: #00ff00;
-}
-td.believed {
-    background-color: #aaff00;
-}
-td.probable {
-    background-color: #ffff00;
-}
-td.range {
-    background-color: #ff8888;
-}
-</style>
-</head>
-<body>
-<table>
-""")
-    sys.stdout.write("<tr>\n")
-    sys.stdout.write("<th>n \\ m</th>\n")
+    limit = 31 # FIXME: configurable
+
+    subst = {}
+
+    table = "<table>"
+    table += "<tr>\n"
+    table += "<th>n&nbsp;\\&nbsp;m</th>\n"
     for m in range(2,limit-1):
-        sys.stdout.write("<th>%d</th>\n" % m)
-    sys.stdout.write("</tr>\n")
+        table += "<th>%d</th>\n" % m
+    table += "</tr>\n"
     for n in range(2,limit):
-        sys.stdout.write("<tr>\n")
-        sys.stdout.write("<th>%d</th>\n" % n)
+        table += "<tr>\n"
+        table += "<th>%d</th>\n" % n
         for m in range(2,n):
-            read(n, m)
-        sys.stdout.write("</tr>\n")
-    sys.stdout.write("</table>\n")
-    sys.stdout.write("</body></html>\n")
+            table += read_and_build_table_cell(n, m)
+        table += "</tr>\n"
+    table += "</table>\n"
+    subst["TABLE"] = table
+
+    subst["DISSECTIONS"] = "".join([data for ((n, m), data) in sorted(details.items())])
+
+    with open("template.html") as f:
+        for line in f:
+            if line[:1] == "%" and line[-2:] == "%\n":
+                sys.stdout.write(subst[line[1:-2]])
+            else:
+                sys.stdout.write(line)
 
 if __name__ == "__main__":
     main(sys.argv[1:])