Commits

Seonghoon Kang committed 5ee829f

snapshot

Comments (0)

Files changed (4)

 # 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.
 nexts = 0
-hasb2 = (gol.parse_rulestring(rule)[0] >> 2) & 1
-cellsvc = gol.min_vertex_cover(cells, hasb2)
+# 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):
     nexts = 1
     cells = list(cellsvc)
 best = None
 bestelims = None
 hasb2 = gol.rule_has_b2(rule)
+flags = gol.parse_rulestring(rule)
 for nexts in xrange(maxnexts + 1):
     sets = 0
     allelims = {}
         else:
             pat = set((x, y) for x, line in enumerate(pat0)
                              for y, c in enumerate(line) if c == 'o')
-            if nexts > 0: pat = gol.min_vertex_cover(pat, hasb2)
+            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
             sets += len(pat) * patcnt
             allelims[patidx] = pat
     cost = sets * cs + nexts * cn
     # 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],
                     lambda s: [l[::-1] for l in s.split('\n')],
                 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, rule_has_b2(rule))
+            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
             elimrules[rule, '\n'.join(pat0)] = sorted(elims0.items())
 
     # verification (duh!)
 
     return elimrules
 
+
 def min_vertex_cover(s, has_b2):
     # 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
 
     i = 0
     vc = set()
-    for ix, pl, l, nl in each_neighbors(s):
+    for x, pl, l, nl in each_neighbors(s):
         i += 1
         if i % 100000 == 0:
-            print >>sys.stderr, 'calculating approx. vertex cover: x=%d' % i
+            print >>sys.stderr, 'calculating approx. vertex cover: %d' % i
 
-        for iy in list(l):
-            if   (iy-1) in pl: pl.discard(iy-1); vc.add((ix-1, iy-1))
-            elif  iy    in pl: pl.discard(iy  ); vc.add((ix-1, iy  ))
-            elif (iy+1) in pl: pl.discard(iy+1); vc.add((ix-1, iy+1))
-            elif (iy-1) in  l:  l.discard(iy-1); vc.add((ix  , iy-1))
-            elif (iy+1) in  l:  l.discard(iy+1); vc.add((ix  , iy+1))
-            elif (iy-1) in nl: nl.discard(iy-1); vc.add((ix+1, iy-1))
-            elif  iy    in nl: nl.discard(iy  ); vc.add((ix+1, iy  ))
-            elif (iy+1) in nl: nl.discard(iy+1); vc.add((ix+1, iy+1))
+        for y in list(l):
+            if   (y-1) in pl: pl.discard(y-1); vc.add((x-1, y-1))
+            elif  y    in pl: pl.discard(y  ); vc.add((x-1, y  ))
+            elif (y+1) in pl: pl.discard(y+1); vc.add((x-1, y+1))
+            elif (y-1) in  l:  l.discard(y-1); vc.add((x  , y-1))
+            elif (y+1) in  l:  l.discard(y+1); vc.add((x  , y+1))
+            elif (y-1) in nl: nl.discard(y-1); vc.add((x+1, y-1))
+            elif  y    in nl: nl.discard(y  ); vc.add((x+1, y  ))
+            elif (y+1) in nl: nl.discard(y+1); vc.add((x+1, y+1))
             else: continue
-            l.discard(iy)
-            vc.add((ix, iy))
+            l.discard(y)
+            vc.add((x, y))
 
     return vc
 
 
     i = 0
     vc = set()
-    for ix, ppl, pl, l, nl, nnl in each_neighbors2(s):
+    for x, ppl, pl, l, nl, nnl in each_neighbors2(s):
         i += 1
         if i % 100000 == 0:
-            print >>sys.stderr, 'calculating approx. vertex cover: x=%d' % i
+            print >>sys.stderr, 'calculating approx. vertex cover: %d' % i
 
-        for iy in list(l):
-            if   (iy-2) in ppl: ppl.discard(iy-2); vc.add((ix-2, iy-2))
-            elif (iy-1) in ppl: ppl.discard(iy-1); vc.add((ix-2, iy-1))
-            elif  iy    in ppl: ppl.discard(iy  ); vc.add((ix-2, iy  ))
-            elif (iy+1) in ppl: ppl.discard(iy+1); vc.add((ix-2, iy+1))
-            elif (iy+2) in ppl: ppl.discard(iy+2); vc.add((ix-2, iy+2))
-            elif (iy-2) in  pl:  pl.discard(iy-2); vc.add((ix-1, iy-2))
-            elif (iy-1) in  pl:  pl.discard(iy-1); vc.add((ix-1, iy-1))
-            elif  iy    in  pl:  pl.discard(iy  ); vc.add((ix-1, iy  ))
-            elif (iy+1) in  pl:  pl.discard(iy+1); vc.add((ix-1, iy+1))
-            elif (iy+2) in  pl:  pl.discard(iy+2); vc.add((ix-1, iy+2))
-            elif (iy-2) in   l:   l.discard(iy-2); vc.add((ix  , iy-2))
-            elif (iy-1) in   l:   l.discard(iy-1); vc.add((ix  , iy-1))
-            elif (iy+1) in   l:   l.discard(iy+1); vc.add((ix  , iy+1))
-            elif (iy+2) in   l:   l.discard(iy+2); vc.add((ix  , iy+2))
-            elif (iy-2) in  nl:  nl.discard(iy-2); vc.add((ix+1, iy-2))
-            elif (iy-1) in  nl:  nl.discard(iy-1); vc.add((ix+1, iy-1))
-            elif  iy    in  nl:  nl.discard(iy  ); vc.add((ix+1, iy  ))
-            elif (iy+1) in  nl:  nl.discard(iy+1); vc.add((ix+1, iy+1))
-            elif (iy+2) in  nl:  nl.discard(iy+2); vc.add((ix+1, iy+2))
-            elif (iy-2) in nnl: nnl.discard(iy-2); vc.add((ix+2, iy-2))
-            elif (iy-1) in nnl: nnl.discard(iy-1); vc.add((ix+2, iy-1))
-            elif  iy    in nnl: nnl.discard(iy  ); vc.add((ix+2, iy  ))
-            elif (iy+1) in nnl: nnl.discard(iy+1); vc.add((ix+2, iy+1))
-            elif (iy+2) in nnl: nnl.discard(iy+2); vc.add((ix+2, iy+2))
+        for y in list(l):
+            if   (y-2) in ppl: ppl.discard(y-2); vc.add((x-2, y-2))
+            elif (y-1) in ppl: ppl.discard(y-1); vc.add((x-2, y-1))
+            elif  y    in ppl: ppl.discard(y  ); vc.add((x-2, y  ))
+            elif (y+1) in ppl: ppl.discard(y+1); vc.add((x-2, y+1))
+            elif (y+2) in ppl: ppl.discard(y+2); vc.add((x-2, y+2))
+            elif (y-2) in  pl:  pl.discard(y-2); vc.add((x-1, y-2))
+            elif (y-1) in  pl:  pl.discard(y-1); vc.add((x-1, y-1))
+            elif  y    in  pl:  pl.discard(y  ); vc.add((x-1, y  ))
+            elif (y+1) in  pl:  pl.discard(y+1); vc.add((x-1, y+1))
+            elif (y+2) in  pl:  pl.discard(y+2); vc.add((x-1, y+2))
+            elif (y-2) in   l:   l.discard(y-2); vc.add((x  , y-2))
+            elif (y-1) in   l:   l.discard(y-1); vc.add((x  , y-1))
+            elif (y+1) in   l:   l.discard(y+1); vc.add((x  , y+1))
+            elif (y+2) in   l:   l.discard(y+2); vc.add((x  , y+2))
+            elif (y-2) in  nl:  nl.discard(y-2); vc.add((x+1, y-2))
+            elif (y-1) in  nl:  nl.discard(y-1); vc.add((x+1, y-1))
+            elif  y    in  nl:  nl.discard(y  ); vc.add((x+1, y  ))
+            elif (y+1) in  nl:  nl.discard(y+1); vc.add((x+1, y+1))
+            elif (y+2) in  nl:  nl.discard(y+2); vc.add((x+1, y+2))
+            elif (y-2) in nnl: nnl.discard(y-2); vc.add((x+2, y-2))
+            elif (y-1) in nnl: nnl.discard(y-1); vc.add((x+2, y-1))
+            elif  y    in nnl: nnl.discard(y  ); vc.add((x+2, y  ))
+            elif (y+1) in nnl: nnl.discard(y+1); vc.add((x+2, y+1))
+            elif (y+2) in nnl: nnl.discard(y+2); vc.add((x+2, y+2))
             else: continue
-            l.discard(iy)
-            vc.add((ix, iy))
+            l.discard(y)
+            vc.add((x, y))
 
     return vc
 
+def greedy_elimination(s, (bflags, sflags)):
+    neighborlimits = (min(j for j in xrange(10) if ((512 | bflags) >> j) & 1),
+                      min(j for j in xrange(10) if ((512 | sflags) >> j) & 1))
+
+    i = 0
+    removed = set()
+    for x, ppl, pl, l, nl, nnl in each_neighbors2(s):
+        i += 1
+        if i % 100000 == 0:
+            print >>sys.stderr, 'calculating greedy elimination: %d' % i
+
+        for y in sorted(l):
+            # a0 a1 a2 a3 a4
+            # b0 b1 b2 b3 b4
+            # c0 c1 ** c3 c4
+            # d0 d1 d2
+            a0 = (y-2) in ppl; a1 = (y-1) in ppl; a2 = y in ppl; a3 = (y+1) in ppl; a4 = (y+2) in ppl
+            b0 = (y-2) in  pl; b1 = (y-1) in  pl; b2 = y in  pl; b3 = (y+1) in  pl; b4 = (y+2) in  pl
+            c0 = (y-2) in   l; c1 = (y-1) in   l;                c3 = (y+1) in   l; c4 = (y+2) in   l
+            d0 = (y-2) in  nl; d1 = (y-1) in  nl; d2 = y in  nl
+
+            # it is sufficient to check four points that have already considered
+            if (a0 + a1 + a2 + b0 + b2 + c0 + c1 + 1  >= neighborlimits[b1] or
+                a1 + a2 + a3 + b1 + b3 + c1 + 1  + c3 >= neighborlimits[b2] or
+                a2 + a3 + a4 + b2 + b4 + 1  + c3 + c4 >= neighborlimits[b3] or
+                b0 + b1 + b2 + c0 + 1  + d0 + d1 + d2 >= neighborlimits[c1]):
+
+                removed.add((x, y))
+                l.discard(y)
+
+    return removed
+
 ----
 
 v = map(int,'''
-4 216 2245906 8457030 3210515 814610 616968 48146 5003295
+4 216 2245771 8178420 2820604 499250 436448 35530 5002855
 ''' '''
-4 204 2245528 8457030 701427 814610 630658 27486 5001495
+4 204 2245528 8457030 701427 814610 616968 27486 5001495
 4 316 2245528 12149490 701427 969414 1024548 86980 5001495
 4 232 3571938 168133350 1015963 858694 1232940 31622 10893045 
 '''.split())