Invent a dissection if none is stored.

[matchsticks-search.git] / tabulate.py
diff --git a/tabulate.py b/tabulate.py

index d06e18694d586f68438d3d1c8db2e88132c7bf1d..564261c2525c48b1143415bec7482dc8375533bc 100755 (executable)
--- 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("</td>\n")
  
  def main(args):
-    limit = 18 # FIXME: configurable
+    limit = 24 # FIXME: configurable
      sys.stdout.write("""\
  <html>
  <head>