zfind discussion

[GUYTU6J]

Next question:how to continue those known partials?Which row can I made into "initrows"?
For example,this c/8 partial

Code: Select all

x = 17, y = 19, rule = B3/S23
8bo$7bobo$7bobo$3b2o3bo3b2o$3b2o7b2o$2bo2bo5bo2bo$3b2o2b3o2b2o$7b3o$4b
o2bobo2bo$2b2ob7ob2o$bo13bo2$bobobo5bobobo$2b2o9b2o$3bob2o3b2obo$4b3o
3b3o$2bo11bo$2b3o3bo3b3o$obo4b3o4bobo!

[Sokwe]

Which row can I made into "initrows"?

The starting row should be one that is still correct after running the partial through the whole period.

Here is the partial you posted (left) compared to the partial after 8 generations (right):

Code: Select all

x = 48, y = 23, rule = B3/S23
8bo29bo$7bobo27bobo$7bobo27bobo$3b2o3bo3b2o19b2o3bo3b2o$3b2o7b2o19b2o
7b2o$2bo2bo5bo2bo17bo2bo5bo2bo$3b2o2b3o2b2o19b2o2b3o2b2o$7b3o27b3o$4bo
2bobo2bo21bo2bobo2bo$2b2ob7ob2o17b2ob7ob2o$bo13bo15bo13bo2$bobobo5bobo
bo15bobobo5bobobo$2b2o9b2o15bo2bobobobobobo2bo$3bob2o3b2obo17bobo2bo3b
o2bobo$4b3o3b3o17b2o13b2o$2bo11bo15b3o11b3o$2b3o3bo3b3o14b2obo11bob2o$
obo4b3o4bobo12bo17bo$30bo4bo5bo4bo$31bo3b7o3bo$36b5o$38bo!

Notice that the first 13 rows are correct. That means the starting row should be row 12 or less. Actually, you should probably use row 10 or less.

[GUYTU6J]

Here's my result after doing as you said

noextension.png (23.84 KiB) Viewed 18597 times

The search quickly came to an end and there was no further improvement Why?
EDIT:Tried several other partials, but the result was the same-no more extended rows than the original partials.

[GUYTU6J]

Strange!I generated this initial row

Code: Select all

....o....
....o....
....o....
....o....
...o.o...
...o.o...
...o.o...
...o.o...

I used it to find a c/4 ,and the output was

Code: Select all

x = 17, y = 264, rule = B3/S23
4bo7bo$3bobo5bobo$4bo7bo$6bo3bo$4bobo3bobo$4bobo3bobo2$6bo3bo$6bo3bo$
5b2o3b2o2$4b2obobob2o$2b2obobobobob2o$2b4o2bo2b4o$2b2o9b2o$b2o11b2o$8b
o$6b2ob2o3$5b3ob3o$5b2o3b2o$b3o9b3o2$bobo9bobo$3b2o7b2o$3bo9bo$2b2o3b
3o3b2o$3bo4bo4bo2$2bobobo3bobobo$2bo3b2ob2o3bo$3b2ob2ob2ob2o$3b2ob2ob
2ob2o$3bo2bo3bo2bo$4o9b4o$3bob2obob2obo$5b7o$5b2obob2o$3b2ob2ob2ob2o$b
2o11b2o$4bob5obo$b3ob7ob3o2$b2o2b2o3b2o2b2o$o4bo5bo4bo$bo3b2o3b2o3bo$
6b2ob2o$4b3o3b3o3$4b2o5b2o$4b2o5b2o$bo3b2o3b2o3bo$bo13bo$obo11bobo2$3b
o9bo$3b2o7b2o$3bob2obob2obo$3bob2obob2obo$4bo3bo3bo2$5bobobobo$5b3ob3o
$4b2ob3ob2o$3bobo5bobo$2b2ob2obob2ob2o$3bo9bo$3bobobobobobo$3bo3b3o3bo
$8bo$2b2o9b2o$2b4o5b4o$8bo$3bo9bo$2bob2o5b2obo2$8bo$2b2ob3ob3ob2o$2b2o
bo5bob2o$2o3b2obob2o3b2o$3b2o7b2o$o2bob2o3b2obo2bo$bo5b3o5bo$3bobo5bob
o$5bo5bo2$4b2o5b2o$6bo3bo$5bo5bo$7bobo$4bo2bobo2bo$4bo7bo$4bo3bo3bo$5b
o5bo$3bo2bo3bo2bo$2bobo2b3o2bobo$8bo$2bo2bo5bo2bo$5bo5bo$3bo2bo3bo2bo$
6b2ob2o$2bob4ob4obo$bo3bo5bo3bo$bobo9bobo$2ob2o7b2ob2o$b2o11b2o$b2o3bo
3bo3b2o$2bob2obobob2obo$5bobobobo$bob2o2bobo2b2obo$bo5bobo5bo$4bob2ob
2obo$bo2bo2bobo2bo2bo$7bobo$2b2obobobobob2o$4b3o3b3o$3b3o5b3o$2b4o5b4o
$6bobobo$2bo3bobobo3bo$2bo2bo5bo2bo$2bo2bobobobo2bo$5bobobobo$4b3o3b3o
$4bo7bo2$2b3o7b3o$2b2o2bo3bo2b2o$bobobobobobobobo$b2o2bobobobo2b2o$3ob
2obobob2ob3o$7bobo$7bobo$2bo3b2ob2o3bo$2b2obobobobob2o$5bobobobo$7bobo
$3bo3bobo3bo$3b3obobob3o$5bobobobo$b2ob2obobob2ob2o$5bobobobo$bo4bo3bo
4bo$o4bo5bo4bo$bob2o7b2obo2$6b2ob2o$3b3obobob3o$3b3obobob3o$7bobo$3b2o
2bobo2b2o$2b4obobob4o$2bo11bo$5b2o3b2o$3bob2o3b2obo$4b2obobob2o$bob3ob
obob3obo$obo4bobo4bobo$bobobobobobobobo$2b4obobob4o$3bo3bobo3bo$6b2ob
2o$4bo2bobo2bo$5bobobobo2$6b2ob2o$2bo3bobobo3bo$2bo5bo5bo$bobo9bobo$8b
o$6bobobo$2b13o$3b2o3bo3b2o2$6bobobo$7b3o$7b3o$6b5o$6bo3bo$6bo3bo$b2o
11b2o$bob2obo3bob2obo$3bob2o3b2obo$b6o3b6o$b2o3bobobo3b2o$2b2obobobobo
b2o$bo3bobobobo3bo$5bobobobo$b2o4bobo4b2o$3b3obobob3o$4bo2bobo2bo$3bob
obobobobo$2obo3bobo3bob2o$2o13b2o$b4o7b4o$5b2o3b2o$5b2obob2o$7b3o$8bo$
5b2o3b2o$bo3b3ob3o3bo$bo4bo3bo4bo$obo2b3ob3o2bobo$5bo2bo2bo$obo3b5o3bo
bo$2o6bo6b2o$3b2o7b2o$3b2o7b2o$2b4o5b4o$2o4b2ob2o4b2o$6b2ob2o$3bo9bo$b
ob2o7b2obo$b2obo7bob2o$3b3o5b3o$3b2o7b2o$2bob2o5b2obo$2bo3bo3bo3bo$bob
5ob5obo$5bobobobo$7bobo$4bo2bobo2bo$4b2obobob2o$4b2obobob2o$5bobobobo$
4b2obobob2o$5bobobobo$2b2obobobobob2o$bo5bobo5bo$4bob2ob2obo$o3bo7bo3b
o$bobo9bobo$3bo9bo$2b2o9b2o$b2obob2ob2obob2o$2bobob2ob2obobo$bo2bo7bo
2bo$2o2bob2ob2obo2b2o$3o11b3o$bobo2bo3bo2bobo$bob3o5b3obo$2b2o9b2o$bo
13bo$bo2bo7bo2bo2$2bob2o5b2obo$3b2obo3bob2o$5b2o3b2o$5b2o3b2o$3b3o5b3o
$b2obo7bob2o2$8bo$5o2bobo2b5o$5bobobobo$5b2obob2o$b3o4bo4b3o$4b2o5b2o$
bo2b2o5b2o2bo$3b2o7b2o$6b2ob2o$5bobobobo!

It said "Spaceship found"but the front end doesn't work.
EDIT:Now I understand why.That's because I generated that initrow with a still life.

[Scorbie]

(Useless, marginally related. Sorry;;;)
Interesting to see a feature of DFS... That dissolves to 1 non-working part and 3 spaceships:

Code: Select all

x = 93, y = 160, rule = B3/S23
79bo$77b2ob2o3$76b3ob3o$bo13bo60b2o3b2o$bo13bo56b3o9b3o$obo11bobo$72bo
bo9bobo$3bo9bo60b2o7b2o$3b2o7b2o60bo9bo$3bob2obob2obo59b2o3b3o3b2o$3bo
b2obob2obo60bo4bo4bo$4bo3bo3bo$73bobobo3bobobo$5bobobobo61bo3b2ob2o3bo
$5b3ob3o62b2ob2ob2ob2o$4b2ob3ob2o61b2ob2ob2ob2o$3bobo5bobo60bo2bo3bo2b
o$2b2ob2obob2ob2o56b4o9b4o$3bo9bo60bob2obob2obo$3bobobobobobo62b7o$3bo
3b3o3bo62b2obob2o$8bo65b2ob2ob2ob2o$2b2o9b2o57b2o11b2o$2b4o5b4o60bob5o
bo$8bo63b3ob7ob3o$3bo9bo$2bob2o5b2obo57b2o2b2o3b2o2b2o$71bo4bo5bo4bo$
8bo63bo3b2o3b2o3bo$2b2ob3ob3ob2o62b2ob2o$2b2obo5bob2o60b3o3b3o$2o3b2ob
ob2o3b2o$3b2o7b2o$o2bob2o3b2obo2bo58b2o5b2o$bo5b3o5bo59b2o5b2o$3bobo5b
obo62b2o3b2o$5bo5bo2$4b2o5b2o$6bo3bo$5bo5bo$7bobo$4bo2bobo2bo$4bo7bo$
4bo3bo3bo$5bo5bo$3bo2bo3bo2bo$2bobo2b3o2bobo$8bo$2bo2bo5bo2bo$5bo5bo$
3bo2bo3bo2bo$6b2ob2o$2bob4ob4obo$bo3bo5bo3bo$bobo9bobo$2ob2o7b2ob2o$b
2o11b2o$b2o3bo3bo3b2o$2bob2obobob2obo$5bobobobo$bob2o2bobo2b2obo$bo5bo
bo5bo$4bob2ob2obo$bo2bo2bobo2bo2bo$7bobo$2b2obobobobob2o$4b3o3b3o$3b3o
5b3o$2b4o5b4o$6bobobo$2bo3bobobo3bo$2bo2bo5bo2bo$2bo2bobobobo2bo$5bobo
bobo$4b3o3b3o$4bo7bo2$2b3o7b3o$2b2o2bo3bo2b2o$bobobobobobobobo$b2o2bob
obobo2b2o$3ob2obobob2ob3o$7bobo$7bobo$2bo3b2ob2o3bo$2b2obobobobob2o62b
o13bo$5bobobobo65bo13bo$7bobo66bobo11bobo$3bo3bobo3bo$3b3obobob3o62bob
o11bobo$5bobobobo64b2o13b2o$b2ob2obobob2ob2o63b2o7b2o$5bobobobo67b2o7b
2o$bo4bo3bo4bo62b4o5b4o$o4bo5bo4bo59b2o4b2ob2o4b2o$bob2o7b2obo66b2ob2o
$79bo9bo$6b2ob2o66bob2o7b2obo$3b3obobob3o63b2obo7bob2o$3b3obobob3o65b
3o5b3o$7bobo69b2o7b2o$3b2o2bobo2b2o64bob2o5b2obo$2b4obobob4o63bo3bo3bo
3bo$2bo11bo62bob5ob5obo$5b2o3b2o69bobobobo$3bob2o3b2obo69bobo$4b2obobo
b2o67bo2bobo2bo$bob3obobob3obo64b2obobob2o$obo4bobo4bobo63b2obobob2o$b
obobobobobobobo65bobobobo$2b4obobob4o65b2obobob2o$3bo3bobo3bo67bobobob
o$6b2ob2o67b2obobobobob2o$4bo2bobo2bo64bo5bobo5bo$5bobobobo68bob2ob2ob
o$76bo3bo7bo3bo$6b2ob2o66bobo9bobo$2bo3bobobo3bo64bo9bo$2bo5bo5bo63b2o
9b2o$bobo9bobo61b2obob2ob2obob2o$8bo69bobob2ob2obobo$6bobobo66bo2bo7bo
2bo$2b13o61b2o2bob2ob2obo2b2o$3b2o3bo3b2o62b3o11b3o$77bobo2bo3bo2bobo$
6bobobo66bob3o5b3obo$7b3o68b2o9b2o$7b3o67bo13bo$6b5o66bo2bo7bo2bo$6bo
3bo$6bo3bo67bob2o5b2obo$b2o11b2o63b2obo3bob2o$bob2obo3bob2obo65b2o3b2o
$3bob2o3b2obo67b2o3b2o$b6o3b6o63b3o5b3o$b2o3bobobo3b2o61b2obo7bob2o$2b
2obobobobob2o$bo3bobobobo3bo68bo$5bobobobo64b5o2bobo2b5o$b2o4bobo4b2o
65bobobobo$3b3obobob3o67b2obob2o$4bo2bobo2bo64b3o4bo4b3o$3bobobobobobo
66b2o5b2o$2obo3bobo3bob2o60bo2b2o5b2o2bo$2o13b2o62b2o7b2o$b4o7b4o66b2o
b2o$5b2o3b2o69bobobobo$5b2obob2o$7b3o$8bo$5b2o3b2o$5b3ob3o$6bo3bo$5b3o
b3o$5bo2bo2bo$6b5o$8bo!

[Sokwe]

The search quickly came to an end and there was no further improvement Why?

Your original partial has a search width of 9, not 8. Look at the row just below the one you selected in generation 5. When you use the row finding script, it uses the row you selected and the row below that to generate initrows.txt.

[GUYTU6J]

Ah,here is what I made

Code: Select all

x = 148, y = 29, rule = B3/S23
2bo6bo33bo6bo32bo6bo44bo6bo$2bo6bo33bo6bo32bo6bo44bo6bo$bobo4bobo31bob
o4bobo30bobo4bobo42bobo4bobo$2bo6bo33bo6bo32bo6bo44bo6bo$2bo6bo33bo6bo
32bo6bo44bo6bo$b2o6b2o31b2o6b2o30b2o6b2o42b2o6b2o$b2o6b2o31b2o6b2o30b
2o6b2o42b2o6b2o$2obo4bob2o29b2obo4bob2o28b2obo4bob2o40b2obo4bob2o$3bo
4bo35bo4bo34bo4bo46bo4bo$4bo2bo37bo2bo36bo2bo48bo2bo$2bo6bo33bo6bo32bo
6bo44bo6bo$4b4o16b4o17b4o36b4o48b4o$3b2o2b2o14b2o2b2o15b2o2b2o34b2o2b
2o46b2o2b2o$3b2o2b2o14b2o2b2o15b2o2b2o34b2o2b2o46b2o2b2o$2bobo2bobo12b
obo2bobo13bobo2bobo32bobo2bobo44bobo2bobo$bob2o2b2obo11b3o2b3o13b3o2b
3o32b3o2b3o44b3o2b3o$bo2bo2bo2bo10bo2bo2bo2bo11bo2bo2bo2bo30bo2bo2bo2b
o42bo2bo2bo2bo$2bo6bo10bobob4obobo9bobob4obobo8bobob4obobo8bobob4obobo
40bobob4obobo$b2ob4ob2o9b2obo4bob2o9b2obo4bob2o8b2obo4bob2o8b2obo4bob
2o10b2obo4bob2o18b2obo4bob2o$2o2bo2bo2b2o8b3o6b3o9b3o6b3o8b3o6b3o8b3o
6b3o10b3o6b3o18b3o6b3o2$22b2o4b2o13b2o4b2o12b2o4b2o12b2o4b2o12b4o4b4o
18b4o4b4o$20b4o4b4o9b4o4b4o12bo2bo16bo2bo13b5o4b5o16b5o4b5o$19bo12bo7b
o12bo7bo3bo2bo3bo8bo3bo2bo3bo8bo4bo4bo4bo14bo4bo4bo4bo$23bo4bo15bo4bo
10b2obo6bob2o6b2obo6bob2o10b2o2b2o2b2o20b2o2b2o2b2o$62bo8bo10bo8bo10b
2ob3o2b3ob2o16b2ob3o2b3ob2o$61bob8obo8bob8obo10b2o3b2o3b2o18b2o3b2o3b
2o$101bo3b2o4b2o3bo14bo3b2o4b2o3bo$100bo3bo3b2o3bo3bo12bo3bo3b2o3bo3bo
!

I used "p7 k2 w6 v" to find the first partial,then I tried to extend it.I found that I have to increase width as my searches going on or zfind will output something like the earlier rows,untill I reached width 9(width 10 blocked my zfind).
Now what's next?

EDIT:The same problem arises when I do as what Sokwe said...
EDIT2:Another extending route,which cannot go on with width 9

Code: Select all

x = 96, y = 27, rule = B3/S23
2bo6bo32bo6bo34bo6bo$2bo6bo32bo6bo34bo6bo$bobo4bobo30bobo4bobo32bobo4b
obo$2bo6bo32bo6bo34bo6bo$2bo6bo32bo6bo34bo6bo$b2o6b2o30b2o6b2o32b2o6b
2o$b2o6b2o30b2o6b2o32b2o6b2o$2obo4bob2o28b2obo4bob2o30b2obo4bob2o$3bo
4bo34bo4bo36bo4bo$4bo2bo36bo2bo38bo2bo$2bo6bo32bo6bo34bo6bo$4b4o36b4o
38b4o$3b2o2b2o34b2o2b2o36b2o2b2o$3b2o2b2o14b2o2b2o14b2o2b2o36b2o2b2o$
2bobo2bobo12bobo2bobo12bobo2bobo34bobo2bobo$bob2o2b2obo10bob2o2b2obo
10bob2o2b2obo32bob2o2b2obo$bo2bo2bo2bo10bo2bo2bo2bo10bo2bo2bo2bo32bo2b
o2bo2bo$2bo6bo12bo6bo12bo6bo34bo6bo$b2ob4ob2o10b2ob4ob2o10b2ob4ob2o12b
2ob4ob2o10b2ob4ob2o$2o2bo2bo2b2o8bo3bo2bo3bo8bo3bo2bo3bo10bo3bo2bo3bo
8bo3bo2bo3bo$20bo10bo8bo10bo10bo10bo8bo10bo$20bo4b2o4bo8bo4b2o4bo10bo
4b2o4bo8bo4b2o4bo$21b3o4b3o10b3o4b3o12b3o4b3o10b3o4b3o$21b2ob4ob2o10b
2ob4ob2o9b2obo8bob2o4b2obo8bob2o$21bob2o2b2obo10bob2o2b2obo10bo3b6o3bo
6bo3b6o3bo$63bo8bo10bo8bo$61bo2bo6bo2bo6bo2bo6bo2bo!

[praosylen]

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.

DISCLAIMER: This was my first experiment with compiler optimizations, so don't trust me completely on what I'm going to say.

I looked through all of the options here and tested the ones I could for zfind-2.0 on my old version of gcc (4.0.4), and the only one that made any difference was profiling for branch probabilities (compiling with -fprofile-arcs, running a small search, and then compiling with -fbranch-probabilities), giving me a ~6% improvement in speed. I'm sure there's plenty to experiment with in terms of what search exactly to run for profiling (I lazily used the same search for intermediate profiling and speed comparison, p12 k6 w6 a, but this is useless except for testing purposes); I have no idea how well branch probabilities correspond with each other between different rules, periods, and speeds.

[HartmutHolzwart]

Could one use zfind to find partial backends?

I mean run zfind with a negative offset s.t. we can see long partials from the back.

[toroidalet]

ntzfind incorrectly outputted a partial:

Code: Select all

o......
.......
o......
..o....
ooo....
.......
.......
o.o....
..o....
..o....
o.o....
.o.o...
.o.....
.......
o..o...
..o....
oo.....
..o....
.o...o.
.......o......
.......
o......
..o....
ooo....
.......
.......
o......
oo.....
o.o....
.......

If you scroll down a bit, you will eventually find a row which has been outputted incorrectly.
It was outputted when run with the following parameters:

Code: Select all

./ntzfind B2i3-ck/S02-i3-ck p9 k1 u w7

It's not the first partial to get outputted.

[Goldtiger997]

ntzfind incorrectly outputted a partial:

Code: Select all

o......
.......
o......
..o....
ooo....
.......
.......
o.o....
..o....
..o....
o.o....
.o.o...
.o.....
.......
o..o...
..o....
oo.....
..o....
.o...o.
.......o......
.......
o......
..o....
ooo....
.......
.......
o......
oo.....
o.o....
.......

If you scroll down a bit, you will eventually find a row which has been outputted incorrectly.
It was outputted when run with the following parameters:

Code: Select all

./ntzfind B2i3-ck/S02-i3-ck p9 k1 u w7

It's not the first partial to get outputted.

I think it's becuase you should write the rule name without a slash like this:

Code: Select all

./ntzfind b2i3-cks02-i3-ck p9 k1 u w7

However, I wouldn't know and that is just my guess.

[toroidalet]

When is ntzfind going to be able to perform searches for spaceships with horizontal offsets? I want to search for a diagonal or oblique ship in B2i3-ck/S02-i3-ck.

[praosylen]

ntzfind incorrectly outputted a partial:

Code: Select all

partial

If you scroll down a bit, you will eventually find a row which has been outputted incorrectly.
It was outputted when run with the following parameters:

Code: Select all

./ntzfind B2i3-ck/S02-i3-ck p9 k1 u w7

It's not the first partial to get outputted.

That's weird. My best guess would honestly be a cosmic ray incident -- a single bit flipped in a newline could certainly result in a zero-width character.

When is ntzfind going to be able to perform searches for spaceships with horizontal offsets? I want to search for a diagonal or oblique ship in B2i3-ck/S02-i3-ck.

Here's a version of ntzfind.c for this:

Code: Select all

/* ntzfind (1.6)
** 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 <time.h>
#include "step.c"

#define BANNER "ntzfind (from zfind 1.6) by \"zdr\", Matthias Merzenich, and Aidan F. Pierce 2 January 2017"

#define MAXPERIOD 30
#define MIN_DUMP_PERIOD 1000000
#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_X_OFFSET 11
#define P_KNIGHT_PHASE 12

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

int sp[NUM_PARAMS];
uint32_t *gInd, *pInd;
uint32_t *pRemain;
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 kshiftb[MAXPERIOD] = {0}, kshift0[MAXPERIOD] = {0}, kshift1[MAXPERIOD] = {0}, kshift2[MAXPERIOD] = {0}, kshift3[MAXPERIOD] = {0};

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

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

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

/*
** 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 for certain periods (e.g., if period == 12 and
** offset == 6 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];
      }
   }
}

void makekshift(int a){
   int i;
   kshift0[a] = 1;
   for(i = 0; i < period; ++i){
      if((3*period + i - fwdOff[i]) % period == a) kshift1[i] = 1;
      if((3*period + i - doubleOff[i]) % period == a) kshift2[i] = 1;
      if((3*period + i - tripleOff[i]) % period == a) kshift3[i] = 1;
      if((3*period + i + backOff[i]) % period == a) kshiftb[i] = 1;
   }
}

int evolveBit(int row1, int row2, int row3, int bshift){
   /**/
   int r[9], i=0, j=0;
   for(i=0;i<3;i++,j++){r[j]=(row1>>(i+bshift))&1;}
   for(i=0;i<3;i++,j++){r[j]=(row2>>(i+bshift))&1;}
   for(i=0;i<3;i++,j++){r[j]=(row3>>(i+bshift))&1;}
   return stepcell(r[4],r[1],r[2],r[5],r[8],r[7],r[6],r[3],r[0]);
}
/*/   int r;
   r = bc[(row1 >> bshift) & 7];
   r += bc[(row2 >> bshift) & 7] + 4 * ((row2 >> bshift) & 2);
   r += bc[(row3 >> bshift) & 7];
   return (rule >> r) & 1;
}//*/

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

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

void u1_0(int a, int b){
   int r[10];
   int v = 2 * period;
   if(sp[P_INIT_ROWS]) v = 0;
   char *out = buf;
   if(b){
      printf("%s", buf);
      fflush(stdout);
      return;
   }
   for(r[2] = a - 1; r[2] >= 0; r[2]--)if(pRows[r[2]])break;
   for(r[0] = v; r[0] <= r[2]; r[0] += sp[P_PERIOD]){
      for(r[1] = 0; r[1] < sp[P_WIDTH]; r[1]++){
         if((pRows[r[0]] >> r[1]) & 1)out += sprintf(out, "o");
         else out += sprintf(out, ".");
      }
      out += sprintf(out, "\n");
   }
   out += sprintf(out, "%d\n", r[2] - 2 * period + 1);
}

int u1_1(int a){
   int r[30];
   r[2] = (pRows[a - sp[P_PERIOD] - fwdOff[phase]] << (2 * sp[P_WIDTH])) + (pRows[a - fwdOff[phase]] << sp[P_WIDTH]);
   r[1] = gInd[r[2] + (pRows[a] >> kshift0[phase])];
   r[3] = gInd[r[2] + pRows[a] + 1] - r[1];
   if(!r[3]) return 0;
   r[2] = (pRows[a - sp[P_PERIOD] - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (pRows[a - doubleOff[phase]] << sp[P_WIDTH]);
   r[7] = gInd[r[2] + (pRows[a - fwdOff[phase]] >> kshift1[phase])];
   r[6] = gInd[r[2] + pRows[a - fwdOff[phase]] + 1] - r[7];
   if(tripleOff[phase] >= sp[P_PERIOD]){
      r[10] = 1;
      r[11] = pInd[a + sp[P_PERIOD] - tripleOff[phase]] + pRemain[a + sp[P_PERIOD] - tripleOff[phase]];
   }
   else{
      r[2] = (pRows[a - sp[P_PERIOD] - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (pRows[a - tripleOff[phase]] << sp[P_WIDTH]);
      r[11] = gInd[r[2] + (pRows[a - doubleOff[phase]] >> kshift2[phase])];
      r[10] = gInd[r[2] + pRows[a - doubleOff[phase]] + 1] - r[11];
   }
   for(r[0] = 0; r[0] < r[3]; r[0]++){
      r[4] = gRows[r[1] + r[0]];
      if(kshift1[phase] && (r[4] & 1)) continue;
      for(r[5] = 0; r[5] < r[6]; r[5]++){
         r[8] = gRows[r[7] + r[5]];
         if(kshift2[phase] && (r[8] & 1)) continue;
         r[9] = (pRows[a - doubleOff[phase]] << (2 * sp[P_WIDTH])) + (r[8] << sp[P_WIDTH]) + (r[4] >> kshift1[phase]);
         r[16] = gInd[r[9]];
         r[15] = gInd[r[9] + 1] - r[16];
         if(!r[15])continue;
         for(r[12] = 0; r[12] < r[10]; r[12]++){
            r[13] = gRows[r[11] + r[12]];
            if(kshift3[phase] && (r[13] & 1)) continue;
            r[14] = (pRows[a - tripleOff[phase]] << (2 * sp[P_WIDTH])) + (r[13] << sp[P_WIDTH]) + (r[8] >> kshift2[phase]);
            r[18] = gInd[r[14]];
            r[17] = gInd[r[14] + 1] - r[18];
            if(!r[17])continue;
            for(r[19] = 0; r[19] < r[15]; r[19]++){
               r[20] = gRows[r[16] + r[19]];
               if(kshift2[phase] && (r[20] & 1)) continue;
               for(r[21] = 0; r[21] < r[17]; r[21]++){
                  r[22] = gRows[r[18] + r[21]];
                  if(kshift3[phase] && (r[22] & 1)) continue;
                  r[23] = (r[13] << (2 * sp[P_WIDTH])) + (r[22] << sp[P_WIDTH]) + (r[20] >> kshift2[phase]);
                  if(gInd[r[23]] != gInd[r[23] + 1])goto _ret1;
               }
            }
         }
      }
   }
   return 0;
   _ret1:;
   return 1;
}

#define FILEVERSION ((unsigned long) 2016091801)  //yyyymmddnn

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

int dumpandexit = 0;

FILE * openDumpFile(){
    FILE * fp;

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

void dumpState(int v){ // v = rowNum
    FILE * fp;
    int i;
    dumpFlag = DUMPFAILURE;
    if (!(fp = openDumpFile())) return;
    fprintf(fp,"%lu\n",FILEVERSION);
    for (i = 0; i < NUM_PARAMS; i++)
       fprintf(fp,"%d\n",sp[i]);
    fprintf(fp,"%llu\n",dumpPeriod);
    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,"%u\n",pRows[i]);
    for (i = 2 * period; i <= v; i++){
       fprintf(fp,"%u\n",pRows[i]);
       fprintf(fp,"%u\n",pInd[i]);
       fprintf(fp,"%u\n",pRemain[i]);
    }
    fclose(fp);
    dumpFlag = DUMPSUCCESS;
}

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 u1(){
   int r[10];
   int j;
   long i, i2;
   unsigned long long calcs;
   int noship = 0;
   int totalShips = 0;
   r[0] = rowNum;
   i = 0;
   i2 = 0;
   calcs = 0;
   r[5] = 0;
   r[6] = 0;
   time_t ms = clock();
   phase = r[0] % period;
   for(;;){
      if(dumpPeriod){
         calcs++;
         calcs %= dumpPeriod;
         if(calcs == 0){
            dumpState(r[0]);
            if (dumpFlag == DUMPSUCCESS) printf("State dumped to file %s%04d\n",DUMPROOT,dumpNum - 1);
            else printf("Dump failed\n");
            fflush(stdout);
         }
      }
      i++;
      if(r[0] > r[5] || !(i & 0xffffff)){
         if(r[0] > r[5]){
            u1_0(r[0], 0);
            r[5] = r[0];
            r[6] = 1;
            i2 = i;
         }
         if((r[6] && i - i2 > 0xffffff) || !(i & 0xffffffff)){
            if(!(i & 0xffffffff))u1_0(r[0], 0);
            u1_0(r[0], 1);
            printf("%d\n", r[0]);
            plong(i);
            plong(clock() - ms);
            r[6] = 0;
         }
      }
      if(!pRemain[r[0]]){
         if(shipNum && lastNonempty[shipNum] == r[0]) --shipNum;
         r[0]--;
         phase = r[0] % period;
         if(sp[P_FULL_PERIOD] && firstFull == r[0]) firstFull = 0;
         if(r[0] < 2 * sp[P_PERIOD]){
            u1_0(r[0], 1);
            if(totalShips == 1)printf("Search complete: 1 spaceship found.\n");
            else printf("Search complete: %d spaceships found.\n",totalShips);
            plong(i);
            return;
         }
         continue;
      }
      pRemain[r[0]]--;
      pRows[r[0]] = gRows[pInd[r[0]] + pRemain[r[0]]];
      if(sp[P_X_OFFSET] && phase == sp[P_KNIGHT_PHASE] && pRows[r[0]] & 1) continue;
      if(sp[P_MAX_LENGTH] && r[0] > sp[P_MAX_LENGTH] + 2 * period - 1 && pRows[r[0]] != 0) continue;  //back up if length exceeds max length
      if(sp[P_FULL_PERIOD] && r[0] > sp[P_FULL_PERIOD] && !firstFull && pRows[r[0]]) continue;        //back up if not full period by certain length
      if(sp[P_FULL_WIDTH] && (pRows[r[0]] & fpBitmask)){
         if(equivRow[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow[phase]]){
            if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow2[phase]])) continue;
         }
      }
      if(shipNum && r[0] == lastNonempty[shipNum] + 2*period && !checkInteract(r[0])) continue;       //back up if new rows don't interact with ship
      if(!u1_1(r[0]))continue;
      if(sp[P_FULL_PERIOD] && !firstFull){
         if(equivRow[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow[phase]]){
            if(!twoSubPeriods || (equivRow2[phase] < 0 && pRows[r[0]] != pRows[r[0] + equivRow2[phase]])) firstFull = r[0];
         }
      }
      r[0]++;
      phase = r[0] % period;
      if(r[0] > sp[P_DEPTH_LIMIT]){
         noship = 0;
         for(j = 1; j <= 2 * period; ++j) noship += pRows[r[0]-j];
         if(!noship){
            if(!sp[P_FULL_PERIOD] || firstFull){
               u1_0(0, 1);
               ++totalShips;
               printf("Spaceship found. (%d)\n",totalShips);
               plong(i);
               --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] = r[0] - 1; lastNonempty[shipNum] >= 0; --lastNonempty[shipNum]) if(pRows[lastNonempty[shipNum]]) break;
            r[0] = lastNonempty[shipNum] + 2 * period;
            phase = r[0] % period;
            r[5] = lastNonempty[shipNum];
            continue;
         }
         else{
            u1_0(0, 1);
            printf("Search terminated: depth limit reached.\n");
            printf("Depth: %d\n", r[0] - 2 * period);
            if(totalShips == 1)printf("1 spaceship found.\n");
            else printf("%d spaceships found.\n",totalShips);
         }
         plong(i);
         return;
      }
      r[4] = (pRows[r[0] - 2 * period] << (2 * sp[P_WIDTH])) + (pRows[r[0] - period] << sp[P_WIDTH]) + (pRows[r[0] - period + backOff[phase]] >> kshiftb[phase]);
      pRemain[r[0]] = gInd[r[4] + 1] - gInd[r[4]];
      pInd[r[0]] = gInd[r[4]];
   }
}

char * loadFile;

void loadFail(){
   printf("Load from file %s failed\n",loadFile);
   exit(1);
}

signed int loadInt(FILE *fp){
   signed int v;
   if (fscanf(fp,"%d\n",&v) != 1) loadFail();
   return v;
}

unsigned long loadUL(FILE *fp){
   unsigned long v;
   if (fscanf(fp,"%lu\n",&v) != 1) loadFail();
   return v;
}

unsigned long long loadULL(FILE *fp){
   unsigned long long v;
   if (fscanf(fp,"%llu\n",&v) != 1) loadFail();
   return v;
}

void loadState(char * cmd, char * file){
   FILE * fp;
   int i;
   
   printf("Loading search state from %s\n",file);
   
   loadFile = file;
   fp = fopen(loadFile, "r");
   if (!fp) loadFail();
   if (loadUL(fp) != FILEVERSION)
   {
      printf("Incompatible file version\n");
      exit(1);
   }
   
   /* Load parameters and set stuff that can be derived from them */
   for (i = 0; i < NUM_PARAMS; i++)
      sp[i] = loadInt(fp);
   dumpPeriod = loadULL(fp);

   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(dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
   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")){
      u1_0(rowNum,0);
      u1_0(rowNum,1);
      exit(0);
   }
}

void loadInitRows(char * file){
   FILE * fp;
   int i,j;
   char rowStr[10];
   
   loadFile = file;
   fp = fopen(loadFile, "r");
   if (!fp) loadFail();
   
   for(i = 0; i < 2 * period; i++){
      fscanf(fp,"%s",rowStr);
      for(j = 0; j < width; j++){
         pRows[i] |= ((rowStr[width - j - 1] == '.') ? 0:1) << j;
      }
   }
   fclose(fp);
}

void initializeSearch(char * file){
   int i;
   if(dumpPeriod > 0 && dumpPeriod < MIN_DUMP_PERIOD)dumpPeriod = MIN_DUMP_PERIOD;
   rule = sp[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);
      }
   }
   if(sp[P_X_OFFSET]) sp[P_SYMMETRY] = SYM_ASYM;
   sp[P_KNIGHT_PHASE] %= period;
   
   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_X_OFFSET]){
      printf("Horizontal offset: %d\n",sp[P_X_OFFSET]);
      printf("Phase %d has width %d\n",sp[P_KNIGHT_PHASE],sp[P_WIDTH] - 1);
   }
   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",sp[P_NUM_SHIPS]);
   else printf("Stop search if %d ships are found\n",sp[P_NUM_SHIPS]);
   if(dumpPeriod)printf("Dump period: %llu\n",dumpPeriod);
   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("  xNN  searches for spaceships that travel NN cells horizontally every period\n");
   printf("       (only values of 0 and 1 are currently supported)\n");
   printf("       when using x1, one phase of the spaceship will have a width of 1 less\n");
   printf("       than the width specified by the 'w' parameter\n");
   printf("  nNN  when using x1, NN is the phase with the smaller width (default: 0)\n");
   printf("\n");
   printf("  dNN  dumps the search state every 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("  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[]){
   buf = malloc(2000000);
   buf[0] = '\0';
   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_X_OFFSET] = 0;
   sp[P_KNIGHT_PHASE] = 0;
   loadDumpFlag = 0;
   dumpPeriod = 0;
   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':     //ignore (formerly 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], "%llu", &dumpPeriod); 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 'x': case 'X': sscanf(&argv[s][1], "%d", &sp[P_X_OFFSET]); break;
            case 'n': case 'N': sscanf(&argv[s][1], "%d", &sp[P_KNIGHT_PHASE]); break;
         }
      }
   }
   if(loadDumpFlag) loadState(argv[1],argv[2]);     //load search state from file
   else{
	   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 'ntzfind c'.\n");
		  return 0;
	   }
	   initializeSearch(argv[sp[P_INIT_ROWS]]);    //initialize search based on input parameters
   }
   echoParams();
   time_t ms = clock();
   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);
      }
   }
   if(sp[P_X_OFFSET]) makekshift(sp[P_KNIGHT_PHASE]);
   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;
   }
   plong(clock() - ms);
   ms = clock();
   u1();
   plong(clock() - ms);
   return 0;
}

[GUYTU6J]

I mean run zfind with a negative offset s.t. we can see long partials from the back.

At least on my computer,zfind 2.0 seems to ignore the negative sign.The first result of " p7 k-1 w9 l1500 v " is this

Code: Select all

...oo...oo...oo...
...ooo.o..o.ooo...
..oo..........oo..
.....o.oooo.o.....
..ooooo....ooooo..
..ooo...oo...ooo..
..oo.o.oooo.o.oo..
....o.oo..oo.o....
..oo..........oo..
..o.o...oo...o.o..
..o............o..
.o..o..o..o..o..o.
.o.o....oo....o.o.
.o..o.oo..oo.o..o.
.ooo.oo.oo.oo.ooo.

EDIT:Could anyone help me with the problem on extending partials aforementioned?

[GUYTU6J]

And here is another question:how to skip those repeatable components?
For example,I recalled my "sidewick" mentioned in this page.I wanted to find a backend for the c/9,but zfind could only lengthen the wick itself until it reached the depth limit...

[Saka]

And here is another question:how to skip those repeatable components?
For example,I recalled my "sidewick" mentioned in this page.I wanted to find a backend for the c/9,but zfind could only lengthen the wick itself until it reached the depth limit...

Make your own zfind mod. Or L = 999999999999...

[wildmyron]

Some ideas for minor usability enhancements:

• When loading rows for a partial to extend from file, if the rows in the file are narrower than the specified width then they are padded with active cells on the right (which becomes the centre-most column in symmetric searches). I appreciate this is unsupported behaviour, but if the rows were instead padded with Off cells on the left (becoming the outermost columns) then it would simplify increasing the search width for a given partial - without editing the initrows file. I suppose this might be such a little used feature that it's not worth the effort, but I tried doing it enough times that I thought it worth mentioning here.
• Regarding the problem of when to output partial results: Perhaps a trigger with some hysteresis built in so that when the current Length has receded say 10 rows from the last partial and then extended out 10 rows again a new partial is output. Keeping track of a local Max Length would allow successively longer partials to be output even if they are shorter than the global Max Length. The local Max Length would be reset whenever the hysteresis criteria is met. Apologies for the vague description rather than an actual algorithm but I thought it might give you a starting point to improve the current partial output algorithm.

And here is another question:how to skip those repeatable components?
For example,I recalled my "sidewick" mentioned in this page.I wanted to find a backend for the c/9,but zfind could only lengthen the wick itself until it reached the depth limit...

Judicious use of the 'm' parameter can help, but might cause valid solutions to be missed. gfind is currently a better option in this situation because of it's duplicate elimination (or possibly knightt if it can search at the desired speed).

[praosylen]

Is there any way to reconstruct a dump state from a long-enough partial, given initial search settings?

[drc]

I'm having an issue. I set up a search in rule B3/S23-cq4iw6c, "./ntzfind a w8", which implies a c/3o spaceship, asymmetric, width 8, but it gave me this, which doesn't run correctly in the rule:

Code: Select all

...oo...
..o.o...
.oo.o...
.ooo.o..
.oo..oo.
....o..o
.......o
.....o..
........
....oo..
........
...o....
....oo..
...o.o..

what is happening?

[wildmyron]

I'm having an issue. I set up a search in rule B3/S23-cq4iw6c, "./ntzfind a w8", which implies a c/3o spaceship, asymmetric, width 8, but it gave me this, which doesn't run correctly in the rule:

Code: Select all

...oo...
..o.o...
.oo.o...
.ooo.o..
.oo..oo.
....o..o
.......o
.....o..
........
....oo..
........
...o....
....oo..
...o.o..

what is happening?

Seems to be a bug in ntzfind-setup.cpp

If I build ntzfind with "./ntz-compile.sh B3S23-cq4iw6c" I see the same output as above.
If I build ntzfind with "./ntz-compile.sh B3S23anrjieky4iw6c", no spaceships are found with the above search. Searching with odd symmetry outputs this pattern, which is a valid ship in the rule:

Code: Select all

x = 15, y = 13, rule = B3/S23-cq4iw6c
7bo$6bobo$5bo3bo$2b2o7b2o$3bo2b3o2bo$bo11bo$6bobo$b2o2bobobo2b2o$bo3bo
3bo3bo$bo2b2obob2o2bo$2b3obobob3o$o2bobo3bobo2bo$bo11bo!

[GUYTU6J]

width10.png (7.95 KiB) Viewed 18156 times

I still don't understand why this happens every time when searching at width 10

[wildmyron]

width10.png

I still don't understand why this happens every time when searching at width 10

Can't be sure, but most likely because there is insufficient RAM available for zfind to allocate to build the look up table.
On the Linux system I am using, zfind uses about 4G for a w10 search. Even if there is sufficient RAM available, the allocation will fail if zfind was built as a 32-bit application, so it's worth checking that zfind was built as a 64-bit executable.

[GUYTU6J]

it's worth checking that zfind was built as a 64-bit executable.

Where can I check it?
By the way, my computer is Win 8.1,64 bit,RAM 8GB.

[wildmyron]

it's worth checking that zfind was built as a 64-bit executable.

Where can I check it?
By the way, my computer is Win 8.1,64 bit,RAM 8GB.

In the Task Manager on Windows you will see "*32" next to the process names for all running processes which are 32bit. If you use Process Explorer, then go to the Properties for the process and select the "Image" tab. You will see either 32bit or 64bit near the bottom of the pane.

If you are using mingw to compile zfind I believe you will have a 32bit executable. I don't know if standard mingw can compile 64bit (I don't use it myself) but there is a 64bit port: mingw-64

From a liitle while ago:

Ah,here is what I made

Code: Select all

rle

I used "p7 k2 w6 v" to find the first partial,then I tried to extend it.I found that I have to increase width as my searches going on or zfind will output something like the earlier rows,untill I reached width 9(width 10 blocked my zfind).
Now what's next?

EDIT:The same problem arises when I do as what Sokwe said...
EDIT2:Another extending route,which cannot go on with width 9

Code: Select all

rle

In case you are still wondering about this problem:

I think this is working as expected. You can see from the "Known spaceships by width" table at http://www.conwaylife.com/wiki/User:Codeholic/Sandbox that there is no even symmetric ship below width 18, so if you take a partial from a width 12 search (w6 in zfind) it is not surprising that there is no completion for it at widths up to 18 (w9 in zfind)

[Goldtiger997]

How can zfind be modified so that when the depth limit is reached, it prints out the partial it already has as usual, but then continues the search for more spaceships?