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 read(n,m):
  45     best = 0
  46
  47     # Look for appropriate file(s).
  48     for filename, nature in [("data/main.%d.%d" % (n,m), "e"),
  49                              ("data/partition.%d.%d" % (n,m), "p"),
  50                              ("data/manual.%d.%d" % (n,m), "m")]:
  51         if os.path.exists(filename):
  52             with open(filename) as f:
  53                 header = f.readline()
  54                 match = header_re.match(header)
  55                 assert match is not None
  56                 assert int(match.group(1)) == n
  57                 assert int(match.group(2)) == m
  58                 this_best = Fraction(match.group(3))
  59
  60                 # Now read the actual dissection.
  61                 dissection = [[],[]]
  62                 for line in f.readlines():
  63                     match = dissect_re.match(line)
  64                     if match is not None:
  65                         count = int(match.group(1))
  66                         pieces = map(Fraction, match.group(2).split(" + "))
  67                         length = sum(pieces)
  68                         if length == n:
  69                             dissection[0].append((count, pieces))
  70                         elif length == m:
  71                             dissection[1].append((count, pieces))
  72                         else:
  73                             assert False, "wrong length"
  74                 verify(n, m, dissection)
  75                 assert find_min_frag(dissection) == this_best
  76                 dissections[(n,m)] = dissection
  77
  78                 if this_best > best:
  79                     best = this_best
  80                     best_nature = nature
  81
  82     bound, bound_type = bounds.upper_bound(n, m)
  83
  84     if best == bound:
  85         tdclass = "known"
  86         show_bound = ""
  87     elif best_nature == 'e':
  88         tdclass = "believed"
  89         show_bound = ""
  90     elif best_nature == 'p':
  91         tdclass = "probable"
  92         show_bound = ""
  93     else:
  94         tdclass = "range"
  95         show_bound = " &ndash; %s"
  96     sys.stdout.write("<td class=\"%s\">" % tdclass)
  97     sys.stdout.write(str(best))
  98     if show_bound != "":
  99         sys.stdout.write(show_bound % str(bound))
 100     sys.stdout.write("</td>\n")
 101
 102 def main(args):
 103     limit = 18 # FIXME: configurable
 104     sys.stdout.write("""\
 105 <html>
 106 <head>
 107 <title>Known bounds for stick-dissecting problem</title>
 108 <style type="text/css">
 109 table, td, th {
 110     border: 1px solid black;
 111     border-collapse: collapse;
 112 }
 113 td.known {
 114     background-color: #00ff00;
 115 }
 116 td.believed {
 117     background-color: #aaff00;
 118 }
 119 td.probable {
 120     background-color: #ffff00;
 121 }
 122 td.range {
 123     background-color: #ff8888;
 124 }
 125 </style>
 126 </head>
 127 <body>
 128 <table>
 129 """)
 130     sys.stdout.write("<tr>\n")
 131     sys.stdout.write("<th>n \\ m</th>\n")
 132     for m in range(2,limit-1):
 133         sys.stdout.write("<th>%d</th>\n" % m)
 134     sys.stdout.write("</tr>\n")
 135     for n in range(2,limit):
 136         sys.stdout.write("<tr>\n")
 137         sys.stdout.write("<th>%d</th>\n" % n)
 138         for m in range(2,n):
 139             read(n, m)
 140         sys.stdout.write("</tr>\n")
 141     sys.stdout.write("</table>\n")
 142     sys.stdout.write("</body></html>\n")
 143
 144 if __name__ == "__main__":
 145     main(sys.argv[1:])