#!/usr/bin/env python import sys, os, re, fractions from fractions import Fraction 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: assert sum(pieces) == n total += count for piece in pieces: collections.setdefault(piece, 0) collections[piece] += count assert total == m total = 0 for count, pieces in dissection: assert sum(pieces) == m total += count for piece in pieces: collections.setdefault(piece, 0) collections[piece] += count assert total == n assert collections == collections 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], [(i*count, [piece*i for piece in pieces]) for count, pieces in prev]], "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[:], prev[:]] for i in range(len(ret)): ret[i] = (ret[i], ret[i] + [m]) ret.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). for filename, nature in [("data/main.%d.%d" % (n,m), "e"), ("data/partition.%d.%d" % (n,m), "p"), ("data/manual.%d.%d" % (n,m), "m")]: if os.path.exists(filename): with open(filename) as f: header = f.readline() match = header_re.match(header) assert match is not None 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.append((count, pieces)) elif length == m: dissection.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: tdclass = "known" show_bound = "" elif best_nature == 'e': tdclass = "believed" show_bound = "" elif best_nature == 'p': tdclass = "probable" show_bound = "" else: tdclass = "range" show_bound = " – %s" ret += "" % (tdclass, n, m) ret += str(best) if show_bound != "": ret += show_bound % str(bound) ret += "\n" dump = "

n=%d, m=%d

\n" % (n, m, n, m) dump += "

Best dissection known for %d into %d: minimum fragment is %s.\n" % (n, m, str(best)) dump += "

• Cut up %d sticks of length %d as follows:
\n" % (m, n) for count, pieces in dissection: dump += "
• %d × (%s)\n" % (count, " + ".join(map(str, pieces))) dump += "
• Reassemble as %d sticks of length %d as follows:
\n" % (n, m) for count, pieces in dissection: dump += "
• %d × (%s)\n" % (count, " + ".join(map(str, pieces))) dump += "
\n" if best == bound: dump += "

This dissection is confidently believed optimal because an upper bound proof (%s) matches it.\n" % bound_type elif best_nature == 'e': dump += "

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 += "

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 probably is. The best upper bound proof (%s) gives an upper bound of %s.\n" % (bound_type, bound) else: dump += "

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 subst = {} table = "" table += "\n" table += "\n" for m in range(2,limit-1): table += "\n" % m table += "\n" for n in range(2,limit): table += "\n" table += "\n" % n for m in range(2,n): table += read_and_build_table_cell(n, m) table += "\n" table += "
n \\ m%d
%d
\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:])