From 2ad01625bf7ff39f8fe56a476587fe154f46baa5 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Mon, 17 Mar 2014 18:45:29 +0000 Subject: [PATCH] One more simple dissector. --- tabulate.py | 39 ++++++++++++++++++++++++--------------- 1 file changed, 24 insertions(+), 15 deletions(-) diff --git a/tabulate.py b/tabulate.py index 29caaae..485b9b1 100755 --- a/tabulate.py +++ b/tabulate.py @@ -41,34 +41,43 @@ def verify(n, m, dissection): 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 None + 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 + 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))]] + 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, this_reason in [ - (gcd_dissector, "trivial gcd solution"), - (add_m_dissector, "extend solution for (%d,%d)" % (n-m, m)), - ]: - dissection = 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 + 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 @@ -138,7 +147,7 @@ def read(n,m): sys.stdout.write("\n") def main(args): - limit = 24 # FIXME: configurable + limit = 31 # FIXME: configurable sys.stdout.write("""\ -- 2.30.2