tabulate.py

   1 #!/usr/bin/env python
   2
   3 import sys, os, re, fractions
   4 from fractions import Fraction
   5
   6 import bounds
   7
   8 header_re = re.compile(r'^(\d+) into (\d+).*:.* ([\d/]+)')
   9 dissect_re = re.compile(r'\s+(\d+)\s+x\s+\((([\d/]+ \+ )*[\d/]+)\)')
  10
  11 dissections = {}
  12
  13 def find_min_frag(dissection):
  14     ret = None
  15     for side in dissection:
  16         for count, pieces in side:
  17             for piece in pieces:
  18                 if piece > 0:
  19                     if ret is None or ret > piece:
  20                         ret = piece
  21     assert ret is not None
  22     return ret
  23
  24 def verify(n, m, dissection):
  25     collections = [{}, {}]
  26     total = 0
  27     for count, pieces in dissection[0]:
  28         assert sum(pieces) == n
  29         total += count
  30         for piece in pieces:
  31             collections[0].setdefault(piece, 0)
  32             collections[0][piece] += count
  33     assert total == m
  34     total = 0
  35     for count, pieces in dissection[1]:
  36         assert sum(pieces) == m
  37         total += count
  38         for piece in pieces:
  39             collections[1].setdefault(piece, 0)
  40             collections[1][piece] += count
  41     assert total == n
  42     assert collections[0] == collections[1]
  43
  44 def factor_dissector(n,m):
  45     ret = []
  46     gcd = fractions.gcd(n,m)
  47     for i in range(1, gcd+1):
  48         if gcd % i != 0: continue
  49         prev = dissections[n/i, m/i]
  50         ret.append(([[(i*count, [piece*i for piece in pieces])
  51                       for count, pieces in prev[0]],
  52                      [(i*count, [piece*i for piece in pieces])
  53                       for count, pieces in prev[1]]],
  54                     "multiply solution for (%d,%d) by %d" % (n/i, m/i, i)))
  55
  56 def add_m_dissector(n,m):
  57     if n <= 2*m:
  58         return []
  59     prev = dissections[(n-m, m)]
  60     ret = [prev[0][:], prev[1][:]]
  61     for i in range(len(ret[0])):
  62         ret[0][i] = (ret[0][i][0], ret[0][i][1] + [m])
  63     ret[1].append((m, (m,)))
  64     return [(ret, "extend solution for (%d,%d) by %d" % (n-m, m, m))]
  65
  66 def gcd_dissector(n,m):
  67     gcd = fractions.gcd(n,m)
  68     return [([[(m, (gcd,) * (n/gcd))],
  69               [(n, (gcd,) * (m/gcd))]], "trivial gcd solution")]
  70
  71 def invent_dissection(n,m):
  72     # Try to come up with a dissection by assorted simple methods.
  73     best = 0
  74     for dissector in [gcd_dissector, add_m_dissector]:
  75         for dissection, this_reason in dissector(n, m):
  76             if dissection is None: continue
  77             verify(n, m, dissection)
  78             this_best = find_min_frag(dissection)
  79             if best < this_best:
  80                 best, best_reason = this_best, this_reason
  81     assert best > 0
  82     return dissection, this_reason
  83
  84 def read(n,m):
  85     best = 0
  86
  87     # Look for appropriate file(s).
  88     for filename, nature in [("data/main.%d.%d" % (n,m), "e"),
  89                              ("data/partition.%d.%d" % (n,m), "p"),
  90                              ("data/manual.%d.%d" % (n,m), "m")]:
  91         if os.path.exists(filename):
  92             with open(filename) as f:
  93                 header = f.readline()
  94                 match = header_re.match(header)
  95                 assert match is not None
  96                 assert int(match.group(1)) == n
  97                 assert int(match.group(2)) == m
  98                 this_best = Fraction(match.group(3))
  99
 100                 # Now read the actual dissection.
 101                 dissection = [[],[]]
 102                 for line in f.readlines():
 103                     match = dissect_re.match(line)
 104                     if match is not None:
 105                         count = int(match.group(1))
 106                         pieces = map(Fraction, match.group(2).split(" + "))
 107                         length = sum(pieces)
 108                         if length == n:
 109                             dissection[0].append((count, pieces))
 110                         elif length == m:
 111                             dissection[1].append((count, pieces))
 112                         else:
 113                             assert False, "wrong length"
 114                 verify(n, m, dissection)
 115                 assert find_min_frag(dissection) == this_best
 116                 dissections[(n,m)] = dissection
 117
 118                 if this_best > best:
 119                     best = this_best
 120                     best_nature = nature
 121
 122     if best == 0:
 123         # We don't have a stored solution at all, so make up something
 124         # plausible if we can.
 125         dissection, best_nature = invent_dissection(n, m)
 126         best = find_min_frag(dissection)
 127         dissections[(n,m)] = dissection
 128
 129     bound, bound_type = bounds.upper_bound(n, m)
 130
 131     if best == bound:
 132         tdclass = "known"
 133         show_bound = ""
 134     elif best_nature == 'e':
 135         tdclass = "believed"
 136         show_bound = ""
 137     elif best_nature == 'p':
 138         tdclass = "probable"
 139         show_bound = ""
 140     else:
 141         tdclass = "range"
 142         show_bound = " &ndash; %s"
 143     sys.stdout.write("<td class=\"%s\">" % tdclass)
 144     sys.stdout.write(str(best))
 145     if show_bound != "":
 146         sys.stdout.write(show_bound % str(bound))
 147     sys.stdout.write("</td>\n")
 148
 149 def main(args):
 150     limit = 31 # FIXME: configurable
 151     sys.stdout.write("""\
 152 <html>
 153 <head>
 154 <title>Known bounds for stick-dissecting problem</title>
 155 <style type="text/css">
 156 table, td, th {
 157     border: 1px solid black;
 158     border-collapse: collapse;
 159 }
 160 td.known {
 161     background-color: #00ff00;
 162 }
 163 td.believed {
 164     background-color: #aaff00;
 165 }
 166 td.probable {
 167     background-color: #ffff00;
 168 }
 169 td.range {
 170     background-color: #ff8888;
 171 }
 172 </style>
 173 </head>
 174 <body>
 175 <table>
 176 """)
 177     sys.stdout.write("<tr>\n")
 178     sys.stdout.write("<th>n \\ m</th>\n")
 179     for m in range(2,limit-1):
 180         sys.stdout.write("<th>%d</th>\n" % m)
 181     sys.stdout.write("</tr>\n")
 182     for n in range(2,limit):
 183         sys.stdout.write("<tr>\n")
 184         sys.stdout.write("<th>%d</th>\n" % n)
 185         for m in range(2,n):
 186             read(n, m)
 187         sys.stdout.write("</tr>\n")
 188     sys.stdout.write("</table>\n")
 189     sys.stdout.write("</body></html>\n")
 190
 191 if __name__ == "__main__":
 192     main(sys.argv[1:])