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).
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:
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 = "<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 × (%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 = 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 \\ 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