3 import sys, os, re, fractions
4 from fractions import Fraction
8 header_re = re.compile(r'^(\d+) into (\d+).*:.* ([\d/]+)')
9 dissect_re = re.compile(r'\s+(\d+)\s+x\s+\((([\d/]+ \+ )*[\d/]+)\)')
13 def find_min_frag(dissection):
15 for side in dissection:
16 for count, pieces in side:
19 if ret is None or ret > piece:
21 assert ret is not None
24 def verify(n, m, dissection):
25 collections = [{}, {}]
27 for count, pieces in dissection[0]:
28 assert sum(pieces) == n
31 collections[0].setdefault(piece, 0)
32 collections[0][piece] += count
35 for count, pieces in dissection[1]:
36 assert sum(pieces) == m
39 collections[1].setdefault(piece, 0)
40 collections[1][piece] += count
42 assert collections[0] == collections[1]
44 def factor_dissector(n,m):
46 gcd = fractions.gcd(n,m)
47 for i in range(1, gcd+1):
48 if gcd % i != 0: continue
49 prev = dissections[n/i, m/i]
50 ret.append(([[(i*count, [piece*i for piece in pieces])
51 for count, pieces in prev[0]],
52 [(i*count, [piece*i for piece in pieces])
53 for count, pieces in prev[1]]],
54 "multiply solution for (%d,%d) by %d" % (n/i, m/i, i)))
56 def add_m_dissector(n,m):
59 prev = dissections[(n-m, m)]
60 ret = [prev[0][:], prev[1][:]]
61 for i in range(len(ret[0])):
62 ret[0][i] = (ret[0][i][0], ret[0][i][1] + [m])
63 ret[1].append((m, (m,)))
64 return [(ret, "extend solution for (%d,%d) by %d" % (n-m, m, m))]
66 def gcd_dissector(n,m):
67 gcd = fractions.gcd(n,m)
68 return [([[(m, (gcd,) * (n/gcd))],
69 [(n, (gcd,) * (m/gcd))]], "trivial gcd solution")]
71 def invent_dissection(n,m):
72 # Try to come up with a dissection by assorted simple methods.
74 for dissector in [gcd_dissector, add_m_dissector]:
75 for dissection, this_reason in dissector(n, m):
76 if dissection is None: continue
77 verify(n, m, dissection)
78 this_best = find_min_frag(dissection)
80 best, best_reason = this_best, this_reason
82 return dissection, this_reason
84 details = {} # maps (n,m) to a snippet of HTML
86 def read_and_build_table_cell(n,m):
91 # Look for appropriate file(s).
92 for filename, nature in [("data/main.%d.%d" % (n,m), "e"),
93 ("data/partition.%d.%d" % (n,m), "p"),
94 ("data/manual.%d.%d" % (n,m), "m")]:
95 if os.path.exists(filename):
96 with open(filename) as f:
98 match = header_re.match(header)
99 assert match is not None
100 assert int(match.group(1)) == n
101 assert int(match.group(2)) == m
102 this_best = Fraction(match.group(3))
104 # Now read the actual dissection.
106 for line in f.readlines():
107 match = dissect_re.match(line)
108 if match is not None:
109 count = int(match.group(1))
110 pieces = map(Fraction, match.group(2).split(" + "))
113 dissection[0].append((count, pieces))
115 dissection[1].append((count, pieces))
117 assert False, "wrong length"
118 verify(n, m, dissection)
119 assert find_min_frag(dissection) == this_best
120 dissections[(n,m)] = dissection
127 # We don't have a stored solution at all, so make up something
128 # plausible if we can.
129 dissection, auto_reason = invent_dissection(n, m)
130 best = find_min_frag(dissection)
131 dissections[(n,m)] = dissection
134 bound, bound_type = bounds.upper_bound(n, m)
139 elif best_nature == 'e':
142 elif best_nature == 'p':
147 show_bound = " – %s"
148 ret += "<td class=\"%s\"><a href=\"#details_%d_%d\">" % (tdclass, n, m)
151 ret += show_bound % str(bound)
154 dump = "<h3><a name=\"details_%d_%d\">n=%d, m=%d</a></h3>\n" % (n, m, n, m)
155 dump += "<p>Best dissection known for %d into %d: minimum fragment is %s.\n" % (n, m, str(best))
156 dump += "<ul><li>Cut up %d sticks of length %d as follows:<ul>\n" % (m, n)
157 for count, pieces in dissection[0]:
158 dump += "<li>%d × (%s)\n" % (count, " + ".join(map(str, pieces)))
159 dump += "</ul><li>Reassemble as %d sticks of length %d as follows:<ul>\n" % (n, m)
160 for count, pieces in dissection[1]:
161 dump += "<li>%d × (%s)\n" % (count, " + ".join(map(str, pieces)))
162 dump += "</ul></ul>\n"
164 dump += "<p>This dissection is confidently believed optimal because an upper bound proof (%s) matches it.\n" % bound_type
165 elif best_nature == 'e':
166 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)
169 elif best_nature == 'p':
170 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)
172 dump += "<p>This dissection was found "
173 if best_nature == 'm':
176 dump += "by a simplistic automated method (%s)" % auto_reason
177 dump += ", and is not known to be optimal. The best upper bound proof (%s) gives an upper bound of %s.\n" % (bound_type, bound)
179 details[(n, m)] = dump
184 limit = 31 # FIXME: configurable
190 table += "<th>n \\ m</th>\n"
191 for m in range(2,limit-1):
192 table += "<th>%d</th>\n" % m
194 for n in range(2,limit):
196 table += "<th>%d</th>\n" % n
198 table += read_and_build_table_cell(n, m)
200 table += "</table>\n"
201 subst["TABLE"] = table
203 subst["DISSECTIONS"] = "".join([data for ((n, m), data) in sorted(details.items())])
205 with open("template.html") as f:
207 if line[:1] == "%" and line[-2:] == "%\n":
208 sys.stdout.write(subst[line[1:-2]])
210 sys.stdout.write(line)
212 if __name__ == "__main__":