zfind discussion
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: zfind discussion
Re: zfind discussion
Code: Select all
15
o.....
.o.oo.
...oo.
..o.o.
.oo...
o.oo..
.o....
...o..
...o..
......
oooo..
...oo.
......
44
501
done
1517
0
Re: zfind discussion
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.Saka wrote:When I run zfind, I IMMEDIATELY get...
For example, running
Code: Select all
zfind b3s23 p10 k1 w5 v
Re: zfind discussion
Err....Sokwe wrote: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.Saka wrote:When I run zfind, I IMMEDIATELY get...
For example, runningwill 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.Code: Select all
zfind b3s23 p10 k1 w5 v
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
Re: zfind discussion
Look at the final pattern output:
Code: Select all
o....
oo...
.....
ooo..
oo...
.....
.oo..
.o.oo
.o...
.....
.....
o....
o....
Re: zfind discussion
Oh, so it reports in halves? How strange...Sokwe wrote:@Saka
Look at the final pattern output:This is half of copperhead, which has all of the properties I mentioned in my previous post (1c/10 orthogonal, even-width symmetric, etc.).Code: Select all
o.... oo... ..... ooo.. oo... ..... .oo.. .o.oo .o... ..... ..... o.... o....
Re: zfind discussion
Code: Select all
Segmentation fault (core dumped)
Re: zfind discussion
Code: Select all
gs = malloc(40000);
Re: zfind discussion
Re: zfind discussion
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.Saka wrote:is there a way to make zfind search for diagonal ships or knightships?
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;
}
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.
Re: zfind discussion
Is that the slower than WLS version, or an updated, faster version?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
Re: zfind discussion
The code I posted does not include the diagonal search feature.Saka wrote:Is that the slower than WLS version, or an updated, faster version?
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.
Re: zfind discussion
I guess it limits the number of unknown cells?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?
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?)
Re: zfind discussion
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.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?)
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.
Re: zfind discussion
WLS uses dfs and it can find oscs very well. I think we only need to tweak these two things: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.
1) Reverse the loop direction if it loops from an empty row to a full row.
2) If the pattern oscillates at subperiods, continue.
Re: zfind discussion
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
Replace lines 177 - 179 with the following:
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];
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.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];
- In the unmodified code, line 112 should read
Replace line 112 with the following:
Code: Select all
for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
This will ensure that the two initial input rows are given in the output patterns.Code: Select all
for(r[0] = 0; r[0] <= r[2]; r[0] += sp[2]){
- Compile the program and run it using the correct settings for the desired spaceship.
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!
Code: Select all
Row[1] = 0b1000
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]
Code: Select all
Row[2] = 0b1000
Code: Select all
row[7] = 0b10100
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;
}
Code: Select all
zfind B3/S23 p6 k1 w9 v
Re: zfind discussion
Re: zfind discussion
Re: zfind discussion
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.codeholic wrote:Have you tried to adapt zfind for puffer search?
Re: zfind discussion
- 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.
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;
}
- Start with the code posted above.
- In the unmodified code, lines 178 - 180 should read
Replace lines 178 - 180 with the following:
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];
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.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]];
- In the unmodified code, line 111 should read
Replace line 111 with the following:
Code: Select all
for(r[0] = 2 * sp[2]; r[0] <= r[2]; r[0] += sp[2]){
This will ensure that the two initial input rows are given in the output patterns.Code: Select all
for(r[0] = 0; r[0] <= r[2]; r[0] += sp[2]){
- Compile the program and run it using the correct settings for the desired spaceship.
- praosylen
- Posts: 2446
- Joined: September 13th, 2014, 5:36 pm
- Location: Pembina University, Home of the Gliders
- Contact:
Re: zfind discussion
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
Run
Code: Select all
./ntzfind-compile.sh
Code: Select all
chmod +x ntzfind-compile.sh
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.
praosylen#5847 (Discord)
The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...
Re: zfind discussion
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;
}
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
Code: Select all
zfind r dump0003
Code: Select all
zfind B3/S23 p5 k1 w9 u j
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):A for awesome wrote:I made an extremely dirty hack of zfind that allows searching non-totalistic rules.
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;
}
Re: zfind discussion
Re: zfind discussion
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;
}
Re: zfind discussion
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 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..
Code: Select all
zfind B3/S23 p6 k1 w9 v e initrows.txt