ConwayLife.com

Posted: **March 21st, 2016, 3:13 pm**

What script? CopperSearch? zdr made zfind...

Posted: **March 22nd, 2016, 3:53 am**

When I run zfind, I IMMEDIATELY get

15
o.....
.o.oo.
...oo.
..o.o.
.oo...
o.oo..
.o....
...o..
...o..
......
oooo..
...oo.
......
44
501
done
1517
0

What??

Posted: **March 22nd, 2016, 4:34 am**

Saka wrote:When I run zfind, I IMMEDIATELY get...

The default settings for zfind cause it to find the turtle. If you want to find anything else, you will need to input alternative parameters.

For example, running

Code: Select all

zfind b3s23 p10 k1 w5 v

will search for a 1c/10 orthogonal even-width symmetric spaceship with search-width 5 in B3/S23. To get odd-width symmetry, gutter symmetry, and asymmetry, replace "v" with "u", "g", or "a" respectively.

Posted: **March 22nd, 2016, 4:48 am**

Sokwe wrote:
Saka wrote:When I run zfind, I IMMEDIATELY get...
The default settings for zfind cause it to find the turtle. If you want to find anything else, you will need to input alternative parameters.

For example, running
Code: Select all
zfind b3s23 p10 k1 w5 v
will search for a 1c/10 orthogonal even-width symmetric spaceship with search-width 5 in B3/S23. To get odd-width symmetry, gutter symmetry, and asymmetry, replace "v" with "u", "g", or "a" respectively.

Err....

Code: Select all

0
o....
..o..
...o.
....o
o...o
.o...
oo...
.....
.o...
.....
.oo..
.....
...o.
.ooo.
.o..o
160
57
33554432
1373
o....
.o...
.o...
o....
.....
.....
.oo..
.oo..
.....
..oo.
.o..o
.o...
.....
...oo
oo...
...o.
.....
189
50
83886080
3323
o....
oo...
.....
ooo..
oo...
.....
.oo..
.o.oo
.o...
.....
.....
.....
.....
..o..
oo.o.
..oo.
..oo.
o..oo
.....
..o..
...oo
.....
..o..
.o.o.
oooo.
ooo.o
277
151
134217728
5398
o....
oo...
.....
ooo..
oo...
.....
.oo..
.o.oo
.o...
.....
.....
o....
o....
.....
.....
o.o..
.oo..
..o..
..o..
.oo..
.....
.o.o.
o....
.o..o
...o.
.ooo.
...o.
o....
..oo.
oooo.
315
183
318767104
12527
o....
oo...
.....
ooo..
oo...
.....
.oo..
.o.oo
.o...
.....
.....
o....
o....
147
501
done
418530519
16443

Posted: **March 22nd, 2016, 5:21 am**

@Saka
Look at the final pattern output:

Code: Select all

o....
oo...
.....
ooo..
oo...
.....
.oo..
.o.oo
.o...
.....
.....
o....
o....

This is half of copperhead, which has all of the properties I mentioned in my previous post (1c/10 orthogonal, even-width symmetric, etc.).

Posted: **March 22nd, 2016, 5:56 am**

Sokwe wrote:@Saka
Look at the final pattern output:
Code: Select all
o....
oo...
.....
ooo..
oo...
.....
.oo..
.o.oo
.o...
.....
.....
o....
o....
This is half of copperhead, which has all of the properties I mentioned in my previous post (1c/10 orthogonal, even-width symmetric, etc.).

Oh, so it reports in halves? How strange...

Posted: **March 22nd, 2016, 5:59 am**

Stupid question, but but what does

Code: Select all

Segmentation fault (core dumped)

Mean?

Posted: **March 22nd, 2016, 6:35 am**

It means that the program tried to access memory it hadn't allocated. Try to increase this number and recompile the program.

Code: Select all

   gs = malloc(40000);

Posted: **March 24th, 2016, 4:04 am**

is there a way to make zfind search for diagonal ships or knightships?

Posted: **March 24th, 2016, 5:37 am**

Saka wrote:is there a way to make zfind search for diagonal ships or knightships?

I made a modification that searched for diagonal spaceships using diagonal rows, but it was still limited to small widths (which is especially bad for diagonal ships), and it was slower than WLS at the same widths.

Edit: I don't intend to post the diagonal search code, because its limitations make it useless when compared to WLS.

It should be possible to modify zfind to search for knightships, but some care needs to be taken to make it work nicely. I intend to get to this at some point, but I'm not sure when.

Recently, I've been trying to rewrite the zfind code to be more human-readable. Here is what I have so far (this includes an update that allows searching for spaceships with gcd(period,offset)>1):

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define MAXPERIOD 30

int sp[8], *gb, *gl, *gs;
int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;

int rule, period, offset, width;

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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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");
   gb = malloc((long)8 << (width * 3));
   int i;
   int total_rows;
   int row1,row2,row3,row4;
   int rows123,rows124;
   int num_valid = 0;
   for(i = 0; i < 1 << (3 * width); i++)gb[2 * 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;
      gb[2 * (rows123 - row3 + row4)]++;
      num_valid++;
   }
   gl = malloc(4 * num_valid);
   total_rows = 0;
   for(rows123 = 0; rows123 < 1 << (3 * width); rows123++){
      total_rows += gb[2 * rows123];
      gb[2 * rows123 + 1] = total_rows;
   }
   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;
      gb[2 * rows124 + 1]--;
      gl[gb[2 * rows124 + 1]] = row3;
   }
   printf("Lookup tables built.\n");
}

void u1_0(int a, int b){
   int r[10];
   char *out = buf;
   if(b){
      printf("%s", buf);
      return;
   }
   for(r[2] = a - 1; r[2] >= 0; r[2]--)if(gs[4 * r[2] + 2])break;
   for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; r[1]++){
         if((gs[4 * r[0] + 2] >> r[1]) & 1)out += sprintf(out, "o");
         else out += sprintf(out, ".");
      }
      out += sprintf(out, "\n");
   }
   out += sprintf(out, "%d\n", r[2]);
}

int u1_1(int a){
   int r[30];
   r[2] = (gs[4 * (a - sp[2] - fwdOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - fwdOff[phase]) + 2] << sp[1]);
   r[3] = gb[2 * (r[2] + gs[4 * a + 2])];
   if(!r[3])return 0;
   r[1] = gb[2 * (r[2] + gs[4 * a + 2]) + 1];
   r[2] = (gs[4 * (a - sp[2] - doubleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - doubleOff[phase]) + 2] << sp[1]);
   r[6] = gb[2 * (r[2] + gs[4 * (a - fwdOff[phase]) + 2])];
   r[7] = gb[2 * (r[2] + gs[4 * (a - fwdOff[phase]) + 2]) + 1];
   if(tripleOff[phase] >= sp[2]){
      r[10] = 1;
      r[11] = gs[4 * (a + sp[2] - tripleOff[phase]) + 1] + gs[4 * (a + sp[2] - tripleOff[phase])];
   }
   else{
      r[2] = (gs[4 * (a - sp[2] - tripleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - tripleOff[phase]) + 2] << sp[1]);
      r[10] = gb[2 * (r[2] + gs[4 * (a - doubleOff[phase]) + 2])];
      r[11] = gb[2 * (r[2] + gs[4 * (a - doubleOff[phase]) + 2]) + 1];
   }
   for(r[0] = 0; r[0] < r[3]; r[0]++){
      r[4] = gl[r[1] + r[0]];
      for(r[5] = 0; r[5] < r[6]; r[5]++){
         r[8] = gl[r[7] + r[5]];
         r[9] = (gs[4 * (a - doubleOff[phase]) + 2] << (2 * sp[1])) + (r[8] << sp[1]) + r[4];
         if(!gb[2 * r[9]])continue;
         r[15] = gb[2 * r[9]];
         r[16] = gb[2 * r[9] + 1];
         for(r[12] = 0; r[12] < r[10]; r[12]++){
            r[13] = gl[r[11] + r[12]];
            r[14] = (gs[4 * (a - tripleOff[phase]) + 2] << (2 * sp[1])) + (r[13] << sp[1]) + r[8];
            if(!gb[2 * r[14]])continue;
            r[17] = gb[2 * r[14]];
            r[18] = gb[2 * r[14] + 1];
            for(r[19] = 0; r[19] < r[15]; r[19]++){
               r[20] = gl[r[16] + r[19]];
               for(r[21] = 0; r[21] < r[17]; r[21]++){
                  r[22] = gl[r[18] + r[21]];
                  r[23] = (r[13] << (2 * sp[1])) + (r[22] << sp[1]) + r[20];
                  if(gb[2 * r[23]])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

void u1(){
   int r[10];
   long i, i2;
   gs = malloc(40000);
   buf = malloc(1000000);
   buf[0] = '\0';
   r[0] = 2 * sp[2];
   for(r[1] = 0; r[1] < r[0]; r[1]++)gs[4 * r[1] + 2] = 0;
   gs[4 * r[0]] = gb[0] - 1;
   gs[4 * r[0] + 1] = gb[1];
   i = 0;
   i2 = 0;
   r[5] = 0;
   r[6] = 0;
   time_t ms = clock();
   phase = r[0] % period;
   for(;;){
      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(!gs[4 * r[0]]){
         r[0]--;
         phase = r[0] % period;
         if(r[0] < 2 * sp[2]){
            u1_0(r[0], 1);
            printf("Search complete: no spaceships found.\n");
            plong(i);
            return;
         }
         continue;
      }
      gs[4 * r[0]]--;
      gs[4 * r[0] + 2] = gl[gs[4 * r[0] + 1] + gs[4 * r[0]]];
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         u1_0(0, 1);
         int noship = 0;
         int j;
         for(j = 1; j <= 2*sp[2]; j++) noship += gs[4*(r[0]-j)+2];
         if(!noship) printf("Spaceship found.\n");
         else{
            printf("Search terminated: depth limit reached.\n");
            printf("Depth: %d\n", r[0]);
         }
         plong(i);
         return;
      }
      r[4] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + backOff[phase]) + 2];
      gs[4 * r[0]] = gb[2 * r[4]];
      gs[4 * r[0] + 1] = gb[2 * r[4] + 1];
   }
}

int main(int argc, char *argv[]){
   sp[0] = 6152;  //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;     //width
   sp[2] = 3;     //period
   sp[3] = 1;     //offset
   sp[4] = 2000;  //depth limit
   sp[5] = 0;     //asymmetry flag
   sp[6] = 0;     //symmetry flag
   sp[7] = 1;     //currently unused
   int s;
   for(s = 1; s < argc; s++){    //read input parameters
      switch(argv[s][0]){
         case 'b': case 'B':     //read rule
            sp[0] = 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[0] += 1 << (sshift + rnum - '0');
            }
         break;
         case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
         case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
         case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
         case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
         case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
         case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
         case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
         case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
      }
   }
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   time_t ms = clock();
   makePhases();        //make phase tables for determining successor row indices
   makeTables();
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}

So far, I have only rewritten the functions that set up the search (and I want to make some more changes to makeTables()). I still need to rewrite the functions u1, u1_0, and u1_1. I also need to add comments.

Please report any bugs you find.

Known issues:

Can't search for ships in rules with B0
Can't search for ships traveling faster than c/2 (e.g., in rules with B2). The fix for this shouldn't be difficult. I might get around to it eventually, but it isn't very important, since gfind should be sufficient for such searches.

There are other features that I want to add, such as save-load and extending partials. These shouldn't be complicated, but I'm not sure when I'll get to them.

Posted: **March 24th, 2016, 5:49 am**

Sokwe wrote: I made a modification that searched for diagonal spaceships using diagonal rows, but it was still limited to small widths (which is especially bad for diagonal ships), and it was slower than WLS at the same widths.

.........
Code: Select all
Lotsa code
.........

Is that the slower than WLS version, or an updated, faster version?

Posted: **March 24th, 2016, 5:56 am**

Saka wrote:Is that the slower than WLS version, or an updated, faster version?

The code I posted does not include the diagonal search feature.

The algorithm used in zfind seems to be inherently slower than WLS when applied to a diagonal search. gfind also seems to be slower than WLS for diagonal ships. I'm not exactly sure why this is.

Posted: **March 25th, 2016, 7:28 am**

Scorbie wrote:Long time no see! My congrats and appreciations to zdr with all the copper thingies and the script!
One question: Is zfind similar to gsearch? (Brute force searching?) How does it work? I see that the code is pretty short.

Edit: okay, I see it's a dfs but how is it different from WLS, for instance?

I guess it limits the number of unknown cells?

Question: Can't this be modified to search for small p9+ oscillators? If it can search for p10 spaceships, why can't it search for oscs (With stators to shrink the search space even more?)

Posted: **March 25th, 2016, 7:47 am**

Scorbie wrote:Can't this be modified to search for small p9+ oscillators? If it can search for p10 spaceships, why can't it search for oscs (With stators to shrink the search space even more?)

The search works essentially like gfind. This means that spaceships are searched for row-by-row, and the order that the rows are stored in is based on the movement of the ship. I'm not sure how well this could be modified to search for oscillators. A place to look might be ofind.c.

Edit: a direct adaptation of zfind to search for oscillators probably wouldn't work. Since zfind is a depth-first search, it would quickly find a small still life or p2 oscillator and terminate. rewriting zfind to be breadth-first would probably be necessary.

Posted: **May 2nd, 2016, 6:30 am**

Sokwe wrote:Edit: a direct adaptation of zfind to search for oscillators probably wouldn't work. Since zfind is a depth-first search, it would quickly find a small still life or p2 oscillator and terminate. rewriting zfind to be breadth-first would probably be necessary.

WLS uses dfs and it can find oscs very well. I think we only need to tweak these two things:
1) Reverse the loop direction if it loops from an empty row to a full row.
2) If the pattern oscillates at subperiods, continue.

Posted: **June 30th, 2016, 7:23 am**

Extending partial results with zfind

Here I will give a brief description of how to extend partial spaceship results using zfind. I will use this version of zfind as the base code.

Start with the code posted here.

In the unmodified code, lines 177 - 179 should read

Code: Select all

   for(r[1] = 0; r[1] < r[0]; r[1]++)gs[4 * r[1] + 2] = 0;
   gs[4 * r[0]] = gb[0] - 1;
   gs[4 * r[0] + 1] = gb[1];

Replace lines 177 - 179 with the following:

Code: Select all

   r[1] = 0;
   
   gs[4 * r[1] + 2] = Row[1];   r[1]++;
   gs[4 * r[1] + 2] = Row[2];   r[1]++;
                    .
                    .
                    .
   gs[4 * r[1] + 2] = Row[2p];   r[1]++;
   
   r[4] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + sp[3]) + 2];
   gs[4 * r[0]] = gb[2 * r[4]];
   gs[4 * r[0] + 1] = gb[2 * r[4] + 1];

where Row[1], Row[2], ..., Row[2p] are integers which, when written in binary, represent one row of the pattern in a particular phase. The number of rows to add is twice the period the partial pattern you are trying to extend. The order in which the rows are placed is important, and will be explained later.

In the unmodified code, line 112 should read
Code: Select all
```
   for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
```
Replace line 112 with the following:
Code: Select all
```
   for(r[0] = 0; r[0] <= r[2]; r[0] += sp[2]){
```
This will ensure that the two initial input rows are given in the output patterns.
Compile the program and run it using the correct settings for the desired spaceship.

Finding Row[1], ..., Row[2p]:

For this discussion, let p represent the period of the partial result, and let k represent the offset (the amount the potential spaceship travels in one period). This explanation only works when gcd(p,k) = 1. For now, I suggest that you not try to deal with the other cases.

As an example, we will try to extend the front end of the dragon in order to complete the spaceship with a symmetric search.

To find Row[1], ..., Row[2p], start by orienting the partial result so that it is travelling upwards (the starting phase, or phase 0, of the pattern rarely matters). Now choose a row to start extending from (this row should not be too close to the unfinished end of the partial pattern). To find the binary representation of this row, simply read left-to-right, writing "1" whenever there is an on cell, and "0" whenever there is an off cell. Note that for a symmetric search, Row[1], ..., Row[2p] only represent the left half of the partial result.

As an example, suppose we are trying to extend the front end of the dragon to complete the spaceship. We will start from this phase:

Code: Select all

x = 18, y = 29, rule = B3/S23
5bo6bo$4bobo4bobo$4bobo4bobo$5bo6bo2$4b3o4b3o$4b4o2b4o$7bo2bo$4b3ob2ob
3o$4b2o6b2o$3b2o8b2o2$2bo12bo$o2bo10bo2bo$o2bo10bo2bo2$3b3o6b3o$3bo10b
o$5bo6bo$3b3o6b3o2$6bob2obo$7bo2bo$3bob2ob2ob2obo$3b3o6b3o2$3bobo6bobo
$3bobo6bobo$b3ob3o2b3ob3o!

This gives

Code: Select all

Row[1] = 0b1000

where the prefix "0b" indicates that "1000" is the binary representation of the number (note: some c compilers will allow you to write binary numbers in your code this way, similar to using "0x" for hexadecimal).

The order that the rows are placed is determined by the period (p) and the offset (k), and is explained in David Eppstein's "searching for spaceships" article. The rules for determining the order of the rows are as follows (only works when gcd(p,k)=1):

Code: Select all

Row[i + k] = advance(Row[i - p], Row[i], Row[i + p])
Row[i + p] = the row directly below and in the same phase as Row[i]

where advance(a,b,c) is the single central row resulting from using the evolution rules to advance the stack of 3 rows, a, b, and c. Continuing with our dragon example, Row[2] = Row[1 + k] is the same row as Row[1], but advanced by one generation. Therefore,

Code: Select all

Row[2] = 0b1000

Row[7] = Row[1 + p] is the second row of phase 0:

Code: Select all

row[7] = 0b10100

Notice that it is easy to input the rows when the offset is 1. Start by highlighting your starting row in Golly, and copying it as Row[1]. To find Row[2], keep the first row highlighted, and advance the pattern by 1 generation. The new highlighted row is Row[2]. Advance the pattern again to find Row[3]. Repeat until you have 2p rows. If k > 1 it's a bit more difficult.

For example, the following code extends the front end of the dragon (uses "0b" prefix for binary numbers, which may not be supported by all compilers):

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define MAXPERIOD 30

int sp[8], *gb, *gl, *gs;
int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;

int rule, period, offset, width;

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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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");
   gb = malloc((long)8 << (width * 3));
   int i;
   int total_rows;
   int row1,row2,row3,row4;
   int rows123,rows124;
   int num_valid = 0;
   for(i = 0; i < 1 << (3 * width); i++)gb[2 * 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;
      gb[2 * (rows123 - row3 + row4)]++;
      num_valid++;
   }
   gl = malloc(4 * num_valid);
   total_rows = 0;
   for(rows123 = 0; rows123 < 1 << (3 * width); rows123++){
      total_rows += gb[2 * rows123];
      gb[2 * rows123 + 1] = total_rows;
   }
   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;
      gb[2 * rows124 + 1]--;
      gl[gb[2 * rows124 + 1]] = row3;
   }
   printf("Lookup tables built.\n");
}

void u1_0(int a, int b){
   int r[10];
   char *out = buf;
   if(b){
      printf("%s", buf);
      return;
   }
   for(r[2] = a - 1; r[2] >= 0; r[2]--)if(gs[4 * r[2] + 2])break;
   for(r[0] = 0; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; r[1]++){
         if((gs[4 * r[0] + 2] >> r[1]) & 1)out += sprintf(out, "o");
         else out += sprintf(out, ".");
      }
      out += sprintf(out, "\n");
   }
   out += sprintf(out, "%d\n", r[2]);
}

int u1_1(int a){
   int r[30];
   r[2] = (gs[4 * (a - sp[2] - fwdOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - fwdOff[phase]) + 2] << sp[1]);
   r[3] = gb[2 * (r[2] + gs[4 * a + 2])];
   if(!r[3])return 0;
   r[1] = gb[2 * (r[2] + gs[4 * a + 2]) + 1];
   r[2] = (gs[4 * (a - sp[2] - doubleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - doubleOff[phase]) + 2] << sp[1]);
   r[6] = gb[2 * (r[2] + gs[4 * (a - fwdOff[phase]) + 2])];
   r[7] = gb[2 * (r[2] + gs[4 * (a - fwdOff[phase]) + 2]) + 1];
   if(tripleOff[phase] >= sp[2]){
      r[10] = 1;
      r[11] = gs[4 * (a + sp[2] - tripleOff[phase]) + 1] + gs[4 * (a + sp[2] - tripleOff[phase])];
   }
   else{
      r[2] = (gs[4 * (a - sp[2] - tripleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - tripleOff[phase]) + 2] << sp[1]);
      r[10] = gb[2 * (r[2] + gs[4 * (a - doubleOff[phase]) + 2])];
      r[11] = gb[2 * (r[2] + gs[4 * (a - doubleOff[phase]) + 2]) + 1];
   }
   for(r[0] = 0; r[0] < r[3]; r[0]++){
      r[4] = gl[r[1] + r[0]];
      for(r[5] = 0; r[5] < r[6]; r[5]++){
         r[8] = gl[r[7] + r[5]];
         r[9] = (gs[4 * (a - doubleOff[phase]) + 2] << (2 * sp[1])) + (r[8] << sp[1]) + r[4];
         if(!gb[2 * r[9]])continue;
         r[15] = gb[2 * r[9]];
         r[16] = gb[2 * r[9] + 1];
         for(r[12] = 0; r[12] < r[10]; r[12]++){
            r[13] = gl[r[11] + r[12]];
            r[14] = (gs[4 * (a - tripleOff[phase]) + 2] << (2 * sp[1])) + (r[13] << sp[1]) + r[8];
            if(!gb[2 * r[14]])continue;
            r[17] = gb[2 * r[14]];
            r[18] = gb[2 * r[14] + 1];
            for(r[19] = 0; r[19] < r[15]; r[19]++){
               r[20] = gl[r[16] + r[19]];
               for(r[21] = 0; r[21] < r[17]; r[21]++){
                  r[22] = gl[r[18] + r[21]];
                  r[23] = (r[13] << (2 * sp[1])) + (r[22] << sp[1]) + r[20];
                  if(gb[2 * r[23]])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

void u1(){
   int r[10];
   long i, i2;
   gs = malloc(40000);
   buf = malloc(1000000);
   buf[0] = '\0';
   r[0] = 2 * sp[2];
   r[1] = 0;
   
   gs[4 * r[1] + 2] = 0b1000;   r[1]++;
   gs[4 * r[1] + 2] = 0b1000;   r[1]++;
   gs[4 * r[1] + 2] = 0b1000;   r[1]++;
   gs[4 * r[1] + 2] = 0b1000;   r[1]++;
   gs[4 * r[1] + 2] = 0b1000;   r[1]++;
   gs[4 * r[1] + 2] = 0b11100;   r[1]++;
   gs[4 * r[1] + 2] = 0b10100;   r[1]++;
   gs[4 * r[1] + 2] = 0b10100;   r[1]++;
   gs[4 * r[1] + 2] = 0b10100;   r[1]++;
   gs[4 * r[1] + 2] = 0b10100;   r[1]++;
   gs[4 * r[1] + 2] = 0b110110;   r[1]++;
   gs[4 * r[1] + 2] = 0b11100;   r[1]++;
   
   r[4] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + sp[3]) + 2];
   gs[4 * r[0]] = gb[2 * r[4]];
   gs[4 * r[0] + 1] = gb[2 * r[4] + 1];
   i = 0;
   i2 = 0;
   r[5] = 0;
   r[6] = 0;
   time_t ms = clock();
   phase = r[0] % period;
   for(;;){
      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(!gs[4 * r[0]]){
         r[0]--;
         phase = r[0] % period;
         if(r[0] < 2 * sp[2]){
            u1_0(r[0], 1);
            printf("Search complete: no spaceships found.\n");
            plong(i);
            return;
         }
         continue;
      }
      gs[4 * r[0]]--;
      gs[4 * r[0] + 2] = gl[gs[4 * r[0] + 1] + gs[4 * r[0]]];
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         u1_0(0, 1);
         int noship = 0;
         int j;
         for(j = 1; j <= 2*sp[2]; j++) noship += gs[4*(r[0]-j)+2];
         if(!noship) printf("Spaceship found.\n");
         else{
            printf("Search terminated: depth limit reached.\n");
            printf("Depth: %d\n", r[0]);
         }
         plong(i);
         return;
      }
      r[4] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + backOff[phase]) + 2];
      gs[4 * r[0]] = gb[2 * r[4]];
      gs[4 * r[0] + 1] = gb[2 * r[4] + 1];
   }
}

int main(int argc, char *argv[]){
   sp[0] = 6152;  //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;     //width
   sp[2] = 3;     //period
   sp[3] = 1;     //offset
   sp[4] = 2000;  //depth limit
   sp[5] = 0;     //asymmetry flag
   sp[6] = 0;     //symmetry flag
   sp[7] = 1;     //currently unused
   int s;
   for(s = 1; s < argc; s++){    //read input parameters
      switch(argv[s][0]){
         case 'b': case 'B':     //read rule
            sp[0] = 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[0] += 1 << (sshift + rnum - '0');
            }
         break;
         case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
         case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
         case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
         case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
         case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
         case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
         case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
         case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
      }
   }
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   time_t ms = clock();
   makePhases();        //make phase tables for determining successor row indices
   makeTables();
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}

Compile and run with the settings

Code: Select all

zfind B3/S23 p6 k1 w9 v

Posted: **June 30th, 2016, 11:53 am**

Thanks a lot... I will get back with that after my exams! I think it will help with cracking zfind code

Thanks again!

Posted: **July 1st, 2016, 3:07 pm**

@Sokwe Thanks for sharing! Have you tried to adapt zfind for puffer search?

Posted: **July 1st, 2016, 6:28 pm**

codeholic wrote:Have you tried to adapt zfind for puffer search?

I have not, although I might try it at some point. There are a few issues with the current zfind that make it bad for puffer searches. When looking for puffers (at least with gfind), you usually need to produce a lot of potential puffers, but zfind is not really suited for finding multiple patterns. Also, puffers seem to be more common at higher speeds, and higher speeds generally need wider spaceships. Since zfind can't search above a width of about 10, this makes finding puffers less likely.

Posted: **July 7th, 2016, 6:32 am**

I have updated zfind with two new features.

The memory usage is reduced by roughly 50%. After this update, a width-10 search takes about 6 gigabytes of RAM, which I can (just barely) run on my computer. It also seems to run slightly faster, possibly due to having a larger number of rows per cache line. Unfortunately, getting zfind to work at width-11 would require a minor rewrite and would need more than 10 times as much memory as the width-10 search.
I added a max length parameter, 'm'. If a search reaches a depth equal to the m value without finding a spaceship, then it will back up and continue, causing it to only find spaceships of length less than (approx.) m/period. This differs from the 'l' parameter, which will stop the search if it reaches a depth equal to the l value. The max length could be useful for searches where a repeating component is discovered before a spaceship (e.g., p6 k1 w9 v). Do not use m if you are trying to show that no ships exist at a certain width, as it can skip over long results.

I also made a minor change to how the current depth of the search is calculated (previously, it included the first 2p empty rows).

Here is the updated code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MAXPERIOD 30

int sp[8], *gs;
uint32_t *gInd;
uint16_t *gRows;
int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;

int rule, period, offset, width;

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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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];
   char *out = buf;
   if(b){
      printf("%s", buf);
      return;
   }
   for(r[2] = a - 1; r[2] >= 0; r[2]--)if(gs[4 * r[2] + 2])break;
   for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; r[1]++){
         if((gs[4 * r[0] + 2] >> 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] = (gs[4 * (a - sp[2] - fwdOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - fwdOff[phase]) + 2] << sp[1]);
   r[1] = gInd[r[2] + gs[4 * a + 2]];
   r[3] = gInd[r[2] + gs[4 * a + 2] + 1];
   r[3] = gInd[r[2] + gs[4 * a + 2] + 1] - r[1];
   if(!r[3]) return 0;
   r[2] = (gs[4 * (a - sp[2] - doubleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - doubleOff[phase]) + 2] << sp[1]);
   r[7] = gInd[r[2] + gs[4 * (a - fwdOff[phase]) + 2]];
   r[6] = gInd[r[2] + gs[4 * (a - fwdOff[phase]) + 2] + 1] - r[7];
   
   if(tripleOff[phase] >= sp[2]){
      r[10] = 1;
      r[11] = gs[4 * (a + sp[2] - tripleOff[phase]) + 1] + gs[4 * (a + sp[2] - tripleOff[phase])];
   }
   else{
      r[2] = (gs[4 * (a - sp[2] - tripleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - tripleOff[phase]) + 2] << sp[1]);
      r[11] = gInd[r[2] + gs[4 * (a - doubleOff[phase]) + 2]];
      r[10] = gInd[r[2] + gs[4 * (a - doubleOff[phase]) + 2] + 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] = (gs[4 * (a - doubleOff[phase]) + 2] << (2 * sp[1])) + (r[8] << sp[1]) + 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] = (gs[4 * (a - tripleOff[phase]) + 2] << (2 * sp[1])) + (r[13] << sp[1]) + 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[1])) + (r[22] << sp[1]) + r[20];
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

void u1(){
   int r[10];
   long i, i2;
   gs = malloc(sp[4] * 16);
   buf = malloc(2000000);
   buf[0] = '\0';
   r[0] = 2 * sp[2];
   for(r[1] = 0; r[1] < r[0]; r[1]++)gs[4 * r[1] + 2] = 0;
   gs[4 * r[0]] = gInd[1] - gInd[0] - 1;
   gs[4 * r[0] + 1] = gInd[0];
   i = 0;
   i2 = 0;
   r[5] = 0;
   r[6] = 0;
   time_t ms = clock();
   phase = r[0] % period;
   for(;;){
      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(!gs[4 * r[0]]){
         r[0]--;
         phase = r[0] % period;
         if(r[0] < 2 * sp[2]){
            u1_0(r[0], 1);
            printf("Search complete: no spaceships found.\n");
            plong(i);
            return;
         }
         continue;
      }
      gs[4 * r[0]]--;
      gs[4 * r[0] + 2] = gRows[gs[4 * r[0] + 1] + gs[4 * r[0]]];
      if(sp[7] && r[0] > sp[7] + 2 * period - 1 && gs[4 * r[0] + 2] != 0) continue;
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         u1_0(0, 1);
         int noship = 0;
         int j;
         for(j = 1; j <= 2*sp[2]; j++) noship += gs[4*(r[0]-j)+2];
         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] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + backOff[phase]) + 2];
      gs[4 * r[0]] = gInd[r[4] + 1] - gInd[r[4]];
      gs[4 * r[0] + 1] = gInd[r[4]];
   }
}

int main(int argc, char *argv[]){
   sp[0] = 6152;  //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;     //width
   sp[2] = 3;     //period
   sp[3] = 1;     //offset
   sp[4] = 2000;  //depth limit
   sp[5] = 0;     //asymmetry flag
   sp[6] = 0;     //symmetry flag
   sp[7] = 0;     //maximum length
   int s;
   for(s = 1; s < argc; s++){    //read input parameters
      switch(argv[s][0]){
         case 'b': case 'B':     //read rule
            sp[0] = 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[0] += 1 << (sshift + rnum - '0');
            }
         break;
         case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
         case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
         case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
         case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
         case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
         case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
         case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
         case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
         case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[7]); break;
      }
   }
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   if(sp[7]) sp[4] = sp[7] + 2 * period;
   sp[4] += 2 * period;
   time_t ms = clock();
   makePhases();        //make phase tables for determining successor row indices
   makeTables();
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}

This update changes the instructions for extending partial results slightly. Here are the updated instructions:

Start with the code posted above.

In the unmodified code, lines 178 - 180 should read

Code: Select all

   for(r[1] = 0; r[1] < r[0]; r[1]++)gs[4 * r[1] + 2] = 0;
   gs[4 * r[0]] = gInd[1] - gInd[0] - 1;
   gs[4 * r[0] + 1] = gInd[0];

Replace lines 178 - 180 with the following:

Code: Select all

   r[1] = 0;
   
   gs[4 * r[1] + 2] = Row[1];   r[1]++;
   gs[4 * r[1] + 2] = Row[2];   r[1]++;
                    .
                    .
                    .
   gs[4 * r[1] + 2] = Row[2p];   r[1]++;
   
   r[4] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + sp[3]) + 2];
   gs[4 * r[0]] = gInd[r[4] + 1] - gInd[r[4]];
   gs[4 * r[0] + 1] = gInd[r[4]];

where Row[1], Row[2], ..., Row[2p] are integers which, when written in binary, represent one row of the pattern in a particular phase. See this post for instructions on how to find these rows.

In the unmodified code, line 111 should read
Code: Select all
```
   for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
```
Replace line 111 with the following:
Code: Select all
```
   for(r[0] = 0; r[0] <= r[2]; r[0] += sp[2]){
```
This will ensure that the two initial input rows are given in the output patterns.
Compile the program and run it using the correct settings for the desired spaceship.

Posted: **August 21st, 2016, 10:18 pm**

Off on a tangent from something else I was developing, I made an extremely dirty hack of zfind that allows searching non-totalistic rules. There are three files this time, which you must save in the same directory:

Code: Select all

//Save this as ntzfind.c.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "step.c"

#define MAXPERIOD 30

int sp[8], *gs;
uint32_t *gInd;
uint16_t *gRows;
int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;

int rule, period, offset, width;

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[9], i=0, j=0;
   for(i=0;i<3;i++,j++){r[j]=(row1>>(i+bshift))&1;}
   for(i=0;i<3;i++,j++){r[j]=(row2>>(i+bshift))&1;}
   for(i=0;i<3;i++,j++){r[j]=(row3>>(i+bshift))&1;}
   return stepcell(r[4],r[1],r[2],r[5],r[8],r[7],r[6],r[3],r[0]);
}
/*/   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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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);
      //printf("%i\n", row4);
      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];
   char *out = buf;
   if(b){
      printf("%s", buf);
      return;
   }
   for(r[2] = a - 1; r[2] >= 0; r[2]--)if(gs[4 * r[2] + 2])break;
   for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; r[1]++){
         if((gs[4 * r[0] + 2] >> 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] = (gs[4 * (a - sp[2] - fwdOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - fwdOff[phase]) + 2] << sp[1]);
   r[1] = gInd[r[2] + gs[4 * a + 2]];
   r[3] = gInd[r[2] + gs[4 * a + 2] + 1];
   r[3] = gInd[r[2] + gs[4 * a + 2] + 1] - r[1];
   if(!r[3]) return 0;
   r[2] = (gs[4 * (a - sp[2] - doubleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - doubleOff[phase]) + 2] << sp[1]);
   r[7] = gInd[r[2] + gs[4 * (a - fwdOff[phase]) + 2]];
   r[6] = gInd[r[2] + gs[4 * (a - fwdOff[phase]) + 2] + 1] - r[7];
   
   if(tripleOff[phase] >= sp[2]){
      r[10] = 1;
      r[11] = gs[4 * (a + sp[2] - tripleOff[phase]) + 1] + gs[4 * (a + sp[2] - tripleOff[phase])];
   }
   else{
      r[2] = (gs[4 * (a - sp[2] - tripleOff[phase]) + 2] << (2 * sp[1])) + (gs[4 * (a - tripleOff[phase]) + 2] << sp[1]);
      r[11] = gInd[r[2] + gs[4 * (a - doubleOff[phase]) + 2]];
      r[10] = gInd[r[2] + gs[4 * (a - doubleOff[phase]) + 2] + 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] = (gs[4 * (a - doubleOff[phase]) + 2] << (2 * sp[1])) + (r[8] << sp[1]) + 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] = (gs[4 * (a - tripleOff[phase]) + 2] << (2 * sp[1])) + (r[13] << sp[1]) + 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[1])) + (r[22] << sp[1]) + r[20];
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

void u1(){
   int r[10];
   long i, i2;
   gs = malloc(sp[4] * 16);
   buf = malloc(2000000);
   buf[0] = '\0';
   r[0] = 2 * sp[2];
   for(r[1] = 0; r[1] < r[0]; r[1]++)gs[4 * r[1] + 2] = 0;
   gs[4 * r[0]] = gInd[1] - gInd[0] - 1;
   gs[4 * r[0] + 1] = gInd[0];
   i = 0;
   i2 = 0;
   r[5] = 0;
   r[6] = 0;
   time_t ms = clock();
   phase = r[0] % period;
   for(;;){
      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(!gs[4 * r[0]]){
         r[0]--;
         phase = r[0] % period;
         if(r[0] < 2 * sp[2]){
            u1_0(r[0], 1);
            printf("Search complete: no spaceships found.\n");
            plong(i);
            return;
         }
         continue;
      }
      gs[4 * r[0]]--;
      gs[4 * r[0] + 2] = gRows[gs[4 * r[0] + 1] + gs[4 * r[0]]];
      if(sp[7] && r[0] > sp[7] + 2 * period - 1 && gs[4 * r[0] + 2] != 0) continue;
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         u1_0(0, 1);
         int noship = 0;
         int j;
         for(j = 1; j <= 2*sp[2]; j++) noship += gs[4*(r[0]-j)+2];
         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] = (gs[4 * (r[0] - 2 * sp[2]) + 2] << (2 * sp[1])) + (gs[4 * (r[0] - sp[2]) + 2] << sp[1]) + gs[4 * (r[0] - sp[2] + backOff[phase]) + 2];
      gs[4 * r[0]] = gInd[r[4] + 1] - gInd[r[4]];
      gs[4 * r[0] + 1] = gInd[r[4]];
   }
}

int main(int argc, char *argv[]){
   sp[0] = 6152;  //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;     //width
   sp[2] = 3;     //period
   sp[3] = 1;     //offset
   sp[4] = 2000;  //depth limit
   sp[5] = 0;     //asymmetry flag
   sp[6] = 0;     //symmetry flag
   sp[7] = 0;     //maximum length
   int s;
   for(s = 1; s < argc; s++){    //read input parameters
      switch(argv[s][0]){
         /*case 'b': case 'B':     //read rule
            sp[0] = 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[0] += 1 << (sshift + rnum - '0');
            }
         break;*/
         case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
         case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
         case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
         case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
         case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
         case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
         case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
         case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
         case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[7]); break;
      }
   }
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   if(sp[7]) sp[4] = sp[7] + 2 * period;
   sp[4] += 2 * period;
   time_t ms = clock();
   makePhases();        //make phase tables for determining successor row indices
   makeTables();
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}

Code: Select all

//Yes, I know, this is C++, not C. I had already made this for a different purpose, and I didn't want to rewrite it all.
//Plus, I don't actually know C. I'm just faking it.
//Save this as ntzfind-setup.cpp.

#include <iostream>
#include <fstream>
#include <string>
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 = "";
	std::ofstream file;
    if(argc != 2){
        std::cout << "Error in ntzfind-setup: 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]];
    }
	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] == '_' || 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] == '_' || 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;
}

Code: Select all

#Save this as anything you want that ends in .sh.

g++ ntzfind-setup.cpp -o ntzfind-setup
./ntzfind-setup $1
gcc ntzfind.c -o ntzfind

Instructions for use (these instructions assume you have saved the third file as ntzfind-compile.sh, like I did):
Run

Code: Select all

./ntzfind-compile.sh

in the terminal followed on the same line by the rule you want to search in B/S format. If there is an error saying "Permission denied", first run

Code: Select all

chmod +x ntzfind-compile.sh

and then repeat the last command. The executable will be called "ntzfind". (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.

Posted: **August 23rd, 2016, 4:37 am**

I have added a save/load feature to zfind. It uses the 'd' parameter to specify how often to save the state of the search. For example, running zfind with 'd500000000' will save the state of the search every 500000000 "calculations" (passes through the main loop). Usually, the 'd' parameter will need to be a pretty big number so that the search state isn't saved too often (my example of 500000000 is actually fairly low). You may need experiment a bit to get a save rate that you like.

The search state is saved to files with the name dumpNNNN where NNNN is a 4-digit number (just like gfind-pt, since I basically copied the code from there).

To continue the search from a saved state, run zfind with exactly two parameters: the first parameter is just 'r', and the second parameter is the name of the file containing the saved search state.

There is also a dump-and-exit option by including 'j' as a parameter. This option initializes the search, dumps the initial state, and then exits without actually running the search.

Here is the updated code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MAXPERIOD 30
#define MIN_DUMP_PERIOD 1000000
#define NUM_PARAMS 8

int 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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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];
   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] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; 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[2] - fwdOff[phase]] << (2 * sp[1])) + (pRows[a - fwdOff[phase]] << sp[1]);
   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[2] - doubleOff[phase]] << (2 * sp[1])) + (pRows[a - doubleOff[phase]] << sp[1]);
   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[2]){
      r[10] = 1;
      r[11] = pInd[a + sp[2] - tripleOff[phase]] + pRemain[a + sp[2] - tripleOff[phase]];
   }
   else{
      r[2] = (pRows[a - sp[2] - tripleOff[phase]] << (2 * sp[1])) + (pRows[a - tripleOff[phase]] << sp[1]);
      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[1])) + (r[8] << sp[1]) + 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[1])) + (r[13] << sp[1]) + 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[1])) + (r[22] << sp[1]) + r[20];
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

#define FILEVERSION ((unsigned long) 2016082301)  //yyyymmddnn

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

int dumpandexit = 0;

FILE * openDumpFile(){
    FILE * fp;

    while (dumpNum < 10000)
    {
        sprintf(dumpFile,"%s%04d",DUMPROOT,dumpNum++);
        if (fp=fopen(dumpFile,"r"))
            fclose(fp);
        else
            return fopen(dumpFile,"w");
    }
    return (FILE *) 0;
}

void dumpState(int v){ // v = rowNum
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%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;
   buf = malloc(2000000);
   buf[0] = '\0';
   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[2]){
            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[7] && r[0] > sp[7] + 2 * period - 1 && pRows[r[0]] != 0) continue;
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         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[1])) + (pRows[r[0] - period] << sp[1]) + 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[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 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);
   }
}

void initializeSearch(){
   int i;
   if(dumpPeriod > 0 && dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   if(sp[7]) sp[4] = sp[7] + 2 * period;
   sp[4] += 2 * period;
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 4);
   rowNum = 2 * period;
   for(i = 0; i < 2 * period; i++)pRows[i] = 0;
}

int main(int argc, char *argv[]){
   sp[0] = 6152;        //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;           //width
   sp[2] = 3;           //period
   sp[3] = 1;           //offset
   sp[4] = 2000;        //depth limit
   sp[5] = 0;           //asymmetry flag
   sp[6] = 0;           //symmetry flag
   sp[7] = 0;           //maximum length
   loadDumpFlag = 0;    //load flag
   dumpPeriod = 0;
   int dumpandexit = 0;
   int s;
   if(argc == 3 && (argv[1][0] == 'r' || argv[1][0] == 'R')) loadDumpFlag = 1;
   else{
      for(s = 1; s < argc; s++){    //read input parameters
         switch(argv[s][0]){
            case 'b': case 'B':     //read rule
               sp[0] = 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[0] += 1 << (sshift + rnum - '0');
               }
            break;
            case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
            case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
            case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
            case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
            case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
            case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
            case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
            case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
            case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[7]); break;
            case 'd': case 'D': sscanf(&argv[s][1], "%llu", &dumpPeriod); break;
            case 'j': case 'J': dumpandexit = 1; break;
         }
      }
   }
   if(loadDumpFlag) loadState("r",argv[2]);     //load search state from file
   else initializeSearch();                     //initialize search based on input parameters
   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(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;
}

Usage examples:

This happens to save the state of the search only once before the search completes:

Code: Select all

zfind B3/S23 p5 k1 w9 u d500000000

This will load the search state from a file called 'dump0003':

Code: Select all

zfind r dump0003

This will initialize the search and dump the state without actually searching:

Code: Select all

zfind B3/S23 p5 k1 w9 u j

A for awesome wrote:I made an extremely dirty hack of zfind that allows searching non-totalistic rules.

Thanks! I was hoping someone would do this so that I wouldn't have to. To get this to work with my updated code, I think you would just need to use the following in place of ntzfind.c (although I haven't tested it):

Code: Select all

//Save this as ntzfind.c.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "step.c"

#define MAXPERIOD 30
#define MIN_DUMP_PERIOD 1000000
#define NUM_PARAMS 8

int 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[9], i=0, j=0;
   for(i=0;i<3;i++,j++){r[j]=(row1>>(i+bshift))&1;}
   for(i=0;i<3;i++,j++){r[j]=(row2>>(i+bshift))&1;}
   for(i=0;i<3;i++,j++){r[j]=(row3>>(i+bshift))&1;}
   return stepcell(r[4],r[1],r[2],r[5],r[8],r[7],r[6],r[3],r[0]);
}
/*   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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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];
   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] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; 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[2] - fwdOff[phase]] << (2 * sp[1])) + (pRows[a - fwdOff[phase]] << sp[1]);
   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[2] - doubleOff[phase]] << (2 * sp[1])) + (pRows[a - doubleOff[phase]] << sp[1]);
   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[2]){
      r[10] = 1;
      r[11] = pInd[a + sp[2] - tripleOff[phase]] + pRemain[a + sp[2] - tripleOff[phase]];
   }
   else{
      r[2] = (pRows[a - sp[2] - tripleOff[phase]] << (2 * sp[1])) + (pRows[a - tripleOff[phase]] << sp[1]);
      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[1])) + (r[8] << sp[1]) + 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[1])) + (r[13] << sp[1]) + 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[1])) + (r[22] << sp[1]) + r[20];
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

#define FILEVERSION ((unsigned long) 2016082301)  //yyyymmddnn

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

int dumpandexit = 0;

FILE * openDumpFile(){
    FILE * fp;

    while (dumpNum < 10000)
    {
        sprintf(dumpFile,"%s%04d",DUMPROOT,dumpNum++);
        if (fp=fopen(dumpFile,"r"))
            fclose(fp);
        else
            return fopen(dumpFile,"w");
    }
    return (FILE *) 0;
}

void dumpState(int v){ // v = rowNum
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%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;
   buf = malloc(2000000);
   buf[0] = '\0';
   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[2]){
            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[7] && r[0] > sp[7] + 2 * period - 1 && pRows[r[0]] != 0) continue;
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         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[1])) + (pRows[r[0] - period] << sp[1]) + 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[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 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);
   }
}

void initializeSearch(){
   int i;
   if(dumpPeriod > 0 && dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   if(sp[7]) sp[4] = sp[7] + 2 * period;
   sp[4] += 2 * period;
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 4);
   rowNum = 2 * period;
   for(i = 0; i < 2 * period; i++)pRows[i] = 0;
}

int main(int argc, char *argv[]){
   sp[0] = 6152;        //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;           //width
   sp[2] = 3;           //period
   sp[3] = 1;           //offset
   sp[4] = 2000;        //depth limit
   sp[5] = 0;           //asymmetry flag
   sp[6] = 0;           //symmetry flag
   sp[7] = 0;           //maximum length
   loadDumpFlag = 0;    //load flag
   dumpPeriod = 0;
   int dumpandexit = 0;
   int s;
   if(argc == 3 && (argv[1][0] == 'r' || argv[1][0] == 'R')) loadDumpFlag = 1;
   else{
      for(s = 1; s < argc; s++){    //read input parameters
         switch(argv[s][0]){
            /*case 'b': case 'B':     //read rule
               sp[0] = 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[0] += 1 << (sshift + rnum - '0');
               }
            break;*/
            case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
            case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
            case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
            case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
            case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
            case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
            case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
            case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
            case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[7]); break;
            case 'd': case 'D': sscanf(&argv[s][1], "%llu", &dumpPeriod); break;
            case 'j': case 'J': dumpandexit = 1; break;
         }
      }
   }
   if(loadDumpFlag) loadState("r",argv[2]);     //load search state from file
   else initializeSearch();                     //initialize search based on input parameters
   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(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: Bug fix

Posted: **August 23rd, 2016, 3:14 pm**

There was a pretty significant bug in the code that I posted earlier, but it has now been fixed.

Posted: **August 23rd, 2016, 11:36 pm**

Here is a very minor modification that allows for viewing the search state in a dump file. To use this feature, run zfind with exactly two parameters: the first is just the letter 'p', and the second is the name of the file with the saved search state. For example, "zfind p dump0003" will output the current pattern in the file dump0003. This can be useful for monitoring the search over time when using the dump feature. The updated code is below:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MAXPERIOD 30
#define MIN_DUMP_PERIOD 1000000
#define NUM_PARAMS 8

int 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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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];
   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] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
      for(r[1] = 0; r[1] < sp[1]; 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[2] - fwdOff[phase]] << (2 * sp[1])) + (pRows[a - fwdOff[phase]] << sp[1]);
   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[2] - doubleOff[phase]] << (2 * sp[1])) + (pRows[a - doubleOff[phase]] << sp[1]);
   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[2]){
      r[10] = 1;
      r[11] = pInd[a + sp[2] - tripleOff[phase]] + pRemain[a + sp[2] - tripleOff[phase]];
   }
   else{
      r[2] = (pRows[a - sp[2] - tripleOff[phase]] << (2 * sp[1])) + (pRows[a - tripleOff[phase]] << sp[1]);
      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[1])) + (r[8] << sp[1]) + 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[1])) + (r[13] << sp[1]) + 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[1])) + (r[22] << sp[1]) + r[20];
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

#define FILEVERSION ((unsigned long) 2016082301)  //yyyymmddnn

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

int dumpandexit = 0;

FILE * openDumpFile(){
    FILE * fp;

    while (dumpNum < 10000)
    {
        sprintf(dumpFile,"%s%04d",DUMPROOT,dumpNum++);
        if (fp=fopen(dumpFile,"r"))
            fclose(fp);
        else
            return fopen(dumpFile,"w");
    }
    return (FILE *) 0;
}

void dumpState(int v){ // v = rowNum
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%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[2]){
            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[7] && r[0] > sp[7] + 2 * period - 1 && pRows[r[0]] != 0) continue;
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         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[1])) + (pRows[r[0] - period] << sp[1]) + 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[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 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);
   }
   
   if(strcmp(cmd,"p") == 0){
      u1_0(rowNum,0);
      u1_0(rowNum,1);
      exit(1);
   }
}

void initializeSearch(){
   int i;
   if(dumpPeriod > 0 && dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
   rule = sp[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   if(sp[7]) sp[4] = sp[7] + 2 * period;
   sp[4] += 2 * period;
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 4);
   rowNum = 2 * period;
   for(i = 0; i < 2 * period; i++)pRows[i] = 0;
}

int main(int argc, char *argv[]){
   buf = malloc(2000000);
   buf[0] = '\0';
   sp[0] = 6152;        //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;           //width
   sp[2] = 3;           //period
   sp[3] = 1;           //offset
   sp[4] = 2000;        //depth limit
   sp[5] = 0;           //asymmetry flag
   sp[6] = 0;           //symmetry flag
   sp[7] = 0;           //maximum length
   loadDumpFlag = 0;    //load flag
   dumpPeriod = 0;
   int dumpandexit = 0;
   int s;
   if(argc == 3 && (argv[1][0] == 'r' || argv[1][0] == 'R' || !strcmp(argv[1],"p"))) loadDumpFlag = 1;
   else{
      for(s = 1; s < argc; s++){    //read input parameters
         switch(argv[s][0]){
            case 'b': case 'B':     //read rule
               sp[0] = 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[0] += 1 << (sshift + rnum - '0');
               }
            break;
            case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
            case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
            case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
            case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
            case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
            case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
            case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
            case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
            case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[7]); break;
            case 'd': case 'D': sscanf(&argv[s][1], "%llu", &dumpPeriod); break;
            case 'j': case 'J': dumpandexit = 1; break;
         }
      }
   }
   if(loadDumpFlag) loadState(argv[1],argv[2]);     //load search state from file
   else initializeSearch();                     //initialize search based on input parameters
   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(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;
}

Posted: **August 26th, 2016, 7:07 am**

Here's a modification of zfind that makes it possible to extend partial results without needing to edit the code and recompile every time. It also echoes some of the important parameters at the beginning of the search.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MAXPERIOD 30
#define MIN_DUMP_PERIOD 1000000
#define NUM_PARAMS 9

#define RULE 0
#define WIDTH 1
#define PERIOD 2
#define OFFSET 3
#define DEPTH_LIMIT 4


#define MAX_LENGTH 7
#define INIT_ROWS 8

int 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;
   if(evolveBit(row1, row2, row3, width - 1)) return -1;
   if(sp[5] && evolveBit(row1 << 2, row2 << 2, row3 << 2, 0)) return -1;
   row1_s = (row1 << 1) + ((row1 >> sp[6]) & 1);
   row2_s = (row2 << 1) + ((row2 >> sp[6]) & 1);
   row3_s = (row3 << 1) + ((row3 >> sp[6]) & 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[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[2]){
      for(r[1] = 0; r[1] < sp[1]; 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[2] - fwdOff[phase]] << (2 * sp[1])) + (pRows[a - fwdOff[phase]] << sp[1]);
   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[2] - doubleOff[phase]] << (2 * sp[1])) + (pRows[a - doubleOff[phase]] << sp[1]);
   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[2]){
      r[10] = 1;
      r[11] = pInd[a + sp[2] - tripleOff[phase]] + pRemain[a + sp[2] - tripleOff[phase]];
   }
   else{
      r[2] = (pRows[a - sp[2] - tripleOff[phase]] << (2 * sp[1])) + (pRows[a - tripleOff[phase]] << sp[1]);
      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[1])) + (r[8] << sp[1]) + 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[1])) + (r[13] << sp[1]) + 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[1])) + (r[22] << sp[1]) + r[20];
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

#define FILEVERSION ((unsigned long) 2016082601)  //yyyymmddnn

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

int dumpandexit = 0;

FILE * openDumpFile(){
    FILE * fp;

    while (dumpNum < 10000)
    {
        sprintf(dumpFile,"%s%04d",DUMPROOT,dumpNum++);
        if (fp=fopen(dumpFile,"r"))
            fclose(fp);
        else
            return fopen(dumpFile,"w");
    }
    return (FILE *) 0;
}

void dumpState(int v){ // v = rowNum
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%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[2]){
            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[7] && r[0] > sp[7] + 2 * period - 1 && pRows[r[0]] != 0) continue;
      if(!u1_1(r[0]))continue;
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[4]){
         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[1])) + (pRows[r[0] - period] << sp[1]) + 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[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 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") == 0){
      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[0];
   width = sp[1];
   period = sp[2];
   offset = sp[3];
   if(sp[7]) sp[4] = sp[7] + 2 * period;
   sp[4] += 2 * period;
   
   pRows = malloc(sp[4] * 2);
   pInd = malloc(sp[4] * 4);
   pRemain = malloc(sp[4] * 4);
   rowNum = 2 * period;
   for(i = 0; i < 2 * period; i++)pRows[i] = 0;
   if(sp[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[PERIOD]);
   printf("Offset: %d\n",sp[OFFSET]);
   printf("Width:  %d\n",sp[WIDTH]);
   if(sp[MAX_LENGTH]) printf("Max length: %d\n",sp[MAX_LENGTH]);
   else printf("Depth limit: %d\n",sp[DEPTH_LIMIT] - 2 * period);
   if(dumpPeriod)printf("Dump period: %llu\n",dumpPeriod);
   if(sp[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");
      }
   }
}

int main(int argc, char *argv[]){
   buf = malloc(2000000);
   buf[0] = '\0';
   sp[0] = 6152;        //rule (first 9 bits represent births; next 9 bits represent survivals)
   sp[1] = 6;           //width
   sp[2] = 3;           //period
   sp[3] = 1;           //offset
   sp[4] = 2000;        //depth limit
   sp[5] = 0;           //asymmetry flag
   sp[6] = 0;           //symmetry flag
   sp[7] = 0;           //maximum length
   sp[INIT_ROWS] = 0;   //extend partial flag
   loadDumpFlag = 0;    //load flag
   dumpPeriod = 0;
   int dumpandexit = 0;
   int skipNext = 0;
   int s;
   if(argc == 3 && (argv[1][0] == 'r' || argv[1][0] == 'R' || !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[0] = 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[0] += 1 << (sshift + rnum - '0');
               }
            break;
            case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[1]); break;
            case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[2]); break;
            case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[3]); break;
            case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[4]); break;
            case 'u': case 'U': sp[6] = 1; sp[5] = 0; break;    //odd-width symmetric
            case 'v': case 'V': sp[6] = 0; sp[5] = 0; break;    //even-width symmetric
            case 'a': case 'A': sp[6] = 30; sp[5] = 1; break;   //asymmetric
            case 'g': case 'G': sp[6] = 30; sp[5] = 0; break;   //gutter symmetric
            case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[7]); break;
            case 'd': case 'D': sscanf(&argv[s][1], "%llu", &dumpPeriod); break;
            case 'j': case 'J': dumpandexit = 1; break;
            case 'e': case 'E': sp[INIT_ROWS] = s + 1; skipNext = 1; break;
         }
      }
   }
   if(loadDumpFlag) loadState(argv[1],argv[2]);     //load search state from file
   else initializeSearch(argv[sp[INIT_ROWS]]);      //initialize search based on input parameters
   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[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;
}

The instructions for inputting the initial rows are similar to what I posted here. The only difference is the format.

The first 2 * period rows of the pattern should be saved in a file. Use '.' (a period) to represent off cells and any other non-whitespace character to represent on cells. Rows should be read from left to right starting at the left edge of the pattern. If the search has symmetry, only the left half of each row should be included.

It is important that the entire width of the row is saved, even if the row ends in off cells. That is, if the width of the search is 7, then each line of the file should have 7 characters.

To run the search with these initial rows, include "e FILENAME" in the parameters, where FILENAME is the name of the file that the initial rows are saved in.

As an example, consider extending the front end of the dragon, as I did in my earlier post. The file containing the initial rows should look something like this (note, the search width is 9, so each line has a width of 9):

Code: Select all

.....o...
.....o...
.....o...
.....o...
.....o...
....ooo..
....o.o..
....o.o..
....o.o..
....o.o..
...oo.oo.
....ooo..

Let's assume this file is saved as "initrows.txt" and is saved in the same directory as zfind. To extend these rows, run

Code: Select all

zfind B3/S23 p6 k1 w9 v e initrows.txt

ConwayLife.com

zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion

Re: zfind discussion