## zfind discussion

For scripts to aid with computation or simulation in cellular automata.

### Re: zfind discussion

Born of my frustration entering rows manually, I have written a Golly python script to automatically generate and organize the rows of a partial pattern for use in zfind:
# This is a script for generating the initial rows when extending a# partial result using zfind, qfind, or gfind# Instructions:# 1. Orient the partial result so that it is traveling upwards.# 2. Select the row that you wish to extend from (for symmetric#    searches, only select the left half of the row). The search#    will essentially use that row and the row below it as the#    initial rows for the search.# 3. Run the script and input the period and translation.# 4. The rows will be saved to "initrows.txt", which can be used#    directly in a zfind or qfind search.# 5. To extend with gfind, the rows need to be converted into#    binary numbers (replace "o" with "1" and "." with "0") and#    entered into the code according to these instructions:#    http://www.conwaylife.com/forums/viewtopic.php?f=9&t=925#p6776#    Note: many compilers allow you to use the "0b" prefix for#    writing numbers in binary.from glife import rect, validintimport golly as gdef getrow(x, y, width):    s = ""    for i in range(width):        if g.getcell(x + i, y): s += "o"        else: s += "."    return sfirstrow = rect(g.getselrect())if len(firstrow) == 0: g.exit("There is no selection.")if firstrow.height != 1: g.exit("Incorrect selection dimensions (height must be 1)")width = firstrow.widthperiod = g.getstring("Enter the period.")if not validint(period): g.exit("Period should be a positive integer.")period = int(period)if period <= 0: g.exit("Period should be a positive integer.")offset = g.getstring("Enter the offset (translation).")if not validint(offset): g.exit("Offset should be a positive integer.")offset = int(offset)if offset <= 0: g.exit("Offset should be a positive integer.")if period <= offset: g.exit("Period must be greater than offset.")backOff = [-1 for i in range(period)]i = 0while True:    j = offset    while ((backOff[(i+j)%period] >= 0) and (j < period)): j += 1    if j == period:        backOff[i] = period - i        break    backOff[i] = j    i = (i+j)%periodrows = ["" for i in range(2*period)]k = 0mp = 0x = firstrow.xy = firstrow.yfor i in range(period):    rows[k] = getrow(x,y - mp,width)    rows[k + period] = getrow(x,y + 1 - mp,width)    k += backOff[k]    if k >= period:        k -= period        mp += 1    g.run(1)try:    f = open('initrows.txt', 'w')    for i in range(2 * period): f.write(rows[i] + "\n")    f.close()except:    g.warn("Unable to save file.")

The instructions are included in the above code, but I will repeat them here:
1. Orient the partial result that you wish to extend so that it is traveling upwards
2. Select the row that you wish to extend from (for symmetric searches, only select the left half of the row). The search will essentially use that row and the row below it as the initial rows for the search.
3. Run the script and input the period and translation.
4. The rows will be saved to "initrows.txt", which can be used directly in a zfind or qfind search (run with "e initrows.txt", as explained in this post).
5. To extend with gfind, the rows need to be converted into binary numbers (replace "o" with "1" and "." with "0") and entered into the code according to these instructions. Note: many compilers allow you to use the "0b" prefix for writing numbers in binary.

This script should make extending partial results with zfind and gfind much easier. In particular, it allows for extending partials with gcd(period,translation) > 1, which was extremely difficult to do manually.
-Matthias Merzenich
Sokwe
Moderator

Posts: 1480
Joined: July 9th, 2009, 2:44 pm

### Re: zfind discussion

@zdr, @Sokwe, and @A for Awesome:
I would like to thank you all for publishing your code which enhances the ability of all of us to find interesting patterns in many rules. In particular, I have recently started using gfind to extend partial spaceship results and these last few posts are very helpful in this endeavour.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1236
Joined: August 9th, 2013, 12:45 am

### Re: zfind discussion

Since many new features have been added to zfind, I have added usage instructions very similar to those in gfind. To view the usage instructions, run "zfind c". Don't forget to compile with optimizations.
#include <stdio.h>#include <stdlib.h>#include <stdint.h>#define MAXPERIOD 30#define MIN_DUMP_PERIOD 1000000#define DEFAULT_DEPTH_LIMIT 2000#define NUM_PARAMS 8#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 SYM_ASYM 1#define SYM_ODD 2#define SYM_EVEN 3#define SYM_GUTTER 4int sp[NUM_PARAMS];uint32_t *gInd, *pInd;uint32_t *pRemain;uint16_t *gRows, *pRows;unsigned long long dumpPeriod;int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};char *buf;int rule, period, offset, width, rowNum, loadDumpFlag;void plong(long a){   if(a > 1000000000)printf("%dM\n", a / 1000000);   else printf("%d\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];   }}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,s2;   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);   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;      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);      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]];   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]]];   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]]];      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]];      for(r[5] = 0; r[5] < r[6]; r[5]++){         r[8] = gRows[r[7] + r[5]];         r[9] = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (r[8] << sp[P_WIDTH]) + r[4];         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]];            r[14] = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (r[13] << sp[P_WIDTH]) + r[8];            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]];               for(r[21] = 0; r[21] < r[17]; r[21]++){                  r[22] = gRows[r[18] + r[21]];                  r[23] = (r[13] << (2 * sp[P_WIDTH])) + (r[22] << sp[P_WIDTH]) + r[20];                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;               }            }         }      }   }   return 0;   _ret1:;   return 1;}#define FILEVERSION ((unsigned long) 2016082901)  //yyyymmddnnint 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,"%u\n",FILEVERSION);    for (i = 0; i < NUM_PARAMS; i++)       fprintf(fp,"%d\n",sp[i]);    fprintf(fp,"%llu\n",dumpPeriod);    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;}void u1(){   int r[10];   int j;   long i, i2;   unsigned long long calcs;   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");         }      }      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]]){         r[0]--;         phase = r[0] % period;         if(r[0] < 2 * sp[P_PERIOD]){            u1_0(r[0], 1);            printf("Search complete: no spaceships found.\n");            plong(i);            return;         }         continue;      }      pRemain[r[0]]--;      pRows[r[0]] = gRows[pInd[r[0]] + pRemain[r[0]]];      if(sp[P_MAX_LENGTH] && r[0] > sp[P_MAX_LENGTH] + 2 * period - 1 && pRows[r[0]] != 0) continue;      if(!u1_1(r[0]))continue;      r[0]++;      phase = r[0] % period;      if(r[0] > sp[P_DEPTH_LIMIT]){         u1_0(0, 1);         int noship = 0;         for(j = 1; j <= 2 * period; j++) noship += pRows[r[0]-j];         if(!noship) printf("Spaceship found.\n");         else{            printf("Search terminated: depth limit reached.\n");            printf("Depth: %d\n", r[0] - 2 * period);         }         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]];      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);   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];      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;      pRows = malloc(sp[P_DEPTH_LIMIT] * 2);   pInd = malloc(sp[P_DEPTH_LIMIT] * 4);   pRemain = malloc(sp[P_DEPTH_LIMIT] * 4);   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_MAX_LENGTH]) printf("Max length: %d\n",sp[P_MAX_LENGTH]);   else printf("Depth limit: %d\n",sp[P_DEPTH_LIMIT] - 2 * period);   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("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("\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("  r    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;   loadDumpFlag = 0;   dumpPeriod = 0;   int dumpandexit = 0;   int skipNext = 0;   int s;   if(argc == 2 && !strcmp(argv[1],"c")){      usage();      return 0;   }   if(argc == 3 && (!strcmp(argv[1],"r") || !strcmp(argv[1],"R") || !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;         }      }   }   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   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;}

I also cleaned up the code a bit.

@wildmyron,
Thanks for the feedback. Please post any bugs you find.

Edit: I did some minor cleaning of the code, but it doesn't affect how the program runs.
-Matthias Merzenich
Sokwe
Moderator

Posts: 1480
Joined: July 9th, 2009, 2:44 pm

### Re: zfind discussion

A for awesome wrote:(Be aware, running this also created a file called step.c in the directory.) The options for running are the same as in regular zfind, except entering a rule does nothing.

Saving the third file is technically optional, and you may replace all the steps until running the actual search itself by entering the commands manually (replacing "$1" with the rule you want to search). I can make no guarantees that all non-totalistic rules will run properly. I tested all of the bitwise expressions used semi-manually, but I may certainly have missed something. As far as I know, extending partials should work the same as in regular zfind. I found no file called step.c. I tried running it anyway but get the error fatal error: 'step.c' file not found#include "step.c" . Can you send me a copy of what the file is supposed to look like? It would help a lot! "Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life." -Terry Pratchett toroidalet Posts: 1002 Joined: August 7th, 2016, 1:48 pm Location: my computer ### Re: zfind discussion toroidalet wrote:I found no file called step.c. :cry: I tried running it anyway but get the error fatal error: 'step.c' file not found#include "step.c" . Can you send me a copy of what the file is supposed to look like? It would help a lot! It should be automatically generated by running ntzfind-setup with a single parameter, the rule you want to search. Here's a copy for B3/S2-i34q: int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){ return (~o&((0x0)|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))))|(o&((0x0)|(~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f)))&~(~(b|d|f|h)&~((a^e)|(c^g))))|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))|(0x0|(((~b&~f)&~((~c^~e)|(~a^~g))&(~e^~g)&~(~d|~h))|((~d&~h)&~((~e^~g)|(~a^~c))&(~c^~e)&~(~b|~f))))));} Could you post exactly what you're running to compile the program? I've also found a few bugs in ntzfind-setup.cpp that cause step.c to be generated with a syntax error, but if it doesn't work, you can manually assemble step.c as follows: Open ntzfind-setup.cpp and find the long sequence of lines beginning with the following: transtable[i] = Transition( Assume there are two empty expressions, called "B" and "S". Then, do the following for each number in the rule corresponding to a birth transition: • If the number is not followed by any lowercase letter, append a "|" to B (if there's anything before it), find the line corresponding to the same number, and append the last quoted string in the line to "B". • If the number is followed by one or more lowercase letters, without a minus sign: for each line corresponding to that number and a letter following it, append a "|" to B (if there's anything before it) and then append the last quoted string on the line. • If the number is followed by a minus sign, and then one or more lowercase letters, append the text "|(" to B (if there's anything before it), find the line corresponding to the same number, and append the last quoted string in the line to "B", and append "&!(". Then, for each line corresponding to that number and a letter following it, append a "|" to B (if there's anything before it) and then append the last quoted string on the line. Finally, append "))". Then, do the same for survival transitions and S. Then, line 2 of step.cpp should read return (~o&(B))|(o&(S)); with "B" and "S" replaced by the corresponding transitions. The rest should be the same as the example above. x₁=ηx V ⃰_η=c²√(Λη) K=(Λu²)/2 Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt) $$x_1=\eta x$$ $$V^*_\eta=c^2\sqrt{\Lambda\eta}$$ $$K=\frac{\Lambda u^2}2$$ $$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$ http://conwaylife.com/wiki/A_for_all Aidan F. Pierce A for awesome Posts: 1876 Joined: September 13th, 2014, 5:36 pm Location: 0x-1 ### Re: zfind discussion A for awesome wrote: toroidalet wrote:I found no file called step.c. I tried running it anyway but get the error fatal error: 'step.c' file not found#include "step.c" . Can you send me a copy of what the file is supposed to look like? It would help a lot! It should be automatically generated by running ntzfind-setup with a single parameter, the rule you want to search. Here's a copy for B3/S2-i34q: int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){ return (~o&((0x0)|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))))|(o&((0x0)|(~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f)))&~(~(b|d|f|h)&~((a^e)|(c^g))))|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))|(0x0|(((~b&~f)&~((~c^~e)|(~a^~g))&(~e^~g)&~(~d|~h))|((~d&~h)&~((~e^~g)|(~a^~c))&(~c^~e)&~(~b|~f))))));} Could you post exactly what you're running to compile the program? I've also found a few bugs in ntzfind-setup.cpp that cause step.c to be generated with a syntax error, but if it doesn't work, you can manually assemble step.c as follows: Open ntzfind-setup.cpp and find the long sequence of lines beginning with the following: transtable[i] = Transition( Assume there are two empty expressions, called "B" and "S". Then, do the following for each number in the rule corresponding to a birth transition: • If the number is not followed by any lowercase letter, append a "|" to B (if there's anything before it), find the line corresponding to the same number, and append the last quoted string in the line to "B". • If the number is followed by one or more lowercase letters, without a minus sign: for each line corresponding to that number and a letter following it, append a "|" to B (if there's anything before it) and then append the last quoted string on the line. • If the number is followed by a minus sign, and then one or more lowercase letters, append the text "|(" to B (if there's anything before it), find the line corresponding to the same number, and append the last quoted string in the line to "B", and append "&!(". Then, for each line corresponding to that number and a letter following it, append a "|" to B (if there's anything before it) and then append the last quoted string on the line. Finally, append "))". Then, do the same for survival transitions and S. Then, line 2 of step.cpp should read return (~o&(B))|(o&(S)); with "B" and "S" replaced by the corresponding transitions. The rest should be the same as the example above. I was using gcc to try and just compile the non-totalistic zfind because I don't know how to run ntzfind-compile. EDIT: I ran ntzfind-compile and got this ntzfind-setup.cpp:1:1: error: expected unqualified-id{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170^1 error generated../ntzfind-compile.sh: line 4: ./ntzfind-setup: No such file or directoryntzfind.c:7:10: fatal error: 'step.c' file not found#include "step.c" ^1 error generated. EDIT2: I didn't have ntzfind-setup saved as a plaintext document. I changed that and got a lot of  warning: treating Unicode character as whitespace ^ntzfind-setup.cpp:342:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8':^ntzfind-setup.cpp:342:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:342:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:342:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:342:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:342:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:342:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:342:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case '8': ^ntzfind-setup.cpp:343:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30;^ntzfind-setup.cpp:343:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:343:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] num = rule[pos] - 0x30; ^ntzfind-setup.cpp:344:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){^ntzfind-setup.cpp:344:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:344:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(rule[pos+1] == '-'){ ^ntzfind-setup.cpp:345:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(";^ntzfind-setup.cpp:345:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:345:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:346:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable);^ntzfind-setup.cpp:346:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:346:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:347:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false;^ntzfind-setup.cpp:347:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:347:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = false; ^ntzfind-setup.cpp:348:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2;^ntzfind-setup.cpp:348:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:348:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos += 2; ^ntzfind-setup.cpp:349:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r...^ntzfind-setup.cpp:349:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:349:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || r... ^ntzfind-setup.cpp:350:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(";^ntzfind-setup.cpp:350:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:350:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|("; ^ntzfind-setup.cpp:351:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable);^ntzfind-setup.cpp:351:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:351:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(std::string(1,rule[pos]), transtable); ^ntzfind-setup.cpp:352:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true;^ntzfind-setup.cpp:352:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:352:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:353:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++;^ntzfind-setup.cpp:353:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:353:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:354:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{^ntzfind-setup.cpp:354:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:354:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }else{ ^ntzfind-setup.cpp:355:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0";^ntzfind-setup.cpp:355:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:355:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")|(0x0"; ^ntzfind-setup.cpp:356:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true;^ntzfind-setup.cpp:356:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:356:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] sign = true; ^ntzfind-setup.cpp:357:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++;^ntzfind-setup.cpp:357:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:357:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:358:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }^ntzfind-setup.cpp:358:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:358:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:359:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break;^ntzfind-setup.cpp:359:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:359:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:360:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S':^ntzfind-setup.cpp:360:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:360:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:360:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:360:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:360:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:360:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:360:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 'S': ^ntzfind-setup.cpp:361:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's':^ntzfind-setup.cpp:361:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:361:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:361:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:361:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:361:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:361:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:361:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] case 's': ^ntzfind-setup.cpp:362:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++;^ntzfind-setup.cpp:362:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:362:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:363:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break;^ntzfind-setup.cpp:363:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:363:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] break; ^ntzfind-setup.cpp:364:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default:^ntzfind-setup.cpp:364:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:364:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:364:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:364:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:364:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:364:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:364:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] default: ^ntzfind-setup.cpp:365:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~(");^ntzfind-setup.cpp:365:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:365:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += (sign?"|(":"&~("); ^ntzfind-setup.cpp:366:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos];^ntzfind-setup.cpp:366:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:366:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack = std::string(1,((char)num+0x30)) + rule[pos]; ^ntzfind-setup.cpp:367:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){^ntzfind-setup.cpp:367:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:367:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] if(!sign){ ^ntzfind-setup.cpp:368:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given ";^ntzfind-setup.cpp:368:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:368:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += "(given "; ^ntzfind-setup.cpp:369:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30);^ntzfind-setup.cpp:369:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:369:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ((char)num+0x30); ^ntzfind-setup.cpp:370:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')';^ntzfind-setup.cpp:370:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:27: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:370:30: warning: treating Unicode character as whitespace [-Wunicode-whitespace] hack += ')'; ^ntzfind-setup.cpp:371:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }^ntzfind-setup.cpp:371:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:371:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:372:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable);^ntzfind-setup.cpp:372:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:372:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += search(hack, transtable); ^ntzfind-setup.cpp:373:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')';^ntzfind-setup.cpp:373:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:373:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ')'; ^ntzfind-setup.cpp:374:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++;^ntzfind-setup.cpp:374:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:16: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:19: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:21: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:374:24: warning: treating Unicode character as whitespace [-Wunicode-whitespace] pos++; ^ntzfind-setup.cpp:375:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }^ntzfind-setup.cpp:375:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:375:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:375:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:375:11: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:375:14: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:376:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }^ntzfind-setup.cpp:376:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:376:6: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:376:9: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:377:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] }^ntzfind-setup.cpp:377:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] } ^ntzfind-setup.cpp:378:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")));\n\^ntzfind-setup.cpp:378:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] code += ")));\n\ ^ntzfind-setup.cpp:380:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] file << code;^ntzfind-setup.cpp:380:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] file << code; ^ntzfind-setup.cpp:381:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] //std::cout << std::endl;^ntzfind-setup.cpp:381:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] //std::cout << std::endl; ^ntzfind-setup.cpp:382:1: warning: treating Unicode character as whitespace [-Wunicode-whitespace] return 0;^ntzfind-setup.cpp:382:4: warning: treating Unicode character as whitespace [-Wunicode-whitespace] return 0; ^1578 warnings generated.Error in ntcasim-setup: wrong number of command-line arguments (1 expected).ntzfind.c:7:10: fatal error: 'step.c' file not found#include "step.c" "Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life." -Terry Pratchett toroidalet Posts: 1002 Joined: August 7th, 2016, 1:48 pm Location: my computer ### Re: zfind discussion I have added two new features to zfind: • The 'f' parameter forces spaceships to have at least one full-period row by the specified depth. For example, "zfind p6 k2 w9 u f200" searches for c/3 ships which have a period-6 row by depth 200 (recall, the length of a ship is approximately depth/period). • The 's' parameter specifies the maximum number of spaceships to be found before the search terminates (default is 1). For example, "zfind p4 k1 w7 u s10" will stop after finding 10 ships. This won't always find the specified number of ships, even if that many ships exist. For example, running "zfind p4 k1 w7 v s5" finds two spaceships and then runs into an antstretcher. The 's' parameter is generally best used in conjunction with the max length parameter ('m'), as not specifying a max length usually results in the search finding a repeating component and terminating by reaching the depth limit. At least for low periods, gfind and knightt are better tools for finding large numbers of spaceships. I also changed the command to load the search state from a file (from 'r' to 's') so that it matches Paul Tooke's gfind modification. For example, if you want to run the search from the file dump0003, run "zfind s dump0003". Here is the updated code: /* zfind 1.4** 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.4 by \"zdr\" and Matthias Merzenich, 16 September 2016"#define MAXPERIOD 30#define MIN_DUMP_PERIOD 1000000#define DEFAULT_DEPTH_LIMIT 2000#define NUM_PARAMS 10#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 SYM_ASYM 1#define SYM_ODD 2#define SYM_EVEN 3#define SYM_GUTTER 4int 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 belowunsigned 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;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 if period == 12, 24, or 30, as then two subperiods** need to be tested (e.g., if period == 12, 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]; } }}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]]; 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]]]; 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]]]; 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]]; for(r[5] = 0; r[5] < r[6]; r[5]++){ r[8] = gRows[r[7] + r[5]]; r[9] = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (r[8] << sp[P_WIDTH]) + r[4]; 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]]; r[14] = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (r[13] << sp[P_WIDTH]) + r[8]; 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]]; for(r[21] = 0; r[21] < r[17]; r[21]++){ r[22] = gRows[r[18] + r[21]]; r[23] = (r[13] << (2 * sp[P_WIDTH])) + (r[22] << sp[P_WIDTH]) + r[20]; if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1; } } } } } return 0; _ret1:; return 1;}#define FILEVERSION ((unsigned long) 2016091601) //yyyymmddnnint 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"); } } 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_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(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]]; 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; 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; 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_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(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(" sNN terminates the search if NN spaceships are found (default: 1)\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; 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; } } } 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); } } 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;} -Matthias Merzenich Sokwe Moderator Posts: 1480 Joined: July 9th, 2009, 2:44 pm ### Re: zfind discussion Here's another update to zfind that allows you to specify a smaller width for full-period rows. This is controlled by the 't' parameter. For example, running "zfind p6 k2 w9 u t3 f300" searches for a 2c/6 spaceship that is period-6 by depth 300, subject to the restriction that all period-6 rows have search-width no more than 3. This modification actually doesn't work quite as advertised. It is possible for some full-period rows to be wider than the specified maximum full-period width. This is because I decided to go with a simpler implementation that approximates the desired result. I might eventually get around to doing it properly. If you haven't already noticed, I added some features to zfind earlier today, which are described in this post. Here is the updated code: /* zfind 1.5** 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.5 by \"zdr\" and Matthias Merzenich, 16 September 2016"#define MAXPERIOD 30#define MIN_DUMP_PERIOD 1000000#define DEFAULT_DEPTH_LIMIT 2000#define NUM_PARAMS 11#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 SYM_ASYM 1#define SYM_ODD 2#define SYM_EVEN 3#define SYM_GUTTER 4int 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 belowunsigned 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;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 if period == 12, 24, or 30, as then two subperiods** need to be tested (e.g., if period == 12, 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]; } }}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]]; 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]]]; 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]]]; 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]]; for(r[5] = 0; r[5] < r[6]; r[5]++){ r[8] = gRows[r[7] + r[5]]; r[9] = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (r[8] << sp[P_WIDTH]) + r[4]; 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]]; r[14] = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (r[13] << sp[P_WIDTH]) + r[8]; 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]]; for(r[21] = 0; r[21] < r[17]; r[21]++){ r[22] = gRows[r[18] + r[21]]; r[23] = (r[13] << (2 * sp[P_WIDTH])) + (r[22] << sp[P_WIDTH]) + r[20]; if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1; } } } } } return 0; _ret1:; return 1;}#define FILEVERSION ((unsigned long) 2016091602) //yyyymmddnnint 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"); } } 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_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]]; 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); } } 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_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(" 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; 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; } } } 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); } } 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;} -Matthias Merzenich Sokwe Moderator Posts: 1480 Joined: July 9th, 2009, 2:44 pm ### Re: zfind discussion 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. There are two new parameters: 1. The 'x' parameter allows you to search for spaceships with a horizontal offset (only x0 and x1 are supported). For example, "zfind p6 k2 w9 a x1" searches for a period-6 knightship. Unfortunately, the restriction described above means that any partial will be width-8 in phase 0. Searches for diagonally-traveling ships are also possible. Notice that "zfind p4 k1 w3 a x1" does not find the glider, because the glider does not have a phase of width 2. Running "zfind p4 k1 w4 a x1" successfully finds the glider. 2. When using 'x1', the 'n' parameter allows you to choose which phase is the "thin" phase (default is phase 0). Changing this parameter usually doesn't make much difference, but it can sometimes result in different longest partials. For example, running "zfind p6 k1 w6 a x1 n5" finds a slightly longer partial than running "zfind p6 k1 w6 a x1 n0" Here is the updated code: /* 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 4int 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 belowunsigned 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) //yyyymmddnnint 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;} Edit: added horizontal displacement to echoed parameters. -Matthias Merzenich Sokwe Moderator Posts: 1480 Joined: July 9th, 2009, 2:44 pm ### Re: zfind discussion @Sokwe: I have been happily using the partial row generator script and zfind with great pleasure. In particular I appreciate the max length option, NN ships to search for option and the horizontal displacement option. There is perhaps a minor detail omitted from the documentation for the Python script when using it with symmetric partials - which is that the selected row must be on the lefthand side of the partial whereas zfind's output is only the right hand side. You mentioned this in your earlier instructions for manual searching of partials with zfind and it should be immediately apparent to anyone trying to use the script so it is perhaps unimportant A very minor bug in zfind - with the 'g' search symmetry option zfind will happily try to find ships that are doomed to fail when cells in the central gutter are born due to B2, B4 or B6 in the rule. You mentioned that gfind is probably suitable for searching for ships with speed > c/2. The exception to this is light speed ships with p>1. If you do consider allowing zfind to search for faster ships would those ships be searchable? Or might it be possible to only increasing the allowed speed to c, and none of the other speeds in between (obviously only if this is a simpler adaptation)? A nebulous idea which I've been wondering about is a means to workaround the memory usage of w>10 searches. The idea would be to use two lookup tables instead of one which have a 2 cell overlap, i.e. one LUT would be used to evolve the LHS of the row and the other used for the RHS of the row. For a w12 search there would be two width 7 tables and for a w13 search there would be one width 7 and one width 8 table. Do you think this is doable or is it a completely hare-brained idea? @A for awesome: Recently started using ntzfind. Seems to be working well so far, thanks again for sharing your work. I shifted the changes in ntzfind.c to zfind v1.6 and I haven't noticed any issues. I did think that ntzfind seemed to be taking a lot longer to build the look up tables but when I used -O3 to compile it's significantly improved. It might be worth adding that option to ntzfind-compile.sh or whatever you call it. The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki. wildmyron Posts: 1236 Joined: August 9th, 2013, 12:45 am ### Re: zfind discussion wildmyron wrote:I appreciate... the horizontal displacement option. Just a note on this option: I think zfind 1.6 might slow down orthogonal spaceship searches. You might be better off using zfind 1.5 for orthogonal searches and zfind 1.6 only when you want the horizontal offset feature. wildmyron wrote:There is perhaps a minor detail omitted from the documentation for the Python script when using it with symmetric partials - which is that the selected row must be on the lefthand side of the partial whereas zfind's output is only the right hand side. You're right. That should have been in the documentation. It's fixed now. wildmyron wrote:A very minor bug in zfind - with the 'g' search symmetry option zfind will happily try to find ships that are doomed to fail when cells in the central gutter are born due to B2, B4 or B6 in the rule. At some point I want to add a feature that checks to make sure the input parameters are reasonable (like gfind does). For now though, I have been focused on search features and have relied on users to determine what is a reasonable search. wildmyron wrote:You mentioned that gfind is probably suitable for searching for ships with speed > c/2. The exception to this is light speed ships with p>1. If you do consider allowing zfind to search for faster ships would those ships be searchable? zfind cannot search for high-period photons for the same reason that gfind cannot. Any workaround for zfind would probably also work for gfind, and at that point gfind would be the better program for running such searches. I haven't thought much about the problem, since it is not relevant to Life. wildmyron wrote:A nebulous idea which I've been wondering about is a means to workaround the memory usage of w>10 searches. The idea would be to use two lookup tables instead of one which have a 2 cell overlap, i.e. one LUT would be used to evolve the LHS of the row and the other used for the RHS of the row. For a w12 search there would be two width 7 tables and for a w13 search there would be one width 7 and one width 8 table. Do you think this is doable or is it a completely hare-brained idea? It's a reasonable idea, but it's enough work that I haven't committed to actually implementing it. I would need to think about how to do it without substantial speed costs. I'm still thinking about updates to zfind, and I'm working on a minor change that seems to increase the speed a little on most searches (basically, I reorder the lookup table to hopefully get the depth-first lookahead to run slightly faster). The code works, but I haven't tested it much, and I need to clean it up before posting. Unfortunately, I'm somewhat busy right now, so I probably won't get to it until the weekend. I also want to profile zfind to see if I can get any other ideas for optimization. -Matthias Merzenich Sokwe Moderator Posts: 1480 Joined: July 9th, 2009, 2:44 pm ### Re: zfind discussion wildmyron wrote:@A for awesome: Recently started using ntzfind. Seems to be working well so far, thanks again for sharing your work. I shifted the changes in ntzfind.c to zfind v1.6 and I haven't noticed any issues. I did think that ntzfind seemed to be taking a lot longer to build the look up tables but when I used -O3 to compile it's significantly improved. It might be worth adding that option to ntzfind-compile.sh or whatever you call it. You're welcome, and thank you for the feedback. I should probably get around to posting an update which uses consistent notation with Golly/LifeViewer/apgsearch-v0.54+0.2Ni/etc., changes an error message to reference the correct program, and allows the omission of the rule-dividing slash, and so here is the new version of ntzfind-setup.cpp: //Yes, I know that it's unnecessary to include both iostream and fstream, but I think it's a bit clearer.#include <iostream>#include <fstream>#include <string>//I wrote this before I knew what a struct was:class Transition{ public: std::string name, code; Transition(){}; Transition(std::string n, std::string c){name = n; code = c;};};int count_ops(std::string exp){ int ctr = 0; for(unsigned int i = 0; i < exp.length(); i++){ if(exp[i] == '&' || exp[i] == '|' || exp[i] == '^'){ ctr++; } } return ctr;}std::string search(std::string name, Transition table[107]){ for(int i = 0; i < 107; i++){ if(table[i].name == name){ return table[i].code; } } return "";}int main(int argc, char** argv){ Transition transtable[107]; std::string* rules[9]; int i = 0, num = -1, sizes[9] = {1,3,7,11,14,11,7,3,1}; unsigned int pos = 0; bool mode = false, sign = true; std::string code = "int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){\n\ return ", rule, step = "", hack = ""; //You know it's a badly-written program when there's a variable called "hack". std::ofstream file; if(argc != 2){ std::cout << "Error in ntzfind-setup.cpp: wrong number of command-line arguments (1 expected)." << std::endl; return 0; } for(int i = 0; i < 9; i++){ rules[i] = new std::string[sizes[i]]; } //This was autogenerated (and manually edited) with some python code from a table I wrote for my own reference, so it's unnecessarily human-readable. transtable[i] = Transition("0", "~(a|b|c|d|e|f|g|h)"); i++; transtable[i] = Transition("1", "(a^b^c^d^e^f^g^h)&~(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))"); i++; transtable[i] = Transition("1c", "~(a|c|e|g)&(b|d|f|h)&~(((b|d)&(f|h))|((b|h)&(d|f)))"); i++; transtable[i] = Transition("1c(given 1)", "b|d|f|h"); i++; transtable[i] = Transition("1e", "~(b|d|f|h)&(a|c|e|g)&~(((a|c)&(e|g))|((a|g)&(c|e)))"); i++; transtable[i] = Transition("1e(given 1)", "a|c|e|g"); i++; transtable[i] = Transition("2", "~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f)))"); i++; transtable[i] = Transition("2a", "(a|c|e|g)&~((((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))|(((a|c)&(e|g))|((a|g)&(c|e))))"); i++; transtable[i] = Transition("2a(given 2)", "~(((a^b)|(c^d)|(e^f))&((b^c)|(d^e)|(f^g)))"); i++; transtable[i] = Transition("2c", "~(a|c|e|g)&(b^f)&~(b^d^f^h)"); i++; transtable[i] = Transition("2c(given 2)", "~(a|c|e|g)&(b^f)"); i++; transtable[i] = Transition("2e", "~(b|d|f|h)&(a^e)&~(a^c^e^g)"); i++; transtable[i] = Transition("2e(given 2)", "~(b|d|f|h)&(a^e)"); i++; transtable[i] = Transition("2i", "~(b|d|f|h)&~((a^e)|(c^g))&(a^c)"); i++; transtable[i] = Transition("2i(given 2)", "~(b|d|f|h)&~((a^e)|(c^g))"); i++; transtable[i] = Transition("2k", "(a|c|e|g)&~((((a^d)|(g^b)|(e^h)|(c^f))&((d^g)|(b^e)|(h^c)|(f^a)))|(((a|c)&(e|g))|((a|g)&(c|e))))"); i++; transtable[i] = Transition("2k(given 2)", "~(((a^d)|(g^b)|(e^h))&((d^g)|(b^e)|(h^c)))"); i++; transtable[i] = Transition("2v", "~(a|c|e|g)&~((b^f)|(d^h))&(b^d)"); i++; transtable[i] = Transition("2v(given 2)", "~(a|c|e|g)&~((b^f)|(d^h))"); i++; transtable[i] = Transition("3", "(a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h))))"); i++; transtable[i] = Transition("3a", "~(a^c^e^g)&~(((b|d)&(f|h))|((b|h)&(d|f)))&((a&~e&((b&c)|(g&h)))|(e&~a&((c&d)|(f&g))))"); i++; transtable[i] = Transition("3a(given 3)", "(a&((b&c)|(g&h)))|(e&((c&d)|(f&g)))"); i++; transtable[i] = Transition("3c", "~(a|c|e|g)&(b^d^f^h)&((b&d)|(f&h))"); i++; transtable[i] = Transition("3c(given 3)", "~(a|c|e|g)"); i++; transtable[i] = Transition("3e", "~(b|d|f|h)&(a^c^e^g)&((a&c)|(e&g))"); i++; transtable[i] = Transition("3e(given 3)", "~(b|d|f|h)"); i++; transtable[i] = Transition("3i", "~(b^d^f^h)&~(((a|c)&(e|g))|((a|g)&(c|e)))&((b&~f&((c&d)|(h&a)))|(f&~b&((d&e)|(g&h))))"); i++; transtable[i] = Transition("3i(given 3)", "(b&((c&d)|(a&h)))|(f&((d&e)|(g&h)))"); i++; transtable[i] = Transition("3j", "~(a^c^e^g)&(((b^f)&((c&e)^(a&g))&~(d|h))|((d^h)&((e&g)^(a&c))&~(b|f)))"); i++; transtable[i] = Transition("3j(given 3)", "((b^f)&((c&e)^(a&g)))|((d^h)&((e&g)^(a&c)))"); i++; transtable[i] = Transition("3k", "~(a^c^e^g)&~(((b|d)&(f|h))|((b|h)&(d|f)))&((a&~e&((c&f)|(d&g)))|(e&~a&((g&b)|(h&c))))"); i++; transtable[i] = Transition("3k(given 3)", "(a&((c&f)|(d&g)))|(e&((c&h)|(b&g)))"); i++; transtable[i] = Transition("3q", "(a|c|e|g)&~(((a|c)&(e|g))|((a|g)&(c|e)))&~((b^f)|(d^h))&(b^d)"); i++; transtable[i] = Transition("3q(given 3)", "(b|d|f|h)&~(b^d)&~(d^h)"); i++; transtable[i] = Transition("3r", "~(b^d^f^h)&~(((c|e)&(a|g))|((a|c)&(e|g)))&((b&~f&((d&g)|(e&h)))|(f&~b&((h&c)|(a&d))))"); i++; transtable[i] = Transition("3r(given 3)", "(b&((d&g)|(e&h)))|(f&((a&d)|(c&h)))"); i++; transtable[i] = Transition("3v", "~(b^d^f^h)&(((a^e)&((b&d)^(f&h))&~(c|g))|((c^g)&((d&f)^(b&h))&~(a|e)))"); i++; transtable[i] = Transition("3v(given 3)", "((a^e)&((b&d)^(f&h)))|((c^g)&((d&f)^(b&h)))"); i++; transtable[i] = Transition("3y", "(b|d|f|h)&~(((b|d)&(f|h))|((b|h)&(d|f)))&~((a^e)|(c^g))&(a^c)"); i++; transtable[i] = Transition("3y(given 3)", "(a|c|e|g)&~(a^e)&~(c^g)"); i++; transtable[i] = Transition("4", "~(a^b^c^d^e^f^g^h)&((a^b^c^d)&(((a&b)|(c&d))^((e&f)|(g&h)))|(~(a^b^c^d)&((a|b|c)^(e&f&g))&((a&b&c)^(e|f|g))))"); i++; transtable[i] = Transition("4a", "((a^c)|(c^e)|(e^g))&((b^d)|(d^f)|(f^h))&~(((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))&(a^e)&(c^g)"); i++; transtable[i] = Transition("4a(given 4)", "~(((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))&(a^e)&(c^g)"); i++; transtable[i] = Transition("4c", "~(a|c|e|g)&b&d&f&h"); i++; transtable[i] = Transition("4c(given 4)", "b&d&f&h"); i++; transtable[i] = Transition("4e", "~(~a|~c|~e|~g)&~b&~d&~f&~h"); i++; transtable[i] = Transition("4e(given 4)", "~b&~d&~f&~h"); i++; transtable[i] = Transition("4i", "((a&e)&~((b^d)|(f^h))&(d^f)&~(c|g))|((c&g)&~((d^f)|(b^h))&(b^d)&~(a|e))"); i++; transtable[i] = Transition("4i(given 4)", "((a&e)&~((b^d)|(f^h))&~c)|((c&g)&~((d^f)|(b^h))&~a)"); i++; transtable[i] = Transition("4j", "((~b&~f)&((~d&(~a^~g)&~(~c|~e|~h))|((~h&(~c^~e)&~(~a|~d|~g)))))|((~d&~h)&((~b&(~e^~g)&~(~a|~c|~f))|((~f&(~a^~c)&~(~b|~e|~g)))))"); i++; transtable[i] = Transition("4j(given 4)", "((~b&~f)&((~d&(~a^~g))|((~h&(~c^~e)))))|((~d&~h)&((~b&(~e^~g))|((~f&(~a^~c)))))"); i++; transtable[i] = Transition("4k", "((a^c)|(c^e)|(e^g))&((b^d)|(d^f)|(f^h))&~(((a^d)|(c^f)|(e^h)|(b^g))&((d^g)|(a^f)|(c^h)|(b^e)))&(a^e)&(c^g)"); i++; transtable[i] = Transition("4k(given 4)", "~(((a^d)|(c^f)|(e^h)|(b^g))&((d^g)|(a^f)|(c^h)|(b^e)))&(a^e)&(c^g)"); i++; transtable[i] = Transition("4q", "((~b&~f)&~((~c^~e)|(~a^~g))&(~e^~g)&~(~d|~h))|((~d&~h)&~((~e^~g)|(~a^~c))&(~c^~e)&~(~b|~f))"); i++; transtable[i] = Transition("4q(given 4)", "((~b&~f)&~((~c^~e)|(~a^~g))&d)|((~d&~h)&~((~e^~g)|(~a^~c))&b)"); i++; transtable[i] = Transition("4r", "((b&f)&((d&(a^g)&~(c|e|h))|((h&(c^e)&~(a|d|g)))))|((d&h)&((b&(e^g)&~(a|c|f))|((f&(a^c)&~(b|e|g)))))"); i++; transtable[i] = Transition("4r(given 4)", "((b&f)&((d&(a^g))|((h&(c^e)))))|((d&h)&((b&(e^g))|((f&(a^c)))))"); i++; transtable[i] = Transition("4t", "((~a&~e)&~((~b^~d)|(~f^~h))&(~d^~f)&~(~c|~g))|((~c&~g)&~((~d^~f)|(~b^~h))&(~b^~d)&~(~a|~e))"); i++; transtable[i] = Transition("4t(given 4)", "((~a&~e)&~((~b^~d)|(~f^~h))&c)|((~c&~g)&~((~d^~f)|(~b^~h))&a)"); i++; transtable[i] = Transition("4v", "((b&f)&((d&(c^e)&~(a|g|h))|((h&(a^g)&~(c|d|e)))))|((d&h)&((b&(a^c)&~(e|f|g))|((f&(e^g)&~(a|b|c)))))"); i++; transtable[i] = Transition("4v(given 4)", "((b&f)&((d&(c^e))|((h&(a^g)))))|((d&h)&((b&(a^c))|((f&(e^g)))))"); i++; transtable[i] = Transition("4w", "((b&f)&~((c^e)|(a^g))&(e^g)&~(d|h))|((d&h)&~((e^g)|(a^c))&(c^e)&~(b|f))"); i++; transtable[i] = Transition("4w(given 4)", "((b&f)&~((c^e)|(a^g))&~d)|((d&h)&~((e^g)|(a^c))&~b)"); i++; transtable[i] = Transition("4y", "((~b&~f)&((~d&(~c^~e)&~(~a|~g|~h))|((~h&(~a^~g)&~(~c|~d|~e)))))|((~d&~h)&((~b&(~a^~c)&~(~e|~f|~g))|((~f&(~e^~g)&~(~a|~b|~c)))))"); i++; transtable[i] = Transition("4y(given 4)", "((~b&~f)&((~d&(~c^~e))|((~h&(~a^~g)))))|((~d&~h)&((~b&(~a^~c))|((~f&(~e^~g)))))"); i++; transtable[i] = Transition("4z", "~((a^e)|(b^f)|(c^g)|(d^h))&(a^c)&(b^d)"); i++; transtable[i] = Transition("4z(given 4)", "~((a^e)|(b^f)|(c^g)|(d^h))&(a^c)&(b^d)"); i++; transtable[i] = Transition("5", "(~a^~b^~c^~d^~e^~f^~g^~h)&(((~a|~b|~c|~d)&(~e|~f|~g|~h))|((~a|~b|~e|~f)&(~c|~d|~g|~h)))&~(((~a|~b)&(~c|~d)&(~e|~f)&(~g|~h))|(~((~a&~b)^(~c&~d)^(~e&~f)^(~g&~h))&((~a&~b)|(~c&~d)|(~e&~f)|(~g&~h))))"); i++; transtable[i] = Transition("5a", "~(~a^~c^~e^~g)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&((~a&e&((~b&~c)|(~g&~h)))|(~e&a&((~c&~d)|(~f&~g))))"); i++; transtable[i] = Transition("5a(given 5)", "(~a&((~b&~c)|(~g&~h)))|(~e&((~c&~d)|(~f&~g)))"); i++; transtable[i] = Transition("5c", "~(~a|~c|~e|~g)&(~b^~d^~f^~h)&((~b&~d)|(~f&~h))"); i++; transtable[i] = Transition("5c(given 5)", "~(~a|~c|~e|~g)"); i++; transtable[i] = Transition("5e", "~(~b|~d|~f|~h)&(~a^~c^~e^~g)&((~a&~c)|(~e&~g))"); i++; transtable[i] = Transition("5e(given 5)", "~(~b|~d|~f|~h)"); i++; transtable[i] = Transition("5i", "~(~b^~d^~f^~h)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))&((~b&f&((~c&~d)|(~h&~a)))|(~f&b&((~d&~e)|(~g&~h))))"); i++; transtable[i] = Transition("5i(given 5)", "(~b&((~c&~d)|(~a&~h)))|(~f&((~d&~e)|(~g&~h)))"); i++; transtable[i] = Transition("5j", "~(~a^~c^~e^~g)&(((~b^~f)&((~c&~e)^(~a&~g))&~(~d|~h))|((~d^~h)&((~e&~g)^(~a&~c))&~(~b|~f)))"); i++; transtable[i] = Transition("5j(given 5)", "((~b^~f)&((~c&~e)^(~a&~g)))|((~d^~h)&((~e&~g)^(~a&~c)))"); i++; transtable[i] = Transition("5k", "~(~a^~c^~e^~g)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&((~a&e&((~c&~f)|(~d&~g)))|(~e&a&((~g&~b)|(~h&~c))))"); i++; transtable[i] = Transition("5k(given 5)", "(~a&((~c&~f)|(~d&~g)))|(~e&((~c&~h)|(~b&~g)))"); i++; transtable[i] = Transition("5q", "(~a|~c|~e|~g)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))&~((~b^~f)|(~d^~h))&(~b^~d)"); i++; transtable[i] = Transition("5q(given 5)", "(~b|~d|~f|~h)&~(~b^~d)&~(~d^~h)"); i++; transtable[i] = Transition("5r", "~(~b^~d^~f^~h)&~(((~c|~e)&(~a|~g))|((~a|~c)&(~e|~g)))&((~b&f&((~d&~g)|(~e&~h)))|(~f&b&((~h&~c)|(~a&~d))))"); i++; transtable[i] = Transition("5r(given 5)", "(~b&((~d&~g)|(~e&~h)))|(~f&((~a&~d)|(~c&~h)))"); i++; transtable[i] = Transition("5v", "~(~b^~d^~f^~h)&(((~a^~e)&((~b&~d)^(~f&~h))&~(~c|~g))|((~c^~g)&((~d&~f)^(~b&~h))&~(~a|~e)))"); i++; transtable[i] = Transition("5v(given 5)", "((~a^~e)&((~b&~d)^(~f&~h)))|((~c^~g)&((~d&~f)^(~b&~h)))"); i++; transtable[i] = Transition("5y", "(~b|~d|~f|~h)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&~((~a^~e)|(~c^~g))&(~a^~c)"); i++; transtable[i] = Transition("5y(given 5)", "(~a|~c|~e|~g)&~(~a^~e)&~(~c^~g)"); i++; transtable[i] = Transition("6", "~(~a^~b^~c^~d^~e^~f^~g^~h)&(~a|~b|~c|~d|~e|~f|~g|~h)&~(((~a|~b|~c)&(~d|~e|~f)&(~g|~h))|( ~a&~b&~c)|(~d&~e&~f)|((~a|~b|~c)&(~d|~e|~f)&(~(~a^~b^~c)|~(~d^~e^~f)))|(~g&~h&(~a|~b|~c|~d|~e|~f)))"); i++; transtable[i] = Transition("6a", "(~a|~c|~e|~g)&~((((~a^~b)|(~c^~d)|(~e^~f)|(~g^~h))&((~b^~c)|(~d^~e)|(~f^~g)|(~a^~h)))|(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e))))"); i++; transtable[i] = Transition("6a(given 6)", "~(((~a^~b)|(~c^~d)|(~e^~f))&((~b^~c)|(~d^~e)|(~f^~g)))"); i++; transtable[i] = Transition("6c", "~(~a|~c|~e|~g)&(~b^~f)&~(~b^~d^~f^~h)"); i++; transtable[i] = Transition("6c(given 6)", "~(~a|~c|~e|~g)&(~b^~f)"); i++; transtable[i] = Transition("6e", "~(~b|~d|~f|~h)&(~a^~e)&~(~a^~c^~e^~g)"); i++; transtable[i] = Transition("6e(given 6)", "~(~b|~d|~f|~h)&(~a^~e)"); i++; transtable[i] = Transition("6i", "~(~b|~d|~f|~h)&~((~a^~e)|(~c^~g))&(~a^~c)"); i++; transtable[i] = Transition("6i(given 6)", "~(~b|~d|~f|~h)&~((~a^~e)|(~c^~g))"); i++; transtable[i] = Transition("6k", "(~a|~c|~e|~g)&~((((~a^~d)|(~g^~b)|(~e^~h)|(~c^~f))&((~d^~g)|(~b^~e)|(~h^~c)|(~f^~a)))|(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e))))"); i++; transtable[i] = Transition("6k(given 6)", "~(((~a^~d)|(~g^~b)|(~e^~h))&((~d^~g)|(~b^~e)|(~h^~c)))"); i++; transtable[i] = Transition("6v", "~(~a|~c|~e|~g)&~((~b^~f)|(~d^~h))&(~b^~d)"); i++; transtable[i] = Transition("6v(given 6)", "~(~a|~c|~e|~g)&~((~b^~f)|(~d^~h))"); i++; transtable[i] = Transition("7", "(~a^~b^~c^~d^~e^~f^~g^~h)&~(((~a|~b|~c|~d)&(~e|~f|~g|~h))|((~a|~b|~e|~f)&(~c|~d|~g|~h)))"); i++; transtable[i] = Transition("7c", "~(~a|~c|~e|~g)&(~b|~d|~f|~h)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))"); i++; transtable[i] = Transition("7c(given 7)", "~b|~d|~f|~h"); i++; transtable[i] = Transition("7e", "~(~b|~d|~f|~h)&(~a|~c|~e|~g)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))"); i++; transtable[i] = Transition("7e(given 7)", "~a|~c|~e|~g"); i++; transtable[i] = Transition("8", "~(~a|~b|~c|~d|~e|~f|~g|~h)"); rule = argv[1]; file.open("step.c"); if(rule[0] == 'B' || rule[0] == 'b'){ mode = true; pos++; } code += '('; code += (mode?"~":""); code += "o&((0x0"; while(pos < rule.length()){ if(mode){ switch(rule[pos]){ case '/': case '_': case 'S': case 's': code += ")))|(o&((0x0"; mode = false; num = -1; pos++; break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': num = rule[pos] - 0x30; if(rule[pos+1] == '-'){ code += ")|("; code += search(std::string(1,rule[pos]), transtable); sign = false; pos += 2; }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || rule[pos+1] == '/' || rule[pos+1] == '_' || rule[pos+1] == 'S' || rule[pos+1] == 's' || pos == rule.length()-1){ code += ")|("; code += search(std::string(1,rule[pos]), transtable); sign = true; pos++; }else{ code += ")|(0x0"; sign = true; pos++; } break; case 'B': case 'b': pos++; break; default: code += (sign?"|(":"&~("); hack = std::string(1,((char)num+0x30)) + rule[pos]; if(!sign){ hack += "(given "; hack += ((char)num+0x30); hack += ')'; } code += search(hack, transtable); code += ')'; pos++; } }else{ switch(rule[pos]){ case '/': case '_': case 'B': case 'b': code += ")))|(~o&((0x0"; mode = true; num = -1; pos++; break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': num = rule[pos] - 0x30; if(rule[pos+1] == '-'){ code += ")|("; code += search(std::string(1,rule[pos]), transtable); sign = false; pos += 2; }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || rule[pos+1] == '/' || rule[pos+1] == '_' || rule[pos+1] == 'B' || rule[pos+1] == 'b' || pos == rule.length()-1){ code += ")|("; code += search(std::string(1,rule[pos]), transtable); sign = true; pos++; }else{ code += ")|(0x0"; sign = true; pos++; } break; case 'S': case 's': pos++; break; default: code += (sign?"|(":"&~("); hack = std::string(1,((char)num+0x30)) + rule[pos]; if(!sign){ hack += "(given "; hack += ((char)num+0x30); hack += ')'; } code += search(hack, transtable); code += ')'; pos++; } } } code += ")));\n\}"; file << code; //std::cout << std::endl; return 0;} And here is the new ntzfind-compile.sh (or whatever else) version, just for reference: g++ ntzfind-setup.cpp -o ntzfind-setup./ntzfind-setup$1gcc ntzfind.c -O3 -o ntzfind

EDIT: Got rid of some debugging statements I forgot to remove.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

A for awesome

Posts: 1876
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: zfind discussion

@Sokwe: Thanks for the detailed responses. I will keep your advice on v1.6 in mind.
Sokwe wrote:
wildmyron wrote:A nebulous idea which I've been wondering about is a means to workaround the memory usage of w>10 searches. The idea would be to use two lookup tables instead of one which have a 2 cell overlap, i.e. one LUT would be used to evolve the LHS of the row and the other used for the RHS of the row. For a w12 search there would be two width 7 tables and for a w13 search there would be one width 7 and one width 8 table. Do you think this is doable or is it a completely hare-brained idea?

It's a reasonable idea, but it's enough work that I haven't committed to actually implementing it. I would need to think about how to do it without substantial speed costs.

Not expecting anything from yourself (or myself) on this front, but I will note that I considered the second LUT would only be used when w>9 (perhaps as an option?). I would expect a speed penalty of at least 100% when using a second LUT compared to using just one, but there might be some clever tricks to reduce that.

@A for awesome: Thanks for the update. The required rule-string format did catch me out at first.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1236
Joined: August 9th, 2013, 12:45 am

### Re: zfind discussion

When I attempt to compile ntzfind, I get this error message:

ntzfind.c:2:20: fatal error: iostream: No such file or directory #include <iostream>                    ^compilation terminated.

@A for awesome, why does this happen and how can I fix it?

Goldtiger997

Posts: 538
Joined: June 21st, 2016, 8:00 am
Location: 11.329903°N 142.199305°E

### Re: zfind discussion

Goldtiger997 wrote:When I attempt to compile ntzfind, I get this error message:

ntzfind.c:2:20: fatal error: iostream: No such file or directory #include <iostream>                    ^compilation terminated.

@A for awesome, why does this happen and how can I fix it?

iostream is a C++ library. Did you modify ntzfind.c or perhaps save what is meant to be ntzfind-setup.cpp as ntzfind.c ?
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1236
Joined: August 9th, 2013, 12:45 am

### Re: zfind discussion

wildmyron wrote:
Goldtiger997 wrote:When I attempt to compile ntzfind, I get this error message:

ntzfind.c:2:20: fatal error: iostream: No such file or directory #include <iostream>                    ^compilation terminated.

@A for awesome, why does this happen and how can I fix it?

iostream is a C++ library. Did you modify ntzfind.c or perhaps save what is meant to be ntzfind-setup.cpp as ntzfind.c ?

Oh sorry, somehow i managed to save the c++ code for ntzfind-setup in ntzfind.c.

It works now, thank you.

Goldtiger997

Posts: 538
Joined: June 21st, 2016, 8:00 am
Location: 11.329903°N 142.199305°E

### Re: zfind discussion

Goldtiger997 wrote:It works now, thank you.

You're welcome.

@A for awesome:
ntzfind-setup.cpp seems to use the 'r'-'y' swapped and 'v' in place of 'n' version of Hensel notation. Observed when I tried to search "BestFriends", a.k.a. B2ce3air/S12aei3y
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1236
Joined: August 9th, 2013, 12:45 am

### Re: zfind discussion

wildmyron wrote:ntzfind-setup.cpp seems to use the 'r'-'y' swapped and 'v' in place of 'n' version of Hensel notation. Observed when I tried to search "BestFriends", a.k.a. B2ce3air/S12aei3y

Oops. I fixed that in something else and thought I had fixed it in ntzfind. Here's the patched version of ntzfind-setup.cpp:
//Yes, I know that it's unnecessary to include both iostream and fstream, but I think it's a bit clearer.#include <iostream>#include <fstream>#include <string>//I wrote this before I knew what a struct was:class Transition{   public:      std::string name, code;      Transition(){};      Transition(std::string n, std::string c){name = n; code = c;};};int count_ops(std::string exp){    int ctr = 0;   for(unsigned int i = 0; i < exp.length(); i++){      if(exp[i] == '&' || exp[i] == '|' || exp[i] == '^'){         ctr++;      }   }   return ctr;}std::string search(std::string name, Transition table[107]){   for(int i = 0; i < 107; i++){      if(table[i].name == name){         return table[i].code;      }   }   return "";}int main(int argc, char** argv){    Transition transtable[107];    std::string* rules[9];    int i = 0, num = -1, sizes[9] = {1,3,7,11,14,11,7,3,1};    unsigned int pos = 0;    bool mode = false, sign = true;    std::string code = "int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){\n\   return ", rule, step = "", hack = ""; //You know it's a badly-written program when there's a variable called "hack".   std::ofstream file;    if(argc != 2){        std::cout << "Error in ntzfind-setup.cpp: wrong number of command-line arguments (1 expected)." << std::endl;       return 0;    }    for(int i = 0; i < 9; i++){       rules[i] = new std::string[sizes[i]];    }   //This was autogenerated (and manually edited) with some python code from a table I wrote for my own reference, so it's unnecessarily human-readable.   transtable[i] = Transition("0", "~(a|b|c|d|e|f|g|h)");   i++;   transtable[i] = Transition("1", "(a^b^c^d^e^f^g^h)&~(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))");   i++;   transtable[i] = Transition("1c", "~(a|c|e|g)&(b|d|f|h)&~(((b|d)&(f|h))|((b|h)&(d|f)))");   i++;   transtable[i] = Transition("1c(given 1)", "b|d|f|h");   i++;   transtable[i] = Transition("1e", "~(b|d|f|h)&(a|c|e|g)&~(((a|c)&(e|g))|((a|g)&(c|e)))");   i++;   transtable[i] = Transition("1e(given 1)", "a|c|e|g");   i++;   transtable[i] = Transition("2", "~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f)))");   i++;   transtable[i] = Transition("2a", "(a|c|e|g)&~((((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))|(((a|c)&(e|g))|((a|g)&(c|e))))");   i++;   transtable[i] = Transition("2a(given 2)", "~(((a^b)|(c^d)|(e^f))&((b^c)|(d^e)|(f^g)))");   i++;   transtable[i] = Transition("2c", "~(a|c|e|g)&(b^f)&~(b^d^f^h)");   i++;   transtable[i] = Transition("2c(given 2)", "~(a|c|e|g)&(b^f)");   i++;   transtable[i] = Transition("2e", "~(b|d|f|h)&(a^e)&~(a^c^e^g)");   i++;   transtable[i] = Transition("2e(given 2)", "~(b|d|f|h)&(a^e)");   i++;   transtable[i] = Transition("2i", "~(b|d|f|h)&~((a^e)|(c^g))&(a^c)");   i++;   transtable[i] = Transition("2i(given 2)", "~(b|d|f|h)&~((a^e)|(c^g))");   i++;   transtable[i] = Transition("2k", "(a|c|e|g)&~((((a^d)|(g^b)|(e^h)|(c^f))&((d^g)|(b^e)|(h^c)|(f^a)))|(((a|c)&(e|g))|((a|g)&(c|e))))");   i++;   transtable[i] = Transition("2k(given 2)", "~(((a^d)|(g^b)|(e^h))&((d^g)|(b^e)|(h^c)))");   i++;   transtable[i] = Transition("2n", "~(a|c|e|g)&~((b^f)|(d^h))&(b^d)");   i++;   transtable[i] = Transition("2n(given 2)", "~(a|c|e|g)&~((b^f)|(d^h))");   i++;   transtable[i] = Transition("3", "(a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h))))");   i++;   transtable[i] = Transition("3a", "~(a^c^e^g)&~(((b|d)&(f|h))|((b|h)&(d|f)))&((a&~e&((b&c)|(g&h)))|(e&~a&((c&d)|(f&g))))");   i++;   transtable[i] = Transition("3a(given 3)", "(a&((b&c)|(g&h)))|(e&((c&d)|(f&g)))");   i++;   transtable[i] = Transition("3c", "~(a|c|e|g)&(b^d^f^h)&((b&d)|(f&h))");   i++;   transtable[i] = Transition("3c(given 3)", "~(a|c|e|g)");   i++;   transtable[i] = Transition("3e", "~(b|d|f|h)&(a^c^e^g)&((a&c)|(e&g))");   i++;   transtable[i] = Transition("3e(given 3)", "~(b|d|f|h)");   i++;   transtable[i] = Transition("3i", "~(b^d^f^h)&~(((a|c)&(e|g))|((a|g)&(c|e)))&((b&~f&((c&d)|(h&a)))|(f&~b&((d&e)|(g&h))))");   i++;   transtable[i] = Transition("3i(given 3)", "(b&((c&d)|(a&h)))|(f&((d&e)|(g&h)))");   i++;   transtable[i] = Transition("3j", "~(a^c^e^g)&(((b^f)&((c&e)^(a&g))&~(d|h))|((d^h)&((e&g)^(a&c))&~(b|f)))");   i++;   transtable[i] = Transition("3j(given 3)", "((b^f)&((c&e)^(a&g)))|((d^h)&((e&g)^(a&c)))");   i++;   transtable[i] = Transition("3k", "~(a^c^e^g)&~(((b|d)&(f|h))|((b|h)&(d|f)))&((a&~e&((c&f)|(d&g)))|(e&~a&((g&b)|(h&c))))");   i++;   transtable[i] = Transition("3k(given 3)", "(a&((c&f)|(d&g)))|(e&((c&h)|(b&g)))");   i++;   transtable[i] = Transition("3n", "~(b^d^f^h)&(((a^e)&((b&d)^(f&h))&~(c|g))|((c^g)&((d&f)^(b&h))&~(a|e)))");   i++;   transtable[i] = Transition("3n(given 3)", "((a^e)&((b&d)^(f&h)))|((c^g)&((d&f)^(b&h)))");   i++;   transtable[i] = Transition("3q", "(a|c|e|g)&~(((a|c)&(e|g))|((a|g)&(c|e)))&~((b^f)|(d^h))&(b^d)");   i++;   transtable[i] = Transition("3q(given 3)", "(b|d|f|h)&~(b^d)&~(d^h)");   i++;   transtable[i] = Transition("3r", "(b|d|f|h)&~(((b|d)&(f|h))|((b|h)&(d|f)))&~((a^e)|(c^g))&(a^c)");   i++;   transtable[i] = Transition("3r(given 3)", "(a|c|e|g)&~(a^e)&~(c^g)");   i++;   transtable[i] = Transition("3y", "~(b^d^f^h)&~(((c|e)&(a|g))|((a|c)&(e|g)))&((b&~f&((d&g)|(e&h)))|(f&~b&((h&c)|(a&d))))");   i++;   transtable[i] = Transition("3y(given 3)", "(b&((d&g)|(e&h)))|(f&((a&d)|(c&h)))");   i++;   transtable[i] = Transition("4", "~(a^b^c^d^e^f^g^h)&((a^b^c^d)&(((a&b)|(c&d))^((e&f)|(g&h)))|(~(a^b^c^d)&((a|b|c)^(e&f&g))&((a&b&c)^(e|f|g))))");   i++;   transtable[i] = Transition("4a", "((a^c)|(c^e)|(e^g))&((b^d)|(d^f)|(f^h))&~(((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))&(a^e)&(c^g)");   i++;   transtable[i] = Transition("4a(given 4)", "~(((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))&(a^e)&(c^g)");   i++;   transtable[i] = Transition("4c", "~(a|c|e|g)&b&d&f&h");   i++;   transtable[i] = Transition("4c(given 4)", "b&d&f&h");   i++;   transtable[i] = Transition("4e", "~(~a|~c|~e|~g)&~b&~d&~f&~h");   i++;   transtable[i] = Transition("4e(given 4)", "~b&~d&~f&~h");   i++;   transtable[i] = Transition("4i", "((a&e)&~((b^d)|(f^h))&(d^f)&~(c|g))|((c&g)&~((d^f)|(b^h))&(b^d)&~(a|e))");   i++;   transtable[i] = Transition("4i(given 4)", "((a&e)&~((b^d)|(f^h))&~c)|((c&g)&~((d^f)|(b^h))&~a)");   i++;   transtable[i] = Transition("4j", "((~b&~f)&((~d&(~a^~g)&~(~c|~e|~h))|((~h&(~c^~e)&~(~a|~d|~g)))))|((~d&~h)&((~b&(~e^~g)&~(~a|~c|~f))|((~f&(~a^~c)&~(~b|~e|~g)))))");   i++;   transtable[i] = Transition("4j(given 4)", "((~b&~f)&((~d&(~a^~g))|((~h&(~c^~e)))))|((~d&~h)&((~b&(~e^~g))|((~f&(~a^~c)))))");   i++;   transtable[i] = Transition("4k", "((a^c)|(c^e)|(e^g))&((b^d)|(d^f)|(f^h))&~(((a^d)|(c^f)|(e^h)|(b^g))&((d^g)|(a^f)|(c^h)|(b^e)))&(a^e)&(c^g)");   i++;   transtable[i] = Transition("4k(given 4)", "~(((a^d)|(c^f)|(e^h)|(b^g))&((d^g)|(a^f)|(c^h)|(b^e)))&(a^e)&(c^g)");   i++;   transtable[i] = Transition("4n", "((b&f)&((d&(c^e)&~(a|g|h))|((h&(a^g)&~(c|d|e)))))|((d&h)&((b&(a^c)&~(e|f|g))|((f&(e^g)&~(a|b|c)))))");   i++;   transtable[i] = Transition("4n(given 4)", "((b&f)&((d&(c^e))|((h&(a^g)))))|((d&h)&((b&(a^c))|((f&(e^g)))))");   i++;   transtable[i] = Transition("4q", "((~b&~f)&~((~c^~e)|(~a^~g))&(~e^~g)&~(~d|~h))|((~d&~h)&~((~e^~g)|(~a^~c))&(~c^~e)&~(~b|~f))");   i++;   transtable[i] = Transition("4q(given 4)", "((~b&~f)&~((~c^~e)|(~a^~g))&d)|((~d&~h)&~((~e^~g)|(~a^~c))&b)");   i++;   transtable[i] = Transition("4r", "((~b&~f)&((~d&(~c^~e)&~(~a|~g|~h))|((~h&(~a^~g)&~(~c|~d|~e)))))|((~d&~h)&((~b&(~a^~c)&~(~e|~f|~g))|((~f&(~e^~g)&~(~a|~b|~c)))))");   i++;   transtable[i] = Transition("4r(given 4)", "((~b&~f)&((~d&(~c^~e))|((~h&(~a^~g)))))|((~d&~h)&((~b&(~a^~c))|((~f&(~e^~g)))))");   i++;   transtable[i] = Transition("4t", "((~a&~e)&~((~b^~d)|(~f^~h))&(~d^~f)&~(~c|~g))|((~c&~g)&~((~d^~f)|(~b^~h))&(~b^~d)&~(~a|~e))");   i++;   transtable[i] = Transition("4t(given 4)", "((~a&~e)&~((~b^~d)|(~f^~h))&c)|((~c&~g)&~((~d^~f)|(~b^~h))&a)");   i++;   transtable[i] = Transition("4w", "((b&f)&~((c^e)|(a^g))&(e^g)&~(d|h))|((d&h)&~((e^g)|(a^c))&(c^e)&~(b|f))");   i++;   transtable[i] = Transition("4w(given 4)", "((b&f)&~((c^e)|(a^g))&~d)|((d&h)&~((e^g)|(a^c))&~b)");   i++;   transtable[i] = Transition("4y", "((b&f)&((d&(a^g)&~(c|e|h))|((h&(c^e)&~(a|d|g)))))|((d&h)&((b&(e^g)&~(a|c|f))|((f&(a^c)&~(b|e|g)))))");   i++;   transtable[i] = Transition("4y(given 4)", "((b&f)&((d&(a^g))|((h&(c^e)))))|((d&h)&((b&(e^g))|((f&(a^c)))))");   i++;   transtable[i] = Transition("4z", "~((a^e)|(b^f)|(c^g)|(d^h))&(a^c)&(b^d)");   i++;   transtable[i] = Transition("4z(given 4)", "~((a^e)|(b^f)|(c^g)|(d^h))&(a^c)&(b^d)");   i++;   transtable[i] = Transition("5", "(~a^~b^~c^~d^~e^~f^~g^~h)&(((~a|~b|~c|~d)&(~e|~f|~g|~h))|((~a|~b|~e|~f)&(~c|~d|~g|~h)))&~(((~a|~b)&(~c|~d)&(~e|~f)&(~g|~h))|(~((~a&~b)^(~c&~d)^(~e&~f)^(~g&~h))&((~a&~b)|(~c&~d)|(~e&~f)|(~g&~h))))");   i++;   transtable[i] = Transition("5a", "~(~a^~c^~e^~g)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&((~a&e&((~b&~c)|(~g&~h)))|(~e&a&((~c&~d)|(~f&~g))))");   i++;   transtable[i] = Transition("5a(given 5)", "(~a&((~b&~c)|(~g&~h)))|(~e&((~c&~d)|(~f&~g)))");   i++;   transtable[i] = Transition("5c", "~(~a|~c|~e|~g)&(~b^~d^~f^~h)&((~b&~d)|(~f&~h))");   i++;   transtable[i] = Transition("5c(given 5)", "~(~a|~c|~e|~g)");   i++;   transtable[i] = Transition("5e", "~(~b|~d|~f|~h)&(~a^~c^~e^~g)&((~a&~c)|(~e&~g))");   i++;   transtable[i] = Transition("5e(given 5)", "~(~b|~d|~f|~h)");   i++;   transtable[i] = Transition("5i", "~(~b^~d^~f^~h)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))&((~b&f&((~c&~d)|(~h&~a)))|(~f&b&((~d&~e)|(~g&~h))))");   i++;   transtable[i] = Transition("5i(given 5)", "(~b&((~c&~d)|(~a&~h)))|(~f&((~d&~e)|(~g&~h)))");   i++;   transtable[i] = Transition("5j", "~(~a^~c^~e^~g)&(((~b^~f)&((~c&~e)^(~a&~g))&~(~d|~h))|((~d^~h)&((~e&~g)^(~a&~c))&~(~b|~f)))");   i++;   transtable[i] = Transition("5j(given 5)", "((~b^~f)&((~c&~e)^(~a&~g)))|((~d^~h)&((~e&~g)^(~a&~c)))");   i++;   transtable[i] = Transition("5k", "~(~a^~c^~e^~g)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&((~a&e&((~c&~f)|(~d&~g)))|(~e&a&((~g&~b)|(~h&~c))))");   i++;   transtable[i] = Transition("5k(given 5)", "(~a&((~c&~f)|(~d&~g)))|(~e&((~c&~h)|(~b&~g)))");   i++;   transtable[i] = Transition("5n", "~(~b^~d^~f^~h)&(((~a^~e)&((~b&~d)^(~f&~h))&~(~c|~g))|((~c^~g)&((~d&~f)^(~b&~h))&~(~a|~e)))");   i++;   transtable[i] = Transition("5n(given 5)", "((~a^~e)&((~b&~d)^(~f&~h)))|((~c^~g)&((~d&~f)^(~b&~h)))");   i++;   transtable[i] = Transition("5q", "(~a|~c|~e|~g)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))&~((~b^~f)|(~d^~h))&(~b^~d)");   i++;   transtable[i] = Transition("5q(given 5)", "(~b|~d|~f|~h)&~(~b^~d)&~(~d^~h)");   i++;   transtable[i] = Transition("5r", "(~b|~d|~f|~h)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&~((~a^~e)|(~c^~g))&(~a^~c)");   i++;   transtable[i] = Transition("5r(given 5)", "(~a|~c|~e|~g)&~(~a^~e)&~(~c^~g)");   i++;   transtable[i] = Transition("5y", "~(~b^~d^~f^~h)&~(((~c|~e)&(~a|~g))|((~a|~c)&(~e|~g)))&((~b&f&((~d&~g)|(~e&~h)))|(~f&b&((~h&~c)|(~a&~d))))");   i++;   transtable[i] = Transition("5y(given 5)", "(~b&((~d&~g)|(~e&~h)))|(~f&((~a&~d)|(~c&~h)))");   i++;   transtable[i] = Transition("6", "~(~a^~b^~c^~d^~e^~f^~g^~h)&(~a|~b|~c|~d|~e|~f|~g|~h)&~(((~a|~b|~c)&(~d|~e|~f)&(~g|~h))|( ~a&~b&~c)|(~d&~e&~f)|((~a|~b|~c)&(~d|~e|~f)&(~(~a^~b^~c)|~(~d^~e^~f)))|(~g&~h&(~a|~b|~c|~d|~e|~f)))");   i++;   transtable[i] = Transition("6a", "(~a|~c|~e|~g)&~((((~a^~b)|(~c^~d)|(~e^~f)|(~g^~h))&((~b^~c)|(~d^~e)|(~f^~g)|(~a^~h)))|(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e))))");   i++;   transtable[i] = Transition("6a(given 6)", "~(((~a^~b)|(~c^~d)|(~e^~f))&((~b^~c)|(~d^~e)|(~f^~g)))");   i++;   transtable[i] = Transition("6c", "~(~a|~c|~e|~g)&(~b^~f)&~(~b^~d^~f^~h)");   i++;   transtable[i] = Transition("6c(given 6)", "~(~a|~c|~e|~g)&(~b^~f)");   i++;   transtable[i] = Transition("6e", "~(~b|~d|~f|~h)&(~a^~e)&~(~a^~c^~e^~g)");   i++;   transtable[i] = Transition("6e(given 6)", "~(~b|~d|~f|~h)&(~a^~e)");   i++;   transtable[i] = Transition("6i", "~(~b|~d|~f|~h)&~((~a^~e)|(~c^~g))&(~a^~c)");   i++;   transtable[i] = Transition("6i(given 6)", "~(~b|~d|~f|~h)&~((~a^~e)|(~c^~g))");   i++;   transtable[i] = Transition("6k", "(~a|~c|~e|~g)&~((((~a^~d)|(~g^~b)|(~e^~h)|(~c^~f))&((~d^~g)|(~b^~e)|(~h^~c)|(~f^~a)))|(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e))))");   i++;   transtable[i] = Transition("6k(given 6)", "~(((~a^~d)|(~g^~b)|(~e^~h))&((~d^~g)|(~b^~e)|(~h^~c)))");   i++;   transtable[i] = Transition("6n", "~(~a|~c|~e|~g)&~((~b^~f)|(~d^~h))&(~b^~d)");   i++;   transtable[i] = Transition("6n(given 6)", "~(~a|~c|~e|~g)&~((~b^~f)|(~d^~h))");   i++;   transtable[i] = Transition("7", "(~a^~b^~c^~d^~e^~f^~g^~h)&~(((~a|~b|~c|~d)&(~e|~f|~g|~h))|((~a|~b|~e|~f)&(~c|~d|~g|~h)))");   i++;   transtable[i] = Transition("7c", "~(~a|~c|~e|~g)&(~b|~d|~f|~h)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))");   i++;   transtable[i] = Transition("7c(given 7)", "~b|~d|~f|~h");   i++;   transtable[i] = Transition("7e", "~(~b|~d|~f|~h)&(~a|~c|~e|~g)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))");   i++;   transtable[i] = Transition("7e(given 7)", "~a|~c|~e|~g");   i++;   transtable[i] = Transition("8", "~(~a|~b|~c|~d|~e|~f|~g|~h)");   rule = argv[1];   file.open("step.c");   if(rule[0] == 'B' || rule[0] == 'b'){      mode = true;      pos++;   }   code += '(';   code += (mode?"~":"");   code += "o&((0x0";   while(pos < rule.length()){      if(mode){         switch(rule[pos]){            case '/':            case '_':            case 'S':            case 's':               code += ")))|(o&((0x0";                mode = false;                num = -1;                pos++;                break;            case '0':            case '1':            case '2':            case '3':            case '4':            case '5':            case '6':            case '7':            case '8':                num = rule[pos] - 0x30;                if(rule[pos+1] == '-'){                    code += ")|(";                    code += search(std::string(1,rule[pos]), transtable);                    sign = false;                   pos += 2;                }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || rule[pos+1] == '/' || rule[pos+1] == '_' || rule[pos+1] == 'S' || rule[pos+1] == 's' || pos == rule.length()-1){                   code += ")|(";                    code += search(std::string(1,rule[pos]), transtable);                    sign = true;                    pos++;                }else{                   code += ")|(0x0";                    sign = true;                   pos++;                }                break;            case 'B':            case 'b':                pos++;                break;            default:                code += (sign?"|(":"&~(");                hack = std::string(1,((char)num+0x30)) + rule[pos];                if(!sign){                   hack += "(given ";                   hack += ((char)num+0x30);                   hack += ')';                }                code += search(hack, transtable);                code += ')';                pos++;         }      }else{         switch(rule[pos]){            case '/':            case '_':            case 'B':            case 'b':               code += ")))|(~o&((0x0";                mode = true;                num = -1;                pos++;                break;            case '0':            case '1':            case '2':            case '3':            case '4':            case '5':            case '6':            case '7':            case '8':                num = rule[pos] - 0x30;                if(rule[pos+1] == '-'){                    code += ")|(";                    code += search(std::string(1,rule[pos]), transtable);                    sign = false;                   pos += 2;                }else if((rule[pos+1] >= '0' && rule[pos+1] <= '9') || rule[pos+1] == '/' || rule[pos+1] == '_' || rule[pos+1] == 'B' || rule[pos+1] == 'b' || pos == rule.length()-1){                   code += ")|(";                    code += search(std::string(1,rule[pos]), transtable);                    sign = true;                    pos++;                }else{                   code += ")|(0x0";                    sign = true;                   pos++;                }                break;            case 'S':            case 's':                pos++;                break;            default:                code += (sign?"|(":"&~(");                hack = std::string(1,((char)num+0x30)) + rule[pos];                if(!sign){                   hack += "(given ";                   hack += ((char)num+0x30);                   hack += ')';                }                code += search(hack, transtable);                code += ')';                pos++;         }      }   }   code += ")));\n\}";   file << code;   //std::cout << std::endl;   return 0;}
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

A for awesome

Posts: 1876
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: zfind discussion

A for awesome wrote:Oops. I fixed that in something else and thought I had fixed it in ntzfind. Here's the patched version of ntzfind-setup.cpp:
<snip>

Thanks.

P.S. Just noticed I swapped 'r' and 'y' in the rulestring for BestFriends above. Oops.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1236
Joined: August 9th, 2013, 12:45 am

### Re: zfind discussion

Here is a small update to zfind that I advertised earlier. It seems to make the search 2% - 9% faster (at least for searches where no ships exist). That's not much (I was hoping for more, honestly), but it might as well be included. The idea is to reorder the rows in the lookup table to reduce the time taken on the lookahead. The rows will be reordered by default. To prevent reordering of the rows, include 'o' as a parameter.

In more detail: every time a potential row is to be added to the current pattern, a small amount of lookahead is performed. This idea is explained in section 6 of David Eppstein's "Searching for Spaceships" article (although zfind does a deeper lookahead than gfind). Essentially, it tries to find a slight extension using the new row. If it finds an extension, then it keeps the row, but if it runs through all possibilities without finding an extension, then it discards the row.

My intention with this update is to run through the possible extensions in a way that if extensions exist they are more likely to be found early on in the lookahead process. What I did was quite simple. As part of building the lookup tables, zfind calculates the results of evolving every possible combination of 3 rows stacked on top of each other (where the result is the single central row that comes from evolving the stack of 3 rows). I reasoned that if a row had more predecessors, then it was more likely to be part of a valid extension. The program counts the number of times each row occurred from advancing 3 rows, and sorts the lookup table so that rows that occurred more often would be searched first in the lookahead process.

Maybe there's a more clever way to order the rows, but I couldn't think of one. Interestingly, this did not seem to improve searches with a horizontal shift. For this reason, I did not include the horizontal shift option in the updated code. There might be a better way to sort the rows for a horizontal shift search, but I haven't thought about it much.

In addition to performing the lookahead, the lookup tables are used to determine the potential new rows to be added to the pattern. Since the rows get reordered, this means that the entire search will be done in a different order. This causes the program to find spaceships at different times than it would without reordering.

For example, the reordering causes the search "zfind p10 k1 w5 v" to take longer to find the copperhead.

Another example: the search "zfind p6 k1 w9 v" now finds the dragon. Without reordering, the search quickly runs into the repeating component from 114P6H1V0.

Here is the updated code:
/* zfind 1.7 (horizontal shift not included in this version)** 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.7 by \"zdr\" and Matthias Merzenich, 13 December 2016"#define FILEVERSION ((unsigned long) 2016121301)  //yyyymmddnn#define MAXPERIOD 30#define MIN_DUMP_PERIOD 1000000#define DEFAULT_DEPTH_LIMIT 2000#define NUM_PARAMS 12#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_REORDER 11#define SYM_ASYM 1#define SYM_ODD 2#define SYM_EVEN 3#define SYM_GUTTER 4int sp[NUM_PARAMS];uint32_t *gInd, *pInd;uint32_t *pRemain;uint32_t *gcount;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 belowunsigned 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;void plong(unsigned long long a){   if(a > 1000000000)printf("%lluM\n", a / 1000000);   else printf("%llu\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 if period == 12, 24, or 30, as then two subperiods** need to be tested (e.g., if period == 12, 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];      }   }}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 sortRows(uint32_t rowSet){   uint32_t totalRows = gInd[rowSet + 1] - gInd[rowSet];   uint16_t *row = &(gRows[gInd[rowSet]]);   uint32_t i;   int64_t j;   uint16_t t;   for(i = 1; i < totalRows; ++i){      t = row[i];      j = i - 1;      while(j >= 0 && gcount[row[j]] < gcount[t]){         row[j+1] = row[j];         --j;      }      row[j+1] = t;   }}void makeTables(){   printf("Building lookup tables.\n");   gInd = malloc(((long long)4 << (width * 3)) + 4);   ev2Rows = malloc((long long)sizeof(*ev2Rows) * (1 << (width * 2)));   gcount = malloc((long long)sizeof(*gcount) * (1 << width));   int i;   int row1,row2,row3,row4;   int rows123,rows124;   int numValid = 0;   for(i = 0; i < 1 << width; ++i) gcount[i] = 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;      ++gcount[row4];      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");      gcount[0] = 0;   if(sp[P_REORDER]){      printf("Sorting table.\n");      for(rows123 = 0; rows123 < 1 << (3 * width); ++rows123){         sortRows(rows123);      }      printf("Table sorted.\n");   }   free(gcount);}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]];   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]]];   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]]];      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]];      for(r[5] = 0; r[5] < r[6]; r[5]++){         r[8] = gRows[r[7] + r[5]];         r[9] = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (r[8] << sp[P_WIDTH]) + r[4];         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]];            r[14] = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (r[13] << sp[P_WIDTH]) + r[8];            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]];               for(r[21] = 0; r[21] < r[17]; r[21]++){                  r[22] = gRows[r[18] + r[21]];                  r[23] = (r[13] << (2 * sp[P_WIDTH])) + (r[22] << sp[P_WIDTH]) + r[20];                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;               }            }         }      }   }   return 0;   _ret1:;   return 1;}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;   unsigned long long i, i2;   int noship = 0;   int totalShips = 0;   r[0] = rowNum;   i = 0;   i2 = 0;   r[5] = 0;   r[6] = 0;   time_t ms = clock();   phase = r[0] % period;   for(;;){      ++i;      if(dumpPeriod){         if(i % dumpPeriod == 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);         }      }      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_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]];      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);      }   }      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_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_REORDER]) printf("Use naive search order.\n");   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("  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("  o    uses naive search order (search will take longer when no ships exist)\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_REORDER] = 1;   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 'o': case 'O': sp[P_REORDER] = 0; 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);      }   }   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;}
-Matthias Merzenich
Sokwe
Moderator

Posts: 1480
Joined: July 9th, 2009, 2:44 pm

### Re: zfind discussion

Is the width limited to 10?
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.
David

Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: zfind discussion

David wrote:Is the width limited to 10?

Yes. A width-11 search would probably require over 80 gigabytes of memory to store the lookup tables. Most people are not going to have that much RAM available, and storing the lookup tables elsewhere is going to slow down the search significantly.
-Matthias Merzenich
Sokwe
Moderator

Posts: 1480
Joined: July 9th, 2009, 2:44 pm

### Re: zfind discussion

Typed "p7 k1 w10 a l65536 s2" and got these partials:
x = 270, y = 40, rule = B3/S232b2o3bo15b2o18b2o18b2o18b2o19bo19bo19bo19bo19bo19bo19bo19bo19bo$bob5o13bo4bo14bo4bo14bo4bo14bo4bo15bo3bo15bo3bo15bo3bo15bo3bo15bo19bo19bo19bo19bo$bo19bo4bo14bo4bo14bo4bo14bo4bo14bo5bo13bo5bo13bo5bo13bo5bo13bo5bo13bo5bo13bo5bo13bo5bo13bo5bo$2b4ob2o12bo4bo14bo4bo14bo4bo13bo2b2obo13bo7bo11bo7bo11bo7bo11bo7bo11bo19bo19bo19bo19bo$5bo94b2ob3ob2o11b2ob3ob2o11b2ob3ob2o11b2ob3ob2o11b2ob3ob2o11b2ob3ob2o11b2ob3ob2o11b2ob3ob2o11b2ob3ob2o$6b2o17bo17bobo17bobo20bo$3bo2bo13b3ob2o17b3ob2o14b3ob2o15bo3bo15bo19bo19bo19bo19bo19bo19bo19bo19bo$2b3ob2o12b3obo2bo14bo3b2o14bo3b2o16b3o16bobo17bob2o15b2obo16b2obo17bobo17bobo17bobo17bobo17bobo$2b2obobo13bobo2b2o13b3ob2o14b3ob2o18bo3bo13bobo17bo2b2o14bo19bo17b2o4bo13b2o4bo13b2o4bo13b2o4bo13b2o4bo$3bo17b2o4b2o12b2o2bo15b2o2bo20bo2bo13b3o17bo4bo14b2o3bo14b2o3bo11b4o3b2o11b4o3b2o11b4o3b2o11b4o3b2o11b4o3b2o$2o2bo16bo3b2obo13b4o16bob2o19b2obo16bo16b2obo18bo3bo15bo3bo15bo3bo15bo3bo15bo3bo15bo3bo15bo3bo$2o2b2obo14b5o16b3o16bo2b4o13b3o21bob2o11b2obo19bob2obo14bob2obo16bo19bo19bo19bo19bo$b2ob2ob2o12bo4bo18b2o16bob4o11b2obo2bo17bo3bo13bo2b3o15b2o18b2o21bo19bo19bo19bo19bo$3o2bobobo11bobobo14b3o21bo3bo12b3obo17bo3bo17b2o16b2o18b2o$2o19bo4bo17b2ob2o13bobo20b2o13bo3bobo18bo20b2o18b2o13b5o15b5o15b5o15b5o15b5o$b2o3b2o14b5o13b2o2b2o16b2obo3bo16b2o12bobo20bo2bo17b4o16b4o13bo19bo19bo19bo19bo$o2bo4bo12bo6bo15b5o17bobo12b2obo2bo14bob3o16bo3bo15b2ob2o15bob2o14bo19bo18bo19bo19bo$4b2o15b3obo2bo12b2ob2o17b2o4bo11bo2b3o15bo2bo14b2o3bobo16b2o16b2obo18b2o18b2o$20bo19bo4bo3bo11b2ob3obo11b2obob2o41bo12b2o2bobo14b2o17bo4bo15bo3bo$62bo2bo14b2ob2o18b4o14b2obo3bo12bo2bo17bo2b2o14b6o16bobobo12b2o3b2o13b2o2bo15b2o2bo$82bo4b2o13bob2ob2o12bo2bob2o13bob2o3bo11b3ob3o18bo16bob2o14b2ob2o2bo12b2obobo14b2obobo$82bo3bobo12b2obo16bo2bo2bo14b3o2bo15bo18bo21bo2bo15b3o17bo2bo16bo2bo$83b5o12bo8bo12b2o4b2o11bo3b2ob2o11bo3b2obo11bobo18b3o41bo19bo$102b2o5bo12bobo3b2o11b4obo15bobo3bo13b2o2b3o12b4obo15b6o13bob2o16bob2o$100bo5b3o11b2o2bob3o13b2o2bo2bo12bo3bobo12b3o2b3o16bo15bo2b2o2bo12bo2bo16bo2bo$126bo15bo4bo15bo3bo14bobo15bo22b2o4bo12bobob2o14bobob2o$120bobo20bobob2o13bo22bo2bo11bo22bobo15b2o3b2o13b2o3b2o$122bob3o13b2obo2bobo11b3ob3obo11b2obo4bo12b3o19b2o2b3o11bo2b2obo16b2obo$140b2o3bo2bo15b2obo12b2ob3ob2o12bo2b5o15bo16b5o14bo2b2obo$162b2ob4o12b2ob2o2b2o10b2obo5bo13bobo16bo2b3o15b2o2bo$162bo21bobo34bo4bob2o12b2o5bo12bo3b2o$200bo8bo11b3o2bo41bo$242b3o16bo6bo$241b4obo14bo5bobo$261bo4bo2bo$262b2o2bo$261b3o2bo2bo$262bo2b2obo$263bob2o$260b3o! This searching is still going on, it has been about 20 hours, and my goal is to find a spaceship other than the loafer. How long time do I need? Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki. David Posts: 212 Joined: November 3rd, 2009, 2:47 am Location: Daejeon, South Korea ### Re: zfind discussion David wrote:Typed "p7 k1 w10 a l65536 s2"... This searching is still going on, it has been about 20 hours, and my goal is to find a spaceship other than the loafer. How long time do I need? It's hard to know how long it will take. It could take only a few days or it could take a month. There is a good chance that the loafer is the only width-10 (1,0)c/7 spaceship. You might have better luck if you search for a gutter ship (use the 'g' parameter instead of 'a'). Also, you should use at least 's3', because your search will find the loafer twice (the second time it will be flipped over the center axis). You should also dump the state periodically (use the 'd' parameter). Then you can restart the search from the saved state. My suggestion is to restart the search with these new parameters. Edit: by the way, I am currently running "zfind B3/S23 p7 k1 w10 u" (odd-symmetric). Edit 2: that last partial gives an extensible pushalong: x = 15, y = 69, rule = B3/S2310bo$8bo$7bo5bo$6bo$6b2ob3ob2o2$10bo$9bobo$6b2o4bo$6b4o3b2o$10bo3bo$12bo$12bo2$7b5o$7bo$6bo4$5b2o3bo$4bo2b3ob2o$4bo6bo$5bobob2o$8bo$6bo3bo$5bo3b2obo$4bo2bo2bob2o$5b3obo$6bo3b2o$6bob3o$8b3o$4bo$4b2o3$5b3o$4b6o$3b7o$2b2o5b2o3$5b3o$3bo2b2o$2b6o$8b4o$4bo3b2o2$4bo2bo$3bo$2bobob2o2$2b2o3$bo5bo$ob2obobo$3obob2o$3bobo$3bo$6bo$b2o3b3o$o5bobo$bob2obobo$2bo$3bob2o$bo3bo$o$2o2bo!
-Matthias Merzenich
Sokwe
Moderator

Posts: 1480
Joined: July 9th, 2009, 2:44 pm

### Re: zfind discussion

1) first new result in c/7 since the original discovery of the loafer! If ever we find a back end for this, we will have a series of c/7 space ships.

2) Your insight clearly shows that it pays off to have a closer look at partials and understand the interactions. To recognize this kind of self supporting pushalong automatically would be one step further!

Congratulations!

Are there other results from zfind searches in B3/S23 I overlooked?
HartmutHolzwart

Posts: 422
Joined: June 27th, 2009, 10:58 am
Location: Germany

PreviousNext