assert best > 0
return dissection, this_reason
-def read(n,m):
+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).
if best == 0:
# We don't have a stored solution at all, so make up something
# plausible if we can.
- dissection, best_nature = invent_dissection(n, m)
+ 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)
show_bound = ""
else:
tdclass = "range"
- show_bound = " – %s"
- sys.stdout.write("<td class=\"%s\">" % tdclass)
- sys.stdout.write(str(best))
+ show_bound = " – %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 = "<h2><a name=\"details_%d_%d\">n=%d, m=%d</a></h2>\n" % (n, m, n, m)
+ dump += "<p>Best dissection known for %d into %d, with minimum fragment %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 × (%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 × (%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 = 31 # 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")
+
+ subst = {}
+
+ table = "<table>"
+ table += "<tr>\n"
+ table += "<th>n \\ 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:])
~ianmdlvl / matchsticks-search.git / blobdiff