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 gcd_dissector(n,m):
  45     gcd = fractions.gcd(n,m)
  46     return [[(m, (gcd,) * (n/gcd))],
  47             [(n, (gcd,) * (m/gcd))]]
  48
  49 def invent_dissection(n,m):
  50     # Try to come up with a dissection by assorted simple methods.
  51     best = 0
  52     for dissector, this_reason in [
  53         (gcd_dissector, "trivial gcd solution"),
  54         ]:
  55         dissection = dissector(n, m)
  56         if dissection is None: continue
  57         verify(n, m, dissection)
  58         this_best = find_min_frag(dissection)
  59         if best < this_best:
  60             best, best_reason = this_best, this_reason
  61     assert best > 0
  62     return dissection, this_reason
  63
  64 def read(n,m):
  65     best = 0
  66
  67     # Look for appropriate file(s).
  68     for filename, nature in [("data/main.%d.%d" % (n,m), "e"),
  69                              ("data/partition.%d.%d" % (n,m), "p"),
  70                              ("data/manual.%d.%d" % (n,m), "m")]:
  71         if os.path.exists(filename):
  72             with open(filename) as f:
  73                 header = f.readline()
  74                 match = header_re.match(header)
  75                 assert match is not None
  76                 assert int(match.group(1)) == n
  77                 assert int(match.group(2)) == m
  78                 this_best = Fraction(match.group(3))
  79
  80                 # Now read the actual dissection.
  81                 dissection = [[],[]]
  82                 for line in f.readlines():
  83                     match = dissect_re.match(line)
  84                     if match is not None:
  85                         count = int(match.group(1))
  86                         pieces = map(Fraction, match.group(2).split(" + "))
  87                         length = sum(pieces)
  88                         if length == n:
  89                             dissection[0].append((count, pieces))
  90                         elif length == m:
  91                             dissection[1].append((count, pieces))
  92                         else:
  93                             assert False, "wrong length"
  94                 verify(n, m, dissection)
  95                 assert find_min_frag(dissection) == this_best
  96                 dissections[(n,m)] = dissection
  97
  98                 if this_best > best:
  99                     best = this_best
 100                     best_nature = nature
 101
 102     if best == 0:
 103         # We don't have a stored solution at all, so make up something
 104         # plausible if we can.
 105         dissection, best_nature = invent_dissection(n, m)
 106         best = find_min_frag(dissection)
 107         dissections[(n,m)] = dissection
 108
 109     bound, bound_type = bounds.upper_bound(n, m)
 110
 111     if best == bound:
 112         tdclass = "known"
 113         show_bound = ""
 114     elif best_nature == 'e':
 115         tdclass = "believed"
 116         show_bound = ""
 117     elif best_nature == 'p':
 118         tdclass = "probable"
 119         show_bound = ""
 120     else:
 121         tdclass = "range"
 122         show_bound = " &ndash; %s"
 123     sys.stdout.write("<td class=\"%s\">" % tdclass)
 124     sys.stdout.write(str(best))
 125     if show_bound != "":
 126         sys.stdout.write(show_bound % str(bound))
 127     sys.stdout.write("</td>\n")
 128
 129 def main(args):
 130     limit = 24 # FIXME: configurable
 131     sys.stdout.write("""\
 132 <html>
 133 <head>
 134 <title>Known bounds for stick-dissecting problem</title>
 135 <style type="text/css">
 136 table, td, th {
 137     border: 1px solid black;
 138     border-collapse: collapse;
 139 }
 140 td.known {
 141     background-color: #00ff00;
 142 }
 143 td.believed {
 144     background-color: #aaff00;
 145 }
 146 td.probable {
 147     background-color: #ffff00;
 148 }
 149 td.range {
 150     background-color: #ff8888;
 151 }
 152 </style>
 153 </head>
 154 <body>
 155 <table>
 156 """)
 157     sys.stdout.write("<tr>\n")
 158     sys.stdout.write("<th>n \\ m</th>\n")
 159     for m in range(2,limit-1):
 160         sys.stdout.write("<th>%d</th>\n" % m)
 161     sys.stdout.write("</tr>\n")
 162     for n in range(2,limit):
 163         sys.stdout.write("<tr>\n")
 164         sys.stdout.write("<th>%d</th>\n" % n)
 165         for m in range(2,n):
 166             read(n, m)
 167         sys.stdout.write("</tr>\n")
 168     sys.stdout.write("</table>\n")
 169     sys.stdout.write("</body></html>\n")
 170
 171 if __name__ == "__main__":
 172     main(sys.argv[1:])