import bounds
header_re = re.compile(r'^(\d+) into (\d+).*:.* ([\d/]+)')
+dissect_re = re.compile(r'\s+(\d+)\s+x\s+\((([\d/]+ \+ )*[\d/]+)\)')
+
+dissections = {}
+
+def find_min_frag(dissection):
+ ret = None
+ for side in dissection:
+ for count, pieces in side:
+ for piece in pieces:
+ if piece > 0:
+ if ret is None or ret > piece:
+ ret = piece
+ assert ret is not None
+ return ret
+
+def verify(n, m, dissection):
+ collections = [{}, {}]
+ total = 0
+ for count, pieces in dissection[0]:
+ assert sum(pieces) == n
+ total += count
+ for piece in pieces:
+ collections[0].setdefault(piece, 0)
+ collections[0][piece] += count
+ assert total == m
+ total = 0
+ for count, pieces in dissection[1]:
+ assert sum(pieces) == m
+ total += count
+ for piece in pieces:
+ collections[1].setdefault(piece, 0)
+ collections[1][piece] += count
+ assert total == n
+ assert collections[0] == collections[1]
+
+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 = ""
-def read(n,m):
best = 0
# Look for appropriate file(s).
assert int(match.group(1)) == n
assert int(match.group(2)) == m
this_best = Fraction(match.group(3))
+
+ # Now read the actual dissection.
+ dissection = [[],[]]
+ for line in f.readlines():
+ match = dissect_re.match(line)
+ if match is not None:
+ count = int(match.group(1))
+ pieces = map(Fraction, match.group(2).split(" + "))
+ length = sum(pieces)
+ if length == n:
+ dissection[0].append((count, pieces))
+ elif length == m:
+ dissection[1].append((count, pieces))
+ else:
+ assert False, "wrong length"
+ verify(n, m, dissection)
+ assert find_min_frag(dissection) == this_best
+ dissections[(n,m)] = dissection
+
if this_best > best:
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 = ""
elif best_nature == 'p':
tdclass = "probable"
- show_bound = " (– %s)"
+ 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 = 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: #44ff44;
-}
-td.probable {
- background-color: #88ff88;
-}
-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