Commits

Seonghoon Kang committed 49c5bfd

snapshot

  • Participants
  • Parent commits 48e8533

Comments (0)

Files changed (7)

 data
 analysis
 output
+archive
 result.txt
 result.7z
 code.tar.gz
 bgolly
 dayandnight
+diamoeba
 dumper
 split
 verifier
 	make bgolly
 	./solve.sh
 
-result.txt: ${TESTCASES:%=output/output%.txt}
-	cat $^ > $@
+result.txt: archive/output*.*.txt.xz
+	@for i in ${TESTCASES}; do \
+		xzcat $$(ls archive/output$$i.*.txt.xz | awk -F. 'BEGIN{s=9e9}{if(s>$$(NF-2)){s=$$(NF-2);t=$$0}}END{print t}'); \
+	done > $@
 
 result.7z: result.txt
 	rm -f $@
 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
+		dayandnight.cpp diamoeba.cpp
 	rm -f $@
 	tar czvf $@ $^
 
 
 verify: verifier
 	make bgolly
-	@for ((i=0;i<9;++i)); do echo VERIFYING TESTCASE $$i >&2; ./verify.sh $$i; echo >&2; done
+	@for i in ${TESTCASES}; 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

File diamoeba.cpp

+// Written by Hasegawa Sayuri
+//
+// Special casing for Diamoeba (B35678/S5678) rule. It is notable because
+// it does not contain S4 (or lower) rule, so we can just drop every cells
+// which coordinates (x,y) satisfy x + y = k (mod DIVISOR) for certain k and
+// DIVISOR. Given the enough density (>>1/2) this will make the group of
+// cells disintegrate by themselves.
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <set>
+#include <map>
+#include <vector>
+#include <utility>
+#include "gol.h"
+using namespace std;
+
+static const int DIVISOR = 4; // experimentally determined
+
+int main(int argc, char **argv) {
+	if (argc < 2) {
+		fprintf(stderr, "Usage: %s analysis/inputX-diamoeba.rle <type> < data/inputX.txt > output/outputX-first.txt\n", argv[0]);
+		return 1;
+	}
+
+	populate(stdin);
+
+	int type = atoi(argv[2]);
+	int sub = (type >= DIVISOR);
+	int mod = (type % DIVISOR);
+	fprintf(stderr, "Diamoeba preprocessing: removing cells (sub=%d, mod=%d)\n", sub, mod);
+	for (set<point>::iterator it = itable.begin(); it != itable.end(); ) {
+		int x = it->first, y = it->second;
+		if ((sub ? x + DIVISOR - y % DIVISOR : x + y) % DIVISOR == mod) {
+			printf("SET %d %d\n", x, y);
+			set<point>::iterator iit = it++;
+			itable.erase(iit);
+		} else {
+			++it;
+		}
+	}
+
+	FILE *fp = fopen(argv[1], "w");
+	write_rle(fp, itable);
+	fclose(fp);
+
+	return 0;
+}
+
 1000000 1000000 3252960 1 2 B35678/S5678
 increasing indefinitely
 
+for ((i=0;i<8;++i)); do
+	./diamoeba analysis/input4-diamoeba$i.rle $i < data/input4.txt | wc -l
+	./generate.sh 3000 analysis/input4-diamoeba$i.rle analysis/input4-diamoeba-gen3000.rle analysis/population4-diamoeba$i.csv
+echo least cost:
+	./leastcost.sh 1 2 < analysis/population4-diamoeba$i.csv
+done
+
 #5
 1000000 1000000 5167602 2 4 B3/S23
 population 478954 at generation 5120
 ----
 
 v = map(int,'''
+4 216 2245771 8178420 1020352 499250 436444 34020 5002855
+''' '''
+4 166 2245528 8178420 701427 499250 436444 24392 5001495
+4 166 2245636 9348030 962107 582918 587638 24392 5012535
 4 216 2245771 8178420 2820604 499250 436444 34020 5002855
-''' '''
-4 200 2245528 8178420 701427 499250 436448 26112 5001495
 4 316 2245528 12149490 701427 969414 1024548 86980 5001495
-4 232 3571938 168133350 1015963 858694 1232940 31622 10893045
 '''.split())
 for k in xrange(len(v)//9): u = [100000.*min(z)**2/z[k]**2 for z in zip(*[v[i:i+9] for i in xrange(0,len(v),9)])]; print '%6.0f | %s' % (sum(u), ' '.join('%6.0f'%j for j in u))
 
 	# use patternize.py for inspection on other GoL software.
 	# see elimrules.txt for manually prepared elimination rules.
 
-	echo SOLVING TESTCASE $1 WITH ELIMCOMPS >&2
-	if [ "$2" == "" ]; then
-		TARGET=data/input$1.rle
-		PATTERNFILE=analysis/pattern$1.txt
-		POSITIONFILE=analysis/position$1.txt
+	CASE=$1
+	INITNEXTS=$2
+	CS=$3
+	CN=$4
+
+	echo SOLVING TESTCASE $CASE WITH ELIMCOMPS >&2
+	if [ "$INITNEXTS" == "" ]; then
+		TARGET=data/input$CASE.rle
+		PATTERNFILE=analysis/pattern$CASE.txt
+		POSITIONFILE=analysis/position$CASE.txt
 		make $PATTERNFILE $POSITIONFILE 1>&2 || exit 1
 	else
-		TARGET=analysis/input$1-gen$2.rle
+		TARGET=analysis/input$CASE-gen$INITNEXTS.rle
 		if [ \! -f "$TARGET" ]; then
-			./generate.sh $2 data/input$1.rle $TARGET 1>&2
+			./generate.sh $INITNEXTS data/input$CASE.rle $TARGET 1>&2
 			echo >&2
 		fi
-		PATTERNFILE=analysis/pattern$1-gen$2.txt
-		POSITIONFILE=analysis/position$1-gen$2.txt
+		PATTERNFILE=analysis/pattern$CASE-gen$INITNEXTS.txt
+		POSITIONFILE=analysis/position$CASE-gen$INITNEXTS.txt
 		if [ \! -f "$PATTERNFILE" -o \! -f "$POSITIONFILE" ]; then
 			make split
-			$PYTHON fromrle.py $3 $4 < $TARGET | ./split $PATTERNFILE $POSITIONFILE
+			$PYTHON fromrle.py $GEN $POP < $TARGET | ./split $PATTERNFILE $POSITIONFILE
 		fi
 	fi
 	TEMPFILE=/tmp/$$-output.txt
 	TEMPFILE2=/tmp/$$-output-prepend.txt
 	trap "rm -f $TEMPFILE $TEMPFILE2" INT TERM EXIT
-	if [ "$2" \!= "" ]; then
-		for ((i=0;i<$2;++i)); do
+	if [ "$INITNEXTS" \!= "" ]; then
+		for ((i=0;i<$INITNEXTS;++i)); do
 			echo NEXT
 		done
 	fi > $TEMPFILE2
 	$PYTHON elimcomps.py $PATTERNFILE $POSITIONFILE | $PYTHON prepend.py $TEMPFILE2 > $TEMPFILE || exit 1
 	trap - INT TERM EXIT
 	rm -f $TEMPFILE2
-	mv $TEMPFILE output/output$1.txt
+	mv $TEMPFILE output/output$CASE.txt
 	echo >&2
 }
 
 	#     analysis/population5.csv
 	# ./leastcost.sh 2 4 < analysis/population5.csv
 
-	echo SOLVING TESTCASE $1 WITH CHERRYPICK >&2
-	TARGET=analysis/input$1-gen$2.rle
+	CASE=$1
+	GEN=$2
+	POP=$3
+
+	echo SOLVING TESTCASE $CASE WITH CHERRYPICK >&2
+	TARGET=analysis/input$CASE-gen$GEN.rle
 	if [ \! -f "$TARGET" ]; then
-		./generate.sh $2 data/input$1.rle $TARGET 1>&2
+		./generate.sh $GEN data/input$CASE.rle $TARGET 1>&2
 		echo >&2
 	fi
 	TEMPFILE=/tmp/$$-output.txt
 	trap "rm -f $TEMPFILE" INT TERM EXIT
-	$PYTHON cherrypick.py $2 $3 < $TARGET > $TEMPFILE || exit 1
+	$PYTHON cherrypick.py $GEN $POP < $TARGET > $TEMPFILE || exit 1
 	trap - INT TERM EXIT
-	mv $TEMPFILE output/output$1.txt
+	mv $TEMPFILE output/output$CASE.txt
 	echo >&2
 }
 
-cherrypick_dayandnight() {
-	# similar to CHERRYPICK but uses a special preprocessing for
-	# Day & Night rule. see dayandnight.cpp for details.
+cherrypick_preproc() {
+	# similar to CHERRYPICK but uses a special preprocessing for better
+	# optimization. see dayandnight.cpp and diamoeba.cpp for details.
 	#
-	# the value for test case #3 is determined as follows:
+	# for example, the value for test case #3 is determined as follows:
 	#
 	# make dayandnight
 	# ./dayandnight analysis/input3-dayandnight.rle < data/input3.txt > /dev/null
 	#     analysis/input3-dayandnight-gen80000.rle analysis/population3-dayandnight.csv
 	# ./leastcost.sh 30 60 < analysis/population3-dayandnight.csv
 
-	echo SOLVING TESTCASE $1 WITH CHERRYPICK_DAYANDNIGHT >&2
-	PREPROCESSED=analysis/input$1-dayandnight.rle
-	PART1=output/output$1-part1.txt
-	TARGET=analysis/input$1-dayandnight-gen$2.rle
+	CASE=$1
+	GEN=$2
+	POP=$3
+	PREPROCESSOR=$4
+	SUFFIX=-$PREPROCESSOR$5
+	shift 4
+
+	echo SOLVING TESTCASE $CASE WITH CHERRYPICK_PREPROC >&2
+	PREPROCESSED=analysis/input$CASE$SUFFIX.rle
+	PART1=output/output$CASE-part1.txt
+	TARGET=analysis/input$CASE$SUFFIX-gen$GEN.rle
 	if [ \! -f "$PART1" -o \( \! -f "$TARGET" -a \! -f "$PREPROCESSED" \) ]; then
-		make dayandnight
-		./dayandnight "$PREPROCESSED" < data/input$1.txt > "$PART1"
+		make $PREPROCESSOR
+		./$PREPROCESSOR "$PREPROCESSED" "$@" < data/input$CASE.txt > "$PART1"
 	fi
 	if [ \! -f "$TARGET" ]; then
-		./generate.sh $2 $PREPROCESSED $TARGET 1>&2
+		./generate.sh $GEN $PREPROCESSED $TARGET 1>&2
 		echo >&2
 	fi
 	TEMPFILE=/tmp/$$-output.txt
 	trap "rm -f $TEMPFILE" INT TERM EXIT
-	$PYTHON cherrypick.py $2 $3 < $TARGET | $PYTHON prepend.py $PART1 > $TEMPFILE || exit 1
+	$PYTHON cherrypick.py $GEN $POP < $TARGET | $PYTHON prepend.py $PART1 > $TEMPFILE || exit 1
 	trap - INT TERM EXIT
-	mv $TEMPFILE output/output$1.txt
+	mv $TEMPFILE output/output$CASE.txt
 	echo >&2
 }
 
 shouldrun 0 && elimcomps 0
 shouldrun 1 && elimcomps 1
 shouldrun 2 && elimcomps 2
-#shouldrun 3 && cherrypick 3 41561 6629443
-shouldrun 3 && cherrypick_dayandnight 3 67114 146947
-shouldrun 4 && bruteforce 4 3252960
+shouldrun 3 && cherrypick_preproc 3 67114 146947 dayandnight
+shouldrun 4 && cherrypick_preproc 4 1373 207274 diamoeba 0
 shouldrun 5 && cherrypick 5 5414 470856
-#shouldrun 6 && bruteforce 6 3025056
 shouldrun 6 && elimcomps 6 5120 2 4
-#shouldrun 7 && cherrypick 7 282 43029
 shouldrun 7 && elimcomps 7 282 2 4
 shouldrun 8 && elimcomps 8
 exit 0

File verifier.cpp

 
 int main(int argc, char **argv) {
 	if (argc < 3) {
-		fprintf(stderr, "Usage: %s data/outputX.txt data/outputX-prev.txt < data/inputX.txt\n", argv[0]);
+		fprintf(stderr, "Usage: %s data/outputX.txt data/outputX-prev.txt [data/outputX.txt.cost] < data/inputX.txt\n", argv[0]);
 		return 1;
 	}
 
 		fprintf(stderr, "okay, check passed. cost=%d\n", cost);
 	}
 	fclose(fp);
+
+	if (argc > 3) {
+		fp = fopen(argv[3], "w");
+		if (fp == NULL) {
+			fprintf(stderr, "Fatal Error: failed to write to %s\n", argv[3]);
+			return 2;
+		}
+		fprintf(fp, "%d\n", cost);
+		fclose(fp);
+	}
+
 	return 0;
 }
 
 	exit 1
 fi
 
-make verifier > /dev/null && \
-./verifier output/output$1.txt output/output$1-prev.txt < data/input$1.txt
+make verifier > /dev/null || exit $?
+COSTFILE=/tmp/$$-verify-cost
+OUTFILE=/tmp/$$-verify.txt.xz
+trap "rm -f $COSTFILE $OUTFILE" INT TERM EXIT
+./verifier output/output$1.txt output/output$1-prev.txt "$COSTFILE" < data/input$1.txt || exit $?
+mkdir -p archive
+xz -1 --compress --stdout output/output$1.txt > "$OUTFILE"
+mv "$OUTFILE" archive/output$1.$(<"$COSTFILE").txt.xz
+exit 0