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 » December 15th, 2016, 12:14 pm

Can it be somehow mixed with a loafer to at the very least have a nontrivial interaction, and at best stabilise it?

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 15th, 2016, 6:15 pm

Unrelated to the previous discussion, but would it be possible to modify zfind to (possibly optionally) consider possible offsetting of rows when one or more edge cells are empty in all generations of a specific row in asymmetric mode? Better stated, if the end of the partial looks like

Code: Select all

...0000???...???000...
...0000???...??0000...
(where 0 denotes empty in all generations), could zfind be modified to consider the possibility of the next row being in this position:

Code: Select all

...0000???...???000...
...0000???...??0000...
...000???...???0000...
as well as that of it being in this position:

Code: Select all

...0000???...???000...
...0000???...??0000...
...0000???...???000...
?
This doesn't seem like it would significantly increase memory requirements, although it would slow down the search (as a result of larger search space) as well as requiring more complex procedures to handle edges (maybe), lookahead, and other assorted things. DISCLAIMER: I only sort of know how zfind works, so forgive me if I'm making incorrect assumtions.
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...

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: zfind discussion

Post by David » December 15th, 2016, 6:57 pm

A few more partials found:

Code: Select all

x = 190, y = 25, rule = B3/S23
4bo19bo19bo19bo19bo19bo19bo19bo19bo19bo$2b2obo17b2o17b2obo17bobo17bobo
17bobo17bobo17bobo17bobo17bobo$5bo16bo18b2o2bo17bo2bo16bo2bo16bo2bo16b
obo16bo2bo16bo2bo16bo2bo$bo4b2o13b2obo17bo21b2o18b2o18b2o18bo18b2o18b
2o18b2o$4bob3o13bob3obo12bo2b2o$2b3o2bo17b2ob2o11bob3o17bo19bo19bo17b
2obo20bo19bo19bo$25bo2bo15b2o18bo19bo19bo16bo2bo18bo2bob2o13bo2bob2o
13bo2bob2o$25bo2bo34b2o18b2o18b2o38bo4b2o13bo4b2o13bo4b2o$3bo20bo18b3o
17bo3b2o14bo19bo4bo15b2o17bo4bo14bo4bo14bo4bo$2b3o20bobo16b2o20bo2bo
18bo18bobo17bo15b2obobo14b2obobo14b2obobo$5bo20b3o15b2o20bobo17b2obo
16bo16bo4bo13b6o14b6o14b6o$2bo3bo19b3o15bo16b3o2bo17b2obobo17b2o14b3o
3bo33b2o18b2o$bo5bo17b2o16bo17bo2bo2b2o16bob2o33bo4b2o13bobo18b2o18b2o
$bo5bo16bobo16b4o18bob2o16bobo19bobo10bobo4bo13bo3b2o13b2ob2o15b2ob2o$
5b2o16b2obo2bo13bo2b2o15bobo22bo20bo10bo21b2o3b2o11bo2b2o15bo2b2o$2b2o
16b6ob2o17bobo16b2o18bobo12b2obob2o15bo2b2o17bobobo$2bo38b2o2b2ob2o15b
3o16bo38bob2o16bo3bobo15bo19bo$b2o4b2o34b2obob2o34b2obo35b5o34bo3bo14b
2o3bo$41bob2obobo15bo21b2o37bob3o31bo3bo19bo$64bo96b2o2bo18b4o$62bo3bo
bo53bo39bobo21bobo$61bob5o54b2o4bo38b3o19bo$60bo4bo101b3o13b2o$61bobob
2o$63bobo!
Why isn't the loafer found yet?
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: zfind discussion

Post by David » December 16th, 2016, 3:54 am

zfind is finding mirror images of previously searched patterns; I'm terminating the search.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Post by Sokwe » December 16th, 2016, 4:23 am

HartmutHolzwart wrote:Are there other results from zfind searches in B3/S23 I overlooked?
Probably not. I think most of the zfind results that people have posted are in the following threads:
muzik wrote:Can it be somehow mixed with a loafer to at the very least have a nontrivial interaction, and at best stabilise it?
Yes, that is possible. It also might just find some other spaceship before it finds the loafer.
David wrote:Why isn't the loafer found yet?
The search has not found the right front end yet. There are a few partials that look like the start of the loafer, but the loaf is not in the right place. The loaf is near the center of the search space, but it needs to be near the edge to find the loafer. To see what I mean, look at this LifeHistory pattern where the blue cells represent the search space:

Code: Select all

x = 40, y = 40, rule = LifeHistory
10B20.10B$10B20.10B$10B20.10B$10B20.10B$10B20.10B$10B20.10B$10B20.10B
$10B20.10B$10B20.10B$10B20.10B$4BA5B20.2BA7B$3BABA4B20.BABA6B$3BA2BA
3B20.BA2BA5B$4B2A4B20.2B2A6B$10B20.10B$3BA6B20.BA5BA2B$4BA5B20.2BA3BA
BAB$3B2A5B20.B2A3BA2BA$3BA3B2AB20.BA3B2A2BA$6BA2BA20.10B$6BABAB20.10B
$B3A2BA3B20.10B$BA2BA2B2AB20.10B$5BAB2AB20.10B$3BABA4B20.10B$5B2A3B
20.10B$5B3A2B20.10B$10B20.10B$4BA5B20.10B$4BA5B20.10B$2BA3BABAB20.10B
$BAB5A2B20.10B$A4BA4B20.10B$BABAB2A3B20.10B$3BABA4B20.10B$10B20.10B$
10B20.10B$10B20.10B$10B20.10B$10B20.10B!
David wrote:zfind is finding mirror images of previously searched patterns; I'm terminating the search.
This was guaranteed to happen at some point. It doesn't mean that the search is done finding new patterns. It just means that it happened to start with the reverse of a row that it had already looked at. I eventually plan to fix it so that it doesn't do this. Again, I suggest doing a gutter search ('g' parameter) instead of an asymmetric search.
A for awesome wrote:Unrelated to the previous discussion, but would it be possible to modify zfind to (possibly optionally) consider possible offsetting of rows when one or more edge cells are empty in all generations of a specific row in asymmetric mode?
There are some complexities to this request. I will try to give an idea of it, but the explanation might be hard to follow. First, how zfind finds a new row:

zfind works similarly to gfind, so understanding gfind is helpful. zfind uses the ideas in sections 4 and 6 of David Eppstein's "Searching for Spaceships" article.

To find a new row, zfind takes 3 known rows, A, B, and Y, and looks for a row X so that evolve(A,B,X)=Y. That is,

Code: Select all

AAAAAAAA
BBBBBBBB   ->   YYYYYYYY
XXXXXXXX
It does this by using two lookup tables. The first table actually gives the rows X that we are looking for (stored as unsigned 16-bit integers). The second table gives indices into the first table (stored as unsigned 32-bit integers). The input for the second lookup table is the three rows A, B, and Y. So for any combination of 3 rows we must store a 32-bit integer. That's 2^(3*width) 32-bit integers. This is over 4 gigabytes for a width-10 search. If we allow for row shifting, we have to expand the lookup table somewhat. We would need to add shift information to each row that tells us how far it is shifted compared to nearby rows. I don't know the best way to do this, so I will have to think about it some more.

The proposal isn't bad, however. There should be ways to reduce the memory usage for asymmetric searches, since a lot of the lookup table is redundant (because I don't check for equivalent reversed rows). This memory saving might be enough to offset the extra memory from the expanded lookup table.

Such an update seems somewhat complex. I'll put on a list of things to consider when I'm fixing the asymmetric search so that it doesn't find ships twice.
-Matthias Merzenich

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

Re: zfind discussion

Post by Saka » December 16th, 2016, 6:35 am

Random partials

Code: Select all

x = 242, y = 96, rule = B3/S23
73b2o$27bo6bo16bo5bo$26b2o6b2o14bobo3bobo11bo6bo$28bo4bo16bobo3bobo10b
o8bo$25b2o8b2o14bo5bo10bob8obo$3bobobo3bobobo12bo4bo34bo4b2o4bo50b2o
20bo$25b2o2bo2bo2b2o30b2obo6bob2o47b6o18bo$3bo7bo3bo9b2ob2o2b2ob2o13b
3o3b3o8b3o8b3o22bobobo3bobobo11b8o15b5o$28bo4bo15bobobobobobo11bo4bo
49bo8bo$3bo7bobobo34bo2bobo2bo12bob2obo26bo7bo3bo10b2o6b2o74b2o$27b3o
2b3o18bobo15b2o2b2o49b2ob4ob2o47bobobo3bo3bo$3bo7bo3bo12bo4bo19bobo13b
ob2o2b2obo24bo7bobobo11bob4obo16b3o53bo6bo19b2o$28bo4bo17bobobobo10b2o
bo4bob2o46bo2bo2bo2bo14b2ob2o28bo7bo3bo10bo8bo$3bobobo3bobobo12b2o2b2o
18bo3bo11b2o8b2o23bo11bo13bo2bo16bobobobo52b2o2b2o$28bob2obo34b2ob2o2b
2ob2o46bo2bo2bo2bo12b2obobob2o26bo7bo3bo11bo6bo14bo10bo$27b2o4b2o16b2o
3b2o11bob6obo24bobobo3bobobo11bo6bo12bo9bo50b2o2b2o14b2obob4obob2o$28b
ob2obo15bo2bo3bo2bo8bo4b2o4bo67bo9bo25bo7bo3bo11b3o2b3o13b2o2bo4bo2b2o
$49bob2o3b2obo8b2obo4bob2o46bo8bo11bo3b3o3bo49bobo2bobo18b4o$26bo3b2o
3bo31b2o2bo4bo2b2o45bob6obo11bo3bobo3bo25bobobo3bo3bo12b2o2b2o$52b2ob
2o10b2ob3o2b3ob2o45bob2o2b2obo12b3o3b3o52bo2bo21b2o$27b3o2b3o17b2ob2o
11bo4b2o4bo48bo4bo14bobo3bobo49b2ob4ob2o14b2o6b2o$28b2o2b2o17b3ob3o71b
o2bo13bo2bo5bo2bo48bo6bo15bob6obo$52bo3bo69b2o6b2o10bo3bo3bo3bo74b4o$
27bobo2bobo15b4ob4o66bob2o4b2obo13bo3bo51b3o4b3o16b2o2b2o$26bob2o2b2ob
o18bo72bo6bo11bo2b2o3b2o2bo47b4o2b4o15b2o4b2o$25b3o6b3o12b2o7b2o64bo
12bo8bo11bo49bo4bo16b2o6b2o$24b3o8b3o11bo9bo65b3o6b3o11b3o3b3o49bobo4b
obo15b2ob2ob2o$24b2o10b2o10b4ob3ob4o66bo6bo16bobo50bob2ob4ob2obo12bo3b
2o3bo$28b6o15b2o7b2o69bo2bo17b2ob2o49bo2bo6bo2bo10b2o3bo2bo3b2o$28b2o
2b2o16bo7bo69b2o2b2o12b3o3bo3b3o46bo10bo12b2o3b2o3b2o$25b2obo4bob2o88b
ob3o2b3obo13bo3bo51bo3b2o3bo13bo2bo4bo2bo$28bob2obo91b2obo4bob2o68b3ob
4ob3o13b4o2b4o$25b2obob2obob2o89b2o6b2o68bo12bo10bo4bo2bo4bo$25bo3bo2b
o3bo$27b3o2b3o90bo3b4o3bo$24bo3bo4bo3bo$24bob2o6b2obo$28b2o2b2o33$104b
o6bo$103b2o6b2o2$101bo2bo6bo2bo$101bo2bo6bo2bo$77bo6bo18b2o6b2o$77bo6b
o20bo4bo$76bobo4bobo17b3o4b3o$78bo4bo20bo6bo$79bo2bo$58b2o$obobo3bobob
o3bobobo14bo6bo13bo4bo43b6o$34b2o6b2o11bo6bo13b2ob4ob2o18bo2b2o2bo$4bo
3bo7bo3bo33bo8bo11bob2ob2ob2obo16bo3b2o3bo$32bo2bo6bo2bo8bo2b4o2bo11bo
bo6bobo16bo2bo2bo2bo$obobo3bo7bobobo11bo2bo6bo2bo8bo8bo11bobo6bobo16b
3o4b3o$34b2o6b2o10bobob2obobo39bob6obo$o7bo11bo15bo4bo12bobob2obobo13b
o6bo22b2o$34b3o4b3o9b2o8b2o12bob4obo17b2o8b2o$obobo3bobobo3bobobo14bo
6bo10b3o6b3o10b2o2bo2bo2b2o15b2obo4bob2o$53b2o8b2o11bobo4bobo17bob2o2b
2obo$38b2o15bob4obo13b2ob4ob2o16bo2b2o2b2o2bo$37b4o14bob4obo13bo8bo17b
ob2o2b2obo$36bo4bo12b2o6b2o11b2o2b4o2b2o15b2obo4bob2o$33bo2bob2obo2bo
8bo10bo10b2o2b4o2b2o16b2ob4ob2o$52bobo8bobo9bo3bo2bo3bo16bo8bo!
Looking at the 2c/9 section one may exist and be smaller than expected!

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: zfind discussion

Post by muzik » December 16th, 2016, 7:04 am

I feel like the discovery of c/8 elementary is not too far off now.

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 16th, 2016, 6:42 pm

Sokwe wrote:If we allow for row shifting, we have to expand the lookup table somewhat. We would need to add shift information to each row that tells us how far it is shifted compared to nearby rows. I don't know the best way to do this, so I will have to think about it some more.
Oh, sorry, I'm stupid; I forgot that the effective width at the shorter row would be one too large compared to the others. If the requirement for the number of reduced-width rows to trigger the consideration of a shift was increased to two, would that allow the lookup table expansion to be replaced with a simple bit-shift?
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
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: zfind discussion

Post by Saka » December 17th, 2016, 1:50 am

Random partials. Figuring out their speed is an exercise for the reader.

Code: Select all

x = 91, y = 33, rule = B3/S23
6b2o$4bo4bo$4bo4bo$4bo4bo2$6b2o$5b4o$3b2o4b2o$4bo4bo$4bo4bo$5bo2bo$4b
2o2b2o$2bob2o2b2obo$bo3bo2bo3bo$o4bo2bo4bo66bo6bo$bo2bo4bo2bo40bo6bo
18bobo4bobo$b2ob2o2b2ob2o13b2o24bobo4bobo16b2ob2o2b2ob2o$4b2o2b2o42bo
2bo2bo2bo16b2o2bo2bo2b2o$52bobo4bobo17b2ob4ob2o$3b2o4b2o10bo10bo20b2o
4b2o19bobo2bobo$2bo8bo8bo4b4o4bo18bobo4bobo17bo3b2o3bo$2bo8bo41bo6bo
19b3o2b3o$bo2bo4bo2bo9b3o4b3o20bo8bo17b2o2b2o2b2o$2b4o2b4o10bo8bo20b2o
6b2o16b2o3b2o3b2o$5bo2bo12bobo6bobo18b12o18bo4bo$3bo6bo10bo2b2o2b2o2bo
17b2o2bo4bo2b2o15b4o2b4o$4b6o11bo10bo17b3o8b3o15bo2bo2bo2bo$bobo6bobo
9b3o4b3o20bobo4bobo18bob4obo$o2bobo2bobo2bo8bo3b2o3bo20b4o2b4o20bo2bo$
b5o2b5o13b2o25bo6bo19bob4obo$bo4b2o4bo9bo2b4o2bo22bo4bo18b2o8b2o$5bo2b
o12bo2b6o2bo18b2ob6ob2o15bo3bo2bo3bo$77b2ob2o4b2ob2o!

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

Re: zfind discussion

Post by drc » December 17th, 2016, 1:28 pm

Answers(highlight text to reveal): c/7, c/12, 4c/11, 2c/5 |

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

Re: zfind discussion

Post by Saka » December 18th, 2016, 3:40 am

Code: Select all

x = 91, y = 31, rule = B3/S23
3bo6bo$2bobo4bobo$2bo2bo2bo2bo$3b2o4b2o2$2bobo4bobo$2bo2bo2bo2bo31bo$
2bobo4bobo30bobo$2b3o4b3o30bobo15bo5bo$bobo6bobo30bo15bobo3bobo$2ob2o
4b2ob2o45bobo3bobo17b2o$3bo6bo49bo5bo17bo2bo$23bo60bo2bo$21bo3bo16b3o
40b2o$6b2o13bo3bo15bo3bo13b3o3b3o$4bo4bo11bobobo14bo5bo11bobobobobobo$
bob3o2b3obo27bo5bo12bo2bobo2bo15bo4bo$o12bo7b2ob2o15b2ob2o16bobo17bob
4obo$bob3o2b3obo8b2ob2o15b2ob2o16bobo18b2o2b2o$2b2o6b2o31bo16bobobobo
16b2o2b2o$42bobo16bo3bo$3b2o4b2o29b2o3b2o35b3o2b3o$4bob2obo10b3ob3o12b
2ob3ob2o12b2o3b2o14bo2bo2bo2bo$2b10o8b2obob2o11bo3bobo3bo10bo2bobo2bo
13b2obo2bob2o$2b2obo2bob2o26bo3bobo3bo12b2ob2o18b4o$3bobo2bobo12bo35bo
bo3bobo14bobo2bobo$5bo2bo12bo3bo12bo3b3o3bo10b2o5b2o14b3o2b3o$2obo6bob
2o5bob5obo31b2o5b2o13bob2o2b2obo$2b2obo2bob2o8bo2bo2bo12b3obob3o13bo3b
o$5bo2bo11b2o3b2o12b2obobob2o11b9o14bo6bo$2bo8bo9bobobo12bo2bo3bo2bo
10bo3bo3bo13b10o!

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

Re: zfind discussion

Post by Saka » December 19th, 2016, 4:03 am

Help! I cannot compile ntzfind.

Code: Select all

Saka@Saka-PC ~/ntzfind
$ ./ntzfind-setup b3-cnry4-acery5i/s23-a4-jknqr5y8

Saka@Saka-PC ~/ntzfind
$ ./ntzfind-compile.sh
./ntzfind-compile.sh: line 2: $'\r': command not found
In file included from ntzfind.c:7:0:
step.c: In function ‘stepcell’:
step.c:2:21: error: expected expression before ‘)’ token
    return (o&((0x0|())));
                     ^

Saka@Saka-PC ~/ntzfind
$
Here is 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|())));
}

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

Re: zfind discussion

Post by wildmyron » December 19th, 2016, 4:46 am

Saka wrote:Help! I cannot compile ntzfind.
You seem to be mixing up the instructions: Executing ntzfind-compile.sh with no argument will run ntzfind-setup again with no rule specified, which is why step.c is missing the required logic to implement the rule.

Either,

run ntzfind-compile.sh with the rule as argument, i.e.

Code: Select all

./ntzfind-compile.sh  b3-cnry4-acery5i/s23-a4-jknqr5y8
OR,

run ntzfind-setup followed by compiling ntzfind, which is exactly what ntzfind-compile.sh does

Code: Select all

$ ./ntzfind-setup b3-cnry4-acery5i/s23-a4-jknqr5y8
$ gcc ntzfind.c -O3 -o ntzfind
(which presupposes the existence of a compiled ntzfind-setup)


P.S. Can you please post your zfind results in more appropriate threads, unless they specifically relate to discussion about zfind itself.
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.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: zfind discussion

Post by Naszvadi » December 20th, 2016, 7:45 pm

Is there an available glider searching program for (B0 and) Neumann-neighbourhood rules?

If no, then zfind or any other glider searching tool is capable to work with B0 and nontotalistic rulestrings together?

Thanks!

Unfortunately, Neumann - two state 2D cellular automata cannot have gliders withOUT B0 in rulestring.

EDIT: tools for converting Neumann rulestrings are here:

http://conwaylife.com/forums/viewtopic. ... 502#p38502

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Post by Sokwe » December 21st, 2016, 11:16 am

Note: there are two versions of zfind provided in this post. zfind 2.0 has more features, but zfind-s is faster.

I have made a small update to zfind. Functionally, all it does is change how the dump period works. Now, including "dNN" in the parameters means that the state will be dumped every 2^NN calculations. Anything less than NN = 20 is probably too fast, so I set that as a minimum (MIN_DUMP in the source code). This change was made because the modulo operator was noticeably slowing down the program.

I also added what should be a more portable timer function (taken from here). Here is the updated code:

Code: Select all

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

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

#define BANNER "zfind 2.0 by \"zdr\" and Matthias Merzenich, 21 December 2016"
#define FILEVERSION ((unsigned long) 2016122101)  //yyyymmddnn

#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){
   int r;
   r = bc[(row1 >> bshift) & 7];
   r += bc[(row2 >> bshift) & 7] + 4 * ((row2 >> bshift) & 2);
   r += bc[(row3 >> bshift) & 7];
   return (rule >> r) & 1;
}

int evolveRow(int row1, int row2, int row3){
   int row4;
   int row1_s,row2_s,row3_s;
   int j,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;
}
For this version, I also rewrote most of the code that remained from the original zfind into what I consider a more readable form. It still lacks comments, but at least I am more sure that it works correctly.

After rewriting the code, I went over it very carefully and convinced myself that if a search finishes and finds no spaceships, then no ships exist, provided that zfind 2.0 or zfind-s is used, gcd(period,offset) = 1, and none of the following special features were used:
  • multiple ships
  • max length
  • full period by specified depth
  • max width of full-period rows
That is, if you run a search with the above restrictions and it finishes with "Search complete: 0 spaceships found." then no spaceships exist for those parameters.

I have added a zfind section to my spaceship search page, and I will also add zfind results to the spaceship search status page, as long as they satisfy the conditions given above.

I have also created an alternate version of zfind (called "zfind-s") that removes all "extraneous features". Basically, it removes the special features mentioned above and requires gcd(period,offset) = 1. It also requires that PERIOD, OFFSET, and WIDTH be set at compile time (see lines 15-17 of the code below). The purpose of all of this is to make zfind slightly faster for these searches. You should definitely use this version if you are trying to, for example, find an elementary c/8 spaceship.

Note that when using the dump feature for zfind-s, the period, offset, and width are not saved, so you will need to keep track of these parameters yourself.

Here is the code for zfind-s:

Code: Select all

/* zfind-s (simple zfind)
** A spaceship search program by "zdr" with modifications by Matthias Merzenich
**
** Warning: this program uses a lot of memory (especially for wide searches).
*/

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

#define BANNER "zfind-s by \"zdr\" and Matthias Merzenich, 21 December 2016"
#define FILEVERSION ((unsigned long) 2016122102)  //yyyymmddnn

#define WIDTH 6
#define PERIOD 3
#define OFFSET 1

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

#define P_RULE 0
#define P_DEPTH_LIMIT 1
#define P_SYMMETRY 2
#define P_INIT_ROWS 3
#define P_REORDER 4
#define P_DUMP 5

#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;
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 gcd(int a, int b){
   int c;
   while (b){
      c = b;
      b = a % b;
      a = c;
   }
   return a;
}

int evolveBit(int row1, int row2, int row3, int bshift){
   int r;
   r = bc[(row1 >> bshift) & 7];
   r += bc[(row2 >> bshift) & 7] + 4 * ((row2 >> bshift) & 2);
   r += bc[(row3 >> bshift) & 7];
   return (rule >> r) & 1;
}

int evolveRow(int row1, int row2, int row3){
   int row4;
   int row1_s,row2_s,row3_s;
   int j,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);
   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];
      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 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",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;
}

void search(){
   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;
   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;
   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();
   for(;;){
      ++calcs;
      if(currRow > longest || !(calcs & 0xffffff)){
         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){
            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]){
         --currRow;
         if(currRow < 2 * PERIOD){
            printPattern();
            printf("Search complete: 0 spaceship found.\n");
            printInfo(-1,calcs,get_cpu_time() - ms);
            return;
         }
         continue;
      }
      --pRemain[currRow];
      pRows[currRow] = gRows[pInd[currRow] + pRemain[currRow]];
      
      rowSet11 = (pRows[currRow - PERIOD - (OFFSET)] << (2 * WIDTH))
                +(pRows[currRow - (OFFSET)] << WIDTH)
                + pRows[currRow];
      riStart11 = gInd[rowSet11];
      numRows11 = gInd[rowSet11 + 1] - riStart11;
      if(!numRows11) continue;
      
      rowSet12 = (pRows[currRow - PERIOD - (2 * OFFSET)] << (2 * WIDTH))
                +(pRows[currRow - (2 * OFFSET)] << WIDTH)
                + pRows[currRow - (OFFSET)];
      riStart12 = gInd[rowSet12];
      numRows12 = gInd[rowSet12 + 1] - riStart12;
      
      if((3 * OFFSET) >= PERIOD){
         riStart13 = pInd[currRow + PERIOD - (3 * OFFSET)] + pRemain[currRow + PERIOD - (3 * OFFSET)];
         numRows13 = 1;
      }
      else{
         rowSet13 = (pRows[currRow - PERIOD - (3 * OFFSET)] << (2 * WIDTH))
                   +(pRows[currRow - (3 * OFFSET)] << WIDTH)
                   + pRows[currRow - (2 * OFFSET)];
         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[currRow - (2 * OFFSET)] << (2 * WIDTH))
                      +(row12 << 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[currRow - (3 * OFFSET)] << (2 * WIDTH))
                         +(row13 << 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 * WIDTH))
                               +(row23 << WIDTH)
                               + row22;
                     if(gInd[rowSet33] != gInd[rowSet33 + 1]) goto foundRow33;
                  }
               }
            }
         }
      }
      continue;
      foundRow33:;
      
      ++currRow;
      
      if(currRow > sp[P_DEPTH_LIMIT]){
         noship = 0;
         for(j = 1; j <= 2 * period; ++j) noship |= pRows[currRow-j];
         if(!noship){
            printPattern();
            printf("Search terminated: spaceship found.\n");
         }
         else{
            printPattern();
            printf("Search terminated: depth limit reached.\n");
            printf("Depth: %d\n", currRow - 2 * period);
         }
         printInfo(currRow,calcs,get_cpu_time() - ms);
         return;
      }
      newRowSet = (pRows[currRow - 2 * period] << (2 * WIDTH))
                 +(pRows[currRow - period] << WIDTH)
                 + pRows[currRow - period + OFFSET];
      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);
   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 = WIDTH;
   period = PERIOD;
   offset = OFFSET;
   
   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 = WIDTH;
   period = PERIOD;
   offset = OFFSET;
   sp[P_DEPTH_LIMIT] += 2 * period;
   
   pRows = malloc(sp[P_DEPTH_LIMIT] * 2);
   pInd = malloc(sp[P_DEPTH_LIMIT] * 4);
   pRemain = malloc(sp[P_DEPTH_LIMIT] * 4);
   
   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",PERIOD);
   printf("Offset: %d\n",OFFSET);
   printf("Width:  %d\n",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");
   printf("Depth limit: %d\n",sp[P_DEPTH_LIMIT] - 2 * period);
   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("Note: period, offset, and width must be changed in the source code.");
   printf("\n");
   printf("Available options:\n");
   printf("  bNN/sNN searches for spaceships in the specified rule (default: b3/s23)\n");
   printf("\n");
   printf("  lNN  terminates the search if it reaches a depth of NN (default: %d)\n",DEFAULT_DEPTH_LIMIT);
   printf("\n");
   printf("  dNN  dumps the search state every 2^NN calculations\n");
   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-s 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_DEPTH_LIMIT] = DEFAULT_DEPTH_LIMIT;
   sp[P_SYMMETRY] = 0;
   sp[P_INIT_ROWS] = 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 '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 '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 '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_SYMMETRY]){
      printf("You must specify a symmetry type.\n");
      printf("For command line options, type 'zfind-s c'.\n");
      return 0;
   }
   echoParams();
   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 + OFFSET];
         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*WIDTH + 4) * sp[P_DEPTH_LIMIT]);  // I think this gives more than enough space
   buf[0] = '\0';
   printf("Starting search\n");
   search();
   return 0;
}
-Matthias Merzenich

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

Re: zfind discussion

Post by wildmyron » December 21st, 2016, 10:26 pm

@Sokwe: Many thanks for your continued efforts in developing zfind.

Are the results in the new zfind table on your Spaceship Search Status page derived from your testing of zfind-s / zfind 2.0 or do any of them still need verification?

I had just kicked off a c/8 search yesterday which will run over the holiday period but in light of your comments I'll restart it today with zfind-s. The search I'm running is

Code: Select all

zfind b3s23 p8 k1 w9 g
As far as I can tell from the Spaceship discussion thread, this search hasn't been run yet and I'm hoping it will take between 2-4 weeks. I haven't run the w8 search myself so the time estimate is very much a "swag".

Edit: I see that zfind outputs the full ship now, nice!
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 » December 21st, 2016, 11:10 pm

wildmyron wrote: I had just kicked off a c/8 search yesterday which will run over the holiday period but in light of your comments I'll restart it today with zfind-s. The search I'm running is

Code: Select all

zfind b3s23 p8 k1 w9 g
Good luck with the search!

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Post by Sokwe » December 22nd, 2016, 12:33 am

wildmyron wrote:Are the results in the new zfind table on your Spaceship Search Status page derived from your testing of zfind-s / zfind 2.0 or do any of them still need verification?
The results in my table were all checked with zfind 2.0. The longest search so far was the c/6 width-19 gutter search which took about 2 hours and 20 minutes. My current plan is to use zfind 2.0 / zfind-s to verify the results in the main table (at least as much as possible). I am also running the c/7 width-17 odd search with zfind-s.
wildmyron wrote:I had just kicked off a c/8 search yesterday which will run over the holiday period but in light of your comments I'll restart it today with zfind-s. The search I'm running is

Code: Select all

zfind b3s23 p8 k1 w9 g
You should definitely run the search with the dump state parameter. Also, you should probably increase the depth limit (something large like "l8000"). One nice thing about the dumps is that if the depth limit is reached, you can go into the last dump file, increase the depth limit, save the file, and continue the search.

And yes, you should use zfind-s. At least for me, zfind-s ran around 15% faster for some small (1-2 minute) test searches. That could be almost a day off of a week-long search.

Edit: you should also probably redirect the output to a file (maybe you're already doing all of this stuff, but I just wanted to be sure).
wildmyron wrote:As far as I can tell from the Spaceship discussion thread, this search hasn't been run yet
Nobody has mentioned it, so it probably hasn't been run. Good luck!
Naszvadi wrote:Is there an available glider searching program for (B0 and) Neumann-neighbourhood rules?
gfind has support for life-like rules with B0. This could possibly be adapted to von Neumann neighbourhood rules, but I don't know the details.

To accomplish this with zfind, you would need to keep track of the parity in each phase (i.e. whether the background is on or off). You would also probably need another lookup table for when the background is on.
A for awesome wrote:If the requirement for the number of reduced-width rows to trigger the consideration of a shift was increased to two, would that allow the lookup table expansion to be replaced with a simple bit-shift?
Possibly? I'll have to give it more thought, but it's a low priority right now.
-Matthias Merzenich

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

Re: zfind discussion

Post by wildmyron » December 22nd, 2016, 3:34 am

Sokwe wrote:
wildmyron wrote:I had just kicked off a c/8 search yesterday which will run over the holiday period but in light of your comments I'll restart it today with zfind-s. The search I'm running is

Code: Select all

zfind b3s23 p8 k1 w9 g
You should definitely run the search with the dump state parameter. Also, you should probably increase the depth limit (something large like "l8000"). One nice thing about the dumps is that if the depth limit is reached, you can go into the last dump file, increase the depth limit, save the file, and continue the search.

And yes, you should use zfind-s. At least for me, zfind-s ran around 15% faster for some small (1-2 minute) test searches. That could be almost a day off of a week-long search.

Edit: you should also probably redirect the output to a file (maybe you're already doing all of this stuff, but I just wanted to be sure).
Thanks for the tips. I am redirecting to file and have specified d32 - this gives me a dump approximately every 10min. d33 or d34 might be more suitable for such a long running search. I hadn't considered that the max depth might be insufficient, but of course with p8 that corresponds to about 250 rows. It seems unlikely to me the search will reach that far without hitting a repeating component considering the length of partials for c/8 posted so far but I'll up the depth limit and dump interval and continue at the next dump file.

As a test, I ran the "p8 k1 w7 u" search with zfind 2.0 and zfind-s. The speed improvement was consistent with your 15% improvement for shorter searches. (533s for zfind-s)

As an aside, have you considered other compiler options? I simply compiled with -O3 and haven't though about other optimizations.

Edit: Actually, I should note that there were some other searches running at the same time as the above tests, so don't take any of the numbers as accurate performance characteristics.
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.

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Post by Sokwe » December 22nd, 2016, 4:45 am

wildmyron wrote:As an aside, have you considered other compiler options? I simply compiled with -O3 and haven't though about other optimizations.
I must admit that I don't know much about using compiler options to maximize performance. I have been compiling with gcc -O3. For me at least, the difference between -O3 and -O2 doesn't seem like much.

Maybe someone with more experience in the subject will have something to add. If anyone can figure anything out that gives a noticeable performance increase, please share it.
-Matthias Merzenich

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: zfind discussion

Post by simeks » December 22nd, 2016, 7:14 am

Sokwe wrote:
wildmyron wrote:As an aside, have you considered other compiler options? I simply compiled with -O3 and haven't though about other optimizations.
I must admit that I don't know much about using compiler options to maximize performance. I have been compiling with gcc -O3. For me at least, the difference between -O3 and -O2 doesn't seem like much.

Maybe someone with more experience in the subject will have something to add. If anyone can figure anything out that gives a noticeable performance increase, please share it.
I would suggest adding "-march=native" as a compiler option. It will generate the most appropriate instructions for the particular CPU of the machine used while compiling. Of course, the generated executable is not guaranteed to work properly on a machine with a different (older) CPU architecture.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: zfind discussion

Post by GUYTU6J » December 24th, 2016, 11:23 am

Now I am trying to use zfind opened in Command Prompt on my computer,and it works like this
zfindproblem.png
zfindproblem.png (10.09 KiB) Viewed 16711 times
I have two questions :cry:
1.How can I know that the zfind is running?
2.I'm using the initial rows generator from the top of the 3rd page of this topic,but it fails...Why?

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

Re: zfind discussion

Post by drc » December 24th, 2016, 1:49 pm

ntzfind keeps tossing errors:

Code: Select all

$ ./ntzfind-compile.sh b2i34c/s2-i3
./ntzfind-compile.sh: line 2: ./ntzfind-setup: No such file or directory
ntzfind.c:7:18: fatal error: step.c: No such file or directory
 #include "step.c"

Code: Select all

$ ./ntzfind-setup.cpp b2i34c/s2-i3
./ntzfind-setup.cpp: line 1: //Yes,: No such file or directory
./ntzfind-setup.cpp: line 5: //I: No such file or directory
./ntzfind-setup.cpp: line 6: class: command not found
./ntzfind-setup.cpp: line 7: $'public:\r': command not found
./ntzfind-setup.cpp: line 8: std::string: command not found
./ntzfind-setup.cpp: line 8: $'\r': command not found
./ntzfind-setup.cpp: line 9: syntax error near unexpected token `{}'
'/ntzfind-setup.cpp: line 9: `      Transition(){};

Code: Select all

$ ./ntzfind.c
./ntzfind.c: line 1: //Save: No such file or directory
./ntzfind.c: line 2: $'\r': command not found
./ntzfind.c: line 8: $'\r': command not found
./ntzfind.c: line 10: $'\r': command not found
./ntzfind.c: line 11: int: command not found
./ntzfind.c: line 11: $'\r': command not found
./ntzfind.c: line 12: uint32_t: command not found
./ntzfind.c: line 12: $'\r': command not found
./ntzfind.c: line 13: uint16_t: command not found
./ntzfind.c: line 13: $'\r': command not found
./ntzfind.c: line 14: int: command not found
./ntzfind.c: line 14: $'\r': command not found
./ntzfind.c: line 15: char: command not found
./ntzfind.c: line 15: $'\r': command not found
./ntzfind.c: line 16: $'\r': command not found
./ntzfind.c: line 17: int: command not found
./ntzfind.c: line 17: $'\r': command not found
./ntzfind.c: line 18: $'\r': command not found
./ntzfind.c: line 19: syntax error near unexpected token `('
'/ntzfind.c: line 19: `void plong(long a){
Windows 7, applied patches.

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 24th, 2016, 2:15 pm

drc wrote:ntzfind keeps tossing errors
Try running

Code: Select all

g++ ntzfind-setup.cpp -o ntzfind-setup
and tell me what happens. There's probably some error there that isn't getting displayed.
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...

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Post by Sokwe » December 24th, 2016, 4:05 pm

GUYTU6J wrote:Now I am trying to use zfind opened in Command Prompt on my computer
First, zfind only works for widths up to 10. Your first search uses a width of 16 and your second search uses a width of 27. Your first search crashed because the width was greater than 10.
GUYTU6J wrote:How can I know that the zfind is running?
One way to tell is that it won't allow you to write anything in the terminal/command prompt while the search is running. It will also give a lot of output while it's running. When it finishes, it either says "search complete" or "search terminated".
I'm using the initial rows generator from the top of the 3rd page of this topic,but it fails...Why?
Is initrows.txt in the same folder as zfind.exe?
-Matthias Merzenich

Post Reply