Seonghoon Kang avatar Seonghoon Kang committed a3956dc

snapshot

Comments (0)

Files changed (7)

 all: solve zip
 
 clean:
-	rm -f dumper verifier code.tar.gz
+	rm -f dumper verifier split *.pyc code.tar.gz analysis/
 
 dumper: dumper.cpp
 verifier: verifier.cpp
 	make bgolly
 	./solve.sh
 
-result.txt:
-	cat ${TESTCASES:%=output/output%.txt} > $@
+result.txt: ${TESTCASES:%=output/output%.txt}
+	cat $^ > $@
 
 result.7z: result.txt
 	rm -f $@
 import sys
 import gol
 
-# (rulestring, patternstring): dict from (# of further nexts) to list of prior sets
-elimrules0 = {}
-currules = curpat = curnexts = curelims = None
-with open('elimrules.txt', 'r') as f:
-    for line in f:
-        if not line.strip(): continue
-        if line.startswith('#'): continue
-        line = line.rstrip('\r\n')
-        if line.startswith('B'): # rulestring
-            if currules:
-                if not curpat and not curelims:
-                    currules.append(line)
-                else:
-                    assert curpat and curelims
-                    for currule in currules:
-                        elimrules0[currule, '\n'.join(curpat)] = \
-                                dict((k, '\n'.join(v)) for k,v in curelims.items())
-                    currules = [line]
-            else:
-                currules = [line]
-            curpat = []
-            curnexts = None
-            curelims = {}
-        elif line.startswith(('.', 'o')): # pattern
-            if curnexts is None:
-                curpat.append(line)
-            else:
-                curelims[curnexts].append(line)
-        elif line.startswith(tuple('0123456789')): # elimination
-            curnexts = int(line)
-            assert curnexts not in curelims
-            curelims[curnexts] = []
-        else:
-            assert False
-    if currules:
-        assert curpat and curelims
-        for currule in currules:
-            elimrules0[currule, '\n'.join(curpat)] = \
-                    dict((k, '\n'.join(v)) for k,v in curelims.items())
-
-def rule_has_b2(rule):
-    return (gol.parse_rulestring(rule)[0] >> 2) & 1
-
-# expand elimrules0 for rotation and mirroring.
-elimrules = {}
-for (rule, patstr), elims in elimrules0.items():
-    for rot in [lambda s: s.split('\n'),
-                lambda s: s.split('\n')[::-1],
-                lambda s: [l[::-1] for l in s.split('\n')],
-                lambda s: [l[::-1] for l in s.split('\n')[::-1]],
-                lambda s: [''.join(l) for l in zip(*s.split('\n'))],
-                lambda s: [''.join(l) for l in zip(*s.split('\n')[::-1])],
-                lambda s: [''.join(l[::-1]) for l in zip(*s.split('\n'))],
-                lambda s: [''.join(l[::-1]) for l in zip(*s.split('\n')[::-1])]]:
-        pat0 = rot(patstr)
-        pat = set((x, y) for x, line in enumerate(pat0)
-                         for y, c in enumerate(line) if c == 'o')
-        elims0 = {0: pat}
-        for k, v in sorted(elims.items()):
-            v = set((x, y) for x, line in enumerate(rot(v))
-                           for y, c in enumerate(line) if c == 'o')
-            elims0[k] = pat.difference(v)
-        minvc = gol.min_vertex_cover(pat, rule_has_b2(rule))
-        if 1 not in elims0 or len(minvc) < len(elims0[1]): elims0[1] = minvc
-        elimrules[rule, '\n'.join(pat0)] = sorted(elims0.items())
+elimrules = gol.read_elimrules()
+if elimrules is None: raise SystemExit(2)
 
 rule = cs = cn = patidx = None
 patterns = {}
 mincost = 99999999999999
 best = None
 bestelims = None
-hasb2 = rule_has_b2(rule)
+hasb2 = gol.rule_has_b2(rule)
 for nexts in xrange(maxnexts + 1):
     sets = 0
     allelims = {}
-    for patidx, pat in patterns.items():
+    for patidx, pat0 in patterns.items():
         patcnt = patterncounts[patidx]
-        elims = elimrules.get((rule, '\n'.join(pat)))
+        elims = elimrules.get((rule, '\n'.join(pat0)))
         if elims:
             isets, ielims = min((len(v), v) for k, v in elims if k <= nexts)
             sets += isets * patcnt
             allelims[patidx] = ielims
         else:
-            pat = set((x, y) for x, line in enumerate(pat)
+            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)
             sets += len(pat) * patcnt
 
 1
 ..o
-o..
+...
 ..o
 
 2
 
 1
 .o.
+...
+.o.
+
+2
+.o.
 o..
 .o.
 
         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).
+    # we take advantage of this fact...
+    s = sorted(s)
+    pl = set(); l = set(); nl = set()
+    ix = start - 1
+    for x, y in s:
+        while x > ix + 1:
+            yield ix, pl, l, nl
+            ix += 1
+            t = pl; pl = l; l = nl; nl = t
+            t.clear()
+        nl.add(y)
+    x += 3
+    while x > ix + 1:
+        yield ix, pl, l, nl
+        ix += 1
+        t = pl; pl = l; l = nl; nl = t
+        t.clear()
+
+def each_neighbors2(s, start=0):
+    s = sorted(s)
+    ppl = set(); pl = set(); l = set(); nl = set(); nnl = set()
+    ix = start - 2
+    for x, y in s:
+        while x > ix + 2:
+            yield ix, ppl, pl, l, nl, nnl
+            ix += 1
+            t = ppl; ppl = pl; pl = l; l = nl; nl = nnl; nnl = t
+            t.clear()
+        nnl.add(y)
+    x += 5
+    while x > ix + 2:
+        yield ix, ppl, pl, l, nl, nnl
+        ix += 1
+        t = ppl; ppl = pl; pl = l; l = nl; nl = nnl; nnl = t
+        t.clear()
+
+def evolve(s, (bflags, sflags)):
+    # XXX should use each_neighbors instead
+    neighbors = set(s)
+    neighbors.update((x-1, y-1) for x, y in s)
+    neighbors.update((x-1, y  ) for x, y in s)
+    neighbors.update((x-1, y+1) for x, y in s)
+    neighbors.update((x  , y-1) for x, y in s)
+    neighbors.update((x  , y+1) for x, y in s)
+    neighbors.update((x+1, y-1) for x, y in s)
+    neighbors.update((x+1, y  ) for x, y in s)
+    neighbors.update((x+1, y+1) for x, y in s)
+
+    result = set()
+    flags = (bflags, sflags)
+    for x, y in neighbors:
+        v = (((x-1, y-1) in s) + ((x-1, y) in s) + ((x-1, y+1) in s) +
+             ((x  , y-1) in s) +                   ((x  , y+1) in s) +
+             ((x+1, y-1) in s) + ((x+1, y) in s) + ((x+1, y+1) in s))
+        if (flags[(x, y) in s] >> v) & 1:
+            result.add((x, y))
+    return result
+
+def read_elimrules():
+    # (rulestring, patternstring): dict from (# of further nexts) to list of prior sets
+    elimrules0 = {}
+    currules = curpat = curnexts = curelims = None
+    with open('elimrules.txt', 'r') as f:
+        for line in f:
+            if not line.strip(): continue
+            if line.startswith('#'): continue
+            line = line.rstrip('\r\n')
+            if line.startswith('B'): # rulestring
+                if currules:
+                    if not curpat and not curelims:
+                        currules.append(line)
+                    else:
+                        assert curpat and curelims
+                        for currule in currules:
+                            elimrules0[currule, '\n'.join(curpat)] = \
+                                    dict((k, '\n'.join(v)) for k,v in curelims.items())
+                        currules = [line]
+                else:
+                    currules = [line]
+                curpat = []
+                curnexts = None
+                curelims = {}
+            elif line.startswith(('.', 'o')): # pattern
+                if curnexts is None:
+                    curpat.append(line)
+                else:
+                    curelims[curnexts].append(line)
+            elif line.startswith(tuple('0123456789')): # elimination
+                curnexts = int(line)
+                assert curnexts not in curelims
+                curelims[curnexts] = []
+            else:
+                assert False
+        if currules:
+            assert curpat and curelims
+            for currule in currules:
+                elimrules0[currule, '\n'.join(curpat)] = \
+                        dict((k, '\n'.join(v)) for k,v in curelims.items())
+
+    # expand elimrules0 for rotation and mirroring.
+    elimrules = {}
+    for (rule, patstr), elims in elimrules0.items():
+        for rot in [lambda s: s.split('\n'),
+                    lambda s: s.split('\n')[::-1],
+                    lambda s: [l[::-1] for l in s.split('\n')],
+                    lambda s: [l[::-1] for l in s.split('\n')[::-1]],
+                    lambda s: [''.join(l) for l in zip(*s.split('\n'))],
+                    lambda s: [''.join(l) for l in zip(*s.split('\n')[::-1])],
+                    lambda s: [''.join(l[::-1]) for l in zip(*s.split('\n'))],
+                    lambda s: [''.join(l[::-1]) for l in zip(*s.split('\n')[::-1])]]:
+            pat0 = rot(patstr)
+            pat = set((x, y) for x, line in enumerate(pat0)
+                             for y, c in enumerate(line) if c == 'o')
+            elims0 = {0: pat}
+            for k, v in sorted(elims.items()):
+                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))
+            if 1 not in elims0 or len(minvc) < len(elims0[1]): elims0[1] = minvc
+            elimrules[rule, '\n'.join(pat0)] = sorted(elims0.items())
+
+    # verification (duh!)
+    for (rule, pat0), elims in elimrules.items():
+        pat = set((x, y) for x, line in enumerate(pat0.split('\n'))
+                         for y, c in enumerate(line) if c == 'o')
+        flags = parse_rulestring(rule)
+        for nexts, diff in elims:
+            ipat = pat ^ diff
+            for i in xrange(nexts):
+                ipat = evolve(ipat, flags)
+            if ipat:
+                print >>sys.stderr, 'Error: elimrules.txt contains an incorrect entry!'
+                print >>sys.stderr, rule
+                print >>sys.stderr, pat0
+                print >>sys.stderr, nexts
+                print >>sys.stderr, '<-', pat ^ diff
+                print >>sys.stderr, '->', ipat
+                print >>sys.stderr
+
+    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
     # basic approach: we only consider consecutive three lines at a time,
     # otherwise we need to store at most len(s)*16 edges!
 
-    # sentinel for avoiding code duplication, should be disconnected
-    # from other cells
-    s = sorted(s)
-    s.append((s[-1][0] + 2, 0))
+    i = 0
+    vc = set()
+    for ix, pl, l, nl in each_neighbors(s):
+        i += 1
+        if i % 100000 == 0:
+            print >>sys.stderr, 'calculating approx. vertex cover: x=%d' % i
 
-    pl = set()
-    l = set()
-    nl = set()
-    ix = -2
-    vc = set()
-    i = 0
-    for x, y in s:
-        i += 1
-        if i % 200000 == 0:
-            print >>sys.stderr, 'calculating approx. vertex cover: %d out of %d' % (i, len(s))
-
-        # eliminate any vertices in pl with degree 2 if any
-        while x > ix + 1:
-            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))
-                else: continue
-                l.discard(iy)
-                vc.add((ix, iy))
-
-            ix += 1
-            t = pl
-            pl = l
-            l = nl
-            nl = t
-            t.clear()
-
-        nl.add(y)
+        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))
+            else: continue
+            l.discard(iy)
+            vc.add((ix, iy))
 
     return vc
 
     # ... has two disconnected components but it evolves to .o. .
     # ..o                                                   ...
 
-    s = sorted(s)
-    s.append((s[-1][0] + 3, 0))
+    i = 0
+    vc = set()
+    for ix, 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
 
-    ppl = set()
-    pl = set()
-    l = set()
-    nl = set()
-    nnl = set()
-    ix = -3
-    vc = set()
-    for x, y in s:
-        # eliminate any vertices in pl with degree 2 if any
-        while x > ix + 2:
-            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))
-                else: continue
-                l.discard(iy)
-                vc.add((ix, iy))
-
-            ix += 1
-            t = ppl
-            ppl = pl
-            pl = l
-            l = nl
-            nl = nnl
-            nnl = t
-            t.clear()
-
-        nnl.add(y)
+        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))
+            else: continue
+            l.discard(iy)
+            vc.add((ix, iy))
 
     return vc
 
+#!/usr/bin/python
+import sys, re
+v=open(sys.argv[1]).readlines()
+open(sys.argv[2],"w").write(v[0] + re.sub('([0-9]*)\$', lambda m:'$\n'*int(m.group(1) or 1), "".join(v[1:]).replace("\n","")))
 ----
 
 v = map(int,'''
-4 216 2245906 8457030 3210515 814610 630658 155834 5003295
+4 216 2245906 8457030 3210515 814610 616968 48146 5003295
 ''' '''
-4 204 2245528 12149490 701427 858694 966868 27486 5001495 
+4 204 2245528 8457030 701427 814610 630658 27486 5001495
 4 316 2245528 12149490 701427 969414 1024548 86980 5001495
 4 232 3571938 168133350 1015963 858694 1232940 31622 10893045 
 '''.split())
 #include "gol.h"
 using namespace std;
 
+int verifytemp = 0;
+
 void evolve_with_golly(int ngens) {
+	char tempin[256], tempout[256];
+	sprintf(tempin, "temp-verify%d.rle", verifytemp++);
+	sprintf(tempout, "temp-verify%d.rle", verifytemp++);
+
 	char buf[256];
-	sprintf(buf, "./generate.sh %d temp1.rle temp2.rle >&2", ngens);
+	sprintf(buf, "./generate.sh %d %s %s >&2", ngens, tempin, tempout);
 
 	FILE *fp;
 	fprintf(stderr, "evolving %d generations with Golly... (previous population %d)\n", ngens, p);
 
-	fp = fopen("temp1.rle", "w");
+	fp = fopen(tempin, "w");
 	if (fp == NULL) {
 		fprintf(stderr, "Fatal Error: failed to write to temp1.rle\n");
 		exit(2);
 	system(buf);
 	fprintf(stderr, "\n");
 
-	fp = fopen("temp2.rle", "r");
+	fp = fopen(tempout, "r");
 	if (fp == NULL) {
 		fprintf(stderr, "Fatal Error: failed to read from temp2.rle\n");
 		exit(2);
 	p = read_rle(fp, table);
 	fclose(fp);
 
-	unlink("temp1.rle");
-	unlink("temp2.rle");
+	if (getenv("KEEPTEMP") == NULL) {
+		unlink(tempin);
+		unlink(tempout);
+	}
 }
 
 void evolven(int k) {
 	}
 
 	if (p > 0 || !table.empty()) {
-		fprintf(stderr, "Error: population 0 expected, %d actual (table size %d)\n", p, (int) table.size());
+		fprintf(stderr, "Error: population 0 expected, %d actual\n", p);
 
 		rename(argv[1], argv[2]); // but we still has a pointer to the original file
 		fseek(fp, 0, SEEK_SET);
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.