Commits

Seonghoon Kang committed d44177a

trying to specialize elimcomps for #3

  • Participants
  • Parent commits 7742982

Comments (0)

Files changed (4)

File dayandnight_holes.py

+import gol
+import os
+import sys
+
+rects = []
+sizes = set()
+with open('analysis/position3.txt') as f:
+    for line in f:
+        x, y, w, h = map(int, line.split())
+        rects.append((x, y, w, h))
+        if w < h: w, h = h, w
+        sizes.add((w, h)) # always w > h
+
+holes = {}
+for q, (w, h) in enumerate(sizes):
+    if q%10==0: print >>sys.stderr, 'reading populations', q, len(sizes)
+    choices = {}
+    sets = [1,2,3,4,2,2]
+    for k in xrange(6):
+        with open('analysis/input3-preproc/%d-%d-%d.csv' % (w,h,k)) as f:
+            for line in f:
+                g, p = map(int, line.split(','))
+                try:
+                    pp, pk = choices[g]
+                    if pp > p + sets[k]:
+                        choices[g] = p + sets[k], k
+                except KeyError:
+                    choices[g] = p + sets[k], k
+    holes[w, h] = min((p, g, k) for g, (p,k) in choices.items())
+
+flags = gol.parse_rulestring('B3678/S34678')
+layers = {0: set()} # SETs required after k-th NEXTs
+cache = {}
+q=0
+for q, (x, y, w0, h0) in enumerate(rects):
+    if q%10==0: print >>sys.stderr, '\neliminating clusters', q, len(rects)
+    w = max(w0, h0); h = min(w0, h0)
+    bestcost, bestg, bestk = holes[w, h]
+    if (w0, h0) in cache:
+        sets, addg, cells = cache[w0, h0]
+    else:
+        sets = ([(1,1)], [(1,1),(1,w-2)], [(1,1),(1,w-2),(h-2,1)], [(1,1),(1,w-2),(h-2,1),(h-2,w-2)], [(1,1),(h-2,1)], [(1,w-2),(h-2,1)])[bestk]
+        if w != w0: sets = [(j,i) for i,j in sets]
+
+        z = []
+        z.append(['b'] + ['o' if i%3==2 else 'b' for i in xrange(w0)] + ['b'])
+        for i in xrange(h0):
+            s = 'o' if i%3==2 else 'b'
+            z.append([s] + ['o'] * w0 + [s])
+        z.append(z[0])
+
+        for i,j in sets:
+            assert z[i+1][j+1] == 'o'
+            z[i+1][j+1] = 'b'
+
+        with open('temp-dayandnight-holes1.rle', 'w') as f:
+            print >>f, 'x = 1000000, y = 1000000, rule = B3678/S34678:P1000000,1000000'
+            print >>f, '49999$'
+            for l in z:
+                print >>f, '49999b%s$' % ''.join(l)
+            print >>f, '!'
+
+        os.system('./generate.sh %d temp-dayandnight-holes1.rle temp-dayandnight-holes2.rle 1>&2' % bestg)
+        with open('temp-dayandnight-holes2.rle') as f:
+            _, _, _, cells = gol.parse_rle(f)
+            addg = 0
+            for g, elims in gol.best_general_eliminations(cells, flags):
+                if len(cells) > len(elims):
+                    addg = g; cells = elims
+
+        cache[w0, h0] = sets, addg, cells
+
+    for i,j in sets: layers[0].add((x+i, y+j))
+    layer = layers.setdefault(bestg + addg, set())
+    for i,j in cells: layer.add((x-50000+i,y-50000+j))
+
+prevg = 0
+print max(layers) + sum(map(len, layers.values()))
+for g, sets in sorted(layers.items()):
+    for i in xrange(g-prevg): print 'NEXT'
+    prevg = g
+    for i, j in sorted(sets): print 'SET', i, j
+

File dayandnight_leastcost.py

+import gol
+
+sizes = set()
+with open('analysis/position3.txt') as f:
+    for line in f:
+        x, y, w, h = map(int, line.split())
+        if w < h: w, h = h, w
+        sizes.add((w, h)) # always w > h
+
+def write_rle(z, w, h, k):
+    with open('analysis/input3-preproc/%d-%d-%d.rle' % (w,h,k), 'w') as f:
+        print >>f, 'x = 1000000, y = 1000000, rule = B3678/S34678:P1000000,1000000'
+        print >>f, '49999$'
+        for l in z:
+            print >>f, '49999b%s$' % ''.join(l)
+        print >>f, '!'
+
+for w, h in sorted(sizes):
+    # six possible cases
+    z = []
+    z.append(['b'] + ['o' if i%3==2 else 'b' for i in xrange(w)] + ['b'])
+    for i in xrange(h):
+        s = 'o' if i%3==2 else 'b'
+        z.append([s] + ['o'] * w + [s])
+    z.append(z[0])
+
+    # +--+ +--+ +--+ +--+ +--+ +--+
+    # |x | |xx| |xx| |xx| |x | | x|
+    # |  | |  | |  | |  | |  | |  |
+    # |  | |  | |x | |xx| |x | |x |
+    # +--+ +--+ +--+ +--+ +--+ +--+
+    z[2][2] = 'b'; write_rle(z, w, h, 0)
+    z[2][w-1] = 'b'; write_rle(z, w, h, 1)
+    z[h-1][2] = 'b'; write_rle(z, w, h, 2)
+    z[h-1][w-1] = 'b'; write_rle(z, w, h, 3)
+    z[2][w-1] = z[h-1][w-1] = 'o'; write_rle(z, w, h, 4)
+    z[2][w-1] = 'b'; z[2][2] = 'o'; write_rle(z, w, h, 5)
+

File dayandnight_split.cpp

+// Written by Hasegawa Sayuri
+//
+// A special casing for Day & Night (B3678/S34678) rules. There are only
+// two kinds of patterns in case #3:
+//
+// - A horizontal line, or
+// - A stable like this:
+//
+//     ...o..o..o..o...
+//     .oooooooooooooo.
+//     .oxoooooooooooo.
+//     oooooooooooooooo
+//     .oooooooooooooo.
+//     .oooooooooooooo.
+//     oooooooooooooooo
+//     .oooooooooooooo.
+//     .oooooooooooooo.
+//     ...o..o..o..o...
+//
+// Both patterns are flexible in their dimensions but can be detected with
+// not that much efforts, so we specialize for these cases.
+
+#include <stdio.h>
+#include <unistd.h>
+#include <set>
+#include "gol.h"
+using namespace std;
+
+int main(int argc, char **argv) {
+	if (argc < 2) {
+		fprintf(stderr, "Usage: %s analysis/inputX-remainder.rle < data/inputX.txt > analysis/positionX.txt\n", argv[0]);
+		return 1;
+	}
+
+	populate(stdin);
+
+	// we detect the following pattern (8 fixed cells):
+	//
+	//  ..
+	// .oo
+	// .oo
+	//
+	// as the original pattern (mostly) only contains this kind of stables
+	// and highly unstable horizontal lines.
+
+	int i = 0;
+	for (set<point>::iterator it = itable.begin(); it != itable.end(); ++i) {
+		if (i % 1000000 == 0) {
+			fprintf(stderr, "Day & Night preprocessing: %d out of %d\n", i, ip);
+		}
+		if (table.find(*it) != table.end()) {
+			itable.erase(it++);
+			continue;
+		}
+
+		//                      ?..
+		// something like this: .oo
+		//                      ???
+		int x = it->first, y = it->second;
+		if (itable.find(xy(x-1, y)) != itable.end() ||
+		    itable.find(xy(x-1, y+1)) != itable.end() ||
+		    itable.find(xy(x, y-1)) != itable.end() ||
+		    itable.find(xy(x, y+1)) == itable.end()) {
+			goto skip;
+		}
+
+		int x2, y2;
+		for (y2 = y + 1; itable.find(xy(x, y2)) != itable.end(); ++y2);
+		for (x2 = x + 1; ; ++x2) {
+			for (int iy = y; iy < y2; ++iy) {
+				if (itable.find(xy(x2, iy)) == itable.end()) goto endofrect;
+			}
+		}
+	endofrect:
+
+		if (x2 - x > 3 && y2 - y > 3 && (x2 - x) % 3 == 2 && (y2 - y) % 3 == 2) {
+			// maybe rectangular stable. check neighbors.
+			int x11 = x - 2, x1 = x - 1, x22 = x2 + 2;
+			int y11 = y - 2, y1 = y - 1, y22 = y2 + 2;
+			if (itable.find(xy(x1, y1)) != itable.end()) goto skip;
+			if (itable.find(xy(x1, y2)) != itable.end()) goto skip;
+			if (itable.find(xy(x2, y1)) != itable.end()) goto skip;
+			if (itable.find(xy(x2, y2)) != itable.end()) goto skip;
+			for (int iy = y, my = 0; iy < y2; ++iy) {
+				if ((itable.find(xy(x1, iy)) == itable.end()) ^ (my != 2)) goto skip;
+				if ((itable.find(xy(x2, iy)) == itable.end()) ^ (my != 2)) goto skip;
+				if (itable.find(xy(x11, iy)) != itable.end()) goto skip;
+				if (itable.find(xy(x22, iy)) != itable.end()) goto skip;
+				++my;
+				if (my == 3) my = 0;
+			}
+			for (int ix = x, mx = 0; ix < x2; ++ix) {
+				if ((itable.find(xy(ix, y1)) == itable.end()) ^ (mx != 2)) goto skip;
+				if ((itable.find(xy(ix, y2)) == itable.end()) ^ (mx != 2)) goto skip;
+				if (itable.find(xy(ix, y11)) != itable.end()) goto skip;
+				if (itable.find(xy(ix, y22)) != itable.end()) goto skip;
+				++mx;
+				if (mx == 3) mx = 0;
+			}
+
+			printf("%d %d %d %d\n", x, y, x2 - x, y2 - y);
+			for (int ix = x1; ix <= x2; ++ix) {
+				for (int iy = y1; iy <= y2; ++iy) {
+					table.insert(xy(ix, iy));
+				}
+			}
+			itable.erase(it++);
+			continue;
+		}
+
+	skip:
+		++it;
+	}
+
+	for (set<point>::iterator it = itable.begin(); it != itable.end(); ) {
+		if (table.find(*it) != table.end()) {
+			itable.erase(it++);
+		} else {
+			++it;
+		}
+	}
+
+	FILE *fp = fopen(argv[1], "w");
+	write_rle(fp, itable);
+	fclose(fp);
+
+	fflush(stdout);
+	_exit(0); // no need to wait for deallocation
+	return 0;
+}
+

File dayandnight_test.sh

+for i in analysis/input3-preproc/*.rle; do
+    echo $i
+    ./generate.sh 100000 $i $i.output.rle ${i/.rle/.csv} > /dev/null
+    rm -f $i.output.rle
+done
+#pypy dayandnight_holes.py > output/output3-temp.txt
+