Commits

Seonghoon Kang committed d8e59f2

snapshot

Comments (0)

Files changed (64)

+syntax: glob
+data
+analysis
+output
+result.txt
+result.7z
+code.tar.gz
+bgolly
+dayandnight
+dumper
+split
+verifier
+*.pyc
+.PHONY: all clean dump solve verify zip
+
+PYTHON=pypy
+CPPFLAGS=-O3 -W -Wall
+
+TESTCASES=0 1 2 3 4 5 6 7 8
+
+all: solve zip
+
+clean:
+	rm -f dumper verifier code.tar.gz
+
+dumper: dumper.cpp
+verifier: verifier.cpp
+split: split.cpp
+
+bgolly: golly/gollybase/*.cpp golly/cmdline/bgolly.cpp
+	${CXX} ${CPPFLAGS} -Igolly/gollybase -o $@ $^
+
+%: %.cpp gol.h gol.cpp
+	${CXX} ${CPPFLAGS} -o $@ $< gol.cpp
+
+dump: ${TESTCASES:%=data/input%.txt} ${TESTCASES:%=data/input%.rle}
+
+data/input%.txt data/input%.rle: data/input.txt
+	mkdir -p data
+	make dumper
+	./dumper < data/input.txt
+
+solve: ${TESTCASES:%=output/output%.txt}
+
+output/output%.txt: solve.sh
+	make bgolly
+	./solve.sh
+
+result.txt:
+	cat ${TESTCASES:%=output/output%.txt} > $@
+
+result.7z: result.txt
+	rm -f $@
+	7za -mx=3 a $@ $^
+
+code.tar.gz: README.txt GNUmakefile gol.cpp gol.h gol.py dumper.cpp split.py split.cpp \
+		fromrle.py patternize.py elimcomps.py elimrules.txt generate.sh leastcost.sh \
+		solve.sh verifier.cpp verify.sh golly score.sh prepend.py append.py \
+		dayandnight.cpp
+	rm -f $@
+	tar czvf $@ $^
+
+zip: result.7z code.tar.gz
+
+verify: verifier
+	make bgolly
+	@for ((i=0;i<9;++i)); do echo VERIFYING TESTCASE $$i >&2; ./verify.sh $$i; echo >&2; done
+
+analysis/pattern%.txt analysis/position%.txt: split data/input%.txt
+	./split analysis/pattern$*.txt analysis/position$*.txt < data/input$*.txt
+
+Hi! This is Sayuri Hasegawa. I hope enjoy reading this submission. Basically
+you use the submission like this:
+
+	mkdir data
+	mv ... data/input.txt
+	make dump               # produces data/input*.txt and others
+	make solve              # produces analysis/ and output/
+	make verify             # optional, but it's helpful to double-check
+	                        # and it often patches a last-minute error.
+	make zip                # produces result.7z and code.tar.gz
+
+You require bash, GNU make, p7zip, Python (2 only, PyPy is just fine), any
+optimizing C++ compiler. I've also used a modified version of Golly for fast
+board generation: `grep 'Hasegawa Sayuri' golly/` for all modifications.
+
+You can also use `./solve.sh N` and `./verify.sh N` for individually solving
+and verifying single test case. See `solve.sh` for strategies used.
+
+The entire process took less than 20 minutes in MacBook Air (Mid 2011) with
+4 GiB RAM. This does not include the time spent for tweaking various
+parameters and algorithms. YMMV.
+
+import sys
+n = int(raw_input())
+with open(sys.argv[1], 'r') as f:
+    suffix = f.readlines()
+print n + len(suffix)
+for line in sys.stdin: sys.stdout.write(line)
+for line in prefix: sys.stdout.write(line)
+
+#!/bin/bash
+(
+for ((i=0;i<$1;++i)); do
+	cat output/output$i.txt
+done
+for ((i=$i;i<9;++i)); do
+	echo 0
+done
+) > result.txt
+rm -f result.7z
+make zip
+import sys
+import re
+import gol
+
+if len(sys.argv) < 3:
+    print >>sys.stderr, 'Usage: %s target_gen target_pop < analysis/inputX-genY.rle' % sys.argv[0]
+    raise SystemExit(1)
+
+targetgen = int(sys.argv[1])
+targetpop = int(sys.argv[2])
+
+print >>sys.stderr, 'parsing RLE...'
+width, height, rule, cells = gol.parse_rle()
+if len(cells) != targetpop:
+    print >>sys.stderr, 'Error: population %d expected, %d actual' % (targetpop, len(cells))
+    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.
+nexts = 0
+hasb2 = (gol.parse_rulestring(rule)[0] >> 2) & 1
+cellsvc = gol.min_vertex_cover(cells, hasb2)
+if len(cellsvc) + 2 < len(cells):
+    nexts = 1
+    cells = list(cellsvc)
+
+print >>sys.stderr, 'writing %d NEXTs and %d SETs...' % (targetgen + nexts, len(cells))
+cells.sort()
+print targetgen + len(cells) + nexts
+for i in xrange(targetgen):
+    print 'NEXT'
+for x, y in cells:
+    print 'SET', x, y
+for i in xrange(nexts):
+    print 'NEXT'
+
+// Written by Hasegawa Sayuri
+//
+// Special casing for Day & Night (B3678/S34678) rule: if it has a stable
+// looks like this:
+//
+// ...o..o..o..o...
+// .oooooooooooooo.
+// .oxoooooooooooo.
+// oooooooooooooooo
+// .oooooooooooooo.
+// .oooooooooooooo.
+// oooooooooooooooo
+// .oooooooooooooo.
+// .oooooooooooooo.
+// ...o..o..o..o...
+//
+// then it holes down in the cell marked x. This will make the stable
+// unstable and highly likely to decompose by itself.
+
+#include <stdio.h>
+#include <set>
+#include <map>
+#include <vector>
+#include <utility>
+#include "gol.h"
+using namespace std;
+
+int main(int argc, char **argv) {
+	if (argc < 2) {
+		fprintf(stderr, "Usage: %s analysis/inputX-dayandnight.rle < data/inputX.txt > output/outputX-first.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>::const_iterator it = itable.begin(); it != itable.end(); ++it, ++i) {
+		if (i % 1000000 == 0) {
+			fprintf(stderr, "Day & Night preprocessing: %d out of %d\n", i, ip);
+		}
+
+		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+1, y-1)) == itable.end() &&
+		    itable.find(xy(x  , y+1)) != itable.end() &&
+		    itable.find(xy(x+1, y  )) != itable.end() &&
+		    itable.find(xy(x+1, y+1)) != itable.end()) {
+			printf("SET %d %d\n", x+1, y+1);
+			itable.erase(xy(x+1, y+1));
+		}
+	}
+
+	FILE *fp = fopen(argv[1], "w");
+	write_rle(fp, itable);
+	fclose(fp);
+
+	return 0;
+}
+
+// Written by Hasegawa Sayuri
+//
+// Dumper for Golly and other tools. Slow.
+
+#include <stdio.h>
+#include <set>
+#include "gol.h"
+using namespace std;
+
+int main(void) {
+	int k;
+	scanf("%d", &k);
+	for (int i = 0; i < k; ++i) {
+		fprintf(stderr, "preparing test case %d...\n", i);
+		populate(stdin);
+
+		char buf[32];
+		FILE *fp;
+
+		// emit the individual input file
+		sprintf(buf, "data/input%d.txt", i);
+		fp = fopen(buf, "w");
+		fprintf(fp, "%d %d %d %d %d %s\n", n, m, ip, cs, cn, get_rulestring(buf));
+		for (set<point>::const_iterator it = itable.begin(); it != itable.end(); ++it) {
+			fprintf(fp, "%d %d\n", it->first, it->second);
+		}
+		fclose(fp);
+
+		// emit the RLE file for further inspection
+		sprintf(buf, "data/input%d.rle", i);
+		fp = fopen(buf, "w");
+		write_rle(fp, itable);
+		fclose(fp);
+	}
+	return 0;
+}
+
+import sys
+import gol
+
+# (rulestring, patternstring): dict from (# of further nexts) to list of prior sets
+elimrules0 = {}
+currule = 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 currule:
+                assert curpat and curelims
+                elimrules0[currule, '\n'.join(curpat)] = \
+                        dict((k, '\n'.join(v)) for k,v in curelims.items())
+            currule = 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 currule:
+        assert curpat and curelims
+        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())
+
+rule = cs = cn = patidx = None
+patterns = {}
+patterncounts = {}
+with open(sys.argv[1]) as f:
+    patidx = None
+    for line in f:
+        line = line.rstrip('\r\n')
+        if not line: continue
+        if line.startswith('seek '):
+            continue
+        if line.startswith('cost '):
+            _, cs, cn = line.split()
+            cs = int(cs)
+            cn = int(cn)
+            continue
+        if line.startswith('rule '):
+            rule = line[5:].strip()
+            continue
+        if line.startswith('pattern '):
+            _, patidx, patcnt = line.split()
+            patidx = int(patidx)
+            patterncounts[patidx] = int(patcnt)
+            continue
+        line = line.replace('[]','o').replace('  ','.')
+        patterns.setdefault(patidx, []).append(line)
+
+# try to eliminate each components with the minimal cost
+maxnexts = 1 # we want to try at least the minimal vertex cover approach...
+for patidx, pat in patterns.items():
+    pat = '\n'.join(pat)
+    try: maxnexts = max(maxnexts, max(n for n, _ in elimrules[rule, pat]))
+    except KeyError: pass
+mincost = 99999999999999
+best = None
+bestelims = None
+hasb2 = rule_has_b2(rule)
+for nexts in xrange(maxnexts + 1):
+    sets = 0
+    allelims = {}
+    for patidx, pat in patterns.items():
+        patcnt = patterncounts[patidx]
+        elims = elimrules.get((rule, '\n'.join(pat)))
+        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)
+                             for y, c in enumerate(line) if c == 'o')
+            if nexts > 0: pat = gol.min_vertex_cover(pat, hasb2)
+            sets += len(pat) * patcnt
+            allelims[patidx] = pat
+    cost = sets * cs + nexts * cn
+    print >>sys.stderr, '%d sets, %d nexts -> cost %d' % (sets, nexts, cost)
+    if mincost > cost:
+        mincost = cost
+        best = nexts
+        bestelims = allelims
+
+with open(sys.argv[2]) as f:
+    lines = []
+    for line in f:
+        basex, basey, patidx = line.split()
+        basex = int(basex)
+        basey = int(basey)
+        for ix, iy in bestelims[int(patidx)]:
+            lines.append('SET %d %d' % (basex + ix, basey + iy))
+    for i in xrange(best):
+        lines.append('NEXT')
+    print len(lines)
+    for line in lines: print line
+
+# list of rules that implements "SETs then NEXTs to eliminiate" logics.
+#
+# the tool is able to generate rules for rotation and horizontal/vertical flip,
+# and also able to generate a default 1-NEXT rule (which is unfortunately
+# horribly inefficient for many cases).
+#
+# the rule looks like this:
+# B3/S23        <- rulestring
+# ..o           <- source pattern
+# o.o
+# .oo
+# 1             <- number of NEXTs after the transformation
+# ..o           <- target pattern, the differences between this and
+# o..              source pattern become the SETs
+# ..o
+# 2             <- multiple rules for the same source pattern are allowed
+# ..o
+# o..
+# .oo
+#
+# blank lines and lines starting with # are ignored.
+
+B3/S23
+..o
+o.o
+.oo
+
+1
+..o
+o..
+..o
+
+2
+..o
+o..
+.oo
+
+###
+
+B3/S23
+oo
+oo
+
+1
+o.
+.o
+
+###
+
+B3/S23
+ooo
+
+1
+o.o
+
+###
+
+B3/S23
+.o.
+o.o
+.o.
+
+1
+...
+o.o
+...
+
+###
+
+B3/S23
+.oo.
+o..o
+.oo.
+
+1
+.oo.
+....
+.oo.
+
+3
+.oo.
+...o
+.oo.
+
+###
+
+B3/S23
+oo.
+o.o
+.o.
+
+1
+o..
+...
+.o.
+
+2
+o..
+..o
+.o.
+
+3
+oo.
+..o
+.o.
+
+###
+
+B3/S23
+oo.
+o.o
+.oo
+
+1
+o..
+...
+..o
+
+2
+oo.
+ooo
+.oo
+
+3
+.o.
+o.o
+..o
+
+###
+
+B3/S23
+.oo.
+o..o
+o.o.
+.o..
+
+1
+.o..
+o..o
+....
+.o..
+
+###
+
+B3/S23
+.oo.
+o..o
+o..o
+.oo.
+
+1
+..o.
+o...
+...o
+.o..
+
+2
+..o.
+o...
+o..o
+..o.
+
+###
+
+B3/S23
+..ooo..
+.......
+o.....o
+o.....o
+o.....o
+.......
+..ooo..
+
+1
+..o.o..
+.......
+o.....o
+.......
+o.....o
+.......
+..o.o..
+
+###
+
+B3/S23
+....o....
+....o....
+....o....
+.........
+ooo...ooo
+.........
+....o....
+....o....
+....o....
+
+1
+....o....
+.........
+....o....
+.........
+o.o...o.o
+.........
+....o....
+.........
+....o....
+
+###
+
+B3/S23
+.oo...oo.
+o..o.o..o
+oo.o.o.oo
+...o.o...
+oo.o.o.oo
+o..o.o..o
+.oo...oo.
+
+1
+.........
+o..o.o..o
+.o.....o.
+.........
+.o.....o.
+o..o.o..o
+.........
+
+###
+
+B3/S23
+......o.
+oo...o.o
+o.o.o.o.
+..o.o...
+o.o.o.o.
+oo...oo.
+
+1
+......o.
+o.......
+..o.o...
+........
+..o.o...
+o.....o.
+
+###
+
+B3/S23
+..o.
+.o.o
+o.o.
+o...
+.o..
+..o.
+...o
+..oo
+
+1
+....
+.o.o
+....
+o...
+.o..
+....
+...o
+..o.
+
+###
+
+B3/S23
+...oo.oo
+...oo.oo
+........
+...oo.oo
+...o...o
+....ooo.
+........
+....ooo.
+...o...o
+...oo.oo
+.oo.....
+o.o.....
+.o......
+
+1
+....o.o.
+...o...o
+........
+....o.o.
+...o...o
+........
+........
+....o.o.
+........
+...o...o
+.o......
+........
+.o......
+
+###
+
+B3/S23
+.......oo....oo
+.......o.o..o.o
+........oo..oo.
+..........oo...
+........oo..oo.
+.......o.o..o.o
+.......oo....oo
+...............
+...............
+...............
+.oo...oo.......
+o..o.o..o......
+oo.o.o.oo......
+...o.o.........
+...o.o.........
+..oo.oo........
+
+1
+........o....o.
+.......o......o
+...............
+..........oo...
+...............
+.......o......o
+........o....o.
+...............
+...............
+...............
+...............
+o..o.o..o......
+.o.....o.......
+...............
+...o.o.........
+..o...o........
+
+###
+
+B3/S23
+....o
+..ooo
+.o...
+o.o..
+.o...
+
+1
+....o
+...o.
+.o...
+.....
+.o...
+
+###
+
+B3/S23
+.oo.oo.
+..o.o.o
+o....o.
+oo.....
+
+1
+.oo..o.
+.......
+.....o.
+oo.....
+
+###
+
+B2
+.oo.
+....
+o..o
+
+1
+....
+....
+o..o
+
+###
+
+B2
+..o
+...
+o..
+
+1
+...
+...
+o..
+
+2
+..o
+...
+o..
+
+###
+
+B2
+o..
+..o
+..o
+
+1
+...
+...
+..o
+
+2
+o..
+...
+..o
+
+import sys
+import gol
+cs = int(sys.argv[1])
+cn = int(sys.argv[2])
+width, height, rule, cells = gol.parse_rle()
+print height, width, len(cells), cs, cn, rule
+for x, y in sorted(cells): print x, y
+#!/bin/bash
+MAXGENS=$1
+INPUT=$2
+OUTPUT=$3
+POPCOUNT=$4
+if [ "$MAXGENS" == "" -o "$INPUT" == "" ]; then
+    echo Usage: $0 '<maxgens> <input> {<output>|""} [<path to write popcnts>]' >&2
+    exit 1
+fi
+
+function run_bgolly() {
+    if [ "$OUTPUT" == "" ]; then
+        ./bgolly -m "$MAXGENS" -v "$INPUT"
+    else
+        ./bgolly -m "$MAXGENS" -o "$OUTPUT" -v "$INPUT"
+    fi
+}
+
+if [ "$POPCOUNT" == "" ]; then
+    run_bgolly | grep '000:'
+else
+    TEMPFILE=/tmp/$$-population.csv
+    trap "rm -f $TEMPFILE" INT TERM EXIT
+    run_bgolly | grep : | sed 's/,//g;s/: /,/g' | tee "$TEMPFILE" | grep 000,
+    trap - INT TERM EXIT
+    mv "$TEMPFILE" "$POPCOUNT"
+fi
+// Written by Hasegawa Sayuri
+
+#include <stdio.h>
+#include "gol.h"
+using namespace std;
+
+int n, m, cs, cn, bflags, sflags;
+int ip, p, pp; // population count
+set<point> itable, table, ptable;
+
+void populate(FILE *fp) {
+	char bstring[10], sstring[10];
+	int k = fscanf(fp, "%d %d %d %d %d B%[012345678]/S%[012345678]%*[\r\n]",
+			&n, &m, &ip, &cs, &cn, bstring, sstring);
+	if (k < 7) sstring[0] = '\0'; // special casing for B2
+	bflags = sflags = 0;
+	for (int i = 0; bstring[i]; ++i) bflags |= 1 << (bstring[i] - '0');
+	for (int i = 0; sstring[i]; ++i) sflags |= 1 << (sstring[i] - '0');
+
+	itable.clear();
+	for (int i = 0; i < ip; ++i) {
+		int x, y;
+		fscanf(fp, "%d %d", &x, &y);
+		itable.insert(xy(x, y));
+	}
+}
+
+void evolve(void) {
+	swap(ptable, table);
+	pp = p;
+	table.clear();
+
+	static const int dx[9] = {1,1,1,0,-1,-1,-1,0,0};
+	static const int dy[9] = {1,0,-1,-1,-1,0,1,1,0};
+
+	map<point,bool> neighbors;
+	for (set<point>::const_iterator it = ptable.begin(); it != ptable.end(); ++it) {
+		for (int i = 0; i < 9; ++i) {
+			int x = it->first + dx[i];
+			int y = it->second + dy[i];
+			neighbors[xy(x, y)] = (ptable.find(xy(x, y)) != ptable.end());
+		}
+	}
+	for (map<point,bool>::const_iterator it = neighbors.begin(); it != neighbors.end(); ++it) {
+		int x = it->first.first, y = it->first.second;
+		int v = 0;
+		for (int i = 0; i < 8; ++i) {
+			v += (ptable.find(xy(x+dx[i], y+dy[i])) != ptable.end() ? 1 : 0);
+		}
+		if (((it->second ? sflags : bflags) >> v) & 1) {
+			table.insert(xy(x, y));
+		}
+	}
+
+	p = table.size();
+}
+
+const char *get_rulestring(char *buf) {
+	char *origbuf = buf;
+	*buf++ = 'B';
+	for (int j = 0; j <= 8; ++j) if ((bflags >> j) & 1) *buf++ = '0' + j;
+	if (sflags) {
+		*buf++ = '/';
+		*buf++ = 'S';
+		for (int j = 0; j <= 8; ++j) if ((sflags >> j) & 1) *buf++ = '0' + j;
+	}
+	*buf = '\0';
+	return origbuf;
+}
+
+int read_rle(FILE *fp, set<point>& table) {
+	// skip header lines
+	while (true) {
+		int c = fgetc(fp);
+		if (c != '#') {
+			ungetc(c, fp);
+			break;
+		}
+		while (fgetc(fp) != '\n');
+	}
+	while (fgetc(fp) != '\n');
+
+	int p = 0, x = 0, y = 0;
+	int c;
+	table.clear();
+	while (true) {
+		c = fgetc(fp);
+		while (c == ' ' || c == '\t' || c == '\r' || c == '\n') c = fgetc(fp);
+		int run = 1;
+		if ('0' <= c && c <= '9') {
+			run = 0;
+			while ('0' <= c && c <= '9') {
+				run = run * 10 + (c - '0');
+				c = fgetc(fp);
+			}
+		}
+		while (c == ' ' || c == '\t' || c == '\r' || c == '\n') c = fgetc(fp);
+		switch (c) {
+		case 'b':
+			y += run;
+			break;
+		case 'o':
+			for (int i = 0; i < run; ++i) {
+				table.insert(xy(x, y+i));
+			}
+			y += run;
+			p += run;
+			break;
+		case '$':
+			x += run;
+			y = 0;
+			break;
+		default:
+			return p;
+		}
+	}
+}
+
+void write_rle(FILE *fp, const set<point>& table) {
+	char buf[32]; // should be sufficient
+	fprintf(fp, "x = %d, y = %d, rule = %s:P%d,%d\n", m, n, get_rulestring(buf), m, n);
+
+	// XXX if we use unordered_set instead of set we need a separate sorting
+	int lastx = 0, lasty = 0, run = 0;
+	for (set<point>::const_iterator it = table.begin(); it != table.end(); ++it) {
+		if (lastx != it->first) {
+			if (run > 0) {
+				if (run > 1) fprintf(fp, "%d", run);
+				fputc('o', fp);
+				run = 0;
+			}
+			if (it->first - lastx > 1) {
+				fprintf(fp, "%d", it->first - lastx);
+			}
+			fputc('$', fp);
+			lastx = it->first;
+			lasty = 0;
+		}
+		if (lasty != it->second) {
+			if (run > 0) {
+				if (run > 1) fprintf(fp, "%d", run);
+				fputc('o', fp);
+				run = 0;
+			}
+			if (it->second - lasty > 1) {
+				fprintf(fp, "%d", it->second - lasty);
+			}
+			fputc('b', fp);
+		}
+		++run;
+		lasty = it->second + 1;
+	}
+	if (run > 0) {
+		if (run > 1) fprintf(fp, "%d", run);
+		fputc('o', fp);
+	}
+	fputc('!', fp);
+}
+
+// Written by Hasegawa Sayuri
+
+#ifndef GOL_H
+#define GOL_H
+
+#include <cstdio>
+#include <utility>
+#include <set>
+#include <map>
+
+typedef std::pair<int,int> point;
+
+extern int n, m, cs, cn, bflags, sflags;
+extern int ip, p, pp; // population count
+extern std::set<point> itable, table, ptable;
+
+inline point xy(int x, int y) {
+	return std::make_pair<int,int>(x, y);
+}
+
+void populate(std::FILE *fp);
+void evolve(void);
+const char *get_rulestring(char *buf);
+int read_rle(std::FILE *fp, std::set<point>& table);
+void write_rle(std::FILE *fp, const std::set<point>& table);
+
+#endif
+import sys
+import re
+
+def parse_rle(f=sys.stdin):
+    # skip header line(s), the final non-hash-starting line should be a parameter line
+    params = f.readline()
+    while params.startswith('#'): params = f.readline()
+    m = re.match(r'^x *= *(\d+) *, *y *= *(\d+) *, *rule *= *([^ :]+)(?::[^ ]+)?$', params)
+    width = int(m.group(1))
+    height = int(m.group(2))
+    rule = m.group(3)
+
+    cells = []
+    parts = re.split('([bo$!])', sys.stdin.read())
+    x = y = 0
+    for count, kind in zip(parts[::2], parts[1::2]):
+        count = int(count.strip() or '1')
+        if kind == 'b':
+            y += count
+        elif kind == 'o':
+            for i in xrange(count):
+                cells.append((x, y + i))
+            y += count
+        elif kind == '$':
+            x += count
+            y = 0
+        elif kind == '!':
+            break
+    return width, height, rule, cells
+
+def parse_rulestring(rule):
+    rule, _, _ = rule.partition(':')
+    brule = srule = ''
+    for i in rule.split('/'):
+        if i.startswith('B'): brule = i[1:]
+        elif i.startswith('S'): srule = i[1:]
+        else: assert False
+    return (sum(1<<int(i) for i in brule), sum(1<<int(i) for i in srule))
+
+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
+    # 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!
+
+    # sentinel for avoiding code duplication, should be disconnected
+    # from other cells
+    s = sorted(s)
+    s.append((s[-1][0] + 2, 0))
+
+    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)
+
+    return vc
+
+def min_vertex_cover_2(s):
+    # same as min_vertex_cover_1 but uses 5x5 boundary instead. this is must
+    # for B2 rules as the following thing is possible:
+    #
+    # o..                                                   ...
+    # ... has two disconnected components but it evolves to .o. .
+    # ..o                                                   ...
+
+    s = sorted(s)
+    s.append((s[-1][0] + 3, 0))
+
+    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)
+
+    return vc
+

golly/cmdline/bgolly.cpp

+                        /*** /
+
+This file is part of Golly, a Game of Life Simulator.
+Copyright (C) 2012 Andrew Trevorrow and Tomas Rokicki.
+
+This program is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License
+as published by the Free Software Foundation; either version 2
+of the License, or (at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+ Web site:  http://sourceforge.net/projects/golly
+ Authors:   rokicki@gmail.com  andrew@trevorrow.com
+
+                        / ***/
+#include "qlifealgo.h"
+#include "hlifealgo.h"
+#include "generationsalgo.h"
+#include "jvnalgo.h"
+#include "ruleloaderalgo.h"
+#include "readpattern.h"
+#include "util.h"
+#include "viewport.h"
+#include "liferender.h"
+#include "writepattern.h"
+#include <stdlib.h>
+#include <iostream>
+#include <cstdio>
+#include <string.h>
+#include <cstdlib>
+#ifdef TIMING
+#include <sys/time.h>
+#endif
+using namespace std ;
+viewport viewport(1000, 1000) ;
+/*
+ *   This is a "renderer" that is just stubs, for performance testing.
+ */
+class nullrender : public liferender {
+public:
+   nullrender() {}
+   virtual ~nullrender() {}
+   virtual void killrect(int, int, int, int) {}
+   virtual void pixblit(int, int, int, int, char*, int) {}
+   virtual void getcolors(unsigned char** r, unsigned char** g, unsigned char** b) {
+      static unsigned char dummy[256];
+      *r = *g = *b = dummy;
+   }
+} ;
+
+nullrender renderer ;
+/*
+ *   This is a "lifeerrors" that we can use to test some edge
+ *   conditions.  In this case the only real thing we use
+ *   it for is to check rendering during a progress dialog.
+ */
+class nullerrors : public lifeerrors {
+public:
+   nullerrors() {}
+   virtual void fatal(const char *) {}
+   virtual void warning(const char *) {}
+   virtual void status(const char *) {}
+   virtual void beginprogress(const char *s) { abortprogress(0, s) ; }
+   virtual bool abortprogress(double, const char *) ;
+   virtual void endprogress() { abortprogress(1, "") ; }
+   virtual const char* getuserrules() { return "" ; }
+   virtual const char* getrulesdir() { return "Rules/" ; }
+} ;
+nullerrors nullerror ;
+#ifdef TIMING
+double start ;
+double timestamp() {
+   struct timeval tv ;
+   gettimeofday(&tv, 0) ;
+   double now = tv.tv_sec + 0.000001 * tv.tv_usec ;
+   double r = now - start ;
+   start = now ;
+   return r ;
+}
+#endif
+/*
+ *   This is a "lifeerrors" that we can use to test some edge
+ *   conditions.  In this case the only real thing we use
+ *   it for is to check rendering during a progress dialog.
+ */
+class verbosestatus : public lifeerrors {
+public:
+   verbosestatus() {}
+   virtual void fatal(const char *) {}
+   virtual void warning(const char *) {}
+   virtual void status(const char *s) {
+#ifdef TIMING
+      cout << timestamp() << " " << s << endl ;
+#endif
+   }
+   virtual void beginprogress(const char *) {}
+   virtual bool abortprogress(double, const char *) { return 0 ; }
+   virtual void endprogress() {}
+   virtual const char* getuserrules() { return "" ; }
+   virtual const char* getrulesdir() { return "Rules/" ; }
+} ;
+verbosestatus verbosestatus_instance ;
+char *filename ;
+lifealgo *imp = 0 ;
+struct options {
+  const char *shortopt ;
+  const char *longopt ;
+  const char *desc ;
+  char opttype ;
+  void *data ;
+} ;
+bigint maxgen = -1, inc = 0 ;
+int maxmem = 256 ;
+int hyper, render, autofit, quiet, popcount, progress ;
+int hashlife ;
+char *algoName = 0 ;
+int verbose ;
+int timeline ;
+int stepthresh, stepfactor ;
+char *liferule = 0 ;
+char *outfilename = 0 ;
+char *renderscale = (char *)"1" ;
+char *testscript = 0 ;
+int outputgzip, outputismc ;
+int numberoffset ; // where to insert file name numbers
+options options[] = {
+  { "-m", "--generation", "How far to run", 'I', &maxgen },
+  { "-i", "--stepsize", "Step size", 'I', &inc },
+  { "-M", "--maxmemory", "Max memory to use in megabytes", 'i', &maxmem },
+  { "-2", "--exponential", "Use exponentially increasing steps", 'b', &hyper },
+  { "-q", "--quiet", "Don't show population; twice, don't show anything", 'b', &quiet },
+  { "-r", "--rule", "Life rule to use", 's', &liferule },
+  { "-h", "--hashlife", "Use Hashlife algorithm", 'b', &hashlife },
+  { "-a", "--algorithm", "Select algorithm by name", 's', &algoName },
+  { "-o", "--output", "Output file (*.rle, *.mc, *.rle.gz, *.mc.gz)", 's',
+                                                               &outfilename },
+  { "-v", "--verbose", "Verbose", 'b', &verbose },
+  { "-t", "--timeline", "Use timeline", 'b', &timeline },
+  { "",   "--render", "Render (benchmarking)", 'b', &render },
+  { "",   "--progress", "Render during progress dialog (debugging)", 'b', &progress },
+  { "",   "--popcount", "Popcount (benchmarking)", 'b', &popcount },
+  { "",   "--scale", "Rendering scale", 's', &renderscale },
+//{ "",   "--stepthreshold", "Stepsize >= gencount/this (default 1)",
+//                                                          'i', &stepthresh },
+//{ "",   "--stepfactor", "How much to scale step by (default 2)",
+//                                                        'i', &stepfactor },
+  { "",   "--autofit", "Autofit before each render", 'b', &autofit },
+  { "",   "--exec", "Run testing script", 's', &testscript },
+  { 0, 0, 0, 0, 0 }
+} ;
+int endswith(const char *s, const char *suff) {
+   int off = (int)(strlen(s) - strlen(suff)) ;
+   if (off <= 0)
+      return 0 ;
+   s += off ;
+   while (*s)
+      if (tolower(*s++) != tolower(*suff++))
+         return 0 ;
+   numberoffset = off ;
+   return 1 ;
+}
+void usage(const char *s) {
+  fprintf(stderr, "Usage:  bgolly [options] patternfile\n") ;
+  for (int i=0; options[i].shortopt; i++)
+    fprintf(stderr, "%3s %-15s %s\n", options[i].shortopt, options[i].longopt,
+            options[i].desc) ;
+  if (s)
+    lifefatal(s) ;
+  exit(0) ;
+}
+#define STRINGIFY(ARG) STR2(ARG)
+#define STR2(ARG) #ARG
+#define MAXRLE 1000000000
+void writepat(int fc) {
+   char *thisfilename = outfilename ;
+   char tmpfilename[256] ;
+   if (fc >= 0) {
+      strcpy(tmpfilename, outfilename) ;
+      char *p = tmpfilename + numberoffset ;
+      *p++ = '-' ;
+      sprintf(p, "%d", fc) ;
+      p += strlen(p) ;
+      strcpy(p, outfilename + numberoffset) ;
+      thisfilename = tmpfilename ;
+   }
+   cerr << "(->" << thisfilename << flush ;
+   bigint t, l, b, r ;
+   imp->findedges(&t, &l, &b, &r) ;
+   // Hasegawa Sayuri: we keep the empty borders for bounded universe.
+   if (imp->gridwd) {
+       l = imp->gridleft;
+       r = imp->gridright;
+   }
+   if (imp->gridht) {
+       t = imp->gridtop;
+       b = imp->gridbottom;
+   }
+   // Hasegawa Sayuri: end of addition.
+   if (!outputismc && (t < -MAXRLE || l < -MAXRLE || b > MAXRLE || r > MAXRLE))
+      lifefatal("Pattern too large to write in RLE format") ;
+   const char *err = writepattern(thisfilename, *imp,
+                                  outputismc ? MC_format : RLE_format,
+                                  outputgzip ? gzip_compression : no_compression,
+                                  t.toint(), l.toint(), b.toint(), r.toint()) ;
+   if (err != 0)
+      lifewarning(err) ;
+   cerr << ")" << flush ;
+}
+const int MAXCMDLENGTH = 2048 ;
+struct cmdbase {
+   cmdbase(const char *cmdarg, const char *argsarg) {
+      verb = cmdarg ;
+      args = argsarg ;
+      next = list ;
+      list = this ;
+   }
+   const char *verb ;
+   const char *args ;
+   int iargs[4] ;
+   char *sarg ;
+   bigint barg ;
+   virtual void doit() {}
+   // for convenience, we put the generic loop here that takes a
+   // 4x bounding box and runs getnext on all y values until
+   // they are done.  Input is assumed to be a bounding box in the
+   // form minx miny maxx maxy
+   void runnextloop() {
+      int minx = iargs[0] ;
+      int miny = iargs[1] ;
+      int maxx = iargs[2] ;
+      int maxy = iargs[3] ;
+      int v ;
+      for (int y=miny; y<=maxy; y++) {
+         for (int x=minx; x<=maxx; x++) {
+            int dx = imp->nextcell(x, y, v) ;
+            if (dx < 0)
+               break ;
+            if (x > 0 && (x + dx) < 0)
+               break ;
+            x += dx ;
+            if (x > maxx)
+               break ;
+            nextloopinner(x, y) ;
+         }
+      }
+   }
+   virtual void nextloopinner(int, int) {}
+   int parseargs(const char *cmdargs) {
+      int iargn = 0 ;
+      char sbuf[MAXCMDLENGTH+2] ;
+      for (const char *rargs = args; *rargs; rargs++) {
+         while (*cmdargs && *cmdargs <= ' ')
+            cmdargs++ ;
+         if (*cmdargs == 0) {
+            lifewarning("Missing needed argument") ;
+            return 0 ;
+         }
+         switch (*rargs) {
+         case 'i':
+           if (sscanf(cmdargs, "%d", iargs+iargn) != 1) {
+             lifewarning("Missing needed integer argument") ;
+             return 0 ;
+           }
+           iargn++ ;
+           break ;
+         case 'b':
+           {
+              int i = 0 ;
+              for (i=0; cmdargs[i] > ' '; i++)
+                 sbuf[i] = cmdargs[i] ;
+              sbuf[i] = 0 ;
+              barg = bigint(sbuf) ;
+           }
+           break ;
+         case 's':
+           if (sscanf(cmdargs, "%s", sbuf) != 1) {
+             lifewarning("Missing needed string argument") ;
+             return 0 ;
+           }
+           sarg = strdup(sbuf) ;
+           break ;
+         default:
+           lifefatal("Internal error in parseargs") ;
+         }
+         while (*cmdargs && *cmdargs > ' ')
+           cmdargs++ ;
+      }
+      return 1 ;
+   }
+   static void docmd(const char *cmdline) {
+      for (cmdbase *cmd=list; cmd; cmd = cmd->next)
+         if (strncmp(cmdline, cmd->verb, strlen(cmd->verb)) == 0 &&
+             cmdline[strlen(cmd->verb)] <= ' ') {
+            if (cmd->parseargs(cmdline+strlen(cmd->verb))) {
+               cmd->doit() ;
+            }
+            return ;
+         }
+      lifewarning("Didn't understand command") ;
+   }
+   cmdbase *next ;
+   virtual ~cmdbase() {}
+   static cmdbase *list ;
+} ;
+cmdbase *cmdbase::list = 0 ;
+struct loadcmd : public cmdbase {
+   loadcmd() : cmdbase("load", "s") {}
+   virtual void doit() {
+     const char *err = readpattern(sarg, *imp) ;
+     if (err != 0)
+       lifewarning(err) ;
+   }
+} load_inst ;
+struct stepcmd : public cmdbase {
+   stepcmd() : cmdbase("step", "b") {}
+   virtual void doit() {
+      imp->setIncrement(barg) ;
+      imp->step() ;
+      cout << imp->getGeneration().tostring() << ": " ;
+      cout << imp->getPopulation().tostring() << endl ;
+   }
+} step_inst ;
+struct showcmd : public cmdbase {
+   showcmd() : cmdbase("show", "") {}
+   virtual void doit() {
+      cout << imp->getGeneration().tostring() << ": " ;
+      cout << imp->getPopulation().tostring() << endl ;
+   }
+} show_inst ;
+struct quitcmd : public cmdbase {
+   quitcmd() : cmdbase("quit", "") {}
+   virtual void doit() {
+      cout << "Buh-bye!" << endl ;
+      exit(10) ;
+   }
+} quit_inst ;
+struct setcmd : public cmdbase {
+   setcmd() : cmdbase("set", "ii") {}
+   virtual void doit() {
+      imp->setcell(iargs[0], iargs[1], 1) ;
+   }
+} set_inst ;
+struct unsetcmd : public cmdbase {
+   unsetcmd() : cmdbase("unset", "ii") {}
+   virtual void doit() {
+      imp->setcell(iargs[0], iargs[1], 0) ;
+   }
+} unset_inst ;
+struct helpcmd : public cmdbase {
+   helpcmd() : cmdbase("help", "") {}
+   virtual void doit() {
+      for (cmdbase *cmd=list; cmd; cmd = cmd->next)
+         cout << cmd->verb << " " << cmd->args << endl ;
+   }
+} help_inst ;
+struct getcmd : public cmdbase {
+   getcmd() : cmdbase("get", "ii") {}
+   virtual void doit() {
+     cout << "At " << iargs[0] << "," << iargs[1] << " -> " <<
+        imp->getcell(iargs[0], iargs[1]) << endl ;
+   }
+} get_inst ;
+struct getnextcmd : public cmdbase {
+   getnextcmd() : cmdbase("getnext", "ii") {}
+   virtual void doit() {
+     int v ;
+     cout << "At " << iargs[0] << "," << iargs[1] << " next is " <<
+        imp->nextcell(iargs[0], iargs[1], v) << endl ;
+   }
+} getnext_inst ;
+vector<pair<int, int> > cutbuf ;
+struct copycmd : public cmdbase {
+   copycmd() : cmdbase("copy", "iiii") {}
+   virtual void nextloopinner(int x, int y) {
+      cutbuf.push_back(make_pair(x-iargs[0], y-iargs[1])) ;
+   }
+   virtual void doit() {
+      cutbuf.clear() ;
+      runnextloop() ;
+      cout << cutbuf.size() << " pixels copied." << endl ;
+   }
+} copy_inst ;
+struct cutcmd : public cmdbase {
+   cutcmd() : cmdbase("cut", "iiii") {}
+   virtual void nextloopinner(int x, int y) {
+      cutbuf.push_back(make_pair(x-iargs[0], y-iargs[1])) ;
+      imp->setcell(x, y, 0) ;
+   }
+   virtual void doit() {
+      cutbuf.clear() ;
+      runnextloop() ;
+      cout << cutbuf.size() << " pixels cut." << endl ;
+   }
+} cut_inst ;
+// this paste only sets cells, never clears cells
+struct pastecmd : public cmdbase {
+   pastecmd() : cmdbase("paste", "ii") {}
+   virtual void doit() {
+      for (unsigned int i=0; i<cutbuf.size(); i++)
+         imp->setcell(cutbuf[i].first, cutbuf[i].second, 1) ;
+      cout << cutbuf.size() << " pixels pasted." << endl ;
+   }
+} paste_inst ;
+struct showcutcmd : public cmdbase {
+   showcutcmd() : cmdbase("showcut", "") {}
+   virtual void doit() {
+      for (unsigned int i=0; i<cutbuf.size(); i++)
+         cout << cutbuf[i].first << " " << cutbuf[i].second << endl ;
+   }
+} showcut_inst ;
+lifealgo *createUniverse() {
+   if (algoName == 0) {
+     if (hashlife)
+       algoName = (char *)"HashLife" ;
+     else
+       algoName = (char *)"QuickLife" ;
+   } else if (strcmp(algoName, "RuleTable") == 0 ||
+              strcmp(algoName, "RuleTree") == 0) {
+       // RuleTable and RuleTree algos have been replaced by RuleLoader
+       algoName = (char *)"RuleLoader" ;
+   }
+   staticAlgoInfo *ai = staticAlgoInfo::byName(algoName) ;
+   if (ai == 0)
+      lifefatal("No such algorithm") ;
+   lifealgo *imp = (ai->creator)() ;
+   if (imp == 0)
+      lifefatal("Could not create universe") ;
+   imp->setMaxMemory(maxmem) ;
+   return imp ;
+}
+struct newcmd : public cmdbase {
+   newcmd() : cmdbase("new", "") {}
+   virtual void doit() {
+     if (imp != 0)
+        delete imp ;
+     imp = createUniverse() ;
+   }
+} new_inst ;
+struct sethashingcmd : public cmdbase {
+   sethashingcmd() : cmdbase("sethashing", "i") {}
+   virtual void doit() {
+      hashlife = iargs[0] ;
+   }
+} sethashing_inst ;
+struct setmaxmemcmd : public cmdbase {
+   setmaxmemcmd() : cmdbase("setmaxmem", "i") {}
+   virtual void doit() {
+      maxmem = iargs[0] ;
+   }
+} setmaxmem_inst ;
+struct setalgocmd : public cmdbase {
+   setalgocmd() : cmdbase("setalgo", "s") {}
+   virtual void doit() {
+      algoName = sarg ;
+   }
+} setalgocmd_inst ;
+struct edgescmd : public cmdbase {
+   edgescmd() : cmdbase("edges", "") {}
+   virtual void doit() {
+      bigint t, l, b, r ;
+      imp->findedges(&t, &l, &b, &r) ;
+      cout << "Bounding box " << l.tostring() ;
+      cout << " " << t.tostring() ;
+      cout << " .. " << r.tostring() ;
+      cout << " " << b.tostring() << endl ;
+   }
+} edges_inst ;
+bool nullerrors::abortprogress(double, const char *) {
+   imp->draw(viewport, renderer) ;
+   return 0 ;
+}
+void runtestscript(const char *testscript) {
+   FILE *cmdfile = 0 ;
+   if (strcmp(testscript, "-") != 0)
+      cmdfile = fopen(testscript, "r") ;
+   else
+      cmdfile = stdin ;
+   char cmdline[MAXCMDLENGTH + 10] ;
+   if (cmdfile == 0)
+      lifefatal("Cannot open testscript") ;
+   for (;;) {
+     cerr << flush ;
+     if (cmdfile == stdin)
+       cout << "bgolly> " << flush ;
+     else
+       cout << flush ;
+     if (fgets(cmdline, MAXCMDLENGTH, cmdfile) == 0)
+        break ;
+     cmdbase::docmd(cmdline) ;
+   }
+   exit(0) ;
+}
+// Hasegawa Sayuri: adapted from MainFrame::{ClearRect,DeleteBorderCells} from
+// gui-wx/wxcontrol.cpp.
+void ClearRect(int top, int left, int bottom, int right)
+{
+    int cx, cy, v;
+    for ( cy = top; cy <= bottom; cy++ ) {
+        for ( cx = left; cx <= right; cx++ ) {
+            int skip = imp->nextcell(cx, cy, v);
+            if (skip + cx > right)
+                skip = -1;           // pretend we found no more live cells
+            if (skip >= 0) {
+                // found next live cell so delete it
+                cx += skip;
+                imp->setcell(cx, cy, 0);
+            } else {
+                cx = right + 1;     // done this row
+            }
+        }
+    }
+}
+bool deletebordercells()
+{
+    // no need to do anything if there is no pattern
+    if (imp->isEmpty()) return true;
+    
+    int gwd = imp->gridwd;
+    int ght = imp->gridht;
+    
+    // need to find pattern edges because pattern may have expanded beyond grid
+    // (typically by 2 cells, but could be more if rule allows births in empty space)
+    bigint top, left, bottom, right;
+    imp->findedges(&top, &left, &bottom, &right);
+
+    // no need to do anything if grid encloses entire pattern
+    if ( (gwd == 0 || (imp->gridleft <= left && imp->gridright >= right)) &&
+        (ght == 0 || (imp->gridtop <= top && imp->gridbottom >= bottom)) ) {
+        return true;
+    }
+    
+    // set pattern edges
+    int pl = left.toint();
+    int pt = top.toint();
+    int pr = right.toint();      
+    int pb = bottom.toint();
+    
+    // set grid edges
+    int gl = imp->gridleft.toint();
+    int gt = imp->gridtop.toint();
+    int gr = imp->gridright.toint();
+    int gb = imp->gridbottom.toint();
+    
+    if (ght > 0 && pt < gt) {
+        // delete live cells above grid
+        ClearRect(pt, pl, gt-1, pr);
+        pt = gt; // reduce size of rect below
+    }
+    
+    if (ght > 0 && pb > gb) {
+        // delete live cells below grid
+        ClearRect(gb+1, pl, pb, pr);
+        pb = gb; // reduce size of rect below
+    }
+    
+    if (gwd > 0 && pl < gl) {
+        // delete live cells left of grid
+        ClearRect(pt, pl, pb, gl-1);
+    }
+    
+    if (gwd > 0 && pr > gr) {
+        // delete live cells right of grid
+        ClearRect(pt, gr+1, pb, pr);
+    }
+    
+    imp->endofpattern();
+    return true;
+}
+// Hasegawa Sayuri: end of addition.
+int main(int argc, char *argv[]) {
+   cout << 
+    "This is bgolly " STRINGIFY(VERSION) " Copyright 2012 The Golly Gang." 
+                                                            << endl << flush ;
+   qlifealgo::doInitializeAlgoInfo(staticAlgoInfo::tick()) ;
+   hlifealgo::doInitializeAlgoInfo(staticAlgoInfo::tick()) ;
+   generationsalgo::doInitializeAlgoInfo(staticAlgoInfo::tick()) ;
+   jvnalgo::doInitializeAlgoInfo(staticAlgoInfo::tick()) ;
+   ruleloaderalgo::doInitializeAlgoInfo(staticAlgoInfo::tick()) ;
+   while (argc > 1 && argv[1][0] == '-') {
+      argc-- ;
+      argv++ ;
+      char *opt = argv[0] ;
+      int hit = 0 ;
+      for (int i=0; options[i].shortopt; i++) {
+        if (strcmp(opt, options[i].shortopt) == 0 ||
+            strcmp(opt, options[i].longopt) == 0) {
+          switch (options[i].opttype) {
+case 'i':
+             if (argc < 2)
+                lifefatal("Bad option argument") ;
+             *(int *)options[i].data = atol(argv[1]) ;
+             argc-- ;
+             argv++ ;
+             break ;
+case 'I':
+             if (argc < 2)
+                lifefatal("Bad option argument") ;
+             *(bigint *)options[i].data = bigint(argv[1]) ;
+             argc-- ;
+             argv++ ;
+             break ;
+case 'b':
+             (*(int *)options[i].data) += 1 ;
+             break ;
+case 's':
+             if (argc < 2)
+                lifefatal("Bad option argument") ;
+             *(char **)options[i].data = argv[1] ;
+             argc-- ;
+             argv++ ;
+             break ;
+          }
+          hit++ ;
+          break ;
+        }
+      }
+      if (!hit)
+        usage("Bad option given") ;
+   }
+   if (argc < 2 && !testscript)
+     usage("No pattern argument given") ;
+   if (argc > 2)
+     usage("Extra stuff after pattern argument") ;
+   if (outfilename) {
+      if (endswith(outfilename, ".rle")) {
+      } else if (endswith(outfilename, ".mc")) {
+         outputismc = 1 ;
+#ifdef ZLIB
+      } else if (endswith(outfilename, ".rle.gz")) {
+         outputgzip = 1 ;
+      } else if (endswith(outfilename, ".mc.gz")) {
+         outputismc = 1 ;
+         outputgzip = 1 ;
+#endif
+      } else {
+         lifefatal("Output filename must end with .rle or .mc.") ;
+      }
+      if (strlen(outfilename) > 200)
+         lifefatal("Output filename too long") ;
+   }
+   if (timeline && hyper)
+      lifefatal("Cannot use both timeline and hyperthreading") ;
+   imp = createUniverse() ;
+   if (progress)
+     lifeerrors::seterrorhandler(&nullerror) ;
+   else if (verbose) {
+     lifeerrors::seterrorhandler(&verbosestatus_instance) ;
+     hlifealgo::setVerbose(1) ;
+   }
+   imp->setMaxMemory(maxmem) ;
+#ifdef TIMING
+   timestamp() ;
+#endif
+   if (testscript) {
+     if (argc > 1) {
+       filename = argv[1] ;
+       const char *err = readpattern(argv[1], *imp) ;
+       if (err)
+         lifefatal(err) ;
+     }
+     runtestscript(testscript) ;
+   }
+   filename = argv[1] ;
+   const char *err = readpattern(argv[1], *imp) ;
+   if (err)
+      lifefatal(err) ;
+   if (liferule)
+      imp->setrule(liferule) ;
+   if (inc != 0)
+      imp->setIncrement(inc) ;
+   if (timeline) {
+      int lowbit = inc.lowbitset() ;
+      bigint t = 1 ;
+      for (int i=0; i<lowbit; i++)
+         t.mul_smallint(2) ;
+      if (t != inc)
+         lifefatal("Bad increment for timeline") ;
+      imp->startrecording(2, lowbit) ;
+   }
+   int fc = 0 ;
+   for (;;) {
+      if (quiet < 2) {
+         cout << imp->getGeneration().tostring() ;
+         if (!quiet)
+           cout << ": " << imp->getPopulation().tostring() << endl ;
+         else
+           cout << endl ;
+      }
+      if (popcount)
+         imp->getPopulation() ;
+      if (autofit)
+        imp->fit(viewport, 1) ;
+      if (render)
+        imp->draw(viewport, renderer) ;
+      if (maxgen >= 0 && imp->getGeneration() >= maxgen)
+         break ;
+      // Hasegawa Sayuri: we keep an increment to 1 for bounded grids
+      //if (!hyper && maxgen > 0 && inc == 0) {
+      if (!hyper && (imp->gridwd == 0 || imp->gridht == 0) && maxgen > 0 && inc == 0) {
+      // Hasegawa Sayuri: end of change.
+         bigint diff = maxgen ;
+         diff -= imp->getGeneration() ;
+         int bs = diff.lowbitset() ;
+         diff = 1 ;
+         diff <<= bs ;
+         imp->setIncrement(diff) ;
+      }
+      imp->step() ;
+      // Hasegawa Sayuri: well, Golly creates an illusion of bounded grids by
+      // removing border cells repeatedly. but why only the wx version supports
+      // this facility?!
+      if (imp->gridwd > 0 && imp->gridht > 0) deletebordercells();
+      // Hasegawa Sayuri: end of addition.
+      if (maxgen < 0 && outfilename != 0)
+         writepat(fc++) ;
+      if (timeline && imp->getframecount() + 2 > MAX_FRAME_COUNT)
+         imp->pruneframes() ;
+      if (hyper)
+         imp->setIncrement(imp->getGeneration()) ;
+   }
+   if (maxgen >= 0 && outfilename != 0)
+      writepat(-1) ;
+   exit(0) ;
+}

golly/gollybase/bigint.cpp

+                        /*** /
+
+This file is part of Golly, a Game of Life Simulator.
+Copyright (C) 2012 Andrew Trevorrow and Tomas Rokicki.
+
+This program is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License
+as published by the Free Software Foundation; either version 2
+of the License, or (at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+ Web site:  http://sourceforge.net/projects/golly
+ Authors:   rokicki@gmail.com  andrew@trevorrow.com
+
+                        / ***/
+#include "bigint.h"
+#include <cstdlib>
+#include <string.h>
+#include <iostream>
+#include <cmath>
+#include <limits.h>
+#include "util.h"
+#undef SLOWCHECK
+using namespace std ;
+/**
+ *   Static data.
+ */
+static const int MAX_SIMPLE = 0x3fffffff ;
+static const int MIN_SIMPLE = -0x40000000 ;
+char *bigint::printbuf ;
+int *bigint::work ;
+int bigint::printbuflen ;
+int bigint::workarrlen ;
+char bigint::sepchar = ',' ;
+int bigint::sepcount = 3 ;
+/**
+ *   Routines.
+ */
+bigint::bigint() {
+   v.i = 1 ;
+}
+bigint::bigint(int i) {
+   fromint(i) ;
+}
+bigint::bigint(G_INT64 i) {
+   if (i <= INT_MAX && i >= INT_MIN)
+      fromint((int)i) ;
+   else {
+      v.i = 0 ;
+      vectorize(0) ;
+      v.p[0] = 3 ;
+      v.p[1] = (int)(i & 0x7fffffff) ;
+      v.p[2] = (int)((i >> 31) & 0x7fffffff) ;
+      v.p[3] = 0 ;
+      ripple((int)(i >> 62), 3) ;
+   }
+}
+// we can parse ####, 2^###, -#####
+// AKT: we ignore all non-digits (except for leading '-')
+// so we can parse strings like "1,234" or "+1.234";
+// it is up to caller to impose smarter restrictions
+bigint::bigint(const char *s) {
+   if (*s == '2' && s[1] == '^') {
+      long x = atol(s+2) ;
+      if (x < 31)
+         fromint(1 << x) ;
+      else {
+         int sz = 2 + (x + 1) / 31 ;
+         int asz = sz ;
+         while (asz & (asz - 1))
+            asz &= asz - 1 ;
+         asz *= 2 ;
+         v.p = new int[asz] ;
+         v.p[0] = sz ;
+         for (int i=1; i<=sz; i++)
+            v.p[i] = 0 ;
+         v.p[sz-1] = 1 << (x % 31) ;
+      }
+   } else {
+      int neg = 0 ;
+      if (*s == '-') {
+         neg = 1 ;
+         s++ ;
+      }
+      fromint(0) ;
+      while (*s) {
+         // AKT: was *s != sepchar
+         if (*s >= '0' && *s <= '9') {
+            mul_smallint(10) ;
+            if (neg)
+               add_smallint('0'-*s) ;
+            else
+               add_smallint(*s-'0') ;
+         }
+         s++ ;
+      }
+   }
+}
+static int *copyarr(int *p) {
+   int sz = *p ;
+   while (sz & (sz - 1))
+      sz &= sz - 1 ;
+   sz *= 2 ;
+   int *r = new int[sz] ;
+   memcpy(r, p, sizeof(int) * (p[0] + 1)) ;
+#ifdef SLOWCHECK
+   for (int i=p[0]+1; i<sz; i++)
+      r[i] = 0xdeadbeef ;
+#endif
+   return r ;
+}
+bigint::bigint(const bigint &a) {
+   if (a.v.i & 1)
+      v.i = a.v.i ;
+   else
+      v.p = copyarr(a.v.p) ;
+}
+/**
+ *   We special-case the p=0 case so we can "initialize" bigint memory
+ *   with zero.
+ */
+bigint &bigint::operator=(const bigint &b) {
+   if (&b != this) {
+      if (0 == (v.i & 1))
+         if (v.p)
+            delete [] v.p ;
+      if (b.v.i & 1)
+         v.i = b.v.i ;
+      else
+         v.p = copyarr(b.v.p) ;
+   }
+   return *this ;
+}
+bigint::~bigint() {
+   if (0 == (v.i & 1))
+      delete [] v.p ;
+}
+const char *bigint::tostring(char sep) const {
+   int lenreq = 32 ;
+   if ((v.i & 1) == 0)
+      lenreq = size() * 32 ;
+   if (lenreq > printbuflen) {
+     if (printbuf)
+         delete [] printbuf ;
+      printbuf = new char[2 * lenreq] ;
+      printbuflen = 2 * lenreq ;
+   }
+   int sz = 1 ;
+   if (0 == (v.i & 1))
+      sz = size() ;
+   ensurework(sz) ;
+   int neg = sign() < 0 ;
+   if (v.i & 1) {
+      if (neg)
+         work[0] = -(v.i >> 1) ;
+      else
+         work[0] = v.i >> 1 ;
+   } else {
+      if (neg) {
+         int carry = 1 ;
+         for (int i=0; i+1<sz; i++) {
+            int c = carry + (v.p[i+1] ^ 0x7fffffff) ;
+            work[i] = c & 0x7fffffff ;
+            carry = (c >> 31) & 1 ;
+         }
+         work[sz-1] = carry + ~v.p[sz] ;
+      } else {
+         for (int i=0; i<sz; i++)
+            work[i] = v.p[i+1] ;
+      }
+   }
+   char *p = printbuf ;
+   const int bigradix = 1000000000 ; // 9 digits at a time
+   for (;;) {
+      int allbits = 0 ;
+      int carry = 0 ;
+      int i;
+      for (i=sz-1; i>=0; i--) {
+         G_INT64 c = carry * G_MAKEINT64(0x80000000) + work[i] ;
+         carry = (int)(c % bigradix) ;
+         work[i] = (int)(c / bigradix) ;
+         allbits |= work[i] ;
+      }
+      for (i=0; i<9; i++) { // put the nine digits in
+         *p++ = (char)(carry % 10 + '0') ;
+         carry /= 10 ;
+      }
+      if (allbits == 0)
+         break ;
+   }
+   while (p > printbuf + 1 && *(p-1) == '0')
+      p-- ;
+   char *r = p ;
+   if (neg)
+      *r++ = '-' ;
+   for (int i=(int)(p-printbuf-1); i>=0; i--) {
+      *r++ = printbuf[i] ;
+      if (i && sep && (i % sepcount == 0))
+         *r++ = sep ;
+   }
+   *r++ = 0 ;
+   return p ;
+}
+void bigint::grow(int osz, int nsz) {
+   int bdiffs = osz ^ nsz ;
+   if (bdiffs > osz) {
+      while (bdiffs & (bdiffs - 1))
+         bdiffs &= bdiffs - 1 ;
+      int *nv = new int[2*bdiffs] ;
+      for (int i=0; i<=osz; i++)
+         nv[i] = v.p[i] ;
+#ifdef SLOWCHECK
+      for (int i=osz+1; i<2*bdiffs; i++)
+         nv[i] = 0xdeadbeef ;
+#endif
+      delete [] v.p ;
+      v.p = nv ;
+   }
+   int av = v.p[osz] ;
+   while (osz < nsz) {
+      v.p[osz] = av & 0x7fffffff ;
+      osz++ ;
+   }
+   v.p[nsz] = av ;
+   v.p[0] = nsz ;
+}
+bigint& bigint::operator+=(const bigint &a) {
+   if (a.v.i & 1)
+      add_smallint(a.v.i >> 1) ;
+   else {
+      if (v.i & 1)
+         vectorize(v.i >> 1) ;
+      ripple(a, 0) ;
+   }
+   return *this ;
+}
+bigint& bigint::operator-=(const bigint &a) {
+   if (a.v.i & 1)
+      add_smallint(-(a.v.i >> 1)) ;
+   else {
+      if (v.i & 1)
+         vectorize(v.i >> 1) ;
+      ripplesub(a, 1) ;
+   }