I have modified zfind to do limited knightship searches. There is one unfortunate restriction: for whatever width you search at, there will be one phase whose width is 1 less. Unfortunately, it seems like it will be fairly complicated to remove this restriction, so I don't plan on pursuing that right now.
Code: Select all
/* zfind 1.6
** A spaceship search program by "zdr" with modifications by Matthias Merzenich
**
** Warning: this program uses a lot of memory (especially for wide searches).
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#define BANNER "zfind 1.6 by \"zdr\" and Matthias Merzenich, 18 September 2016"
#define MAXPERIOD 30
#define MIN_DUMP_PERIOD 1000000
#define DEFAULT_DEPTH_LIMIT 2000
#define NUM_PARAMS 13
#define P_RULE 0
#define P_WIDTH 1
#define P_PERIOD 2
#define P_OFFSET 3
#define P_DEPTH_LIMIT 4
#define P_SYMMETRY 5
#define P_MAX_LENGTH 6
#define P_INIT_ROWS 7
#define P_FULL_PERIOD 8
#define P_NUM_SHIPS 9
#define P_FULL_WIDTH 10
#define P_X_OFFSET 11
#define P_KNIGHT_PHASE 12
#define SYM_ASYM 1
#define SYM_ODD 2
#define SYM_EVEN 3
#define SYM_GUTTER 4
int sp[NUM_PARAMS];
uint32_t *gInd, *pInd;
uint32_t *pRemain;
uint16_t *gRows, *pRows;
uint16_t *ev2Rows; // lookup table that gives the evolution of a row with a blank row above and a specified row below
unsigned int *lastNonempty;
unsigned long long dumpPeriod;
int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;
int rule, period, offset, width, rowNum, loadDumpFlag;
int shipNum, firstFull;
uint16_t fpBitmask = 0;
int kshiftb[MAXPERIOD] = {0}, kshift0[MAXPERIOD] = {0}, kshift1[MAXPERIOD] = {0}, kshift2[MAXPERIOD] = {0}, kshift3[MAXPERIOD] = {0};
void plong(long a){
if(a > 1000000000)printf("%ldM\n", a / 1000000);
else printf("%ld\n", a);
}
int phase, fwdOff[MAXPERIOD], backOff[MAXPERIOD], doubleOff[MAXPERIOD], tripleOff[MAXPERIOD];
void makePhases(){
int i;
for (i = 0; i < period; i++) backOff[i] = -1;
i = 0;
for (;;) {
int j = offset;
while (backOff[(i+j)%period] >= 0 && j < period) j++;
if (j == period) {
backOff[i] = period-i;
break;
}
backOff[i] = j;
i = (i+j)%period;
}
for (i = 0; i < period; i++)
fwdOff[(i+backOff[i])%period] = backOff[i];
for (i = 0; i < period; i++) {
int j = (i - fwdOff[i]);
if (j < 0) j += period;
doubleOff[i] = fwdOff[i] + fwdOff[j];
}
for (i = 0; i < period; i++){
int j = (i - fwdOff[i]);
if (j < 0) j += period;
tripleOff[i] = fwdOff[i] + doubleOff[j];
}
}
/*
** For each possible phase of the ship, equivRow[phase] gives the row that
** is equivalent if the pattern is subperiodic with a specified period.
** equivRow2 is necessary for certain periods (e.g., if period == 12 and
** offset == 6 we must test subperiods 4 and 6).
** twoSubPeriods is a flag that tells the program to test two subperiods.
*/
int equivRow[MAXPERIOD];
int equivRow2[MAXPERIOD];
int twoSubPeriods = 0;
int gcd(int a, int b){
int c;
while (b){
c = b;
b = a % b;
a = c;
}
return a;
}
int smallestDivisor(int b){
int c = 2;
while(b % c) ++c;
return c;
}
void makeEqRows(int maxFactor, int a){
int tempEquivRow[MAXPERIOD];
int i,j;
for(i = 0; i < period; ++i){
tempEquivRow[i] = i;
for(j = 0; j < maxFactor; ++j){
tempEquivRow[i] += backOff[tempEquivRow[i] % period];
}
tempEquivRow[i] -= offset * maxFactor + i;
if(a == 1) equivRow[i] = tempEquivRow[i];
else equivRow2[i] = tempEquivRow[i];
}
for(i = 0; i < period; ++i){ // make equivRow[i] negative if possible
if(tempEquivRow[i] > 0){
if(a == 1) equivRow[i + tempEquivRow[i]] = -1 * tempEquivRow[i];
else equivRow2[i + tempEquivRow[i]] = -1 * tempEquivRow[i];
}
}
}
void makekshift(int a){
int i;
kshift0[a] = 1;
for(i = 0; i < period; ++i){
if((3*period + i - fwdOff[i]) % period == a) kshift1[i] = 1;
if((3*period + i - doubleOff[i]) % period == a) kshift2[i] = 1;
if((3*period + i - tripleOff[i]) % period == a) kshift3[i] = 1;
if((3*period + i + backOff[i]) % period == a) kshiftb[i] = 1;
}
}
int evolveBit(int row1, int row2, int row3, int bshift){
int r;
r = bc[(row1 >> bshift) & 7];
r += bc[(row2 >> bshift) & 7] + 4 * ((row2 >> bshift) & 2);
r += bc[(row3 >> bshift) & 7];
return (rule >> r) & 1;
}
int evolveRow(int row1, int row2, int row3){
int row4;
int row1_s,row2_s,row3_s;
int j,s1 = 0,s2 = 0;
if(sp[P_SYMMETRY] == SYM_ASYM){s1 = 1; s2 = 30;}
else if(sp[P_SYMMETRY] == SYM_ODD){s1 = 0; s2 = 1;}
else if(sp[P_SYMMETRY] == SYM_EVEN){s1 = 0; s2 = 0;}
else if(sp[P_SYMMETRY] == SYM_GUTTER){s1 = 0; s2 = 30;}
if(evolveBit(row1, row2, row3, width - 1)) return -1;
if(s1 && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
row1_s = (row1 << 1) + ((row1 >> s2) & 1);
row2_s = (row2 << 1) + ((row2 >> s2) & 1);
row3_s = (row3 << 1) + ((row3 >> s2) & 1);
row4 = evolveBit(row1_s, row2_s, row3_s, 0);
for(j = 1; j < width; j++)row4 += evolveBit(row1, row2, row3, j - 1) << j;
return row4;
}
void makeTables(){
printf("Building lookup tables.\n");
gInd = malloc(((long long)4 << (width * 3)) + 4);
ev2Rows = malloc((long long)sizeof(*ev2Rows) * (1 << (width * 2)));
int i;
int row1,row2,row3,row4;
int rows123,rows124;
int numValid = 0;
for(i = 0; i < ((1 << (3 * width)) + 1); i++)gInd[i] = 0;
rows123 = -1; //represents row1, row2, and row3 stacked vertically
for(row1 = 0; row1 < 1 << width; row1++)for(row2 = 0; row2 < 1 << width; row2++)for(row3 = 0; row3 < 1 << width; row3++){
rows123++;
row4 = evolveRow(row1,row2,row3);
if(row4 < 0) continue;
if(row1 == 0) ev2Rows[rows123] = row4;
gInd[rows123 - row3 + row4]++;
numValid++;
}
gRows = malloc(2 * numValid);
for(rows123 = 1; rows123 < 1 << (3 * width); rows123++) gInd[rows123] += gInd[rows123 - 1];
gInd[1 << (3 * width)] = gInd[(1 << (3 * width)) - 1]; //extra needed for last set to calculate number
rows123 = -1;
for(row1 = 0; row1 < 1 << width; row1++)for(row2 = 0; row2 < 1 << width; row2++)for(row3 = 0; row3 < 1 << width; row3++){
rows123++;
row4 = evolveRow(row1,row2,row3);
if(row4 < 0) continue;
rows124 = rows123 - row3 + row4;
gInd[rows124]--;
gRows[gInd[rows124]] = (uint16_t)row3;
}
printf("Lookup tables built.\n");
}
void u1_0(int a, int b){
int r[10];
int v = 2 * period;
if(sp[P_INIT_ROWS]) v = 0;
char *out = buf;
if(b){
printf("%s", buf);
fflush(stdout);
return;
}
for(r[2] = a - 1; r[2] >= 0; r[2]--)if(pRows[r[2]])break;
for(r[0] = v; r[0] <= r[2]; r[0] += sp[P_PERIOD]){
for(r[1] = 0; r[1] < sp[P_WIDTH]; r[1]++){
if((pRows[r[0]] >> r[1]) & 1)out += sprintf(out, "o");
else out += sprintf(out, ".");
}
out += sprintf(out, "\n");
}
out += sprintf(out, "%d\n", r[2] - 2 * period + 1);
}
int u1_1(int a){
int r[30];
r[2] = (pRows[a - sp[P_PERIOD] - fwdOff[phase]] << (2 * sp[P_WIDTH])) + (pRows[a - fwdOff[phase]] << sp[P_WIDTH]);
r[1] = gInd[r[2] + (pRows[a] >> kshift0[phase])];
r[3] = gInd[r[2] + pRows[a] + 1] - r[1];
if(!r[3]) return 0;
r[2] = (pRows[a - sp[P_PERIOD] - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (pRows[a - doubleOff[phase]] << sp[P_WIDTH]);
r[7] = gInd[r[2] + (pRows[a - fwdOff[phase]] >> kshift1[phase])];
r[6] = gInd[r[2] + pRows[a - fwdOff[phase]] + 1] - r[7];
if(tripleOff[phase] >= sp[P_PERIOD]){
r[10] = 1;
r[11] = pInd[a + sp[P_PERIOD] - tripleOff[phase]] + pRemain[a + sp[P_PERIOD] - tripleOff[phase]];
}
else{
r[2] = (pRows[a - sp[P_PERIOD] - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (pRows[a - tripleOff[phase]] << sp[P_WIDTH]);
r[11] = gInd[r[2] + (pRows[a - doubleOff[phase]] >> kshift2[phase])];
r[10] = gInd[r[2] + pRows[a - doubleOff[phase]] + 1] - r[11];
}
for(r[0] = 0; r[0] < r[3]; r[0]++){
r[4] = gRows[r[1] + r[0]];
if(kshift1[phase] && (r[4] & 1)) continue;
for(r[5] = 0; r[5] < r[6]; r[5]++){
r[8] = gRows[r[7] + r[5]];
if(kshift2[phase] && (r[8] & 1)) continue;
r[9] = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (r[8] << sp[P_WIDTH]) + (r[4] >> kshift1[phase]);
r[16] = gInd[r[9]];
r[15] = gInd[r[9] + 1] - r[16];
if(!r[15])continue;
for(r[12] = 0; r[12] < r[10]; r[12]++){
r[13] = gRows[r[11] + r[12]];
if(kshift3[phase] && (r[13] & 1)) continue;
r[14] = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (r[13] << sp[P_WIDTH]) + (r[8] >> kshift2[phase]);
r[18] = gInd[r[14]];
r[17] = gInd[r[14] + 1] - r[18];
if(!r[17])continue;
for(r[19] = 0; r[19] < r[15]; r[19]++){
r[20] = gRows[r[16] + r[19]];
if(kshift2[phase] && (r[20] & 1)) continue;
for(r[21] = 0; r[21] < r[17]; r[21]++){
r[22] = gRows[r[18] + r[21]];
if(kshift3[phase] && (r[22] & 1)) continue;
r[23] = (r[13] << (2 * sp[P_WIDTH])) + (r[22] << sp[P_WIDTH]) + (r[20] >> kshift2[phase]);
if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
}
}
}
}
}
return 0;
_ret1:;
return 1;
}
#define FILEVERSION ((unsigned long) 2016091801) //yyyymmddnn
int dumpNum = 1;
char dumpFile[12];
#define DUMPROOT "dump"
int dumpFlag = 0; /* Dump status flags, possible values follow */
#define DUMPPENDING (1)
#define DUMPFAILURE (2)
#define DUMPSUCCESS (3)
int dumpandexit = 0;
FILE * openDumpFile(){
FILE * fp;
while (dumpNum < 10000)
{
sprintf(dumpFile,"%s%04d",DUMPROOT,dumpNum++);
if((fp=fopen(dumpFile,"r")))
fclose(fp);
else
return fopen(dumpFile,"w");
}
return (FILE *) 0;
}
void dumpState(int v){ // v = rowNum
FILE * fp;
int i;
dumpFlag = DUMPFAILURE;
if (!(fp = openDumpFile())) return;
fprintf(fp,"%lu\n",FILEVERSION);
for (i = 0; i < NUM_PARAMS; i++)
fprintf(fp,"%d\n",sp[i]);
fprintf(fp,"%llu\n",dumpPeriod);
fprintf(fp,"%d\n",firstFull);
fprintf(fp,"%d\n",shipNum);
for (i = 1; i <= shipNum; i++)
fprintf(fp,"%u\n",lastNonempty[i]);
fprintf(fp,"%d\n",v);
for (i = 0; i < 2 * period; i++)
fprintf(fp,"%u\n",pRows[i]);
for (i = 2 * period; i <= v; i++){
fprintf(fp,"%u\n",pRows[i]);
fprintf(fp,"%u\n",pInd[i]);
fprintf(fp,"%u\n",pRemain[i]);
}
fclose(fp);
dumpFlag = DUMPSUCCESS;
}
int checkInteract(int a){
int i;
for(i = a - period; i > a - 2*period; --i){
if(ev2Rows[(pRows[i] << width) + pRows[i + period]] != pRows[i + backOff[i % period]]) return 1;
}
return 0;
}
void u1(){
int r[10];
int j;
long i, i2;
unsigned long long calcs;
int noship = 0;
int totalShips = 0;
r[0] = rowNum;
i = 0;
i2 = 0;
calcs = 0;
r[5] = 0;
r[6] = 0;
time_t ms = clock();
phase = r[0] % period;
for(;;){
if(dumpPeriod){
calcs++;
calcs %= dumpPeriod;
if(calcs == 0){
dumpState(r[0]);
if (dumpFlag == DUMPSUCCESS) printf("State dumped to file %s%04d\n",DUMPROOT,dumpNum - 1);
else printf("Dump failed\n");
fflush(stdout);
}
}
i++;
if(r[0] > r[5] || !(i & 0xffffff)){
if(r[0] > r[5]){
u1_0(r[0], 0);
r[5] = r[0];
r[6] = 1;
i2 = i;
}
if((r[6] && i - i2 > 0xffffff) || !(i & 0xffffffff)){
if(!(i & 0xffffffff))u1_0(r[0], 0);
u1_0(r[0], 1);
printf("%d\n", r[0]);
plong(i);
plong(clock() - ms);
r[6] = 0;
}
}
if(!pRemain[r[0]]){
if(shipNum && lastNonempty[shipNum] == r[0]) --shipNum;
r[0]--;
phase = r[0] % period;
if(sp[P_FULL_PERIOD] && firstFull == r[0]) firstFull = 0;
if(r[0] < 2 * sp[P_PERIOD]){
u1_0(r[0], 1);
if(totalShips == 1)printf("Search complete: 1 spaceship found.\n");
else printf("Search complete: %d spaceships found.\n",totalShips);
plong(i);
return;
}
continue;
}
pRemain[r[0]]--;
pRows[r[0]] = gRows[pInd[r[0]] + pRemain[r[0]]];
if(sp[P_X_OFFSET] && phase == sp[P_KNIGHT_PHASE] && pRows[r[0]] & 1) continue;
if(sp[P_MAX_LENGTH] && r[0] > sp[P_MAX_LENGTH] + 2 * period - 1 && pRows[r[0]] != 0) continue; //back up if length exceeds max length
if(sp[P_FULL_PERIOD] && r[0] > sp[P_FULL_PERIOD] && !firstFull && pRows[r[0]]) continue; //back up if not full period by certain length
if(sp[P_FULL_WIDTH] && (pRows[r[0]] & fpBitmask)){
if(equivRow[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow[phase]]){
if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow2[phase]])) continue;
}
}
if(shipNum && r[0] == lastNonempty[shipNum] + 2*period && !checkInteract(r[0])) continue; //back up if new rows don't interact with ship
if(!u1_1(r[0]))continue;
if(sp[P_FULL_PERIOD] && !firstFull){
if(equivRow[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow[phase]]){
if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow2[phase]])) firstFull = r[0];
}
}
r[0]++;
phase = r[0] % period;
if(r[0] > sp[P_DEPTH_LIMIT]){
noship = 0;
for(j = 1; j <= 2 * period; ++j) noship += pRows[r[0]-j];
if(!noship){
if(!sp[P_FULL_PERIOD] || firstFull){
u1_0(0, 1);
++totalShips;
printf("Spaceship found. (%d)\n",totalShips);
plong(i);
--sp[P_NUM_SHIPS];
}
++shipNum;
if(sp[P_NUM_SHIPS] == 0){
if(totalShips == 1)printf("Search terminated: spaceship found.\n");
else printf("Search terminated: %d spaceships found.\n",totalShips);
return;
}
for(lastNonempty[shipNum] = r[0] - 1; lastNonempty[shipNum] >= 0; --lastNonempty[shipNum]) if(pRows[lastNonempty[shipNum]]) break;
r[0] = lastNonempty[shipNum] + 2 * period;
phase = r[0] % period;
r[5] = lastNonempty[shipNum];
continue;
}
else{
u1_0(0, 1);
printf("Search terminated: depth limit reached.\n");
printf("Depth: %d\n", r[0] - 2 * period);
if(totalShips == 1)printf("1 spaceship found.\n");
else printf("%d spaceships found.\n",totalShips);
}
plong(i);
return;
}
r[4] = (pRows[r[0] - 2 * period] << (2 * sp[P_WIDTH])) + (pRows[r[0] - period] << sp[P_WIDTH]) + (pRows[r[0] - period + backOff[phase]] >> kshiftb[phase]);
pRemain[r[0]] = gInd[r[4] + 1] - gInd[r[4]];
pInd[r[0]] = gInd[r[4]];
}
}
char * loadFile;
void loadFail(){
printf("Load from file %s failed\n",loadFile);
exit(1);
}
signed int loadInt(FILE *fp){
signed int v;
if (fscanf(fp,"%d\n",&v) != 1) loadFail();
return v;
}
unsigned long loadUL(FILE *fp){
unsigned long v;
if (fscanf(fp,"%lu\n",&v) != 1) loadFail();
return v;
}
unsigned long long loadULL(FILE *fp){
unsigned long long v;
if (fscanf(fp,"%llu\n",&v) != 1) loadFail();
return v;
}
void loadState(char * cmd, char * file){
FILE * fp;
int i;
printf("Loading search state from %s\n",file);
loadFile = file;
fp = fopen(loadFile, "r");
if (!fp) loadFail();
if (loadUL(fp) != FILEVERSION)
{
printf("Incompatible file version\n");
exit(1);
}
/* Load parameters and set stuff that can be derived from them */
for (i = 0; i < NUM_PARAMS; i++)
sp[i] = loadInt(fp);
dumpPeriod = loadULL(fp);
firstFull = loadInt(fp);
shipNum = loadInt(fp);
lastNonempty = malloc(sizeof(int) * (sp[P_DEPTH_LIMIT]/10));
for (i = 1; i <= shipNum; i++)
lastNonempty[i] = loadUL(fp);
rowNum = loadInt(fp);
if(dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
rule = sp[P_RULE];
width = sp[P_WIDTH];
period = sp[P_PERIOD];
offset = sp[P_OFFSET];
if(gcd(period,offset) == 1) sp[P_FULL_PERIOD] = 0;
if(sp[P_FULL_WIDTH] > sp[P_WIDTH]) sp[P_FULL_WIDTH] = 0;
if(sp[P_FULL_WIDTH] && sp[P_FULL_WIDTH] < sp[P_WIDTH]){
for(i = sp[P_FULL_WIDTH]; i < sp[P_WIDTH]; ++i){
fpBitmask |= (1 << i);
}
}
pRows = malloc(sp[P_DEPTH_LIMIT] * 2);
pInd = malloc(sp[P_DEPTH_LIMIT] * 4);
pRemain = malloc(sp[P_DEPTH_LIMIT] * 4);
for (i = 0; i < 2 * period; i++)
pRows[i] = (uint16_t) loadUL(fp);
for (i = 2 * period; i <= rowNum; i++){
pRows[i] = (uint16_t) loadUL(fp);
pInd[i] = (uint32_t) loadUL(fp);
pRemain[i] = (uint32_t) loadUL(fp);
}
fclose(fp);
if(!strcmp(cmd,"p") || !strcmp(cmd,"P")){
u1_0(rowNum,0);
u1_0(rowNum,1);
exit(0);
}
}
void loadInitRows(char * file){
FILE * fp;
int i,j;
char rowStr[10];
loadFile = file;
fp = fopen(loadFile, "r");
if (!fp) loadFail();
for(i = 0; i < 2 * period; i++){
fscanf(fp,"%s",rowStr);
for(j = 0; j < width; j++){
pRows[i] |= ((rowStr[width - j - 1] == '.') ? 0:1) << j;
}
}
fclose(fp);
}
void initializeSearch(char * file){
int i;
if(dumpPeriod > 0 && dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
rule = sp[P_RULE];
width = sp[P_WIDTH];
period = sp[P_PERIOD];
offset = sp[P_OFFSET];
if(sp[P_MAX_LENGTH]) sp[P_DEPTH_LIMIT] = sp[P_MAX_LENGTH] + 2 * period;
sp[P_DEPTH_LIMIT] += 2 * period;
if(sp[P_FULL_PERIOD]) sp[P_FULL_PERIOD] += 2 * period - 1;
if(gcd(period,offset) == 1) sp[P_FULL_PERIOD] = 0;
if(sp[P_FULL_WIDTH] > sp[P_WIDTH]) sp[P_FULL_WIDTH] = 0;
if(sp[P_FULL_WIDTH] && sp[P_FULL_WIDTH] < sp[P_WIDTH]){
for(i = sp[P_FULL_WIDTH]; i < sp[P_WIDTH]; ++i){
fpBitmask |= (1 << i);
}
}
if(sp[P_X_OFFSET]) sp[P_SYMMETRY] = SYM_ASYM;
sp[P_KNIGHT_PHASE] %= period;
pRows = malloc(sp[P_DEPTH_LIMIT] * 2);
pInd = malloc(sp[P_DEPTH_LIMIT] * 4);
pRemain = malloc(sp[P_DEPTH_LIMIT] * 4);
lastNonempty = malloc(sizeof(int) * (sp[P_DEPTH_LIMIT]/10));
rowNum = 2 * period;
for(i = 0; i < 2 * period; i++)pRows[i] = 0;
if(sp[P_INIT_ROWS]) loadInitRows(file);
}
void echoParams(){
int i,j;
printf("Rule: B");
for(i = 0; i < 9; i++){
if(rule & (1 << i)) printf("%d",i);
}
printf("/S");
for(i = 9; i < 18; i++){
if(rule & (1 << i)) printf("%d",i - 9);
}
printf("\n");
printf("Period: %d\n",sp[P_PERIOD]);
printf("Offset: %d\n",sp[P_OFFSET]);
printf("Width: %d\n",sp[P_WIDTH]);
if(sp[P_SYMMETRY] == SYM_ASYM) printf("Symmetry: asymmetric\n");
else if(sp[P_SYMMETRY] == SYM_ODD) printf("Symmetry: odd\n");
else if(sp[P_SYMMETRY] == SYM_EVEN) printf("Symmetry: even\n");
else if(sp[P_SYMMETRY] == SYM_GUTTER) printf("Symmetry: gutter\n");
if(sp[P_X_OFFSET]){
printf("Horizontal offset: %d\n",sp[P_X_OFFSET]);
printf("Phase %d has width %d\n",sp[P_KNIGHT_PHASE],sp[P_WIDTH] - 1);
}
if(sp[P_MAX_LENGTH]) printf("Max length: %d\n",sp[P_MAX_LENGTH]);
else printf("Depth limit: %d\n",sp[P_DEPTH_LIMIT] - 2 * period);
if(sp[P_FULL_PERIOD]) printf("Full period by depth %d\n",sp[P_FULL_PERIOD] - 2 * period + 1);
if(sp[P_FULL_WIDTH]) printf("Full period width: %d\n",sp[P_FULL_WIDTH]);
if(sp[P_NUM_SHIPS] == 1) printf("Stop search if a ship is found\n",sp[P_NUM_SHIPS]);
else printf("Stop search if %d ships are found\n",sp[P_NUM_SHIPS]);
if(dumpPeriod)printf("Dump period: %llu\n",dumpPeriod);
if(sp[P_INIT_ROWS]){
printf("Initial rows:\n");
for(i = 0; i < 2 * period; i++){
for(j = width - 1; j >= 0; j--) printf("%c",(pRows[i] & (1 << j)) ? 'o':'.');
printf("\n");
}
}
}
void usage(){
printf("%s\n",BANNER);
printf("\n");
printf("usage: \"zfind options\"\n");
printf(" e.g. \"zfind B3/S23 p3 k1 w6 v\" searches Life (rule B3/S23) for\n");
printf(" c/3 orthogonal spaceships with even bilateral symmetry and a\n");
printf(" search width of 6 (full width 12).\n");
printf("\n");
printf("available options:\n");
printf(" bNN/sNN searches for spaceships in the specified rule (default: b3/s23)\n");
printf("\n");
printf(" pNN searches for spaceships with period NN\n");
printf(" kNN searches for spaceships that travel NN cells every period\n");
printf(" wNN searches for spaceships with search width NN\n");
printf(" (full width depends on symmetry type)\n");
printf("\n");
printf(" lNN terminates the search if it reaches a depth of NN (default: %d)\n",DEFAULT_DEPTH_LIMIT);
printf(" mNN disallows spaceships longer than a depth of NN\n");
printf(" (the spaceship length is approximately depth/period)\n");
printf(" fNN disallows spaceships that do not have the full period by a depth of NN\n");
printf(" tNN disallows full-period rows of width greater than NN\n");
printf(" sNN terminates the search if NN spaceships are found (default: 1)\n");
printf("\n");
printf(" xNN searches for spaceships that travel NN cells horizontally every period\n");
printf(" (only values of 0 and 1 are currently supported)\n");
printf(" when using x1, one phase of the spaceship will have a width of 1 less\n");
printf(" than the width specified by the 'w' parameter\n");
printf(" nNN when using x1, NN is the phase with the smaller width (default: 0)\n");
printf("\n");
printf(" dNN dumps the search state every NN calculations\n");
printf(" j dumps the state at start of search\n");
printf("\n");
printf(" a searches for asymmetric spaceships\n");
printf(" u searches for odd bilaterally symmetric spaceships\n");
printf(" v searches for even bilaterally symmetric spaceships\n");
printf(" g searches for symmetric spaceships with gutters (empty center column)\n");
printf("\n");
printf(" e FF uses rows in the file FF as the initial rows for the search\n");
printf(" (use the companion Golly python script to easily generate the\n");
printf(" initial row file)\n");
printf("\n");
printf("\"zfind command file\" reloads the state from the specified file\n");
printf("and performs the command. Available commands: \n");
printf(" s resumes search from the loaded state\n");
printf(" p outputs the pattern representing the loaded state\n");
}
int main(int argc, char *argv[]){
buf = malloc(2000000);
buf[0] = '\0';
sp[P_RULE] = 6152; //first 9 bits represent births; next 9 bits represent survivals
sp[P_WIDTH] = 0;
sp[P_PERIOD] = 0;
sp[P_OFFSET] = 0;
sp[P_DEPTH_LIMIT] = DEFAULT_DEPTH_LIMIT;
sp[P_SYMMETRY] = 0;
sp[P_MAX_LENGTH] = 0;
sp[P_INIT_ROWS] = 0;
sp[P_FULL_PERIOD] = 0;
sp[P_NUM_SHIPS] = 1;
sp[P_FULL_WIDTH] = 0;
sp[P_X_OFFSET] = 0;
sp[P_KNIGHT_PHASE] = 0;
loadDumpFlag = 0;
dumpPeriod = 0;
int dumpandexit = 0;
int skipNext = 0;
int div1,div2;
int s;
if(argc == 2 && !strcmp(argv[1],"c")){
usage();
return 0;
}
if(argc == 3 && (!strcmp(argv[1],"s") || !strcmp(argv[1],"S") || !strcmp(argv[1],"p") || !strcmp(argv[1],"P"))) loadDumpFlag = 1;
else{
for(s = 1; s < argc; s++){ //read input parameters
if(skipNext){
skipNext = 0;
continue;
}
switch(argv[s][0]){
case 'b': case 'B': //read rule
sp[P_RULE] = 0;
int sshift = 0;
int i;
for(i = 1; i < 100; i++){
int rnum = argv[s][i];
if(!rnum)break;
if(rnum == 's' || rnum == 'S')sshift = 9;
if(rnum >= '0' && rnum <= '8')sp[P_RULE] += 1 << (sshift + rnum - '0');
}
break;
case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[P_WIDTH]); break;
case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[P_PERIOD]); break;
case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[P_OFFSET]); break;
case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[P_DEPTH_LIMIT]); break;
case 'u': case 'U': sp[P_SYMMETRY] = SYM_ODD; break;
case 'v': case 'V': sp[P_SYMMETRY] = SYM_EVEN; break;
case 'a': case 'A': sp[P_SYMMETRY] = SYM_ASYM; break;
case 'g': case 'G': sp[P_SYMMETRY] = SYM_GUTTER; break;
case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[P_MAX_LENGTH]); break;
case 'd': case 'D': sscanf(&argv[s][1], "%llu", &dumpPeriod); break;
case 'j': case 'J': dumpandexit = 1; break;
case 'e': case 'E': sp[P_INIT_ROWS] = s + 1; skipNext = 1; break;
case 'f': case 'F': sscanf(&argv[s][1], "%d", &sp[P_FULL_PERIOD]); break;
case 's': case 'S': sscanf(&argv[s][1], "%d", &sp[P_NUM_SHIPS]); break;
case 't': case 'T': sscanf(&argv[s][1], "%d", &sp[P_FULL_WIDTH]); break;
case 'x': case 'X': sscanf(&argv[s][1], "%d", &sp[P_X_OFFSET]); break;
case 'n': case 'N': sscanf(&argv[s][1], "%d", &sp[P_KNIGHT_PHASE]); break;
}
}
}
if(loadDumpFlag) loadState(argv[1],argv[2]); //load search state from file
else initializeSearch(argv[sp[P_INIT_ROWS]]); //initialize search based on input parameters
if(!sp[P_WIDTH] || !sp[P_PERIOD] || !sp[P_OFFSET] || !sp[P_SYMMETRY]){
printf("You must specify a width, period, offset, and symmetry type.\n");
printf("For command line options, type 'zfind c'.\n");
return 0;
}
echoParams();
time_t ms = clock();
makePhases(); //make phase tables for determining successor row indices
if(gcd(period,offset) > 1){ //make phase tables for determining equivalent subperiodic rows
div1 = smallestDivisor(gcd(period,offset));
makeEqRows(period / div1,1);
div2 = gcd(period,offset);
while(div2 % div1 == 0) div2 /= div1;
if(div2 != 1){
twoSubPeriods = 1;
div2 = smallestDivisor(div2);
makeEqRows(period / div2,2);
}
}
if(sp[P_X_OFFSET]) makekshift(sp[P_KNIGHT_PHASE]);
makeTables(); //make lookup tables for determining successor rows
if(!loadDumpFlag){ //these initialization steps must be performed after makeTables()
pRemain[2 * period] = gInd[1] - gInd[0] - 1;
pInd[2 * period] = gInd[0];
if(sp[P_INIT_ROWS]){
s = (pRows[0] << (2 * width)) + (pRows[period] << width) + pRows[period + backOff[0]];
pRemain[2 * period] = gInd[s + 1] - gInd[s];
pInd[2 * period] = gInd[s];
}
}
if(dumpandexit){
dumpState(rowNum);
if (dumpFlag == DUMPSUCCESS) printf("State dumped to file %s%04d\n",DUMPROOT,dumpNum - 1);
else printf("Dump failed\n");
return 0;
}
plong(clock() - ms);
ms = clock();
u1();
plong(clock() - ms);
return 0;
}
added horizontal displacement to echoed parameters.