Commits

Seonghoon Kang committed afb3cf9

snapshot

Comments (0)

Files changed (4)

     raise SystemExit(1)
 
 # XXX this should really have to be dependent to each test case,
-# but all test cases in question use B2-less rules and Cs/Cn ratio of 2.
+# but all test cases in question use Cs/Cn ratio of 2.
 nexts = 0
-# in the large scale greedy approach is far better than 2-approximate vertex cover
-#hasb2 = (gol.parse_rulestring(rule)[0] >> 2) & 1
-#cellsvc = gol.min_vertex_cover(cells, hasb2)
-cellsvc = gol.greedy_elimination(cells, gol.parse_rulestring(rule))
-if len(cellsvc) + 2 < len(cells):
+elims = gol.best_general_elimination(cells, gol.parse_rulestring(rule))
+if len(elims) + 2 < len(cells):
     nexts = 1
-    cells = list(cellsvc)
+    cells = list(elims)
 
 print >>sys.stderr, 'writing %d NEXTs and %d SETs...' % (targetgen + nexts, len(cells))
 cells.sort()
 mincost = 99999999999999
 best = None
 bestelims = None
-hasb2 = gol.rule_has_b2(rule)
 flags = gol.parse_rulestring(rule)
 for nexts in xrange(maxnexts + 1):
     sets = 0
         else:
             pat = set((x, y) for x, line in enumerate(pat0)
                              for y, c in enumerate(line) if c == 'o')
-            if nexts > 0:
-                patvc = gol.min_vertex_cover(pat, hasb2)
-                patgr = gol.greedy_elimination(pat, flags)
-                pat = patgr if len(patgr) < len(patvc) else patvc
+            if nexts > 0: pat = gol.best_general_elimination(pat, flags)
             sets += len(pat) * patcnt
             allelims[patidx] = pat
     cost = sets * cs + nexts * cn
 o..o.o..o
 .........
 
+7
+.oo...oo.
+o..o.o..o
+o..o.o..o
+...o.o...
+o..o.o..o
+o..o.o..o
+.oo...oo.
+
 ###
 
 B3/S23
 ...o
 ..o.
 
+7
+..o.
+.o.o
+o...
+o...
+.o..
+..o.
+...o
+..oo
+
 ###
 
 B3/S23
 ........
 .o......
 
+5
+...oo.oo
+...oo.oo
+........
+....o.o.
+...o...o
+....ooo.
+........
+....ooo.
+...o...o
+....o.o.
+..o.....
+o.......
+.o......
+
 ###
 
 B3/S23
 ...o.o.........
 ..o...o........
 
+4
+........o....o.
+.......o......o
+...............
+..........oo...
+...............
+.......o......o
+........o....o.
+...............
+...............
+...............
+.oo...oo.......
+o..o.o..o......
+o..o.o..o......
+...o.o.........
+...o.o.........
+..oo.oo........
+
 ###
 
 B3/S23
 .....
 .o...
 
+8
+....o
+..o.o
+.o...
+o.o..
+.o...
+
 ###
 
 B3/S23
 .....o.
 oo.....
 
+5
+.oo.oo.
+......o
+o....o.
+oo.....
+
 ############################################################
 ############################################################
 ############################################################
         else: assert False
     return (sum(1<<int(i) for i in brule), sum(1<<int(i) for i in srule))
 
-def rule_has_b2(rule):
-    return (parse_rulestring(rule)[0] >> 2) & 1
-
 def each_neighbors(s, start=0):
     # well, Python sort is notable for being much faster than other linear or
     # log-linear algorithms due to very good hybrid approach (Timsort).
     # expand elimrules0 for rotation and mirroring.
     elimrules = {}
     for (rule, patstr), elims in elimrules0.items():
-        hasb2 = rule_has_b2(rule)
         flags = parse_rulestring(rule)
         for rot in [lambda s: s.split('\n'),
                     lambda s: s.split('\n')[::-1],
                 v = set((x, y) for x, line in enumerate(rot(v))
                                for y, c in enumerate(line) if c == 'o')
                 elims0[k] = pat ^ v
-            minvc = min_vertex_cover(pat, hasb2)
-            if 1 not in elims0 or len(minvc) < len(elims0[1]): elims0[1] = minvc
-            mingr = greedy_elimination(pat, flags)
-            if len(mingr) < len(elims0[1]): elims0[1] = mingr
+            gelims = best_general_elimination(pat, flags)
+            if 1 not in elims0 or len(gelims) < len(elims0[1]): elims0[1] = gelims
             elimrules[rule, '\n'.join(pat0)] = sorted(elims0.items())
 
     # verification (duh!)
     return elimrules
 
 
-def min_vertex_cover(s, has_b2):
+def min_vertex_cover_1(s):
     # returns a number of cells to eliminate, such that remaining cells do not
     # have neighbors more than 2 cells. this is accomplished by 2-approximate
     # minimal vertex cover (yes, the optimal solution is NP-complete) algorithm.
-    if has_b2:
-        return min_vertex_cover_2(s)
-    else:
-        return min_vertex_cover_1(s)
-
-def min_vertex_cover_1(s):
+    #
     # basic approach: we only consider consecutive three lines at a time,
     # otherwise we need to store at most len(s)*16 edges!
 
 
     return removed
 
+def best_general_elimination(s, (bflags, sflags)):
+    best = greedy_elimination(s, (bflags, sflags)) # baseline
+
+    # other elimination strategies are only effective for small enough patterns
+    if len(s) < 1000:
+        # approximate minimal vertex cover
+        if bflags & 0b100: # has B2
+            minvc = min_vertex_cover_2(s)
+        else:
+            minvc = min_vertex_cover_1(s)
+        if len(best) > len(minvc):
+            best = minvc
+
+    return best
+