chiark / gitweb /
One more simple dissector.
authorSimon Tatham <anakin@pobox.com>
Mon, 17 Mar 2014 18:45:29 +0000 (18:45 +0000)
committerSimon Tatham <anakin@pobox.com>
Mon, 17 Mar 2014 18:46:11 +0000 (18:46 +0000)
tabulate.py

index 29caaae..485b9b1 100755 (executable)
@@ -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("</td>\n")
 
 def main(args):
-    limit = 24 # FIXME: configurable
+    limit = 31 # FIXME: configurable
     sys.stdout.write("""\
 <html>
 <head>