chiark / gitweb /
 author Simon Tatham Mon, 17 Mar 2014 18:45:29 +0000 (18:45 +0000) committer Simon Tatham Mon, 17 Mar 2014 18:46:11 +0000 (18:46 +0000)
 tabulate.py patch | blob | history

index 29caaae..485b9b1 100755 (executable)
@@ -41,34 +41,43 @@ def verify(n, m, dissection):
assert total == n
assert collections == collections

+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],
+                     [(i*count, [piece*i for piece in pieces])
+                      for count, pieces in prev]],
+                    "multiply solution for (%d,%d) by %d" % (n/i, m/i, i)))
+
if n <= 2*m:
-        return None
+        return []
prev = dissections[(n-m, m)]
ret = [prev[:], prev[:]]
for i in range(len(ret)):
ret[i] = (ret[i], ret[i] + [m])
ret.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>