zfind discussion

For scripts to aid with computation or simulation in cellular automata.
User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: zfind discussion

Post by muzik » June 24th, 2017, 5:17 pm

I don't think this zfind works with nontot rules

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm

Re: zfind discussion

Post by drc » June 24th, 2017, 5:18 pm

muzik wrote:I don't think this zfind works with nontot rules
I'm using the older ntzfind.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: zfind discussion

Post by praosylen » June 24th, 2017, 10:34 pm

drc wrote:Okay, tried compiling this on my new computer, followed the same steps as before, but then this keeps happening:

Code: Select all

$ gcc ntzfind.c -O3 -o ntzfind
In file included from ntzfind.c:7:0:
step.c: In function ‘stepcell’:
step.c:2:264: error: expected expression before ‘)’ token
    return (~o&((0x0)|(~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f)))&~(~(a|c|e|g)&(b^f)))))|(o&((0x0)|(0x0|(~(a|c|e|g)&(b^f)&~(b^d^f^h))|(~(b|d|f|h)&~((a^e)|(c^g))&(a^c))|())));
                                                                                                                                                                                                                                                                        ^
Rule is B2-c/2cin
Try B2-c/S2cin if you haven't already. Otherwise, I'm not 100% sure. I may look into this some time soon.
former username: A for Awesome
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...

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Post by AforAmpere » June 25th, 2017, 9:44 pm

That happened to me at the beginning, but I think it was because I got the older ntzfind, with the y and n transitions messed up, are you sure you have the latest version?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: zfind discussion

Post by Scorbie » July 14th, 2017, 8:09 am

The latest version of zfind has a bug when searching for gutter spaceships with a rule with B6. I think this is because it doesn't check whether a cell in the gutter row gets alive. Not sure if qfind has the same bug

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Post by Rhombic » August 6th, 2017, 4:52 pm

Error while compiling

Code: Select all

In file included from ntzfind.c:12:0:
step.c: In function ‘stepcell’:
step.c:2:21: error: expected expression before ‘)’ token
    return (o&((0x0|())));
                             ^
Any ideas?
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Post by AforAmpere » August 7th, 2017, 8:18 am

Try typing in the rule without the - sign, so if it was B2-a/S12, you would type B2cekin/S12, that always works for me.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Post by Rhombic » August 7th, 2017, 12:27 pm

AforAmpere wrote:Try typing in the rule without the - sign, so if it was B2-a/S12, you would type B2cekin/S12, that always works for me.
Still broken... somehow!

Code: Select all

 error: expected expression before ‘)’ token
    return (~o&((0x0)|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))|(0x0|(((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))|(~(a|c|e|g)&b&d&f&h)|(~(~a|~c|~e|~g)&~b&~d&~f&~h)|(((a&e)&~((b^d)|(f^h))&(d^f)&~(c|g))|((c&g)&~((d^f)|(b^h))&(b^d)&~(a|e)))|(((~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))))))|(((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))|(((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)))))))))|(o&((0x0)|(0x0|(~(b|d|f|h)&(a|c|e|g)&~(((a|c)&(e|g))|((a|g)&(c|e)))))|(~(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))))|(0x0|())));
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » August 7th, 2017, 11:06 pm

Rhombic wrote:
AforAmpere wrote:Try typing in the rule without the - sign, so if it was B2-a/S12, you would type B2cekin/S12, that always works for me.
Still broken... somehow!

Code: Select all

 error: expected expression before ‘)’ token
    <snip>
Which rule are you trying to build ntzfind for?
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Post by Rhombic » August 8th, 2017, 5:50 am

wildmyron wrote:Which rule are you trying to build ntzfind for?
I can't remember, but it still doesn't work with JustFriends.
Here is what I'm using:

Code: Select all

./ntzfind-setup B2cekin/S12
gcc ntzfind.c -O3 -o ntzfind
And here is the error:

Code: Select all

step.c:2:340: error: expected expression before ‘)’ token
    return (~o&((0x0)|(0x0|(~(a|c|e|g)&(b^f)&~(b^d^f^h))|(~(b|d|f|h)&(a^e)&~(a^c^e^g))|((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)))))|(~(b|d|f|h)&~((a^e)|(c^g))&(a^c))|(~(a|c|e|g)&~((b^f)|(d^h))&(b^d)))))|(o&((0x0)|((a^b^c^d^e^f^g^h)&~(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h))))|(0x0|())));
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » August 9th, 2017, 1:27 am

Rhombic wrote:
wildmyron wrote:Which rule are you trying to build ntzfind for?
I can't remember, but it still doesn't work with JustFriends.
Here is what I'm using:

Code: Select all

./ntzfind-setup B2cekin/S12
gcc ntzfind.c -O3 -o ntzfind
And here is the error:

Code: Select all

step.c:2:340: error: expected expression before ‘)’ token
    return (~o&((0x0)|(0x0|(~(a|c|e|g)&(b^f)&~(b^d^f^h))|(~(b|d|f|h)&(a^e)&~(a^c^e^g))|((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)))))|(~(b|d|f|h)&~((a^e)|(c^g))&(a^c))|(~(a|c|e|g)&~((b^f)|(d^h))&(b^d)))))|(o&((0x0)|((a^b^c^d^e^f^g^h)&~(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h))))|(0x0|())));
Your step function is different to what is generated by my ntzfind-setup. Either there's something wrong with your ntzfind-setup, or perhaps something funny is happening with the '/' character in the input. Try running ntzfind-setup with "B2cekin_S12". If that doesn't work, try re-downloading ntzfind-setup.cpp

For reference, this is my step.c for Just Friends:

Code: Select all

int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){
   return (~o&((0x0)|(0x0|(~(a|c|e|g)&(b^f)&~(b^d^f^h))|(~(b|d|f|h)&(a^e)&~(a^c^e^g))|((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)))))|(~(b|d|f|h)&~((a^e)|(c^g))&(a^c))|(~(a|c|e|g)&~((b^f)|(d^h))&(b^d)))))|(o&((0x0)|((a^b^c^d^e^f^g^h)&~(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h))))|(~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(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))))));
}
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: zfind discussion

Post by Saka » September 30th, 2017, 10:47 pm

I ran

Code: Select all

./ntzfind-setup B34enw5q6ae7c/S2ac3-cknq4-aenqt5akqy8
and then compiled and did

Code: Select all

./ntzfind w8
and then it returned this, which it claims to be a spaceship:

Code: Select all

x = 16, y = 42, rule = B34enw5q6ae7c/S2ac3-cknq4-aenqt5akqy8
7b2o2$4b3o2b3o$2b3o2b2o2b3o$b4obo2bob4o$bo3bo4bo3bo$2bo10bo$2b2o2b4o2b
2o$6b4o$5b2o2b2o$6b4o$3b2o2b2o2b2o$2b2o8b2o$obo2bo4bo2bobo$2b3o6b3o$bo
2bo6bo2bo$2b2o8b2o$bo12bo$3bo8bo2$3b2o6b2o2$2b2o8b2o$b2o10b2o$b3o8b3o$
3bo2bo2bo2bo$2bo2b2o2b2o2bo$4b2o4b2o$3b3o4b3o$7b2o$3b4o2b4o$2b3o6b3o$
3b2o6b2o$2obob6obob2o$o14bo$b2obob4obob2o$ob2o2b4o2b2obo$5bo4bo$4bo6bo
$6bo2bo2$6b4o!
??

My step.c

Code: Select all

int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){
   return (~o&((0x0)|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))|(0x0|(~(~a|~c|~e|~g)&~b&~d&~f&~h)|(((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))))))|(((b&f)&~((c^e)|(a^g))&(e^g)&~(d|h))|((d&h)&~((e^g)|(a^c))&(c^e)&~(b|f))))|(0x0|((~a|~c|~e|~g)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))&~((~b^~f)|(~d^~h))&(~b^~d)))|(0x0|((~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)))))|(~(~b|~d|~f|~h)&(~a^~e)&~(~a^~c^~e^~g)))|(0x0|(~(~a|~c|~e|~g)&(~b|~d|~f|~h)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))))))|(o&((0x0)|(0x0|((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)))))|(~(a|c|e|g)&(b^f)&~(b^d^f^h)))|((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))))&~(~(a|c|e|g))&~((a&((c&f)|(d&g)))|(e&((c&h)|(b&g))))&~(((a^e)&((b&d)^(f&h)))|((c^g)&((d&f)^(b&h))))&~((b|d|f|h)&~(b^d)&~(d^h)))|(~(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))))&~(~(((a^b)|(c^d)|(e^f)|(g^h))&((b^c)|(d^e)|(f^g)|(a^h)))&(a^e)&(c^g))&~(~b&~d&~f&~h)&~(((b&f)&((d&(c^e))|((h&(a^g)))))|((d&h)&((b&(a^c))|((f&(e^g))))))&~(((~b&~f)&~((~c^~e)|(~a^~g))&d)|((~d&~h)&~((~e^~g)|(~a^~c))&b))&~(((~a&~e)&~((~b^~d)|(~f^~h))&c)|((~c&~g)&~((~d^~f)|(~b^~h))&a)))|(0x0|(~(~a^~c^~e^~g)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&((~a&e&((~b&~c)|(~g&~h)))|(~e&a&((~c&~d)|(~f&~g)))))|(~(~a^~c^~e^~g)&~(((~b|~d)&(~f|~h))|((~b|~h)&(~d|~f)))&((~a&e&((~c&~f)|(~d&~g)))|(~e&a&((~g&~b)|(~h&~c)))))|((~a|~c|~e|~g)&~(((~a|~c)&(~e|~g))|((~a|~g)&(~c|~e)))&~((~b^~f)|(~d^~h))&(~b^~d))|(~(~b^~d^~f^~h)&~(((~c|~e)&(~a|~g))|((~a|~c)&(~e|~g)))&((~b&f&((~d&~g)|(~e&~h)))|(~f&b&((~h&~c)|(~a&~d))))))|(~(~a|~b|~c|~d|~e|~f|~g|~h))));
}

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: zfind discussion

Post by praosylen » September 30th, 2017, 11:04 pm

Saka wrote:I ran

Code: Select all

./ntzfind-setup B34enw5q6ae7c/S2ac3-cknq4-aenqt5akqy8
and then compiled and did

Code: Select all

./ntzfind w8
and then it returned this, which it claims to be a spaceship:

Code: Select all

rle
??
...
I'm honestly quite tired of ntzfind issues, so I'll be posting a new version that should get rid of whatever issues are causing most of these bugs (and also a version for qfind) hopefully soon. For now, I have no idea what's happening and I don't have the time to figure it out.
former username: A for Awesome
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...

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Post by Rhombic » November 29th, 2017, 6:52 am

Is there any news about the new ntzfind? I gave up trying to compile the one I have a while ago.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: zfind discussion

Post by dani » November 29th, 2017, 5:03 pm

Rhombic wrote:Is there any news about the new ntzfind? I gave up trying to compile the one I have a while ago.
I have these handy notes I made a while back

Code: Select all

NTZFIND N T Z F I N D
.c: http://www.conwaylife.com/forums/viewtopic.php?f=9&t=2070&hilit=ntzfind&start=25#p34655
setup.cpp: http://www.conwaylife.com/forums/viewtopic.php?f=9&t=2070&hilit=ntzfind&start=50#p38180
howto: http://www.conwaylife.com/forums/viewtopic.php?f=9&t=2070&hilit=ntzfind&start=100#p38640

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: zfind discussion

Post by praosylen » November 29th, 2017, 8:29 pm

Rhombic wrote:Is there any news about the new ntzfind? I gave up trying to compile the one I have a while ago.
Here is the new version of ntzfind (and ntqfind) (EDIT: Fixed ntqfind link):
ntzfind.c:

Code: Select all

/* ntzfind 2.0 (horizontal shift not included in this version)
** A spaceship search program by "zdr" with modifications by Matthias Merzenich and Aidan Pierce
**
** Warning: this program uses a lot of memory (especially for wide searches).
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "nttable.c"

#define BANNER "ntzfind 2.0 by \"zdr\", Matthias Merzenich, and Aidan Pierce, 29 November 2017"
#define FILEVERSION ((unsigned long) 2016122101)  //yyyymmddnn, same as last qfind release (differs from the above)

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

#define P_RULE 0
#define P_WIDTH 1
#define P_PERIOD 2
#define P_OFFSET 3
#define P_DEPTH_LIMIT 4
#define P_SYMMETRY 5
#define P_MAX_LENGTH 6
#define P_INIT_ROWS 7
#define P_FULL_PERIOD 8
#define P_NUM_SHIPS 9
#define P_FULL_WIDTH 10
#define P_REORDER 11
#define P_DUMP 12

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

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

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

//  Posix/Linux
#else
#include <time.h>
double get_cpu_time(){
    return (double)clock() / CLOCKS_PER_SEC;
}
#endif

int sp[NUM_PARAMS];
uint32_t *gInd, *pInd;
uint32_t *pRemain;
uint32_t *gcount;
uint16_t *gRows, *pRows;
uint16_t *ev2Rows;               // lookup table that gives the evolution of a row with a blank row above and a specified row below
unsigned int *lastNonempty;
unsigned long long dumpPeriod;
int bc[8] = {0, 1, 1, 2, 1, 2, 2, 3};
char *buf;

int rule, period, offset, width, rowNum, loadDumpFlag;
int shipNum, firstFull;
uint16_t fpBitmask = 0;

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

void makePhases(){
   int i;
   for (i = 0; i < period; i++) backOff[i] = -1;
   i = 0;
   for (;;) {
      int j = offset;
      while (backOff[(i+j)%period] >= 0 && j < period) j++;
      if (j == period) {
         backOff[i] = period-i;
         break;
      }
      backOff[i] = j;
      i = (i+j)%period;
   }
   for (i = 0; i < period; i++)
      fwdOff[(i+backOff[i])%period] = backOff[i];
   for (i = 0; i < period; i++) {
      int j = (i - fwdOff[i]);
      if (j < 0) j += period;
      doubleOff[i] = fwdOff[i] + fwdOff[j];
   }
   for (i = 0; i <  period; i++){
      int j = (i - fwdOff[i]);
      if (j < 0) j += period;
      tripleOff[i] = fwdOff[i] + doubleOff[j];
   }
}

/*
** For each possible phase of the ship, equivRow[phase] gives the row that 
** is equivalent if the pattern is subperiodic with a specified period.
** equivRow2 is necessary if period == 12, 24, or 30, as then two subperiods
** need to be tested (e.g., if period == 12, we must test subperiods 4 and 6).
** twoSubPeriods is a flag that tells the program to test two subperiods.
*/

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

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

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

void makeEqRows(int maxFactor, int a){
   int tempEquivRow[MAXPERIOD];
   int i,j;
   for(i = 0; i < period; ++i){
      tempEquivRow[i] = i;
      for(j = 0; j < maxFactor; ++j){
         tempEquivRow[i] += backOff[tempEquivRow[i] % period];
      }
      tempEquivRow[i] -= offset * maxFactor + i;
      if(a == 1) equivRow[i] = tempEquivRow[i];
      else equivRow2[i] = tempEquivRow[i];
   }
   for(i = 0; i < period; ++i){     // make equivRow[i] negative if possible
      if(tempEquivRow[i] > 0){
         if(a == 1) equivRow[i + tempEquivRow[i]] = -1 * tempEquivRow[i];
         else equivRow2[i + tempEquivRow[i]] = -1 * tempEquivRow[i];
      }
   }
}

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

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

void sortRows(uint32_t rowSet){
   uint32_t totalRows = gInd[rowSet + 1] - gInd[rowSet];
   uint16_t *row = &(gRows[gInd[rowSet]]);
   uint32_t i;
   int64_t j;
   uint16_t t;
   for(i = 1; i < totalRows; ++i){
      t = row[i];
      j = i - 1;
      while(j >= 0 && gcount[row[j]] < gcount[t]){
         row[j+1] = row[j];
         --j;
      }
      row[j+1] = t;
   }
}

void makeTables(){
   printf("\nBuilding lookup tables... ");
   gInd = malloc(((long long)4 << (width * 3)) + 4);
   ev2Rows = malloc((long long)sizeof(*ev2Rows) * (1 << (width * 2)));
   gcount = malloc((long long)sizeof(*gcount) * (1 << width));
   uint32_t i;
   int row1,row2,row3,row4;
   long int rows123,rows124;
   uint32_t numValid = 0;
   for(i = 0; i < 1 << width; ++i) gcount[i] = 0;
   for(i = 0; i < ((1 << (3 * width)) + 1); i++)gInd[i] = 0;
   rows123 = -1;     //represents row1, row2, and row3 stacked vertically
   for(row1 = 0; row1 < 1 << width; row1++)for(row2 = 0; row2 < 1 << width; row2++)for(row3 = 0; row3 < 1 << width; row3++){
      rows123++;
      row4 = evolveRow(row1,row2,row3);
      if(row4 < 0) continue;
      ++gcount[row4];
      if(row1 == 0) ev2Rows[rows123] = row4;
      gInd[rows123 - row3 + row4]++;
      numValid++;
   }
   gRows = malloc(2 * numValid);
   for(rows124 = 1; rows124 < 1 << (3 * width); rows124++) gInd[rows124] += gInd[rows124 - 1];
   gInd[1 << (3 * width)] = gInd[(1 << (3 * width)) - 1];  //extra needed for last set to calculate number
   rows123 = -1;
   for(row1 = 0; row1 < 1 << width; row1++)for(row2 = 0; row2 < 1 << width; row2++)for(row3 = 0; row3 < 1 << width; row3++){
      rows123++;
      row4 = evolveRow(row1,row2,row3);
      if(row4 < 0) continue;
      rows124 = rows123 - row3 + row4;
      gInd[rows124]--;
      gRows[gInd[rows124]] = (uint16_t)row3;
   }
   printf("Lookup tables built.\n");
   
   gcount[0] = 0;
   if(sp[P_REORDER]){
      printf("Sorting lookup table..... ");
      for(rows124 = 0; rows124 < 1 << (3 * width); ++rows124){
         sortRows(rows124);
      }
      printf("Lookup table sorted.\n");
   }
   free(gcount);
}

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

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

void printPattern(){
   printf("%s", buf);
   fflush(stdout);
}

int lookAhead(int a){
   uint32_t ri11, ri12, ri13, ri22, ri23;  //indices: first number represents vertical offset, second number represents generational offset
   uint32_t rowSet11, rowSet12, rowSet13, rowSet22, rowSet23, rowSet33;
   uint32_t riStart11, riStart12, riStart13, riStart22, riStart23;
   uint32_t numRows11, numRows12, numRows13, numRows22, numRows23;
   uint32_t row11, row12, row13, row22, row23;
   
   rowSet11 = (pRows[a - sp[P_PERIOD] - fwdOff[phase]] << (2 * sp[P_WIDTH]))
             +(pRows[a - fwdOff[phase]] << sp[P_WIDTH])
             + pRows[a];
   riStart11 = gInd[rowSet11];
   numRows11 = gInd[rowSet11 + 1] - riStart11;
   if(!numRows11) return 0;
   
   rowSet12 = (pRows[a - sp[P_PERIOD] - doubleOff[phase]] << (2 * sp[P_WIDTH]))
             +(pRows[a - doubleOff[phase]] << sp[P_WIDTH])
             + pRows[a - fwdOff[phase]];
   riStart12 = gInd[rowSet12];
   numRows12 = gInd[rowSet12 + 1] - riStart12;
   
   if(tripleOff[phase] >= sp[P_PERIOD]){
      riStart13 = pInd[a + sp[P_PERIOD] - tripleOff[phase]] + pRemain[a + sp[P_PERIOD] - tripleOff[phase]];
      numRows13 = 1;
   }
   else{
      rowSet13 = (pRows[a - sp[P_PERIOD] - tripleOff[phase]] << (2 * sp[P_WIDTH]))
                +(pRows[a - tripleOff[phase]] << sp[P_WIDTH])
                + pRows[a - doubleOff[phase]];
      riStart13 = gInd[rowSet13];
      numRows13 = gInd[rowSet13 + 1] - riStart13;
   }
   
   for(ri11 = 0; ri11 < numRows11; ++ri11){
      row11 = gRows[ri11 + riStart11];
      for(ri12 = 0; ri12 < numRows12; ++ri12){
         row12 = gRows[ri12 + riStart12];
         rowSet22 = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH]))
                   +(row12 << sp[P_WIDTH])
                   + row11;
         riStart22 = gInd[rowSet22];
         numRows22 = gInd[rowSet22 + 1] - riStart22;
         if(!numRows22) continue;
         
         for(ri13 = 0; ri13 < numRows13; ++ri13){
            row13 = gRows[ri13 + riStart13];
            rowSet23 = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH]))
                      +(row13 << sp[P_WIDTH])
                      + row12;
            riStart23 = gInd[rowSet23];
            numRows23 = gInd[rowSet23 + 1] - riStart23;
            if(!numRows23) continue;
            
            for(ri22 = 0; ri22 < numRows22; ++ri22){
               row22 = gRows[ri22 + riStart22];
               for(ri23 = 0; ri23 < numRows23; ++ri23){
                  row23 = gRows[ri23 + riStart23];
                  rowSet33 = (row13 << (2 * sp[P_WIDTH]))
                            +(row23 << sp[P_WIDTH])
                            + row22;
                  if(gInd[rowSet33] != gInd[rowSet33 + 1]) return 1;
               }
            }
         }
      }
   }
   return 0;
}

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

int dumpandexit = 0;

FILE * openDumpFile(){
    FILE * fp;

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

void dumpState(int v){ // v = rowNum
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%lu\n",FILEVERSION);
    for (i = 0; i < NUM_PARAMS; i++)
       fprintf(fp,"%d\n",sp[i]);
    fprintf(fp,"%d\n",firstFull);
    fprintf(fp,"%d\n",shipNum);
    for (i = 1; i <= shipNum; i++)
       fprintf(fp,"%u\n",lastNonempty[i]);
    fprintf(fp,"%d\n",v);
    for (i = 0; i < 2 * period; i++)
       fprintf(fp,"%lu\n",(unsigned long) pRows[i]);
    for (i = 2 * period; i <= v; i++){
       fprintf(fp,"%lu\n",(unsigned long) pRows[i]);
       fprintf(fp,"%lu\n",(unsigned long) pInd[i]);
       fprintf(fp,"%lu\n",(unsigned long) pRemain[i]);
    }
    fclose(fp);
    dumpFlag = DUMPSUCCESS;
}

int checkInteract(int a){
   int i;
   for(i = a - period; i > a - 2*period; --i){
      if(ev2Rows[(pRows[i] << width) + pRows[i + period]] != pRows[i + backOff[i % period]]) return 1;
   }
   return 0;
}

void search(){
   uint32_t currRow = rowNum;    // currRow == index of current row
   uint32_t newRowSet;           // used when determining the next row to be added
   int j;
   unsigned long long calcs, lastLong;
   int noship = 0;
   int totalShips = 0;
   calcs = 0;                    // calcs == "calculations" == number of times through the main loop
   uint32_t longest = 0;         // length of the longest partial seen so far
   lastLong = 0;                 // number of calculations at which longest was updated
   int buffFlag = 0;
   double ms = get_cpu_time();
   phase = currRow % period;
   for(;;){
      ++calcs;
      if(!(calcs & dumpPeriod)){
         dumpState(currRow);
         if(dumpFlag == DUMPSUCCESS) printf("State dumped to file %s%04d\n",DUMPROOT,dumpNum - 1);
         else printf("Dump failed\n");
         fflush(stdout);
      }
      if(currRow > longest || !(calcs & 0xffffff)){
         if(currRow > longest){
            buffPattern(currRow);
            longest = currRow;
            buffFlag = 1;
            lastLong = calcs;
         }
         if((buffFlag && calcs - lastLong > 0xffffff) || !(calcs & 0xffffffff)){
            if(!(calcs & 0xffffffff)) buffPattern(currRow);
            printPattern();
            printInfo(currRow,calcs,get_cpu_time()-ms);
            buffFlag = 0;
         }
      }
      if(!pRemain[currRow]){
         if(shipNum && lastNonempty[shipNum] == currRow) --shipNum;
         --currRow;
         if(phase == 0) phase = period;
         --phase;
         if(sp[P_FULL_PERIOD] && firstFull == currRow) firstFull = 0;
         if(currRow < 2 * sp[P_PERIOD]){
            printPattern();
            if(totalShips == 1)printf("Search complete: 1 spaceship found.\n");
            else printf("Search complete: %d spaceships found.\n",totalShips);
            printInfo(-1,calcs,get_cpu_time() - ms);
            return;
         }
         continue;
      }
      --pRemain[currRow];
      pRows[currRow] = gRows[pInd[currRow] + pRemain[currRow]];
      if(sp[P_MAX_LENGTH] && currRow > sp[P_MAX_LENGTH] + 2 * period - 1 && pRows[currRow] != 0) continue;  //back up if length exceeds max length
      if(sp[P_FULL_PERIOD] && currRow > sp[P_FULL_PERIOD] && !firstFull && pRows[currRow]) continue;        //back up if not full period by certain length
      if(sp[P_FULL_WIDTH] && (pRows[currRow] & fpBitmask)){
         if(equivRow[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow[phase]]){
            if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow2[phase]])) continue;
         }
      }
      if(shipNum && currRow == lastNonempty[shipNum] + 2*period && !checkInteract(currRow)) continue;       //back up if new rows don't interact with ship
      if(!lookAhead(currRow))continue;
      if(sp[P_FULL_PERIOD] && !firstFull){
         if(equivRow[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow[phase]]){
            if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[currRow] != pRows[currRow + equivRow2[phase]])) firstFull = currRow;
         }
      }
      ++currRow;
      ++phase;
      if(phase == period) phase = 0;
      if(currRow > sp[P_DEPTH_LIMIT]){
         noship = 0;
         for(j = 1; j <= 2 * period; ++j) noship |= pRows[currRow-j];
         if(!noship){
            if(!sp[P_FULL_PERIOD] || firstFull){
               printf("\n");
               printPattern();
               ++totalShips;
               printf("Spaceship found. (%d)\n\n",totalShips);
               printInfo(currRow,calcs,get_cpu_time() - ms);
               --sp[P_NUM_SHIPS];
            }
            ++shipNum;
            if(sp[P_NUM_SHIPS] == 0){
               if(totalShips == 1)printf("Search terminated: spaceship found.\n");
               else printf("Search terminated: %d spaceships found.\n",totalShips);
               return;
            }
            for(lastNonempty[shipNum] = currRow - 1; lastNonempty[shipNum] >= 0; --lastNonempty[shipNum]) if(pRows[lastNonempty[shipNum]]) break;
            currRow = lastNonempty[shipNum] + 2 * period;
            phase = currRow % period;
            longest = lastNonempty[shipNum];
            continue;
         }
         else{
            printPattern();
            printf("Search terminated: depth limit reached.\n");
            printf("Depth: %d\n", currRow - 2 * period);
            if(totalShips == 1)printf("1 spaceship found.\n");
            else printf("%d spaceships found.\n",totalShips);
         }
         printInfo(currRow,calcs,get_cpu_time() - ms);
         return;
      }
      newRowSet = (pRows[currRow - 2 * period] << (2 * sp[P_WIDTH]))
                 +(pRows[currRow - period] << sp[P_WIDTH])
                 + pRows[currRow - period + backOff[phase]];
      pRemain[currRow] = gInd[newRowSet + 1] - gInd[newRowSet];
      pInd[currRow] = gInd[newRowSet];
   }
}

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;
}

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);

   firstFull = loadInt(fp);
   shipNum = loadInt(fp);
   lastNonempty = malloc(sizeof(int) * (sp[P_DEPTH_LIMIT]/10));
   for (i = 1; i <= shipNum; i++)
      lastNonempty[i] = loadUL(fp);
   rowNum = loadInt(fp);
   
   if(sp[P_DUMP] > 0){
      if(sp[P_DUMP] < MIN_DUMP) sp[P_DUMP] = MIN_DUMP;
      dumpPeriod = ((long long)1 << sp[P_DUMP]) - 1;
   }
   
   rule = sp[P_RULE];
   width = sp[P_WIDTH];
   period = sp[P_PERIOD];
   offset = sp[P_OFFSET];
   if(gcd(period,offset) == 1) sp[P_FULL_PERIOD] = 0;
   if(sp[P_FULL_WIDTH] > sp[P_WIDTH]) sp[P_FULL_WIDTH] = 0;
   if(sp[P_FULL_WIDTH] && sp[P_FULL_WIDTH] < sp[P_WIDTH]){
      for(i = sp[P_FULL_WIDTH]; i < sp[P_WIDTH]; ++i){
         fpBitmask |= (1 << i);
      }
   }
   
   pRows = malloc(sp[P_DEPTH_LIMIT] * 2);
   pInd = malloc(sp[P_DEPTH_LIMIT] * 4);
   pRemain = malloc(sp[P_DEPTH_LIMIT] * 4);
   
   for (i = 0; i < 2 * period; i++)
      pRows[i] = (uint16_t) loadUL(fp);
   for (i = 2 * period; i <= rowNum; i++){
      pRows[i]   = (uint16_t) loadUL(fp);
      pInd[i]    = (uint32_t) loadUL(fp);
      pRemain[i] = (uint32_t) loadUL(fp);
   }
   fclose(fp);
   
   if(!strcmp(cmd,"p") || !strcmp(cmd,"P")){
      buffPattern(rowNum);
      printPattern();
      exit(0);
   }
}

void loadInitRows(char * file){
   FILE * fp;
   int i,j;
   char rowStr[MAXWIDTH];
   
   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(sp[P_DUMP] > 0){
      if(sp[P_DUMP] < MIN_DUMP) sp[P_DUMP] = MIN_DUMP;
      dumpPeriod = ((long long)1 << sp[P_DUMP]) - 1;
   }
   rule = sp[P_RULE];
   width = sp[P_WIDTH];
   period = sp[P_PERIOD];
   offset = sp[P_OFFSET];
   if(sp[P_MAX_LENGTH]) sp[P_DEPTH_LIMIT] = sp[P_MAX_LENGTH] + 2 * period;
   sp[P_DEPTH_LIMIT] += 2 * period;
   if(sp[P_FULL_PERIOD]) sp[P_FULL_PERIOD] += 2 * period - 1;
   if(gcd(period,offset) == 1) sp[P_FULL_PERIOD] = 0;
   if(sp[P_FULL_WIDTH] > sp[P_WIDTH]) sp[P_FULL_WIDTH] = 0;
   if(sp[P_FULL_WIDTH] && sp[P_FULL_WIDTH] < sp[P_WIDTH]){
      for(i = sp[P_FULL_WIDTH]; i < sp[P_WIDTH]; ++i){
         fpBitmask |= (1 << i);
      }
   }
   
   pRows = malloc(sp[P_DEPTH_LIMIT] * 2);
   pInd = malloc(sp[P_DEPTH_LIMIT] * 4);
   pRemain = malloc(sp[P_DEPTH_LIMIT] * 4);
   lastNonempty = malloc(sizeof(int) * (sp[P_DEPTH_LIMIT]/10));
   rowNum = 2 * period;
   for(i = 0; i < 2 * period; i++)pRows[i] = 0;
   if(sp[P_INIT_ROWS]) loadInitRows(file);
}

void echoParams(){
   int i,j;
   printf("Rule: B");
   for(i = 0; i < 9; i++){
      if(rule & (1 << i)) printf("%d",i);
   }
   printf("/S");
   for(i = 9; i < 18; i++){
      if(rule & (1 << i)) printf("%d",i - 9);
   }
   printf("\n");
   printf("Period: %d\n",sp[P_PERIOD]);
   printf("Offset: %d\n",sp[P_OFFSET]);
   printf("Width:  %d\n",sp[P_WIDTH]);
   if(sp[P_SYMMETRY] == SYM_ASYM) printf("Symmetry: asymmetric\n");
   else if(sp[P_SYMMETRY] == SYM_ODD) printf("Symmetry: odd\n");
   else if(sp[P_SYMMETRY] == SYM_EVEN) printf("Symmetry: even\n");
   else if(sp[P_SYMMETRY] == SYM_GUTTER) printf("Symmetry: gutter\n");
   if(sp[P_MAX_LENGTH]) printf("Max length: %d\n",sp[P_MAX_LENGTH]);
   else printf("Depth limit: %d\n",sp[P_DEPTH_LIMIT] - 2 * period);
   if(sp[P_FULL_PERIOD]) printf("Full period by depth %d\n",sp[P_FULL_PERIOD] - 2 * period + 1);
   if(sp[P_FULL_WIDTH]) printf("Full period width: %d\n",sp[P_FULL_WIDTH]);
   if(sp[P_NUM_SHIPS] == 1) printf("Stop search if a ship is found.\n");
   else printf("Stop search if %d ships are found.\n",sp[P_NUM_SHIPS]);
   if(sp[P_DUMP])printf("Dump period: 2^%d\n",sp[P_DUMP]);
   if(!sp[P_REORDER]) printf("Use naive search order.\n");
   if(sp[P_INIT_ROWS]){
      printf("Initial rows:\n");
      for(i = 0; i < 2 * period; i++){
         for(j = width - 1; j >= 0; j--) printf("%c",(pRows[i] & (1 << j)) ? 'o':'.');
         printf("\n");
      }
   }
}

void usage(){
   printf("%s\n",BANNER);
   printf("\n");
   printf("Usage: \"zfind options\"\n");
   printf("  e.g. \"zfind B3/S23 p3 k1 w6 v\" searches Life (rule B3/S23) for\n");
   printf("  c/3 orthogonal spaceships with even bilateral symmetry and a\n");
   printf("  search width of 6 (full width 12).\n");
   printf("\n");
   printf("Available options:\n");
   printf("  bNN/sNN searches for spaceships in the specified rule (default: b3/s23)\n");
   printf("\n");
   printf("  pNN  searches for spaceships with period NN\n");
   printf("  kNN  searches for spaceships that travel NN cells every period\n");
   printf("  wNN  searches for spaceships with search width NN\n");
   printf("       (full width depends on symmetry type)\n");
   printf("\n");
   printf("  lNN  terminates the search if it reaches a depth of NN (default: %d)\n",DEFAULT_DEPTH_LIMIT);
   printf("  mNN  disallows spaceships longer than a depth of NN\n");
   printf("       (the spaceship length is approximately depth/period)\n");
   printf("  fNN  disallows spaceships that do not have the full period by a depth of NN\n");
   printf("  tNN  disallows full-period rows of width greater than NN\n");
   printf("  sNN  terminates the search if NN spaceships are found (default: 1)\n");
   printf("\n");
   printf("  dNN  dumps the search state every 2^NN calculations (minimum: %d)\n",MIN_DUMP);
   printf("  j    dumps the state at start of search\n");
   printf("\n");
   printf("  a    searches for asymmetric spaceships\n");
   printf("  u    searches for odd bilaterally symmetric spaceships\n");
   printf("  v    searches for even bilaterally symmetric spaceships\n");
   printf("  g    searches for symmetric spaceships with gutters (empty center column)\n");
   printf("\n");
   printf("  o    uses naive search order (search will take longer when no ships exist)\n");
   printf("\n");
   printf("  e FF uses rows in the file FF as the initial rows for the search\n");
   printf("       (use the companion Golly python script to easily generate the\n");
   printf("       initial row file)\n");
   printf("\n");
   printf("\"zfind command file\" reloads the state from the specified file\n");
   printf("and performs the command. Available commands: \n");
   printf("  s    resumes search from the loaded state\n");
   printf("  p    outputs the pattern representing the loaded state\n");
}

int main(int argc, char *argv[]){
   sp[P_RULE] = 6152;         //first 9 bits represent births; next 9 bits represent survivals
   sp[P_WIDTH] = 0;
   sp[P_PERIOD] = 0;
   sp[P_OFFSET] = 0;
   sp[P_DEPTH_LIMIT] = DEFAULT_DEPTH_LIMIT;
   sp[P_SYMMETRY] = 0;
   sp[P_MAX_LENGTH] = 0;
   sp[P_INIT_ROWS] = 0;
   sp[P_FULL_PERIOD] = 0;
   sp[P_NUM_SHIPS] = 1;
   sp[P_FULL_WIDTH] = 0;
   sp[P_REORDER] = 1;
   sp[P_DUMP] = 0;
   loadDumpFlag = 0;
   dumpPeriod = 0xffffffffffffffff;  // default dump period is 2^64, so the state will never be dumped
   int dumpandexit = 0;
   int skipNext = 0;
   int div1,div2;
   int s;
   if(argc == 2 && !strcmp(argv[1],"c")){
      usage();
      return 0;
   }
   if(argc == 3 && (!strcmp(argv[1],"s") || !strcmp(argv[1],"S") || !strcmp(argv[1],"p") || !strcmp(argv[1],"P"))) loadDumpFlag = 1;
   else{
      for(s = 1; s < argc; s++){    //read input parameters
         if(skipNext){
            skipNext = 0;
            continue;
         }
         switch(argv[s][0]){
            case 'b': case 'B':     //read rule
               sp[P_RULE] = 0;
               int sshift = 0;
               int i;
               for(i = 1; i < 100; i++){
                  int rnum = argv[s][i];
                  if(!rnum)break;
                  if(rnum == 's' || rnum == 'S')sshift = 9;
                  if(rnum >= '0' && rnum <= '8')sp[P_RULE] += 1 << (sshift + rnum - '0');
               }
            break;
            case 'w': case 'W': sscanf(&argv[s][1], "%d", &sp[P_WIDTH]); break;
            case 'p': case 'P': sscanf(&argv[s][1], "%d", &sp[P_PERIOD]); break;
            case 'k': case 'K': sscanf(&argv[s][1], "%d", &sp[P_OFFSET]); break;
            case 'l': case 'L': sscanf(&argv[s][1], "%d", &sp[P_DEPTH_LIMIT]); break;
            case 'u': case 'U': sp[P_SYMMETRY] = SYM_ODD; break;
            case 'v': case 'V': sp[P_SYMMETRY] = SYM_EVEN; break;
            case 'a': case 'A': sp[P_SYMMETRY] = SYM_ASYM; break;
            case 'g': case 'G': sp[P_SYMMETRY] = SYM_GUTTER; break;
            case 'm': case 'M': sscanf(&argv[s][1], "%d", &sp[P_MAX_LENGTH]); break;
            case 'd': case 'D': sscanf(&argv[s][1], "%d", &sp[P_DUMP]); break;
            case 'j': case 'J': dumpandexit = 1; break;
            case 'e': case 'E': sp[P_INIT_ROWS] = s + 1; skipNext = 1; break;
            case 'f': case 'F': sscanf(&argv[s][1], "%d", &sp[P_FULL_PERIOD]); break;
            case 's': case 'S': sscanf(&argv[s][1], "%d", &sp[P_NUM_SHIPS]); break;
            case 't': case 'T': sscanf(&argv[s][1], "%d", &sp[P_FULL_WIDTH]); break;
            case 'o': case 'O': sp[P_REORDER] = 0; break;
         }
      }
   }
   if(loadDumpFlag) loadState(argv[1],argv[2]);     //load search state from file
   else initializeSearch(argv[sp[P_INIT_ROWS]]);    //initialize search based on input parameters
   if(!sp[P_WIDTH] || !sp[P_PERIOD] || !sp[P_OFFSET] || !sp[P_SYMMETRY]){
      printf("You must specify a width, period, offset, and symmetry type.\n");
      printf("For command line options, type 'zfind c'.\n");
      return 0;
   }
   echoParams();
   makePhases();                    //make phase tables for determining successor row indices
   if(gcd(period,offset) > 1){      //make phase tables for determining equivalent subperiodic rows
      div1 = smallestDivisor(gcd(period,offset));
      makeEqRows(period / div1,1);
      div2 = gcd(period,offset);
      while(div2 % div1 == 0) div2 /= div1;
      if(div2 != 1){
         twoSubPeriods = 1;
         div2 = smallestDivisor(div2);
         makeEqRows(period / div2,2);
      }
   }
   makeTables();                    //make lookup tables for determining successor rows
   if(!loadDumpFlag){               //these initialization steps must be performed after makeTables()
      pRemain[2 * period] = gInd[1] - gInd[0] - 1;
      pInd[2 * period] = gInd[0];
      if(sp[P_INIT_ROWS]){
         s = (pRows[0] << (2 * width)) + (pRows[period] << width) + pRows[period + backOff[0]];
         pRemain[2 * period] = gInd[s + 1] - gInd[s];
         pInd[2 * period] = gInd[s];
      }
   }
   if(dumpandexit){
      dumpState(rowNum);
      if (dumpFlag == DUMPSUCCESS) printf("State dumped to file %s%04d\n",DUMPROOT,dumpNum - 1);
      else printf("Dump failed\n");
      return 0;
   }
   buf = malloc((2*sp[P_WIDTH] + 4) * sp[P_DEPTH_LIMIT]);  // I think this gives more than enough space
   buf[0] = '\0';
   printf("Starting search\n");
   search();
   return 0;
}
ntqfind.c takes up to many characters to fit in this post along with the other two.

gen-transtable.py:

Code: Select all

import re
from sys import argv
from os import system
zorq = "z" #Change to "q" for ntqfind
#Binary encoding of each isotropic configuration
#Ordering is:
#8 1 2
#7 0 3
#6 5 4
#This could probably be changed by bit-shuffling if necessary.
transitions = {
    '0' : [0],
    '1c': [64, 4, 16, 1],
    '1e': [128, 2, 32, 8],
    '2a': [192, 6, 48, 129, 12, 96, 3, 24],
    '2c': [80, 20, 5, 65],
    '2e': [160, 10, 40, 130],
    '2i': [136, 34],
    '2k': [144, 18, 36, 132, 9, 33, 66, 72],
    '2n': [68, 17],
    '3a': [224, 14, 56, 131],
    '3c': [84, 21, 69, 81],
    '3e': [168, 42, 138, 162],
    '3i': [193, 7, 112, 28],
    '3j': [194, 134, 176, 161, 44, 104, 11, 26],
    '3k': [164, 74, 41, 146],
    '3n': [208, 22, 52, 133, 13, 97, 67, 88],
    '3q': [196, 70, 49, 145, 76, 100, 19, 25],
    '3r': [200, 38, 50, 137, 140, 98, 35, 152],
    '3y': [148, 82, 37, 73],
    '4a': [240, 30, 60, 135, 15, 225, 195, 120],
    '4c': [85],
    '4e': [170],
    '4i': [216, 54, 141, 99],
    '4j': [202, 166, 178, 169, 172, 106, 43, 154],
    '4k': [210, 150, 180, 165, 45, 105, 75, 90],
    '4n': [209, 23, 116, 197, 29, 113, 71, 92],
    '4q': [228, 78, 57, 147],
    '4r': [232, 46, 58, 139, 142, 226, 163, 184],
    '4t': [201, 39, 114, 156],
    '4w': [198, 177, 108, 27],
    '4y': [212, 86, 53, 149, 77, 101, 83, 89],
    '4z': [204, 102, 51, 153],
    '5a': [241, 31, 124, 199],
    '5c': [234, 174, 186, 171],
    '5e': [213, 87, 117, 93],
    '5i': [248, 62, 143, 227],
    '5j': [244, 94, 61, 151, 79, 229, 211, 121],
    '5k': [214, 181, 109, 91],
    '5n': [242, 158, 188, 167, 47, 233, 203, 122],
    '5q': [236, 110, 59, 155, 206, 230, 179, 185],
    '5r': [220, 118, 55, 157, 205, 103, 115, 217],
    '5y': [218, 182, 173, 107],
    '6a': [252, 126, 63, 159, 207, 231, 243, 249],
    '6c': [250, 190, 175, 235],
    '6e': [245, 95, 125, 215],
    '6i': [221, 119],
    '6k': [246, 222, 189, 183, 111, 237, 219, 123],
    '6n': [238, 187],
    '7c': [254, 191, 239, 251],
    '7e': [253, 127, 223, 247],
    '8' : [255]
}
transtable = [0]*512
rulestring = argv[1]

#Parse the rulestring:
b, s = rulestring.split("/") #Separate B and S transitions
b, s = b[1:], s[1:] #Remove the characters 'B' and 'S'
transgroup = re.compile(r"([0-8][a-zA-Z\-]*)") #Matches a group of isotropic transitions sharing the same outer-totalistic count
b, s = re.findall(transgroup, b), re.findall(transgroup, s) #Divide into transition groups

#Build first half of transition table
for i in b:
    # e.g. B3 or B2-an
    if len(i) == 1 or i[1] == "-":
        #Set all transitions with the given outer-totalistic count (possibly preemptively)
        for j in transitions:
            if j[0] == i[0]:
                for k in transitions[j]:
                    transtable[k] = 1
    # e.g. B2ce
    else:
        #Set all given transitions in group
        for j in i[1:]:
            for k in transitions[i[0]+j]:
                transtable[k] = 1
    # e.g. B2-an
    if len(i) > 1 and i[1] == "-":
        #Unset all given transitions in group
        for j in i[2:]:
            for k in transitions[i[0]+j]:
                transtable[k] = 0

#Build second half
for i in s:
    # e.g. B3 or B2-an
    if len(i) == 1 or i[1] == "-":
        #Set all transitions with the given outer-totalistic count (possibly preemptively)
        for j in transitions:
            if j[0] == i[0]:
                for k in transitions[j]:
                    transtable[k|256] = 1
    # e.g. B2ce
    else:
        #Set all given transitions in group
        for j in i[1:]:
            for k in transitions[i[0]+j]:
                transtable[k|256] = 1
    # e.g. B2-an
    if len(i) > 1 and i[1] == "-":
        #Unset all given transitions in group
        for j in i[2:]:
            for k in transitions[i[0]+j]:
                transtable[k|256] = 0

#Print transition table
with open("nttable.c", "w") as f:
    f.write("int nttable[] = {" + "".join([str(transtable[i]) + (",\n"+" "*17 if not (i+1)%16 else ", ") for i in xrange(512)])[:-19] + "};")

system("gcc -fopenmp -O3 nt%sfind.c -o nt%sfind" % ((zorq,)*2)) #Change this command if not applicable to your system
Instructions for use:

Place gen-transtable.py and whichever of the other two files you want to use in the same folder. (For ntqfind, change the variable

Code: Select all

zorq
in gen-transtable.py to

Code: Select all

"q"
.) To compile for a particular rule, run

Code: Select all

python gen-transtable.py Bxx/Sxx
(if it errors, try changing the last line of gen-transtable.py to whatever is appropriate for your system). Then run ntzfind or ntqfind as you would zfind or qfind.

The modifications are fairly simple (just modifications to the evolveBit function and an extra include), and so can probably be adapted to other programs using the the same basic components. I will try to adapt it somewhat soon (which could mean anything from later tonight to a year and a half from now, knowing me) to work for osrc as well, possibly in addition to other osrc improvements.
former username: A for Awesome
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...

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Post by Rhombic » November 30th, 2017, 12:36 pm

Thank you! I can compile it just fine, but however, when I try to execute it like this:

Code: Select all

./ntqfind B3-n/S2-i34r p5 k1 v
it ignores the letters and attempt to run B3/S234. I have attempted "Bxx/Sxx", Bxx_Sxx, bxxsxx but no luck. Why is this?
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: zfind discussion

Post by praosylen » November 30th, 2017, 5:51 pm

Rhombic wrote:Thank you! I can compile it just fine, but however, when I try to execute it like this:

Code: Select all

./ntqfind B3-n/S2-i34r p5 k1 v
it ignores the letters and attempt to run B3/S234. I have attempted "Bxx/Sxx", Bxx_Sxx, bxxsxx but no luck. Why is this?
Sorry, I definitely wasn't clear enough. In this case, I'm not sure it actually matters what you enter as the rule, but if I were you I'd enter it as B3/S234 (although my guess is that any totalistic rule with similar birth conditions would work). It will say it's running the rule you enter, but it'll actually be running B3-n/S2-i34r.
former username: A for Awesome
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...

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: zfind discussion

Post by toroidalet » November 30th, 2017, 8:50 pm

Being a naïve noncoder, I don't know how to fix these 2 errors:

Code: Select all

newntzfind.c:1:1: error: unknown type name 'import'
import re
^
newntzfind.c:1:10: error: expected ';' after top level declarator
import re
Any sufficiently advanced software is indistinguishable from malice.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » November 30th, 2017, 9:17 pm

toroidalet wrote:Being a naïve noncoder, I don't know how to fix these 2 errors:

Code: Select all

newntzfind.c:1:1: error: unknown type name 'import'
import re
^
newntzfind.c:1:10: error: expected ';' after top level declarator
import re
Somehow you've ended up with the text of the python script in your .c file. Try downloading both files again, and running the python script which will compile ntzfind. Make sure you use the same filenames for the .c file as in the instructions because the Python script has it hardcoded on the last line. If you're not using gcc you'll need to modify the compile line. Sorry, not at desktop so can't give more detailed instructions.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Post by Rhombic » December 1st, 2017, 8:40 am

My ntqfind and ntzfind don't search even then, they just print

Code: Select all

Building lookup tables... Lookup tables built.
Sorting lookup table..... Lookup table sorted.
Starting search
Search complete.
As such, with no spaceship or anything, immediately (within <0.1 seconds).
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: zfind discussion

Post by Saka » December 1st, 2017, 9:25 am

Rhombic wrote:

Code: Select all

Building lookup tables... Lookup tables built.
Sorting lookup table..... Lookup table sorted.
Starting search
Search complete.
As such, with no spaceship or anything, immediately (within <0.1 seconds).
What commands are you using to run and compile it? I'll see if it happens on my laptop (where it worked)

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Post by AforAmpere » December 10th, 2017, 8:03 pm

When I try to compile ntqfind with

Code: Select all

gcc -O3 -o ntqfind ntqfind.c
it does not work, saying unidentified reference to "omp_set_num_threads." What am I doing wrong?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: zfind discussion

Post by praosylen » December 10th, 2017, 10:10 pm

AforAmpere wrote:When I try to compile ntqfind with

Code: Select all

gcc -O3 -o ntqfind ntqfind.c
it does not work, saying unidentified reference to "omp_set_num_threads." What am I doing wrong?
Nothing -- I just forgot that you need to insert a -fopenmp flag in there in order to compile qfind. I'll fix that if/when I get around to it; until then, a quick patch would be to insert that flag into the compilation command in your ntqfind copy of gen-transtable.py.
former username: A for Awesome
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...

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: zfind discussion

Post by dani » January 28th, 2018, 12:48 am

Ntqfind Seems to be broken. I compiled the rule B2en3ij4a5e7e8/S1c2cek3-a4aiqw5aky and it isn't giving me spaceships, not even the small c/4 diagonal.

Code: Select all

$ ./ntqfind p4 k1 x1 a w6
ntqfind v0.2 by Matthias Merzenich and Aidan Pierce, 29 November 2017
Rule: B3/S23
Period: 4
Offset: 1
Width:  6
Symmetry: asymmetric
Queue size: 2^23
Hash table size: 2^21
Minimum deepening increment: 4
Number of threads: 1

Building lookup tables... Lookup tables built.
Sorting lookup table..... Lookup table sorted.
Starting search
Search complete.

Post Reply