ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

zfind discussion

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

zfind discussion

Postby Sokwe » March 11th, 2016, 2:14 am

This is a topic for the discussion of zfind, a spaceship search program by zdr.

The latest version of the program can be found here.

A Golly python script for finding initial rows from a partial result is available here.

As an example, running zfind with the arguments
B3/S23 w5 p10 k1 v l500

will search for an orthogonal ship in B3/S23 with a period of 10, a translation of 1 cell per period, a search width of 5, maximum possible length 500/p, and even bilateral symmetry. To get odd bilateral symmetry, replace 'v' with 'u'.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1156
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby Sokwe » March 11th, 2016, 2:30 am

Here is a modification to zfind that allows for p < 3k and incorporates a gutter-symmetric mode:

Edit: This is modification is obsolete. See zdr's post below.
#include <stdio.h>
#include <stdlib.h>

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

void plong(long a){
   if(a > 1000000000)printf("%dM\n", a / 1000000);
   else printf("%d\n", a);
}

int u0_0(int a, int b, int c, int d){
   int r;
   r = bc[(a >> d) & 7];
   r += bc[(b >> d) & 7] + 4 * ((b >> d) & 2);
   r += bc[(c >> d) & 7];
   return (sp[0] >> r) & 1;
}

void u0(){
   int r[10];
   gf = malloc((long)4 << (sp[1] * 3));
   gb = malloc((long)8 << (sp[1] * 3));
   for(r[0] = 0; r[0] < 1 << (3 * sp[1]); r[0]++)gb[2 * r[0]] = 0;
   r[3] = -1;
   r[9] = 0;
   for(r[0] = 0; r[0] < 1 << sp[1]; r[0]++)for(r[1] = 0; r[1] < 1 << sp[1]; r[1]++)for(r[2] = 0; r[2] < 1 << sp[1]; r[2]++){
      r[3]++;
      if(u0_0(r[0], r[1], r[2], sp[1] - 1)){
         gf[r[3]] = -1;
         continue;
      }
      r[4] = (r[0] << 1) + sp[5]*((r[0] >> sp[6]) & 1);
      r[5] = (r[1] << 1) + sp[5]*((r[1] >> sp[6]) & 1);
      r[6] = (r[2] << 1) + sp[5]*((r[2] >> sp[6]) & 1);
      r[7] = u0_0(r[4], r[5], r[6], 0);
      for(r[8] = 1; r[8] < sp[1]; r[8]++)r[7] += u0_0(r[0], r[1], r[2], r[8] - 1) << r[8];
      gf[r[3]] = r[7];
      gb[2 * (r[3] - r[2] + r[7])]++;
      r[9]++;
   }
   gl = malloc(4 * r[9]);
   r[1] = 0;
   for(r[0] = 0; r[0] < 1 << (3 * sp[1]); r[0]++){
      r[1] += gb[2 * r[0]];
      gb[2 * r[0] + 1] = r[1];
   }
   r[3] = -1;
   for(r[0] = 0; r[0] < (1 << (2 * sp[1])); r[0]++)for(r[1] = 0; r[1] < (1 << sp[1]); r[1]++){
      r[3]++;
      r[2] = gf[r[3]];
      if(r[2] < 0)continue;
      r[4] = r[3] - r[1] + r[2];
      gb[2 * r[4] + 1]--;
      gl[gb[2 * r[4] + 1]] = r[1];
   }
   free(gf);
}

void u1_0(int a){
   int r[10];
   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)printf("o");
         else printf(".");
      }
      printf("\n");
   }
   printf("%d\n", r[2]);
}

int u1_1(int a){
   int r[30];
   r[2] = (gs[4 * (a - sp[2] - sp[3]) + 2] << (2 * sp[1])) + (gs[4 * (a - sp[3]) + 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] - 2 * sp[3]) + 2] << (2 * sp[1])) + (gs[4 * (a - 2 * sp[3]) + 2] << sp[1]);
   r[6] = gb[2 * (r[2] + gs[4 * (a - sp[3]) + 2])];
   r[7] = gb[2 * (r[2] + gs[4 * (a - sp[3]) + 2]) + 1];
   //r[2] = (gs[4 * (a - sp[2] - 3 * sp[3]) + 2] << (2 * sp[1])) + (gs[4 * (a - 3 * sp[3]) + 2] << sp[1]);
   //r[10] = gb[2 * (r[2] + gs[4 * (a - 2 * sp[3]) + 2])];
   //r[11] = gb[2 * (r[2] + gs[4 * (a - 2 * sp[3]) + 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 - 2 * sp[3]) + 2] << (2 * sp[1])) + (r[8] << sp[1]) + r[4];
         if(gb[2 * r[9]])return 1;
         /*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 - 3 * sp[3]) + 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]])return 1;
               }
            }
         }*/
      }
   }
   return 0;
}

void u1(){
   int r[10];
   long i;
   gs = malloc(40000);
   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;
   r[5] = 0;
   time_t ms = clock();
   for(;;){
      i++;
      if(r[0] > r[5] || !(i & 0xffffffff)){
         u1_0(r[0]);
         printf("%d\n", r[0]);
         plong(i);
         plong(clock() - ms);         
         if(r[0] > r[5])r[5] = r[0];
      }
      if(!gs[4 * r[0]]){
         r[0]--;
         if(r[0] < 2 * sp[2]){
            printf("end\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]++;
      if(r[0] > sp[4]){
         printf("done\n");
         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] + sp[3]) + 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[]){
   int r[10];
   sp[0] = 6152;
   sp[1] = 6;
   sp[2] = 3;
   sp[3] = 1;
   sp[4] = 500;
   sp[5] = 1;
   sp[6] = 0;
   sp[7] = 1;
   for(r[0] = 1; r[0] < argc; r[0]++){
      switch(argv[r[0]][0]){
         case 'b':
            sp[0] = 0;
            r[1] = 0;
            for(r[2] = 1; r[2] < 100; r[2]++){
               r[3] = argv[r[0]][r[2]];
               if(!r[3])break;
               if(r[3] == 's')r[1] = 9;
               if(r[3] >= '0' && r[3] <= '8')sp[0] += 1 << (r[1] + r[3] - '0');
            }
         break;
         case 'w': sscanf(&argv[r[0]][1], "%d", &sp[1]); break;
         case 'p': sscanf(&argv[r[0]][1], "%d", &sp[2]); break;
         case 'k': sscanf(&argv[r[0]][1], "%d", &sp[3]); break;
         case 'l': sscanf(&argv[r[0]][1], "%d", &sp[4]); break;
         case 'u': sp[6] = 1; break;
         case 'v': sp[6] = 0; break;
         case 't': sp[5] = 0; break;
      }
   }
   time_t ms = clock();
   u0();
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}


The search can be run with gutter symmetry by using 't' instead of 'u' or 'v'.

For the gutter-symmetry mode I made the following modifications:
  • Replace lines 33-35 with
    r[4] = (r[0] << 1) + sp[5]*((r[0] >> sp[6]) & 1);
    r[5] = (r[1] << 1) + sp[5]*((r[1] >> sp[6]) & 1);
    r[6] = (r[2] << 1) + sp[5]*((r[2] >> sp[6]) & 1);
  • Add the following line after line 184:
    case 't': sp[5] = 0; break;

To allow p < 3k I made the following modifications:
  • Comment out lines 82-84.
  • Replace line 90 with
    if(gb[2 * r[9]])return 1;
  • Comment out lines 91-107

I'm not entirely sure of the full implications of this second modification.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1156
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby thunk » March 11th, 2016, 3:16 am

zfind-mm seems to work okay on my computer.

And yes, I think it makes perfect sense not to put the results on the main search table until we have a better understanding of the program and its bugs. Though a separate entry in the tables of individual programs would be nice. (I'm currently keeping records locally).
"What's purple and commutes?
The Evanston Express."
thunk
 
Posts: 165
Joined: October 3rd, 2015, 8:50 pm
Location: Central USA

Re: zfind discussion

Postby muzik » March 11th, 2016, 3:35 am

Being an almost complete programming noob, I want to know how exactly do you run this?
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: zfind discussion

Postby zdr » March 11th, 2016, 3:36 am

Your changes to make it handle searches faster than c/3 slow down the search.
Modified version below, a few small additions:
greatly reduced spam
added symmetry modes a = asymmetric g = gutter
can search for speeds faster than c/3

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

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

void plong(long a){
   if(a > 1000000000)printf("%dM\n", a / 1000000);
   else printf("%d\n", a);
}

int u0_0(int a, int b, int c, int d){
   int r;
   r = bc[(a >> d) & 7];
   r += bc[(b >> d) & 7] + 4 * ((b >> d) & 2);
   r += bc[(c >> d) & 7];
   return (sp[0] >> r) & 1;
}

void u0(){
   int r[10];
   gf = malloc((long)4 << (sp[1] * 3));
   gb = malloc((long)8 << (sp[1] * 3));
   for(r[0] = 0; r[0] < 1 << (3 * sp[1]); r[0]++)gb[2 * r[0]] = 0;
   r[3] = -1;
   r[9] = 0;
   for(r[0] = 0; r[0] < 1 << sp[1]; r[0]++)for(r[1] = 0; r[1] < 1 << sp[1]; r[1]++)for(r[2] = 0; r[2] < 1 << sp[1]; r[2]++){
      r[3]++;
      if(u0_0(r[0], r[1], r[2], sp[1] - 1)){
         gf[r[3]] = -1;
         continue;
      }
      if(sp[5])if(u0_0(r[0] << 2, r[1] << 2, r[2] << 2, 0)){
         gf[r[3]] = -1;
         continue;
      }
      r[4] = (r[0] << 1) + ((r[0] >> sp[6]) & 1);
      r[5] = (r[1] << 1) + ((r[1] >> sp[6]) & 1);
      r[6] = (r[2] << 1) + ((r[2] >> sp[6]) & 1);
      r[7] = u0_0(r[4], r[5], r[6], 0);
      for(r[8] = 1; r[8] < sp[1]; r[8]++)r[7] += u0_0(r[0], r[1], r[2], r[8] - 1) << r[8];
      gf[r[3]] = r[7];
      gb[2 * (r[3] - r[2] + r[7])]++;
      r[9]++;
   }
   gl = malloc(4 * r[9]);
   r[1] = 0;
   for(r[0] = 0; r[0] < 1 << (3 * sp[1]); r[0]++){
      r[1] += gb[2 * r[0]];
      gb[2 * r[0] + 1] = r[1];
   }
   r[3] = -1;
   for(r[0] = 0; r[0] < (1 << (2 * sp[1])); r[0]++)for(r[1] = 0; r[1] < (1 << sp[1]); r[1]++){
      r[3]++;
      r[2] = gf[r[3]];
      if(r[2] < 0)continue;
      r[4] = r[3] - r[1] + r[2];
      gb[2 * r[4] + 1]--;
      gl[gb[2 * r[4] + 1]] = r[1];
   }
   free(gf);
}

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] - sp[3]) + 2] << (2 * sp[1])) + (gs[4 * (a - sp[3]) + 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] - 2 * sp[3]) + 2] << (2 * sp[1])) + (gs[4 * (a - 2 * sp[3]) + 2] << sp[1]);
   r[6] = gb[2 * (r[2] + gs[4 * (a - sp[3]) + 2])];
   r[7] = gb[2 * (r[2] + gs[4 * (a - sp[3]) + 2]) + 1];
   if(3 * sp[3] >= sp[2]){
      r[10] = 1;
      r[11] = gs[4 * (a + sp[2] - 3 * sp[3]) + 1] + gs[4 * (a + sp[2] - 3 * sp[3])];
   }
   else{
      r[2] = (gs[4 * (a - sp[2] - 3 * sp[3]) + 2] << (2 * sp[1])) + (gs[4 * (a - 3 * sp[3]) + 2] << sp[1]);
      r[10] = gb[2 * (r[2] + gs[4 * (a - 2 * sp[3]) + 2])];
      r[11] = gb[2 * (r[2] + gs[4 * (a - 2 * sp[3]) + 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 - 2 * sp[3]) + 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 - 3 * sp[3]) + 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();
   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]--;
         if(r[0] < 2 * sp[2]){
            printf("end\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]++;
      if(r[0] > sp[4]){
         u1_0(r[0], 1);
         printf("%d\n", r[0]);
         printf("done\n");
         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] + sp[3]) + 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[]){
   int r[10];
   sp[0] = 6152;
   sp[1] = 6;
   sp[2] = 3;
   sp[3] = 1;
   sp[4] = 500;
   sp[5] = 0;
   sp[6] = 0;
   sp[7] = 1;
   for(r[0] = 1; r[0] < argc; r[0]++){
      switch(argv[r[0]][0]){
         case 'b':
            sp[0] = 0;
            r[1] = 0;
            for(r[2] = 1; r[2] < 100; r[2]++){
               r[3] = argv[r[0]][r[2]];
               if(!r[3])break;
               if(r[3] == 's')r[1] = 9;
               if(r[3] >= '0' && r[3] <= '8')sp[0] += 1 << (r[1] + r[3] - '0');
            }
         break;
         case 'w': sscanf(&argv[r[0]][1], "%d", &sp[1]); break;
         case 'p': sscanf(&argv[r[0]][1], "%d", &sp[2]); break;
         case 'k': sscanf(&argv[r[0]][1], "%d", &sp[3]); break;
         case 'l': sscanf(&argv[r[0]][1], "%d", &sp[4]); break;
         case 'u': sp[6] = 1; sp[5] = 0; break;
         case 'v': sp[6] = 0; sp[5] = 0; break;
         case 'a': sp[6] = 30; sp[5] = 1; break;
         case 'g': sp[6] = 30; sp[5] = 0; break;
      }
   }
   time_t ms = clock();
   u0();
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}
zdr
 
Posts: 7
Joined: March 5th, 2016, 5:50 am

Re: zfind discussion

Postby thunk » March 11th, 2016, 3:51 am

zdr wrote:Your changes to make it handle searches faster than c/3 slow down the search.
Modified version below, a few small additions:
greatly reduced spam
added symmetry modes a = asymmetric g = gutter
can search for speeds faster than c/3


Thanks again; the spam reduction is appreciated.
Though the search still seems a bit slower-- around 100 seconds for w5p10k1v instead of 80 (but I'm running several instances on different cores.)

Of course, the gold rush has already begun.
"What's purple and commutes?
The Evanston Express."
thunk
 
Posts: 165
Joined: October 3rd, 2015, 8:50 pm
Location: Central USA

Re: zfind discussion

Postby zdr » March 11th, 2016, 4:07 am

thunk wrote:Though the search still seems a bit slower-- around 100 seconds for w5p10k1v instead of 80 (but I'm running several instances on different cores.)


100 seconds is way too slow, it should be close to 20. Your compiler is probably not optimizing it correctly. Compiling with gcc -O3 gives 19 second search time on an i5 laptop.
zdr
 
Posts: 7
Joined: March 5th, 2016, 5:50 am

Re: zfind discussion

Postby muzik » March 11th, 2016, 4:23 am

Again, how do you use this? It kind of looks similar to gfind (I would assume so, since you said you used gfind or something when you found the good ol' copperhead) so would it be prepared in the same way?

And should I quote the zfind searches from the other thread into here?
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: zfind discussion

Postby Sokwe » March 11th, 2016, 4:40 am

zdr wrote:Your changes to make it handle searches faster than c/3 slow down the search.

I thought it probably would.

So, when checking a row, is 3 the ideal number of generations to look back for a predecessor? As, you noted, only looking back 2 generations isn't as fast. Does looking back 4 generations also slow the search down?
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1156
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby zdr » March 11th, 2016, 5:36 am

Sokwe wrote:
zdr wrote:Your changes to make it handle searches faster than c/3 slow down the search.

I thought it probably would.

So, when checking a row, is 3 the ideal number of generations to look back for a predecessor? As, you noted, only looking back 2 generations isn't as fast. Does looking back 4 generations also slow the search down?


It's just a quick test which is useful when it avoids a pattern with no solution. At c/10 with a width of around 6 it is very effective. To find something like c/20 a much better checking function would be needed to make dfs practical.

muzik wrote:Again, how do you use this? It kind of looks similar to gfind (I would assume so, since you said you used gfind or something when you found the good ol' copperhead) so would it be prepared in the same way?

And should I quote the zfind searches from the other thread into here?


It's C code. You need a C compiler to do anything with it.
zdr
 
Posts: 7
Joined: March 5th, 2016, 5:50 am

Re: zfind discussion

Postby codeholic » March 11th, 2016, 11:25 am

@zdr Thanks for sharing your code!

Why do I not find LWSS with
./zfind w5 p4 k2 a
?

P. S. Search for glide-symmetric spaceships would be also a nice addition.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1138
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: zfind discussion

Postby drc » March 12th, 2016, 2:55 pm

What symbols use for the symmetry?
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: zfind discussion

Postby drc » March 12th, 2016, 4:18 pm

Okay, sorry for the triple post, but I tried recompiling zfind and gcc doesn't produce an output file.
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: zfind discussion

Postby simeks » March 12th, 2016, 4:35 pm

On a system with at least 16 Gbytes, zfind seems to work with parameter "w10" if line 27 is changed to
long r_9 = 0;

and "r[9]" is changed to "r_9" on lines 45 and 47.
simeks
 
Posts: 324
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: zfind discussion

Postby Sokwe » March 12th, 2016, 6:00 pm

simeks wrote:On a system with at least 16 Gbytes, zfind seems to work with parameter "w10" if line 27 is changed to
long r_9 = 0;

and "r[9]" is changed to "r_9" on lines 45 and 47.

I think you would also need to make r[3] a long integer. I would think it would be sufficient to replace line 22 (first line of u0()) with
long r[10];

For those with enough available memory, I actually think the maximum width is around 12 or 13 (after this, I think most operating systems won't allocate enough memory to a single process).
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1156
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby rmmh » March 13th, 2016, 6:43 am

Here's some code to add RLE encoding to the output, for easy pasting into Golly.

Add this to the end of u1_0:
   // RLE encoding
   int i, j;
   out += sprintf(out, "\nx = %d, y = %d\n", sp[1], (r[2] - 2 * sp[2]) / sp[2]);
   char *linestart = out;
   for(i = 2 * sp[2]; i <= r[2]; i += sp[2]){
      for(j = 0; gs[4 * i + 2] && j < sp[1]; j++)
         *out++ = (gs[4 * i + 2] >> j) & 1 ? 'o' : 'b';
      *out++ = '$';
   }
   *out = 0;
   char *input = linestart, *output = linestart;
   while (input < out) {  // compress in-place
      char tag = *input;
      int count = 0;
      while (input[count] == tag) count++;
      input += count;
      if (count > 1) output += sprintf(output, "%d", count);
      *output++ = tag;
      if (output - linestart > 70 && output < input) {
         linestart = output;
         *output++ = '\n';
      }
   }
   sprintf(output, "\n\n");
rmmh
 
Posts: 3
Joined: March 10th, 2016, 2:27 am

Re: zfind discussion

Postby HartmutHolzwart » March 14th, 2016, 10:36 am

Would it be possible to modify zfind for short wide searches? Coming from classical low period WLS searches, there should be some new finds hidden in height 8/9/10.
HartmutHolzwart
 
Posts: 377
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: zfind discussion

Postby FractalFusion » March 18th, 2016, 4:25 pm

While results came back negative, I have a better feel for how spaceship searches are done.

I searched for c/13 and 2c/13 with even and odd symmetry up to width 10 (e.g. "zfind p13 k1 w5 l2000"
and "zfind p13 k1 u w5 l2000"), 3c/13 and 4c/13 with odd symmetry up to width 11, c/14 and c/15 with odd symmetry up to width 9, and c/8 with odd symmetry up to width 15, with negative results. The partials reported by the program are here:
x = 195, y = 182, rule = B3/S23
11$94bo$93bobo$93bobo$94bo50bo$144bobo$144bobo$94bo50bo$93bobo2$93b3o
2$144b3o$91b3ob3o45bo3bo$93bobo$142bo5bo$91bobobobo44bobobobo$90bo7bo
44b2ob2o$91b2o3b2o$93bobo$91b2o3b2o44bo5bo$92bo3bo45b2o3b2o$91b2o3b2o
43bobo3bobo$142bobobobo$143bo3bo$93b3o46b2obob2o$92bo3bo48bo$92bo3bo
45b3ob3o$91bobobobo44bo2bo2bo$91b7o$90bo3bo3bo44bobobo$142b7o$90bo7bo
43bo2bo2bo$91bo5bo$90bo2bobo2bo$92b2ob2o34$64b2o$63bo2bo$63bo2bo$64b2o
2$105b2o41b2o$63b4o36bo4bo37bo4bo$62b6o35bo4bo36b2o4b2o$62bob2obo35bo
4bo35bo3b2o3bo27b2o$181b2o$12bo7bo41bob2obo76b2o6b2o25bob2obo$11bobo5b
obo40b6o34b3o2b3o36bo4bo25b3o4b3o$11bobo5bobo41b4o35b2ob2ob2o36b2o2b2o
$12bo7bo127b2o31b2o$60bobo4bobo35b2o39b2o2b2o26b3o2b3o$14bo3bo41bob2o
2b2obo32bo6bo37bo2bo26bobob2obobo$13b3ob3o42b2o2b2o34bobo2bobo$61b2o4b
2o34b2o2b2o$12bobo3bobo40bob4obo33bo6bo$11bob2o3b2obo39bo6bo32b2o6b2o$
11bobo2bo2bobo41bo2bo$10b2obo5bob2o38bo2b2o2bo$10b3o7b3o37bo3b2o3bo$
11b2o7b2o$11b2o7b2o$11bob2o3b2obo$9b2o4b3o4b2o$9bobo9bobo$12bo7bo2$10b
o2bo5bo2bo$12b3o3b3o$12b3o3b3o127bo33bo$11bo9bo126bo33bo$11bo2bo3bo2bo
42bo82b3o31b3o$15bobo45bobo41bo$10b4obobob4o40bobo41bo72b2ob2o$11bo3bo
bo3bo42bo42bo72b2ob2o$14b2ob2o129bo31b2ob2o$13bobobobo127bobo29b3ob3o$
14b2ob2o128bobo28bo2b3o2bo$11b2o2bobo2b2o125bobo31b3o$10bo3bo3bo3bo40b
3o39b5o69b2o3b2o$14bo3bo43bo3bo37bob3obo37bo31bobobo$11b2o7b2o40b2ob2o
37bo5bo68bobobobo$13b3ob3o41bo5bo38bobo37b5o28bobobobo$9b2o3b2ob2o3b2o
37b2o3b2o37b2ob2o36bo3bo$13bo5bo42b2ob2o38b2ob2o35bo5bo$10b2o3b3o3b2o
39bo3bo38bobobo34bob5obo$12bo7bo39bo2bobo2bo36bo3bo$61b2o3b2o35bo7bo$
103bo2bobo2bo$63bobo2$61b2o3b2o$61b3ob3o2$62b2ob2o$61bobobobo6$148bo$
147bobo2$147b3o31bo$181bo$146bo3bo29b3o$145bobobobo$147bobo29b2ob2o$
145b3ob3o27b2ob2o$143b3o5b3o25b2ob2o$148bo31bobo$147bobo28bo5bo$146b2o
b2o25bo3bobo3bo$146b2ob2o25bo3bobo3bo$180bobo$146b5o26bobo3bobo$145bo
2bo2bo26b7o$145bob3obo29bo$144b3o3b3o$144bo3bo3bo23bo4bo4bo$145bobobob
o25b2o5b2o$145bobobobo25bo2b3o2bo$144b3o3b3o$144bo7bo24b9o$144b2o5b2o$
143b3obobob3o$146bobobo!
FractalFusion
 
Posts: 40
Joined: March 27th, 2009, 2:07 pm

Re: zfind discussion

Postby drc » March 18th, 2016, 6:32 pm

FractalFusion wrote:While results came back negative, I have a better feel for how spaceship searches are done.

I searched for c/13 and 2c/13 with even and odd symmetry up to width 10 (e.g. "zfind p13 k1 w5 l2000"
and "zfind p13 k1 u w5 l2000"), 3c/13 and 4c/13 with odd symmetry up to width 11, c/14 and c/15 with odd symmetry up to width 9, and c/8 with odd symmetry up to width 15, with negative results. The partials reported by the program are here:
x = 195, y = 182, rule = B3/S23
11$94bo$93bobo$93bobo$94bo50bo$144bobo$144bobo$94bo50bo$93bobo2$93b3o
2$144b3o$91b3ob3o45bo3bo$93bobo$142bo5bo$91bobobobo44bobobobo$90bo7bo
44b2ob2o$91b2o3b2o$93bobo$91b2o3b2o44bo5bo$92bo3bo45b2o3b2o$91b2o3b2o
43bobo3bobo$142bobobobo$143bo3bo$93b3o46b2obob2o$92bo3bo48bo$92bo3bo
45b3ob3o$91bobobobo44bo2bo2bo$91b7o$90bo3bo3bo44bobobo$142b7o$90bo7bo
43bo2bo2bo$91bo5bo$90bo2bobo2bo$92b2ob2o34$64b2o$63bo2bo$63bo2bo$64b2o
2$105b2o41b2o$63b4o36bo4bo37bo4bo$62b6o35bo4bo36b2o4b2o$62bob2obo35bo
4bo35bo3b2o3bo27b2o$181b2o$12bo7bo41bob2obo76b2o6b2o25bob2obo$11bobo5b
obo40b6o34b3o2b3o36bo4bo25b3o4b3o$11bobo5bobo41b4o35b2ob2ob2o36b2o2b2o
$12bo7bo127b2o31b2o$60bobo4bobo35b2o39b2o2b2o26b3o2b3o$14bo3bo41bob2o
2b2obo32bo6bo37bo2bo26bobob2obobo$13b3ob3o42b2o2b2o34bobo2bobo$61b2o4b
2o34b2o2b2o$12bobo3bobo40bob4obo33bo6bo$11bob2o3b2obo39bo6bo32b2o6b2o$
11bobo2bo2bobo41bo2bo$10b2obo5bob2o38bo2b2o2bo$10b3o7b3o37bo3b2o3bo$
11b2o7b2o$11b2o7b2o$11bob2o3b2obo$9b2o4b3o4b2o$9bobo9bobo$12bo7bo2$10b
o2bo5bo2bo$12b3o3b3o$12b3o3b3o127bo33bo$11bo9bo126bo33bo$11bo2bo3bo2bo
42bo82b3o31b3o$15bobo45bobo41bo$10b4obobob4o40bobo41bo72b2ob2o$11bo3bo
bo3bo42bo42bo72b2ob2o$14b2ob2o129bo31b2ob2o$13bobobobo127bobo29b3ob3o$
14b2ob2o128bobo28bo2b3o2bo$11b2o2bobo2b2o125bobo31b3o$10bo3bo3bo3bo40b
3o39b5o69b2o3b2o$14bo3bo43bo3bo37bob3obo37bo31bobobo$11b2o7b2o40b2ob2o
37bo5bo68bobobobo$13b3ob3o41bo5bo38bobo37b5o28bobobobo$9b2o3b2ob2o3b2o
37b2o3b2o37b2ob2o36bo3bo$13bo5bo42b2ob2o38b2ob2o35bo5bo$10b2o3b3o3b2o
39bo3bo38bobobo34bob5obo$12bo7bo39bo2bobo2bo36bo3bo$61b2o3b2o35bo7bo$
103bo2bobo2bo$63bobo2$61b2o3b2o$61b3ob3o2$62b2ob2o$61bobobobo6$148bo$
147bobo2$147b3o31bo$181bo$146bo3bo29b3o$145bobobobo$147bobo29b2ob2o$
145b3ob3o27b2ob2o$143b3o5b3o25b2ob2o$148bo31bobo$147bobo28bo5bo$146b2o
b2o25bo3bobo3bo$146b2ob2o25bo3bobo3bo$180bobo$146b5o26bobo3bobo$145bo
2bo2bo26b7o$145bob3obo29bo$144b3o3b3o$144bo3bo3bo23bo4bo4bo$145bobobob
o25b2o5b2o$145bobobobo25bo2b3o2bo$144b3o3b3o$144bo7bo24b9o$144b2o5b2o$
143b3obobob3o$146bobobo!


The lowest partial in the middle does this:

x = 41, y = 35, rule = LifeHistory
19.3A$20.A3$20.A$19.A.A$19.A.A$20.A4$18.2D.2D$18.D3.D$19.3D3$19.3A4$
2A7.2A19.2A7.2A$2A6.A2.A17.A2.A6.2A$9.A.A3.2A7.2A3.A.A$10.A4.2A7.2A4.
A$18.2D.2D$18.D3AD$19.3D3$19.3A$16.3D3.3D$15.D3.D.D3.D$15.D3.D.D3.D$
15.D3.D.D3.D$16.3D3.3D!
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: zfind discussion

Postby codeholic » March 19th, 2016, 5:33 pm

I ran zfind with the following params:
./zfind p6 k1 w8 u

There is "done" in the output, but it seems there are no spaceships. Here is the tail of the output:
o........
.o.......
.........
.oo......
.ooo.....
...o.....
...o.....
.........
.........
ooo......
o.oo.....
..o..o...
..o..o...
..oo.o...
.o.o.....
.o...oo..
.o.o..o..
..ooo.o..
..o.o.oo.
oooo.....
oo.o.....
oo.o.....
..o..oo..
.o...oo..
..o...o..
....o....
.ooo.....
.oo..oo..
.o..o.oo.
..ooo.o..
....oo...
....o....
...o.o...
...o.oo..
...oo.o..
....o...o
...oo....
.....o...
...oooooo
...o...o.
.........
....ooo..
....o.o..
...o..o..
...oo....
oo..o....
.o...o...
oooo.o...
..o......
...o.o...
.........
.....oo..
.......o.
o.....o..
o....o.o.
o......o.
.....o.o.
oo.o..o..
oooo.....
..o...o..
o..o..o..
oo..o....
oo...o...
.........
..ooo.oo.
o..o..o..
o.oo.oo..
...o..o..
...o..o..
..oo.oo..
o.oo.o...
..o......
.o.......
.........
..ooo.o..
....o.o..
..o......
...o..oo.
oo.......
.o.oo.oo.
.o.......
.o.o.o.o.
499
500
8022M
-874207416
done
8022M
-874207388

I thought "done" is printed when something is found (in contrast to "end", when nothing is found). Am I wrong?
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1138
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: zfind discussion

Postby simeks » March 19th, 2016, 5:48 pm

codeholic wrote:There is "done" in the output, but it seems there are no spaceships.

The stopping condition for "done" is just that the search reached the number of (lines * period) specified by the "l" parameter (default 500).

zfind doesn't check if enough of the last lines are empty, which would be a valid ship, or non-empty, which is just a long partial.

EDIT: Got the parameter names mixed up, corrected that above, thanks to Sokwe for noticing!
Last edited by simeks on March 19th, 2016, 6:22 pm, edited 1 time in total.
simeks
 
Posts: 324
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: zfind discussion

Postby codeholic » March 19th, 2016, 5:49 pm

Ah, okay, thanks for the clarification.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1138
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: zfind discussion

Postby Sokwe » March 19th, 2016, 6:19 pm

simeks wrote:The stopping condition for "done" is just that the search reached the number of (lines * period) specified by the "k" parameter (default 500).

It's actually specified by the "l" parameter ("k" is the displacement).
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1156
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby Scorbie » March 21st, 2016, 5:48 am

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?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1329
Joined: December 7th, 2013, 1:05 am

Re: zfind discussion

Postby drc » March 21st, 2016, 3:10 pm

@scorbie alexey made the script

Edit: oh wait thought you meant csearch
Last edited by drc on March 21st, 2016, 3:16 pm, edited 1 time in total.
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1665
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Next

Return to Scripts

Who is online

Users browsing this forum: No registered users and 2 guests