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

zfind discussion

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

Re: zfind discussion

Postby muzik » June 24th, 2017, 5:17 pm

I don't think this zfind works with nontot rules
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik
 
Posts: 3249
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: zfind discussion

Postby 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.
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: zfind discussion

Postby A for awesome » 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:
$ 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.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1731
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby 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?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 902
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

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

Re: zfind discussion

Postby Rhombic » August 6th, 2017, 4:52 pm

Error while compiling
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”?
User avatar
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Postby 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.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 902
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Postby 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!
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”?
User avatar
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Postby 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!
error: expected expression before ‘)’ token
    <snip>

Which rule are you trying to build ntzfind for?
wildmyron
 
Posts: 1030
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby 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:
./ntzfind-setup B2cekin/S12
gcc ntzfind.c -O3 -o ntzfind

And here is the error:
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”?
User avatar
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Postby 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:
./ntzfind-setup B2cekin/S12
gcc ntzfind.c -O3 -o ntzfind

And here is the error:
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:
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))))));
}
wildmyron
 
Posts: 1030
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby Saka » September 30th, 2017, 10:47 pm

I ran
./ntzfind-setup B34enw5q6ae7c/S2ac3-cknq4-aenqt5akqy8
and then compiled and did
./ntzfind w8
and then it returned this, which it claims to be a spaceship:
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
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))));
}
If you're the person that uploaded to Sakagolue illegally, please PM me.
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2784
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: zfind discussion

Postby A for awesome » September 30th, 2017, 11:04 pm

Saka wrote:I ran
./ntzfind-setup B34enw5q6ae7c/S2ac3-cknq4-aenqt5akqy8
and then compiled and did
./ntzfind w8
and then it returned this, which it claims to be a spaceship:
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.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1731
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby 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”?
User avatar
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Postby danny » 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

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
Please stop using my full name. Refer to me as dani.

she/they

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.
User avatar
danny
 
Posts: 902
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

Re: zfind discussion

Postby A for awesome » 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:
/* 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:
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
zorq
in gen-transtable.py to
"q"
.) To compile for a particular rule, run
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.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1731
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby 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:
./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
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Postby A for awesome » 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:
./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.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1731
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby toroidalet » November 30th, 2017, 8:50 pm

Being a naïve noncoder, I don't know how to fix these 2 errors:
newntzfind.c:1:1: error: unknown type name 'import'
import re
^
newntzfind.c:1:10: error: expected ';' after top level declarator
import re
x = 4, y = 2, rule = B3/S23
ob2o$2obo!

(Check Gen 2)
User avatar
toroidalet
 
Posts: 920
Joined: August 7th, 2016, 1:48 pm
Location: my computer

Re: zfind discussion

Postby wildmyron » November 30th, 2017, 9:17 pm

toroidalet wrote:Being a naïve noncoder, I don't know how to fix these 2 errors:
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.
wildmyron
 
Posts: 1030
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby Rhombic » December 1st, 2017, 8:40 am

My ntqfind and ntzfind don't search even then, they just print
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
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

Re: zfind discussion

Postby Saka » December 1st, 2017, 9:25 am

Rhombic wrote:
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)
If you're the person that uploaded to Sakagolue illegally, please PM me.
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2784
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: zfind discussion

Postby AforAmpere » December 10th, 2017, 8:03 pm

When I try to compile ntqfind with
gcc -O3 -o ntqfind ntqfind.c
it does not work, saying unidentified reference to "omp_set_num_threads." What am I doing wrong?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 902
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Postby A for awesome » December 10th, 2017, 10:10 pm

AforAmpere wrote:When I try to compile ntqfind with
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.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1731
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby danny » 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.
$ ./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.
Please stop using my full name. Refer to me as dani.

she/they

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.
User avatar
danny
 
Posts: 902
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

PreviousNext

Return to Scripts

Who is online

Users browsing this forum: No registered users and 1 guest