From: Simon Tatham Date: Mon, 17 Mar 2014 18:34:57 +0000 (+0000) Subject: Invent a dissection if none is stored. X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=matchsticks-search.git;a=commitdiff_plain;h=1e51f817c3447e1c988983d01408327ce3a5b68a Invent a dissection if none is stored. This will help to fill in the cells for which neither search program completed in a reasonable time. --- diff --git a/tabulate.py b/tabulate.py index d06e186..564261c 100755 --- a/tabulate.py +++ b/tabulate.py @@ -41,6 +41,26 @@ def verify(n, m, dissection): assert total == n assert collections[0] == collections[1] +def gcd_dissector(n,m): + gcd = fractions.gcd(n,m) + return [[(m, (gcd,) * (n/gcd))], + [(n, (gcd,) * (m/gcd))]] + +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"), + ]: + 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 + assert best > 0 + return dissection, this_reason + def read(n,m): best = 0 @@ -79,6 +99,13 @@ def read(n,m): 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, best_nature = invent_dissection(n, m) + best = find_min_frag(dissection) + dissections[(n,m)] = dissection + bound, bound_type = bounds.upper_bound(n, m) if best == bound: @@ -100,7 +127,7 @@ def read(n,m): sys.stdout.write("\n") def main(args): - limit = 18 # FIXME: configurable + limit = 24 # FIXME: configurable sys.stdout.write("""\