zfind discussion

[wildmyron]

For some reason ntzfind requires some extra padding when doing knight searches:

These comments from Sokwe when the horizontal offset feature was originally introduced are still relevant. https://conwaylife.com/forums/viewtopic ... 891#p35891

It's not possible to see the other phases of the partial but at least one of them would take up the full width of 5 in the second search.

[May13]

When I tried to find a c/3 diagonal spaceship in B3678/S34678 (Day and Night), ntzfind gives it:

Code: Select all

$  ./ntzfind B3678/S34678 p3 k1 x1 w8
ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B3678/S34678 p3 k1 x1 w8
Rule: B3678/S34678
Period: 3
Offset: 1
Width:  8
Symmetry: asymmetric
Horizontal offset: 1
Phase 0 has width 7
Depth limit: 2000
Stop search if a ship is found.
Starting search

..o.....
oooo....
.o.oo...
.o..oo..
..ooo...
....o...
Length: 16
Spaceship found. (1)

Current depth: 2001
Calculations: 32183
CPU time: 0.046000 seconds
Search terminated: spaceship found.

But ntzfind refuses to return a spaceship in B3ai/S2ae3aijr4aiw:

Code: Select all

$  ./ntzfind B3ai/S2ae3aijr4aiw p3 k1 x1 w10
ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B3ai/S2ae3aijr4aiw p3 k1 x1 w10
Rule: B3ai/S2ae3aijr4aiw
Period: 3
Offset: 1
Width:  10
Symmetry: asymmetric
Horizontal offset: 1
Phase 0 has width 9
Depth limit: 2000
Stop search if a ship is found.
Starting search
.o....o...
Length: 2
Search complete: 0 spaceships found.
Calculations: 10803
CPU time: 0.078000 seconds

Though I have this spaceship:

Code: Select all

x = 4, y = 4, rule = B3ai/S2ae3aijr4aiw
3o$o2bo$obo$bo!
[[ TRACK -1/3 -1/3 ]]

Bug or feature?
I'm using Cygwin.

[Sokwe]

ntzfind refuses to return a spaceship in B3ai/S2ae3aijr4aiw...

Though I have this spaceship:

Code: Select all

x = 4, y = 4, rule = B3ai/S2ae3aijr4aiw
3o$o2bo$obo$bo!
[[ TRACK -1/3 -1/3 ]]

Bug or feature?
I'm using Cygwin.

It appears to be a bug of some sort. I believe the problem is in lookAhead(), because if I modify lookAhead() to always return true, then it finds that ship as well as others such as the following:

Code: Select all

x = 5, y = 16, rule = B3ai/S2ae3aijr4aiw
o$2o$b2o3$b3o$o2bo$bobo2$b2o$b3o$b3o2$2bo$2b2o$3b2o!

It's been long enough that I don't really remember how I implemented the horizontal shift, and I was never a fan of the feature in zfind, so I'm not really inclined to hunt this bug down at the moment.

[ihatecorderships]

Is there a precompiled windows version of it?

[yujh]

ntzfind-win-precompiled.rar

Not compiled by me

(82.05 KiB) Downloaded 286 times

Is there a precompiled windows version of it?

[lemon41625]

If I'm not wrong, zfind is able to search for knightships. Does anyone know how the gfind search space is modified in order to allow for these searches?

I was working on implementing oblique / diagonal searches for cfind (unfortunately oblique searches don't work yet), so I'm curious to see how this is implemented in zfind.

[LaundryPizza03]

If I'm not wrong, zfind is able to search for knightships. Does anyone know how the gfind search space is modified in order to allow for these searches?

I was working on implementing oblique / diagonal searches for cfind (unfortunately oblique searches don't work yet), so I'm curious to see how this is implemented in zfind.

zfind searches along the orthogonal direction for knightships. You can find this beginning at line 579 of ntzfind.cpp ("#ifdef KNIGHT"). Paul Tooke's gfind mod includes an implementation of the same, which was used to find the p5 knightship in B3578/S235.

[Sokwe]

If I'm not wrong, zfind is able to search for knightships. Does anyone know how the gfind search space is modified in order to allow for these searches?

I was working on implementing oblique / diagonal searches for cfind (unfortunately oblique searches don't work yet), so I'm curious to see how this is implemented in zfind.

It wasn't particularly clever. When your partial result contains rows A, B, and X, and you're searching for row C such that

Code: Select all

AAAA   evolves into
BBBB ---------------> XXXX
CCCC

just shift row X horizontally by one cell before searching for row C.

As discussed above, I made some mistake in implementing LookAhead() with the horizontal shift. Ultimately, zfind's width limitations meant that this feature was mostly useless anyway, so I removed it. Other programs like ikpx2, LSSS, LLSSS, and even gfind are better. As LaundryPizza03 mentioned above, you're probably better off looking at Paul Tooke's modification of gfind, rather than whatever I wrote for zfind. I think it's the same basic idea.

[dl-rs]

I've made a small alteration on zfind (or ntzfind). Here's the renewed code, with options for RLE format output.
ntzfind.cpp:

Code: Select all

/* ntzfind 3.1
** A spaceship search program by "zdr" with modifications by Matthias Merzenich and Aidan Pierce and Tomas Rokicki
**
** Warning: this program uses a lot of memory (especially for wide searches).
*/

/* define or undef KNIGHT to include knight support */
#define KNIGHT

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <random>
#include "tab.cpp"

#define BANNER "ntzfind 3.0 by \"zdr\", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018"
#define FILEVERSION ((unsigned long) 2016122101)  //yyyymmddnn, same as last qfind release (differs from the above)

#define MAXPERIOD 30
#define MAXWIDTH 10  // increasing this requires a few other changes
#define MIN_DUMP 20
#define DEFAULT_DEPTH_LIMIT 2000
#define NUM_PARAMS 15

#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 P_DUMP 12
#define P_X_OFFSET 13
#define P_KNIGHT_PHASE 14

#define SYM_ASYM 1
#define SYM_ODD 2
#define SYM_EVEN 3
#define SYM_GUTTER 4

const char *rule = "B3/S23" ;

/* get_cpu_time() definition taken from
** http://stackoverflow.com/questions/17432502/how-can-i-measure-cpu-time-and-wall-clock-time-on-both-linux-windows/17440673#17440673
*/

//  Windows
#ifdef _WIN32
#include <Windows.h>
double get_cpu_time(){
    FILETIME a,b,c,d;
    if (GetProcessTimes(GetCurrentProcess(),&a,&b,&c,&d) != 0){
        //  Returns total user time.
        //  Can be tweaked to include kernel times as well.
        return
            (double)(d.dwLowDateTime |
            ((unsigned long long)d.dwHighDateTime << 32)) * 0.0000001;
    }else{
        //  Handle error
        return 0;
    }
}

//  Posix/Linux
#else
double get_cpu_time(){
    return (double)clock() / CLOCKS_PER_SEC;
}
#endif

int nttable[512] ;
long long sp[NUM_PARAMS];
uint16_t **pInd ;
uint16_t **gInd3 ;
long long *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 below
long long *lastNonempty;
unsigned long long dumpPeriod;
long long memusage ;
long long memlimit = 0x7000000000000000LL ;
long long bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;
bool RLE;
long long period, offset, width, rowNum, loadDumpFlag;
long long shipNum, firstFull;
uint16_t fpBitmask = 0;

long long phase, fwdOff[MAXPERIOD], backOff[MAXPERIOD], doubleOff[MAXPERIOD], tripleOff[MAXPERIOD];

void error(const char *s) {
   fprintf(stderr, "%s\n", s) ;
   exit(10) ;
}

void makePhases(){
   long long i;
   for (i = 0; i < period; i++) backOff[i] = -1;
   i = 0;
   for (;;) {
      long long 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++) {
      long long j = (i - fwdOff[i]);
      if (j < 0) j += period;
      doubleOff[i] = fwdOff[i] + fwdOff[j];
   }
   for (i = 0; i <  period; i++){
      long long 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.
*/

long long equivRow[MAXPERIOD];
long long equivRow2[MAXPERIOD];
long long twoSubPeriods = 0;

long long gcd(long long a, long long b){
   long long c;
   while (b){
      c = b;
      b = a % b;
      a = c;
   }
   return a;
}

long long smallestDivisor(long long b){
   long long c = 2;
   while(b % c) ++c;
   return c;
}

void makeEqRows(long long maxFactor, long long a){
   long long tempEquivRow[MAXPERIOD];
   long long 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];
      }
   }
}

char nttable2[512] ;

long long slowEvolveBit(long long row1, long long row2, long long row3, long long bshift){
   return nttable[(((row2>>bshift) & 2)<<7) | (((row1>>bshift) & 2)<<6)
                | (((row1>>bshift) & 4)<<4) | (((row2>>bshift) & 4)<<3)
                | (((row3>>bshift) & 7)<<2) | (((row2>>bshift) & 1)<<1)
                |  ((row1>>bshift) & 1)<<0];
}

void fasterTable() {
   long long p = 0 ;
   for (long long row1=0; row1<8; row1++)
      for (long long row2=0; row2<8; row2++)
         for (long long row3=0; row3<8; row3++)
            nttable2[p++] = slowEvolveBit(row1, row2, row3, 0) ;
}

long long evolveBit(long long row1, long long row2, long long row3, long long bshift) {
   return nttable2[
      (((row1 << 6) >> bshift) & 0700) +
      (((row2 << 3) >> bshift) &  070) +
      (( row3       >> bshift) &   07)] ;
}

long long evolveBit(long long row1, long long row2, long long row3) {
   return nttable2[
      ((row1 << 6) & 0700) +
      ((row2 << 3) &  070) +
      ( row3       &   07)] ;
}

long long evolveRow(long long row1, long long row2, long long row3){
   long long row4;
   long long row1_s,row2_s,row3_s;
   long long j,s = 0;
   if(sp[P_SYMMETRY] == SYM_ODD) s = 1;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[P_SYMMETRY] == SYM_ASYM && evolveBit(row1 << 2, row2 << 2, row3 << 2)) return -1;
   if(sp[P_SYMMETRY] == SYM_ODD || sp[P_SYMMETRY] == SYM_EVEN){
      row1_s = (row1 << 1) + ((row1 >> s) & 1);
      row2_s = (row2 << 1) + ((row2 >> s) & 1);
      row3_s = (row3 << 1) + ((row3 >> s) & 1);
   }
   else{
      row1_s = (row1 << 1);
      row2_s = (row2 << 1);
      row3_s = (row3 << 1);
   }
   row4 = evolveBit(row1_s, row2_s, row3_s);
   for(j = 1; j < width; j++)row4 += evolveBit(row1, row2, row3, j - 1) << j;
   return row4;
}
long long evolveRowHigh(long long row1, long long row2, long long row3, long long bits){
   long long row4=0;
   long long row1_s,row2_s,row3_s;
   long long j ;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   row1_s = (row1 << 1);
   row2_s = (row2 << 1);
   row3_s = (row3 << 1);
   for(j = width-bits; j < width; j++)row4 += evolveBit(row1, row2, row3, j - 1) << j;
   return row4;
}
long long evolveRowLow(long long row1, long long row2, long long row3, long long bits){
   long long row4;
   long long row1_s,row2_s,row3_s;
   long long j,s = 0;
   if(sp[P_SYMMETRY] == SYM_ODD) s = 1;
   if(sp[P_SYMMETRY] == SYM_ASYM && evolveBit(row1 << 2, row2 << 2, row3 << 2)) return -1;
   if(sp[P_SYMMETRY] == SYM_ODD || sp[P_SYMMETRY] == SYM_EVEN){
      row1_s = (row1 << 1) + ((row1 >> s) & 1);
      row2_s = (row2 << 1) + ((row2 >> s) & 1);
      row3_s = (row3 << 1) + ((row3 >> s) & 1);
   }
   else{
      row1_s = (row1 << 1);
      row2_s = (row2 << 1);
      row3_s = (row3 << 1);
   }
   row4 = evolveBit(row1_s, row2_s, row3_s);
   for(j = 1; j < bits; j++)row4 += evolveBit(row1, row2, row3, j - 1) << j;
   return row4;
}

void sortRows(uint16_t *row, uint32_t totalRows) {
   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;
   }
}
uint16_t *makeRow(long long row1, long long row2) ;
uint16_t *getoffset(long long row12) {
   uint16_t *r = gInd3[row12] ;
   if (r == 0)
      r = makeRow(row12 >> width, row12 & ((1 << width) - 1)) ;
   return r ;
}
uint16_t *getoffset(long long row1, long long row2) {
   return getoffset((row1 << width) + row2) ;
}
void getoffsetcount(long long row1, long long row2, long long row3, uint16_t* &p, long long &n) {
   uint16_t *row = getoffset(row1, row2) ;
   p = row + row[row3] ;
   n = row[row3+1] - row[row3] ;
}
long long getcount(long long row1, long long row2, long long row3) {
   uint16_t *row = getoffset(row1, row2) ;
   return row[row3+1] - row[row3] ;
}
long long *gWork ;
long long *rowHash ;
uint16_t *valorder ;
void genStatCounts() ;
void makeTables() {
   gInd3 = (uint16_t **)calloc(sizeof(*gInd3),(1LL<<(width*2))) ;
   rowHash = (long long *)calloc(sizeof(long long),(2LL<<(width*2))) ;
   for (long long i=0; i<1<<(2*width); i++)
      gInd3[i] = 0 ;
   for (long long i=0; i<2<<(2*width); i++)
      rowHash[i] = -1 ;
   ev2Rows = (uint16_t *)calloc(sizeof(*ev2Rows), (1LL << (width * 2)));
   gcount = (uint32_t *)calloc(sizeof(*gcount), (1LL << width));
   memusage += (sizeof(*gInd3)+sizeof(*ev2Rows)+2*sizeof(long long)) << (width*2) ;
   uint32_t i;
   for(i = 0; i < 1 << width; ++i) gcount[i] = 0 ;
   for (long long i=0; i<1<<(2*width); i++)
      ev2Rows[i] = 0 ;
   gWork = (long long *)calloc(sizeof(long long), 3LL << width) ;
   if (sp[P_REORDER] == 1)
      genStatCounts() ;
   if (sp[P_REORDER] == 2) {
      std::mt19937 mt_rand(time(0));
      for (long long i=1; i<1<<width; i++)
         gcount[i] = 1 + (mt_rand() & 0x3fffffff) ;
   }
   if (sp[P_REORDER] == 3)
      for (long long i=1; i<1<<width; i++)
         gcount[i] = 1 + gcount[i & (i - 1)] ;
   gcount[0] = 0 ;
   valorder = (uint16_t *)calloc(sizeof(uint16_t), 1LL << width) ;
   for (long long i=0; i<1<<width; i++)
      valorder[i] = (1<<width)-1-i ;
   if (sp[P_REORDER] != 0)
      sortRows(valorder, 1<<width) ;
   for (long long row2=0; row2<1<<width; row2++)
      makeRow(0, row2) ;
}
uint16_t *bbuf ;
long long bbuf_left = 0 ;
// reduce fragmentation by allocating chunks larger than needed and
// parceling out the small pieces.
uint16_t *bmalloc(long long siz) {
   if (siz > bbuf_left) {
      bbuf_left = 1 << (2 * width) ;
      memusage += 2*bbuf_left ;
      if (memusage > memlimit) {
         printf("Aborting due to excessive memory usage\n") ;
         exit(0) ;
      }
      bbuf = (uint16_t *)calloc(sizeof(uint16_t), bbuf_left) ;
   }
   uint16_t *r = bbuf ;
   bbuf += siz ;
   bbuf_left -= siz ;
   return r ;
}
void unbmalloc(long long siz) {
   bbuf -= siz ;
   bbuf_left += siz ;
}
unsigned long long hashRow(uint16_t *row, long long siz) {
   unsigned long long h = 0 ;
   for (long long i=0; i<siz; i++)
      h = h * 3 + row[i] ;
   return h ;
}
uint16_t *makeRow(long long row1, long long row2) {
   long long good = 0 ;
   long long *gWork2 = gWork + (1 << width) ;
   long long *gWork3 = gWork2 + (1 << width) ;
   if (width < 4) {
      for (long long row3=0; row3<1<<width; row3++)
         gWork3[row3] = evolveRow(row1, row2, row3) ;
   } else {
      long long lowbitcount = (width >> 1) + 1 ;
      long long hibitcount = ((width + 1) >> 1) + 1 ;
      long long hishift = lowbitcount - 2 ;
      long long lowcount = 1 << lowbitcount ;
      for (long long row3=0; row3<1<<lowbitcount; row3++)
         gWork2[row3] = evolveRowLow(row1, row2, row3, lowbitcount-1) ;
      for (long long row3=0; row3<1<<width; row3 += 1<<hishift)
         gWork2[lowcount+(row3>>hishift)] =
                        evolveRowHigh(row1, row2, row3, hibitcount-1) ;
      for (long long row3=0; row3<1<<width; row3++)
         gWork3[row3] = gWork2[row3 & ((1<<lowbitcount) - 1)] |
                        gWork2[lowcount+(row3 >> hishift)] ;
   }
   for (long long row3i = 0; row3i < 1<<width; row3i++) {
      long long row3 = valorder[row3i] ;
      long long row23 = (row2 << width) + row3 ;
      long long row4 = gWork3[row3] ;
      if (row4 < 0)
         continue ;
      if (row1 == 0)
         ev2Rows[row23] = row4 ;
      gWork2[good] = row3 ;
      gWork[good++] = row4 ;
   }
   uint16_t *row = bmalloc((1+(1<<width)+good)) ;
   for (long long row3=0; row3 < 1<<width; row3++)
      row[row3] = 0 ;
   row[0] = 1 + (1 << width) ;
   for (long long row3=0; row3 < good; row3++)
      row[gWork[row3]]++ ;
   row[1<<width] = 0 ;
   for (long long row3=0; row3 < (1<<width); row3++)
      row[row3+1] += row[row3] ;
   for (long long row3=good-1; row3>=0; row3--) {
      long long row4 = gWork[row3] ;
      row[--row[row4]] = gWork2[row3] ;
   }
   unsigned long long h = hashRow(row, 1+(1<<width)+good) ;
   h &= (2 << (2 * width)) - 1 ;
   while (1) {
      if (rowHash[h] == -1) {
         rowHash[h] = (row1 << width) + row2 ;
         break ;
      }
      if (memcmp(row, gInd3[rowHash[h]], 2*(1+(1<<width)+good)) == 0) {
         row = gInd3[rowHash[h]] ;
         unbmalloc(1+(1<<width)+good) ;
         break ;
      }
      h = (h + 1) & ((2 << (2 * width)) - 1) ;
   }
   gInd3[(row1<<width)+row2] = row ;
/*
 *   For debugging:
 *
   printf("R") ;
   for (long long i=0; i<1+(1<<width)+good; i++)
      printf(" %d", row[i]) ;
   printf("\n") ;
   fflush(stdout) ;
 */
   return row ;
}

/*
 *   We calculate the stats using a 2 * 64 << width array.  We use a
 *   leading 1 to separate them.  Index 1 aaa bb cc dd represents
 *   the count for a result of aaa when the last two bits of row1, row2,
 *   and row3 were bb, cc, and dd, respectively.  We have to manage
 *   the edge conditions appropriately.
 */
void genStatCounts() {
   long long *cnt = (long long*)calloc((128 * sizeof(long long)), 1LL << width) ;
   for (long long i=0; i<128<<width; i++)
      cnt[i] = 0 ;
   long long s = 0 ;
   if (sp[P_SYMMETRY] == SYM_ODD)
      s = 2 ;
   else if (sp[P_SYMMETRY] == SYM_EVEN)
      s = 1 ;
   else
      s = width + 2 ;
   // left side: never permit generation left of row4
   for (long long row1=0; row1<2; row1++)
      for (long long row2=0; row2<2; row2++)
         for (long long row3=0; row3<2; row3++)
            if (evolveBit(row1, row2, row3) == 0)
               cnt[(1<<6) + (row1 << 4) + (row2 << 2) + row3]++ ;
   for (long long nb=0; nb<width; nb++) {
      for (long long row1=0; row1<8; row1++)
         for (long long row2=0; row2<8; row2++)
            for (long long row3=0; row3<8; row3++) {
               if (nb == width-1)
                  if ((((row1 >> s) ^ row1) & 1) ||
                      (((row2 >> s) ^ row2) & 1) ||
                      (((row3 >> s) ^ row3) & 1))
                     continue ;
               long long row4b = evolveBit(row1, row2, row3) ;
               for (long long row4=0; row4<1<<nb; row4++)
                  cnt[(((((1<<nb) + row4) << 1) + row4b) << 6) +
                    ((row1 & 3) << 4) + ((row2 & 3) << 2) + (row3 & 3)] +=
                     cnt[(((1<<nb) + row4) << 6) +
                       ((row1 >> 1) << 4) + ((row2 >> 1) << 2) + (row3 >> 1)] ;
            }
   }
   // right side; check left, and accumulate into gcount
   for (long long row1=0; row1<4; row1++)
      for (long long row2=0; row2<4; row2++)
         for (long long row3=0; row3<4; row3++)
            if (sp[P_SYMMETRY] != SYM_ASYM ||
                evolveBit(row1<<1, row2<<1, row3<<1) == 0)
               for (long long row4=0; row4<1<<width; row4++)
                  gcount[row4] +=
                     cnt[(((1<<width) + row4) << 6) +
                       (row1 << 4) + (row2 << 2) + row3] ;
   free(cnt) ;
}

void printInfo(long long currentDepth, unsigned long long numCalcs, double runTime){
   if(currentDepth >= 0) printf("Current depth: %lld\n", currentDepth - 2*period);
   printf("Calculations: ");
   printf("%llu\n", numCalcs);
   printf("CPU time: %f seconds\n",runTime);
   fflush(stdout);
}

#ifdef KNIGHT
long long kshiftb[MAXPERIOD], kshift0[MAXPERIOD], kshift1[MAXPERIOD],
    kshift2[MAXPERIOD], kshift3[MAXPERIOD] ;
void makekshift(long long a){
   long long 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;
   }
}
#endif



void buffPattern(long long theRow){
   long long firstRow = 2 * period;
   if(sp[P_INIT_ROWS]) firstRow = 0;
   long long lastRow;
   long long i, j;
   char *out = buf;
   for(lastRow = theRow - 1; lastRow >= 0; --lastRow)if(pRows[lastRow])break;
   
   for(i = firstRow; i <= lastRow; i += period){
      for(j = width - 1; j >= 0; --j){
         if((pRows[i] >> j) & 1) out += sprintf(out, "o");
         else out += sprintf(out, ".");
      }
      if(sp[P_SYMMETRY] != SYM_ASYM){
         if(sp[P_SYMMETRY] == SYM_GUTTER) out += sprintf(out, ".");
         if(sp[P_SYMMETRY] != SYM_ODD){
            if (pRows[i] & 1) out += sprintf(out, "o");
            else out += sprintf(out, ".");
         }
         for(j = 1; j < width; ++j){
            if((pRows[i] >> j) & 1) out += sprintf(out, "o");
            else out += sprintf(out, ".");
         }
      }
      out += sprintf(out, "\n");
   }
   out += sprintf(out, "Length: %d\n", lastRow - 2 * period + 1);
}

void printPattern() {
   if(RLE){
   printf("x = 0, y = 0, rule = %s\n", rule);
    const char* original_buf = buf; // Keep the original buffer
    std::string processed_buf;      // Temporary buffer to hold the transformed output

    size_t len = strlen(original_buf);
    size_t last_newline_pos = std::string::npos;
    size_t second_last_newline_pos = std::string::npos;

    // Find the positions of the last and second-to-last newline characters
    for (size_t i = 0; i < len; ++i) {
        if (original_buf[i] == '\n') {
            second_last_newline_pos = last_newline_pos;
            last_newline_pos = i;
        }
    }

    // Process the buffer to replace '\n' as specified
    for (size_t i = 0; i < len; ++i) {
        if (i == second_last_newline_pos) {
            processed_buf += "!\n"; // Replace the second-to-last '\n' with "!\n"
        } else if (i == last_newline_pos) {
            processed_buf += '\n'; // Leave the last '\n' unchanged
        } else if (original_buf[i] == '\n') {
            processed_buf += '$'; // Replace other '\n' with '$'
        } else {
            processed_buf += original_buf[i]; // Copy other characters as they are
        }
    }

    // Perform RLE compression for '.' and 'o' characters
    std::string compressed_buf;
    char current_char = '\0';
    int count = 0;

    // Iterate through the processed buffer and perform RLE compression
    for (size_t i = 0; i < processed_buf.size(); ++i) {
        char next_char = processed_buf[i];

        // If it's the same character as the previous one, increment the count
        if (next_char == current_char) {
            count++;
        } else {
            // If we have a count greater than 0, we process the previous character
            if (count > 0 && (current_char == '.' || current_char == 'o')) {
               if(count > 1)
                  compressed_buf += std::to_string(count); // Add the count
                // Compress the characters '.' and 'o' to 'o' and 'b' respectively
                if (current_char == '.') {
                    compressed_buf += 'b'; // '.' becomes 'o'
                } else{
                    compressed_buf += 'o'; // 'o' becomes 'b'
                }
            }
            else {
               compressed_buf.append(count, current_char); // Directly append unchanged chars
            }
            // Reset the counter and update the current character
            current_char = next_char;
            count = 1; // Start counting the new character
        }
    }

    // Append the last character group if count > 0
    if (count > 0) {
        compressed_buf += std::to_string(count); // Add the count

        // Handle the last character group
        if (current_char == '.') {
            compressed_buf += 'o'; // '.' becomes 'o'
        } else if (current_char == 'o') {
            compressed_buf += 'b'; // 'o' becomes 'b'
        } else {
            compressed_buf.append(count, current_char); // Directly append unchanged chars
        }
    }
   compressed_buf.resize(compressed_buf.length() - 2);
   compressed_buf += '\n';
    // Print the compressed result
    printf("%s", compressed_buf.c_str());
   }
   else{
      printf("%s", buf);
   }
    fflush(stdout);
}
long long cachemem = 32 ; // megabytes for the cache
long long cachesize ;
struct cacheentry {
   uint16_t *p1, *p2, *p3 ;
   long long abn, r ;
} *cache ;
long long getkey(uint16_t *p1, uint16_t *p2, uint16_t *p3, long long abn) {
   unsigned long long h = (unsigned long long)p1 +
      17 * (unsigned long long)p2 + 257 * (unsigned long long)p3 +
      513 * abn ;
   h = h + (h >> 15) ;
   h &= (cachesize-1) ;
   struct cacheentry &ce = cache[h] ;
   if (ce.p1 == p1 && ce.p2 == p2 && ce.p3 == p3 && ce.abn == abn)
      return -2 + ce.r ;
   ce.p1 = p1 ;
   ce.p2 = p2 ;
   ce.p3 = p3 ;
   ce.abn = abn ;
   return h ;
}
void setkey(long long h, long long v) {
   cache[h].r = v ;
}
long long lookAhead(long long a){
   long long ri11, ri12, ri13, ri22, ri23;  //indices: first number represents vertical offset, second number represents generational offset
   uint16_t *riStart11, *riStart12, *riStart13, *riStart22, *riStart23;
   long long numRows11, numRows12, numRows13, numRows22, numRows23;
   long long row11, row12, row13, row22, row23;

   getoffsetcount(pRows[a - sp[P_PERIOD] - fwdOff[phase]],
                  pRows[a - fwdOff[phase]],
#ifdef KNIGHT
                  pRows[a] >> kshift0[phase], riStart11, numRows11) ;
#else
                  pRows[a], riStart11, numRows11) ;
#endif
   if (!numRows11)
      return 0 ;
   getoffsetcount(pRows[a - sp[P_PERIOD] - doubleOff[phase]],
                  pRows[a - doubleOff[phase]],
#ifdef KNIGHT
                  pRows[a - fwdOff[phase]] >> kshift1[phase], riStart12, numRows12) ;
#else
                  pRows[a - fwdOff[phase]], riStart12, numRows12) ;
#endif
   
   if(tripleOff[phase] >= sp[P_PERIOD]){
      long long off = a + sp[P_PERIOD] - tripleOff[phase] ;
      if (off < 2 * sp[P_PERIOD]) { // always zero if here
         riStart13 = pRows + off ;
      } else {
         // must *not* point to stack here to keep cache consistent!
         riStart13 = pInd[off] + pRemain[off];
      }
      numRows13 = 1 ;
   } else {
      getoffsetcount(pRows[a - sp[P_PERIOD] - tripleOff[phase]],
                     pRows[a - tripleOff[phase]],
#ifdef KNIGHT
                     pRows[a - doubleOff[phase]] >> kshift2[phase], riStart13, numRows13) ;
#else
                     pRows[a - doubleOff[phase]], riStart13, numRows13) ;
#endif
   }
   long long k = getkey(riStart11, riStart12, riStart13,
#ifdef KNIGHT
    (phase << (2 * width)) +
#endif
    (((pRows[a-doubleOff[phase]] << width) + pRows[a-tripleOff[phase]]) << 1)
        + (numRows13 == 1)) ;
   if (k < 0)
      return k+2 ;
   for(ri11 = 0; ri11 < numRows11; ++ri11){
      row11 = riStart11[ri11];
#ifdef KNIGHT
      if (kshift1[phase] && (row11 & 1))
         continue ;
      row11 >>= kshift1[phase] ;
#endif
      for(ri12 = 0; ri12 < numRows12; ++ri12){
         row12 = riStart12[ri12] ;
#ifdef KNIGHT
         if (kshift2[phase] && (row12 & 1))
            continue ;
         row12 >>= kshift2[phase] ;
#endif
         getoffsetcount(pRows[a - doubleOff[phase]],
                        row12, row11, riStart22, numRows22) ;
         if(!numRows22) continue;
         
         for(ri13 = 0; ri13 < numRows13; ++ri13){
            row13 = riStart13[ri13] ;
#ifdef KNIGHT
            if (kshift3[phase] && (row13 & 1))
               continue ;
            row13 >>= kshift3[phase] ;
#endif
            getoffsetcount(pRows[a - tripleOff[phase]],
                           row13, row12, riStart23, numRows23) ;
            if(!numRows23) continue;
            
            for(ri23 = 0; ri23 < numRows23; ++ri23){
               row23 = riStart23[ri23] ;
               uint16_t *p = getoffset(row13, row23) ;
               for(ri22 = 0; ri22 < numRows22; ++ri22){
                  row22 = riStart22[ri22] ;
#ifdef KNIGHT
                  if (kshift3[phase] && (row22 & 1))
                     continue ;
                  row22 >>= kshift3[phase] ;
#endif
                  if (p[row22+1]!=p[row22]) {
                     setkey(k, 1) ;
                     return 1 ;
                  }
               }
            }
         }
      }
   }
   setkey(k, 0) ;
   return 0;
}

long long dumpNum = 1;
char dumpFile[12];
#define DUMPROOT "dump"
long long dumpFlag = 0; /* Dump status flags, possible values follow */
#define DUMPPENDING (1)
#define DUMPFAILURE (2)
#define DUMPSUCCESS (3)

long long 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(long long v){ // v = rowNum
    printf("Dumping state not supported at the moment.\n") ;
    exit(10) ;
    FILE * fp;
    long long 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,"%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,"%lu\n",(unsigned long) pRows[i]);
    for (i = 2 * period; i <= v; i++){
       fprintf(fp,"%lu\n",(unsigned long) pRows[i]);
// broken       fprintf(fp,"%ld\n", pInd[i]-gInd2);
       fprintf(fp,"%lu\n",(unsigned long) pRemain[i]);
    }
    fclose(fp);
    dumpFlag = DUMPSUCCESS;
}

long long checkInteract(long long a){
   long long 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;
}
/*
 *   Symmetry breaking for asymmetric searches:
 *
 *   Return -1 if bitreverse(v) > v
 *   Return 0 if bitreverse(v) == v
 *   Return 1 if bitreverse(v) < v
 */
long long checkPalindrome(long long v) {
   for (long long i=0; i+i<width; i++) {
      long long t = ((v >> i) & 1) - ((v >> (width - 1 - i)) & 1) ;
      if (t)
         return t ;
   }
   return 0 ;
}
void search(){
   uint32_t currRow = rowNum;    // currRow == index of current row
   long long j;
   unsigned long long calcs, lastLong;
   long long noship = 0;
   long long totalShips = 0;
   calcs = 0;                    // calcs == "calculations" == number of times through the main loop
   uint32_t longest = 0;         // length of the longest partial seen so far
   lastLong = 0;                 // number of calculations at which longest was updated
   long long buffFlag = 0;
   double ms = get_cpu_time();
   phase = currRow % period;
   long long firstasymm = 0 ;
   if (sp[P_SYMMETRY] == SYM_ASYM && sp[P_X_OFFSET] == 0)
      firstasymm = currRow ;
   for(;;){
      ++calcs;
      if(!(calcs & dumpPeriod)){
         dumpState(currRow);
         if(dumpFlag == DUMPSUCCESS) printf("State dumped to file %s%04d\n",DUMPROOT,dumpNum - 1);
         else printf("Dump failed\n");
         fflush(stdout);
      }
      if(currRow > longest || !(calcs & 0xffffff)){
         if(currRow > longest){
            buffPattern(currRow);
            longest = currRow;
            buffFlag = 1;
            lastLong = calcs;
         }
         if((buffFlag && calcs - lastLong > 0xffffff) || !(calcs & 0xffffffff)){
            if(!(calcs & 0xffffffff)) buffPattern(currRow);
            printPattern();
            printInfo(currRow,calcs,get_cpu_time()-ms);
            buffFlag = 0;
         }
      }
      if(!pRemain[currRow]){
         if(shipNum && lastNonempty[shipNum] == currRow) --shipNum;
         --currRow;
         if(phase == 0) phase = period;
         --phase;
         if(sp[P_FULL_PERIOD] && firstFull == currRow) firstFull = 0;
         if(currRow < 2 * sp[P_PERIOD]){
            printPattern();
            if(totalShips == 1)printf("Search complete: 1 spaceship found.\n");
            else printf("Search complete: %d spaceships found.\n",totalShips);
            printInfo(-1,calcs,get_cpu_time() - ms);
            return;
         }
         continue;
      }
      --pRemain[currRow];
      pRows[currRow] = pInd[currRow][pRemain[currRow]];
#ifdef KNIGHT
      if (sp[P_X_OFFSET] && phase == sp[P_KNIGHT_PHASE] && pRows[currRow] & 1)
         continue ;
#endif
      if (currRow <= firstasymm) {
         long long palin = checkPalindrome(pRows[currRow]) ;
         if (palin < 0)
            continue ;
         if (palin == 0)
            firstasymm = currRow + 1 ;
         else
            firstasymm = currRow ;
      }
      if(sp[P_MAX_LENGTH] && currRow > sp[P_MAX_LENGTH] + 2 * period - 1 && pRows[currRow] != 0) continue;  //back up if length exceeds max length
      if(sp[P_FULL_PERIOD] && currRow > sp[P_FULL_PERIOD] && !firstFull && pRows[currRow]) continue;        //back up if not full period by certain length
      if(sp[P_FULL_WIDTH] && (pRows[currRow] & fpBitmask)){
         if(equivRow[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow[phase]]){
            if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow2[phase]])) continue;
         }
      }
      if(shipNum && currRow == lastNonempty[shipNum] + 2*period && !checkInteract(currRow)) continue;       //back up if new rows don't interact with ship
      if(!lookAhead(currRow)) continue ;
      if(sp[P_FULL_PERIOD] && !firstFull){
         if(equivRow[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow[phase]]){
            if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow2[phase]])) firstFull = currRow;
         }
      }
      ++currRow;
      ++phase;
      if(phase == period) phase = 0;
      if(currRow > sp[P_DEPTH_LIMIT]){
         noship = 0;
         for(j = 1; j <= 2 * period; ++j) noship |= pRows[currRow-j];
         if(!noship){
            if(!sp[P_FULL_PERIOD] || firstFull){
               printf("\n");
               printPattern();
               ++totalShips;
               printf("Spaceship found. (%d)\n\n",totalShips);
               printInfo(currRow,calcs,get_cpu_time() - ms);
               --sp[P_NUM_SHIPS];
               fflush(stdout) ;
            }
            ++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] = currRow - 1; lastNonempty[shipNum] >= 0; --lastNonempty[shipNum]) if(pRows[lastNonempty[shipNum]]) break;
            currRow = lastNonempty[shipNum] + 2 * period;
            phase = currRow % period;
            longest = lastNonempty[shipNum];
            continue;
         }
         else{
            printPattern();
            printf("Search terminated: depth limit reached.\n");
            printf("Depth: %d\n", currRow - 2 * period);
            if(totalShips == 1)printf("1 spaceship found.\n");
            else printf("%d spaceships found.\n",totalShips);
         }
         printInfo(currRow,calcs,get_cpu_time() - ms);
         return;
      }
      getoffsetcount(pRows[currRow - 2 * period],
                     pRows[currRow - period],
#ifdef KNIGHT
                     pRows[currRow - period + backOff[phase]] >> kshiftb[phase],
#else
                     pRows[currRow - period + backOff[phase]],
#endif
                     pInd[currRow], pRemain[currRow]) ;
   }
}

char * loadFile;

void loadFail(){
   printf("Load from file %s failed\n",loadFile);
   exit(1);
}

signed long long loadInt(FILE *fp){
   signed long long v;
   if (fscanf(fp,"%d\n",&v) != 1) loadFail();
   return v;
}

long long loadUL(FILE *fp){
   long long v;
   if (fscanf(fp,"%lld\n",&v) != 1) loadFail();
   return v;
}

void loadState(char * cmd, char * file){
   printf("Loading state not supported at the moment.\n") ;
   exit(10) ;
   FILE * fp;
   long long 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);

   firstFull = loadInt(fp);
   shipNum = loadInt(fp);
   lastNonempty = (long long *)calloc(sizeof(long long), (sp[P_DEPTH_LIMIT]/10));
   for (i = 1; i <= shipNum; i++)
      lastNonempty[i] = loadUL(fp);
   rowNum = loadInt(fp);
   
   if(sp[P_DUMP] > 0){
      if(sp[P_DUMP] < MIN_DUMP) sp[P_DUMP] = MIN_DUMP;
      dumpPeriod = ((long long)1 << sp[P_DUMP]) - 1;
   }
   
   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);
      }
   }
   if (sp[P_X_OFFSET]) sp[P_SYMMETRY] = SYM_ASYM ;
   sp[P_KNIGHT_PHASE] %= period ;
   
   pRows = (uint16_t *)calloc(1+sp[P_DEPTH_LIMIT], sizeof(uint16_t));
   pInd = (uint16_t **)calloc(1+sp[P_DEPTH_LIMIT], sizeof(uint16_t *));
   pRemain = (long long *)calloc(1+sp[P_DEPTH_LIMIT], sizeof(long long));
   
   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);
// broken      pInd[i]    = loadUL(fp) + gInd2 ;
      pRemain[i] = (uint32_t) loadUL(fp);
   }
   fclose(fp);
   
   if(!strcmp(cmd,"p") || !strcmp(cmd,"P")){
      buffPattern(rowNum);
      printPattern();
      exit(0);
   }
}

void loadInitRows(char * file){
   FILE * fp;
   long long i,j;
   char rowStr[MAXWIDTH];
   
   loadFile = file;
   fp = fopen(loadFile, "r");
   if (!fp) loadFail();
   
   for(i = 0; i < 2 * period; i++){
      if (fscanf(fp,"%s",rowStr) != 1)
         error("! early end on file when reading initial rows") ;
      for(j = 0; j < width; j++){
         pRows[i] |= ((rowStr[width - j - 1] == '.') ? 0:1) << j;
      }
   }
   fclose(fp);
}

void initializeSearch(char * file){
   long long i;
   if(sp[P_DUMP] > 0){
      if(sp[P_DUMP] < MIN_DUMP) sp[P_DUMP] = MIN_DUMP;
      dumpPeriod = ((long long)1 << sp[P_DUMP]) - 1;
   }
   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 = (uint16_t *)calloc(1+sp[P_DEPTH_LIMIT], sizeof(uint16_t));
   pInd = (uint16_t **)calloc(1+sp[P_DEPTH_LIMIT], sizeof(uint16_t *));
   pRemain = (long long *)calloc(1+sp[P_DEPTH_LIMIT], sizeof(long long));
   lastNonempty = (long long *)calloc(sizeof(long long), (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(){
   long long i,j;
   printf("Rule: %s\n", rule) ;
   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");
   else printf("Stop search if %d ships are found.\n",sp[P_NUM_SHIPS]);
   if(sp[P_DUMP])printf("Dump period: 2^%d\n",sp[P_DUMP]);
   if(!sp[P_REORDER]) printf("Use naive search order.\n");
   if (sp[P_REORDER] == 2) printf("Use randomized search order.\n");
   if (sp[P_REORDER] == 3) printf("Use min population 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");
#ifdef KNIGHT
   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");
#endif
   printf("  dNN  dumps the search state every 2^NN calculations (minimum: %d)\n",MIN_DUMP);
   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("  r    uses randomized search order\n") ;
   printf("  n    uses popcount search order\n") ;
   printf("  z    uses RLE output\n") ;
   printf("  y    uses standard text output (default)\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");
   printf("  RNNN restricts memory usage to NNN megabytes\n") ;
   printf("  CNNN uses about NNN megabytes for lookahead cache\n") ;
   
}

int main(int argc, char *argv[]){
   printf("%s\n", BANNER) ;
   printf("-") ;
   for (long long i=0; i<argc; i++)
      printf(" %s", argv[i]) ;
   printf("\n") ;
   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;
   sp[P_DUMP] = 0;
   sp[P_X_OFFSET] = 0 ;
   sp[P_KNIGHT_PHASE] = 0 ;
   loadDumpFlag = 0;
   dumpPeriod = 0xffffffffffffffff;  // default dump period is 2^64, so the state will never be dumped
   long long dumpandexit = 0;
   long long skipNext = 0;
   long long div1,div2;
   long long s;
   if(argc == 2 && !strcmp(argv[1],"c")){
      usage();
      return 0;
   }
   const char *err ;
   parseRule(rule, nttable) ; // pick up default rule
   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;
         }
         long long sshift ;
         switch(argv[s][0]){
            case 'b': case 'B':     //read rule
               rule = argv[s] ;
               err = parseRule(argv[s], nttable) ;
               if (err != 0) {
                  fprintf(stderr, "Failed to parse rule %s\n", argv[s]) ;
                  exit(10) ;
               }
            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], "%d", &sp[P_DUMP]); 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;
            case 'r':           sp[P_REORDER] = 2; break;
            case 'x': case 'X': sscanf(&argv[s][1], "%d", &sp[P_X_OFFSET]); break;
            case 'N': sscanf(&argv[s][1], "%d", &sp[P_KNIGHT_PHASE]); break;

            case 'n':           sp[P_REORDER] = 3; break;
            case 'R': sscanf(&argv[s][1], "%lld", &memlimit) ; memlimit <<= 20 ; break ;
            case 'C': sscanf(&argv[s][1], "%d", &cachemem); break ;
            case 'z': case 'Z': RLE = true; break ;
            case 'y': case 'Y': RLE = false; break ;
            default:
               printf("Unrecognized option %s\n", argv[s]) ;
               exit(10) ;
         }
      }
   }
   fasterTable() ;
   cachesize = 32768 ;
   while (cachesize * sizeof(cacheentry) < 550000 * cachemem)
      cachesize <<= 1 ;
   memusage += sizeof(cacheentry) * cachesize ;
   cache = (struct cacheentry *)calloc(sizeof(cacheentry), cachesize) ;
   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();
   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);
      }
   }
#ifdef KNIGHT
   if (sp[P_X_OFFSET])
      makekshift(sp[P_KNIGHT_PHASE]) ;
#endif
   makeTables();                    //make lookup tables for determining successor rows
   if(!loadDumpFlag){               //these initialization steps must be performed after makeTables()
      for (long long i=0; i<sp[P_DEPTH_LIMIT]; i++) {
         pInd[i] = gInd3[0] + gInd3[0][0] ;
         pRemain[i] = 0 ;
      }
      pRemain[2 * period] = gInd3[0][1] - gInd3[0][0] - 1 ;
      pInd[2 * period] = gInd3[0] + gInd3[0][0] ;
      if(sp[P_INIT_ROWS]){
         getoffsetcount(pRows[0], pRows[period], pRows[period+backOff[0]],
                        pInd[2*period], pRemain[2*period]) ;
      }
   }
   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;
   }
   buf = (char *)calloc((2*sp[P_WIDTH] + 4), sp[P_DEPTH_LIMIT]);  // I think this gives more than enough space
   buf[0] = '\0';
   printf("Starting search\n");
   fflush(stdout) ;
   search();
   return 0;
}

tab.cpp is not renewed. The alterations include a small change in the argv analysing and a more advanced print pattern option.

[Sokwe]

I've made a small alteration on zfind (or ntzfind).... The alterations include a small change in the argon analysing and a more advanced print pattern option.

Nice! Did you mean "argument analysing", rather than "argon analysing"? Also, I'm curious to know why you replaced every int with long long.

[dl-rs]

I've made a small alteration on zfind (or ntzfind).... The alterations include a small change in the argon analysing and a more advanced print pattern option.

Nice! Did you mean "argument analysing", rather than "argon analysing"? Also, I'm curious to know why you replaced every int with long long.

About the fact that I replaced every int with long long... well, let's just say that I want to enable it to go deeper and be more effective, but that didn't quite work out. And by the way, I meant 'argv'.

[Disaster16439]

Is there a way to modify ntzfind to use less RAM? I want to search at w11. Or is there a better search program?

[Sokwe]

Is there a way to modify ntzfind to use less RAM? I want to search at w11. Or is there a better search program?

Modifying ntzfind to use less RAM would require some major changes to how the lookup tables work, so it's not trivial. Any such modification I can think of would likely slow the search down substantially.

As for a better program, it depends on the search. For periods up to 4 or 5, LLSSS is faster and uses less RAM. ikpx2 uses less RAM than both LLSSS and ntzfind, although it's generally slower for equivalent searches. However, it's has features like floating rows and symmetry switching that allow it to cover a unique search space and sometimes find spaceships faster than ntzfind or LLSSS would.

There is also qfind, which is basically a multi-threaded, breadth-first version of ntzfind. It uses the same amount of RAM as ntzfind, but it's faster (due to multi-threadings), finds shorter ships first (due to breadth-first search ordering), and doesn't get stuck on repeating components (due to row hashing). qfind requires a C compiler with OpenMP support. On Windows, I suggest compiling with gcc under Windows Subsystem for Linux. There is also a precompiled Windows executable if that works better for you. On Mac, you need to install gcc through Homebrew and then use the versioned gcc command to compile qfind as described here.

[TheWayOfTheCon]

Is there a command to see all the usable parameters for the program? Or is there a list somewhere?

[Sokwe]

Is there a command to see all the usable parameters for the program? Or is there a list somewhere?

Run ntzfind with "c" as the only parameter.

[Disaster16439]

Is there a way to modify ntzfind to use less RAM? I want to search at w11. Or is there a better search program?

Modifying ntzfind to use less RAM would require some major changes to how the lookup tables work, so it's not trivial. Any such modification I can think of would likely slow the search down substantially.

As for a better program, it depends on the search. For periods up to 4 or 5, LLSSS is faster and uses less RAM. ikpx2 uses less RAM than both LLSSS and ntzfind, although it's generally slower for equivalent searches. However, it's has features like floating rows and symmetry switching that allow it to cover a unique search space and sometimes find spaceships faster than ntzfind or LLSSS would.

There is also qfind, which is basically a multi-threaded, breadth-first version of ntzfind. It uses the same amount of RAM as ntzfind, but it's faster (due to multi-threadings), finds shorter ships first (due to breadth-first search ordering), and doesn't get stuck on repeating components (due to row hashing). qfind requires a C compiler with OpenMP support. On Windows, I suggest compiling with gcc under Windows Subsystem for Linux. There is also a precompiled Windows executable if that works better for you. On Mac, you need to install gcc through Homebrew and then use the versioned gcc command to compile qfind as described here.

If I understand correctly, zfind doesn’t use lookup tables, so doesn’t use as much RAM. If I modified zfind specifically for my rule without lookup tables, would that work?

[Sokwe]

If I understand correctly, zfind doesn’t use lookup tables, so doesn’t use as much RAM. If I modified zfind specifically for my rule without lookup tables, would that work?

zfind does use lookup tables. Very large ones, in fact. qfind and Tom's ntzfind use much smaller lookup tables than the original zfind while also being faster. Unfortunately, the most obvious ways to modify ntzfind or qfind to use less memory would also likely make them quite a bit slower. However, that trade off might be worth it for some searches. I intend to try making such a modification for qfind someday, but I'm extremely busy with other work at the moment.