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
87 # Look for appropriate file(s).
88 for filename, nature in [("data/main.%d.%d" % (n,m), "e"),
89 ("data/partition.%d.%d" % (n,m), "p"),
90 ("data/manual.%d.%d" % (n,m), "m")]:
91 if os.path.exists(filename):
92 with open(filename) as f:
94 match = header_re.match(header)
95 assert match is not None
96 assert int(match.group(1)) == n
97 assert int(match.group(2)) == m
98 this_best = Fraction(match.group(3))
100 # Now read the actual dissection.
102 for line in f.readlines():
103 match = dissect_re.match(line)
104 if match is not None:
105 count = int(match.group(1))
106 pieces = map(Fraction, match.group(2).split(" + "))
109 dissection[0].append((count, pieces))
111 dissection[1].append((count, pieces))
113 assert False, "wrong length"
114 verify(n, m, dissection)
115 assert find_min_frag(dissection) == this_best
116 dissections[(n,m)] = dissection
123 # We don't have a stored solution at all, so make up something
124 # plausible if we can.
125 dissection, best_nature = invent_dissection(n, m)
126 best = find_min_frag(dissection)
127 dissections[(n,m)] = dissection
129 bound, bound_type = bounds.upper_bound(n, m)
134 elif best_nature == 'e':
137 elif best_nature == 'p':
142 show_bound = " – %s"
143 sys.stdout.write("<td class=\"%s\">" % tdclass)
144 sys.stdout.write(str(best))
146 sys.stdout.write(show_bound % str(bound))
147 sys.stdout.write("</td>\n")
150 limit = 31 # FIXME: configurable
151 sys.stdout.write("""\
154 <title>Known bounds for stick-dissecting problem</title>
155 <style type="text/css">
157 border: 1px solid black;
158 border-collapse: collapse;
161 background-color: #00ff00;
164 background-color: #aaff00;
167 background-color: #ffff00;
170 background-color: #ff8888;
177 sys.stdout.write("<tr>\n")
178 sys.stdout.write("<th>n \\ m</th>\n")
179 for m in range(2,limit-1):
180 sys.stdout.write("<th>%d</th>\n" % m)
181 sys.stdout.write("</tr>\n")
182 for n in range(2,limit):
183 sys.stdout.write("<tr>\n")
184 sys.stdout.write("<th>%d</th>\n" % n)
187 sys.stdout.write("</tr>\n")
188 sys.stdout.write("</table>\n")
189 sys.stdout.write("</body></html>\n")
191 if __name__ == "__main__":