#!/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[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 = ""
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[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:
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" % (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[0]:
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[1]:
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"
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:])