ConwayLife.com

Posted: **April 6th, 2020, 4:11 pm**

wildmyron wrote: April 6th, 2020, 12:42 pm
LaundryPizza03 wrote: April 6th, 2020, 7:04 am qfind gave me some weird results on asymmetric. For example, some results at width 9 in B3578/S23 appear to be broken:
Code: Select all
<snip rle>
Rather, each of these results turns out to be half of a gutter-symmetric ship.
That is very strange, I don't see that result when I run the same search in my build of qfind (current github version)
Code: Select all
./qfind B3578/S23 p3 k1 w9 a
Code: Select all
<snip rle>
It's unclear what would happen in rules like B36/S23 that have no gutter or skew-gutter symmetry.
qfind and zfind both don't check if gutter symmetry is valid in the specified rule. Running such a search will give invalid results.

git pull claims it's already up to date.

Posted: **April 6th, 2020, 8:23 pm**

LaundryPizza03 wrote: April 6th, 2020, 7:04 am qfind gave me some weird results on asymmetric.

Yep. I'm getting failed ships in this rule:

Code: Select all

D:\qfind-master>a B2-ac3acikq4ci5e/S01e2ei3a p5 k1 w10 d
qfind v1.1 by Matthias Merzenich, 7 January 2020
- a B2-ac3acikq4ci5e/S01e2ei3a p5 k1 w10 d

Rule: B2-ac3acikq4ci5e/S01e2ei3a
Period: 5
Offset: 1
Width:  10
Dump state after queue compaction
Queue size: 2^23
Hash table size: 2^21
Minimum deepening increment: 5
Cache memory per thread: 32 megabytes
Number of threads: 1
Starting search
Queue full, depth 5, deepening 5, 1.0M/1.0M -> 8.6k/13k
State dumped to dump0001
Queue full, depth 41, deepening 5, 124k/7.8M -> 2.6k/14k
State dumped to dump0002
Queue full, depth 94, deepening 5, 222k/7.8M -> 6.0k/25k
State dumped to dump0003
Queue full, depth 147, deepening 5, 97k/7.8M -> 2.4k/13k
State dumped to dump0004
Queue full, depth 231, deepening 5, 233k/7.8M -> 5.7k/26k
State dumped to dump0005
Queue full, depth 273, deepening 5, 175k/7.8M -> 6.3k/30k
State dumped to dump0006
Queue full, depth 313, deepening 5, 150k/7.8M -> 3.3k/20k
State dumped to dump0007

x = 10, y = 65, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3bo$3b2obo$3b2obo$2b2o2b
2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o$ob3o$3b2o$2bo$ob2o2b
o2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bobo2bo$o$bo$o3bobo$b3o$
o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o2$obo$bobo$6bo$3bobo$
4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3bo2bobo$2bobo$bo6bo$2b
obo2bo$bo$o2b2o!

Queue full, depth 348, deepening 5, 682k/7.8M -> 17k/66k
State dumped to dump0008
Queue full, depth 360, deepening 5, 1.0M/7.2M -> 24k/97k
State dumped to dump0009
Queue full, depth 371, deepening 5, 879k/7.8M -> 25k/113k
State dumped to dump0010
Queue full, depth 375, deepening 6, 1.0M/2.3M -> 22k/98k
State dumped to dump0011
Queue full, depth 381, deepening 5, 1.0M/3.3M -> 33k/142k
State dumped to dump0012
Queue full, depth 385, deepening 6, 1.0M/2.6M -> 23k/113k
State dumped to dump0013
Queue full, depth 389, deepening 7, 1.0M/2.2M -> 17k/91k
State dumped to dump0014
Queue full, depth 394, deepening 7, 1.0M/2.6M -> 18k/97k
State dumped to dump0015
Queue full, depth 398, deepening 8, 1.0M/2.0M -> 16k/84k
State dumped to dump0016
Queue full, depth 402, deepening 9, 1.0M/2.1M -> 11k/68k
State dumped to dump0017
Queue full, depth 407, deepening 9, 1.0M/2.4M -> 12k/68k
State dumped to dump0018
Queue full, depth 411, deepening 10, 1.0M/2.1M -> 11k/65k
State dumped to dump0019
Queue full, depth 416, deepening 10, 1.0M/2.3M -> 11k/67k
State dumped to dump0020
Queue full, depth 421, deepening 10, 1.0M/2.6M -> 11k/70k
State dumped to dump0021
Queue full, depth 426, deepening 10, 1.0M/3.1M -> 10k/71k
State dumped to dump0022
Queue full, depth 433, deepening 8, 1.0M/4.0M -> 15k/97k
State dumped to dump0023
Queue full, depth 438, deepening 8, 1.0M/2.5M -> 16k/97k
State dumped to dump0024
Queue full, depth 442, deepening 9, 1.0M/2.3M -> 14k/86k
State dumped to dump0025
Queue full, depth 446, deepening 10, 1.0M/1.8M -> 13k/81k
State dumped to dump0026
Queue full, depth 450, deepening 11, 1.0M/1.9M -> 11k/73k
State dumped to dump0027
Queue full, depth 455, deepening 11, 1.0M/2.7M -> 10k/75k
State dumped to dump0028
Queue full, depth 459, deepening 12, 1.0M/2.0M -> 8.9k/66k
State dumped to dump0029
Queue full, depth 463, deepening 13, 1.0M/1.6M -> 8.5k/62k
State dumped to dump0030
Queue full, depth 468, deepening 13, 1.0M/1.9M -> 9.4k/68k
State dumped to dump0031
Queue full, depth 472, deepening 14, 1.0M/1.8M -> 8.7k/66k
State dumped to dump0032
Queue full, depth 476, deepening 15, 1.0M/1.8M -> 8.0k/64k
State dumped to dump0033
Queue full, depth 480, deepening 16, 1.0M/1.8M -> 7.3k/62k
State dumped to dump0034
Queue full, depth 484, deepening 17, 1.0M/1.7M -> 6.5k/59k
State dumped to dump0035
Queue full, depth 488, deepening 18, 1.0M/1.9M -> 5.7k/57k
State dumped to dump0036
Queue full, depth 493, deepening 18, 1.0M/2.0M
x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$5bo
$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$bo$
4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3bo$
3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o$
ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bobo
2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o2$
obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3bo
2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!


x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo3bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$
5bo$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$
bo$4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3b
o$3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o
$ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bob
o2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o
2$obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3b
o2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!

 -> 5.9k/60k
State dumped to dump0037
Queue full, depth 496, deepening 20, 1.0M/1.4M
x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$5bo
$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$bo$
4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3bo$
3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o$
ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bobo
2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o2$
obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3bo
2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!


x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo3bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$
5bo$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$
bo$4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3b
o$3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o
$ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bob
o2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o
2$obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3b
o2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!
^C

None of these RLEs are ship.

Posted: **April 8th, 2020, 3:22 am**

I also note that while gfind and zfind support at least some speeds and periods greater than c/2, qfind does not work at all for such speeds. Even a simple search such as ./qfind B2/S p1 x1 w3 v aborts instantly without returning any of the three main photons in that rule.

Posted: **April 8th, 2020, 5:41 am**

Hunting wrote: April 6th, 2020, 8:23 pm
LaundryPizza03 wrote: April 6th, 2020, 7:04 am qfind gave me some weird results on asymmetric.
Yep. I'm getting failed ships in this rule:

These failed ships seem to all leave the left side of their width-10 bounding box at some point in their evolution. If you disallow these births, the pattern operates normally. This bug probably appeared when I updated to add Tom's code. Unfortunately, I don't have time to work on it right now.

LaundryPizza03 wrote: April 8th, 2020, 3:22 am I also note that while gfind and zfind support at least some speeds and periods greater than c/2, qfind does not work at all for such speeds. Even a simple search such as ./qfind B2/S p1 x1 w3 v aborts instantly without returning any of the three main photons in that rule.

qfind is not designed to work for any speeds above c/2 (if it works, it's a fluke and not intended behavior). Due to the width limitations, I don't think qfind would be useful for finding such ships anyway. It's better to use gfind in those cases.

Posted: **May 13th, 2020, 1:37 am**

There may be some sort of bug with qfind when doing really long searches. For example, this search gets stuck at depth 59879:

Code: Select all

./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u

Changing the hash table size does not affect anything, but increasing the BFS queue size seems to delay when qfind gets stuck. Ntzfind doesn't seem to have problems finding a ship with these parameters. Sokwe, do you know what could be causing this?

Posted: **July 19th, 2020, 7:10 pm**

AforAmpere wrote: May 13th, 2020, 1:37 am There may be some sort of bug with qfind when doing really long searches. For example, this search gets stuck at depth 59879:
Code: Select all
./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u
Changing the hash table size does not affect anything, but increasing the BFS queue size seems to delay when qfind gets stuck. Ntzfind doesn't seem to have problems finding a ship with these parameters. Sokwe, do you know what could be causing this?

Sorry for not responding earlier. I didn't notice this question.

This isn't a bug, but rather a limitation in qfind's method. Here is the output showing clearly where qfind gets "stuck":

Code: Select all

Starting search
Queue full, depth 40811, deepening 19, 299/7.8M -> 182/4.7M
Queue full, depth 52355, deepening 19, 305/7.8M -> 173/6.6M
Queue full, depth 56914, deepening 19, 259/7.8M -> 173/7.3M
Queue full, depth 58710, deepening 19, 234/7.8M -> 175/7.6M
Queue full, depth 59420, deepening 19, 265/7.8M -> 173/7.7M
Queue full, depth 59697, deepening 19, 283/7.8M -> 176/7.8M
Queue full, depth 59811, deepening 19, 256/7.8M -> 181/7.8M
Queue full, depth 59853, deepening 19, 272/7.8M -> 180/7.8M
Queue full, depth 59870, deepening 21, 265/7.8M -> 177/7.8M
Queue full, depth 59877, deepening 33, 213/7.8M -> 167/7.8M
Queue full, depth 59879, deepening 50, 185/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 69, 167/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 88, 164/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 107, 164/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 126, 164/7.8M -> 164/7.8M

Notice that at each step you get "164/7.8M -> 164/7.8M". When you see "MM/NN", MM is the current number of partial results, and NN is the total number of rows in the current search tree (this includes all the rows in each of the MM partial results). The 'q' parameter essentially sets a limit on what NN can be. If the search tree reaches the size set by 'q', then a depth-first step is triggered to try to eliminate some of the partial results, and thus free up some memory to continue the breadth-first search.

The MM/NN before the arrow indicates the values before the depth-first stage is applied. The numbers after the arrow likewise represent the values after the depth-first stage. As can be seen from the output above, once the search reaches a depth of 59879 the deepening steps are unable to eliminate any of the partial results. Therefore no memory is freed and the breadth first search cannot continue. It then tries another depth-first round, going even deeper than before, but still it cannot eliminate any partial results. It could be that each partial result has a subsequent repeating pattern, and the depth-first search will never be able to eliminate any of the partial results. In this case you truly are stuck.

The solution is to run the search with a higher 'q' value. For example, running

Code: Select all

./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u q26

gives me a spaceship of length ~11488. Another thing you can do is run your initial search with the 'd' parameter. When the search gets "stuck", you can stop it and edit the latest dump file to increase the 'q' paremeter (increase the value on line 10 in the dump file). As a warning, only use a dump file for which the program has given the output "State dumped to dumpXXXX". This indicates that writing to the dump file has completed. It is possible to kill the program while the dump file is being written, so if that message hasn't appeared, the latest dump file might be incomplete.

Posted: **October 9th, 2020, 10:14 am**

How do I restart a qfind search from a dump file?

Posted: **October 13th, 2020, 5:40 pm**

wwei23 wrote: October 9th, 2020, 10:14 am How do I restart a qfind search from a dump file?

Code: Select all

./qfind s FILENAME

where "FILENAME" is the name of the dump file. For example,

Code: Select all

./qfind s dump0011

Posted: **October 15th, 2020, 10:28 pm**

How do I make qfind dump automatically, and how do I adjust the dumping interval?

Posted: **October 17th, 2020, 4:20 am**

wwei23 wrote: October 15th, 2020, 10:28 pm How do I make qfind dump automatically, and how do I adjust the dumping interval?

Use the 'd' parameter to dump the state after each queue compaction. You can read qfind's parameter descriptions by running

Code: Select all

./qfind c

The state dumps after each deepening step completes, so there is no direct way to "adjust the dumping interval". You can do things like changing the queue size with the 'q' parameter or changing the minimum deepening increment with the 'm' parameter to affect the length of time the deepening step takes.

Posted: **October 17th, 2020, 7:02 pm**

Can I feed qfind partials? If so, how?
EDIT: I should probably try ./qfind c first.
EDIT 2: Ok, but how do I put in more than one partial?

Posted: **October 17th, 2020, 10:54 pm**

wwei23 wrote: October 17th, 2020, 7:02 pm Can I feed qfind partials? If so, how?
EDIT: I should probably try ./qfind c first.
EDIT 2: Ok, but how do I put in more than one partial?

There's currently no way to put in more than one partial. You need to run separate searches for each partial, or you could do some manual tinkering with dump files to craft one which has multiple partials included. This would require either studying and understanding the dump file format or hoping that Sokwe will provide a tool to combine dump files / add multiple partials.

Posted: **January 31st, 2021, 11:42 am**

qfind v1.4 released

Over the last week I've made some modifications to qfind that collectively comprise versions 1.2 to 1.4. This post will describe the changes made since v1.1. As always, please mention any problems that you encounter.

Options are now POSIX-like:
For various reasons, I made option input somewhat POSIX-like. If you want to run a search for the copperhead using two threads and a queue size of 2^18 nodes, you would run qfind with the following options:

Code: Select all

-r B3/S23 -p 10 -y 1 -w 5 -s even -q 18 -t 2

You can access the list of options by running qfind with the --help option. Any repeated option will overwrite the previous value, so if your options include "-p 4" and somewhere later include "-p 5", then the search will be for period-5 spaceships.

New features:

The program now performs simple checks to make sure some basic input is valid, and prints any errors to stderr. For example, photons are not supported, so the program throws an error if the period and translation have the same value. I only check for a few things, so it's still mostly up to the user to give meaningful input.
The program now prints a short report at the end of the search including the number of ships found and the longest partial result.
The program now saves up to 99999 dump files, rather than 9999.

New options:

-a This suppresses the output of the longest partial result at the end of the search.
-d FF This saves the search state after each queue compaction using the file name prefix FF. For example, using "-d 2c6-" would save the search state to the files 2c6-00001, 2c6-00002, etc. This is just a slight change in behavior from the previous save feature which had a fixed file name prefix of "dump".
-f NN This stops the search after NN spaceships are found.
-j NN This splits the loaded search state (loaded from -l) into NN pieces and saves these pieces in files using the file name prefix defined by the -d option. If -j is used without loading a saved state, it will save a single file based on the given input options using the default file name prefix "dump".
-l FF This loads the search state from the file FF. After loading the saved state, you can change the parameters using other options. For example, if you have a c/5 even-symmetric logical-width-9 search using 2 threads saved in "c5-w9-e-00007", you can increase the number of threads to 4 by running qfind with the options
Code: Select all
```
-l c5-w9-e-00007 -t 4
```
Note that the new parameters need to be given after the load-state option. Changing core options like the period, translation, width, or symmetry type will result in unintended behavior. The program makes no checks to ensure option changes are valid.
-n NN This sets the minimum depth level of the first deepening step to NN. I find this is useful when continuing a search from a saved state where the iterated deepening level has become too large (causing the deepening step to take too long with little added benefit). I can use "-n 0" to reset the deepening level to the minimum deepening increment.

Bug fixes:

Some variables were uninitialized, which could have potentially caused errors. It would probably have caused a crash rather than erroneous results. These variables are now properly initialized.
The bug mentioned in this post was caused by calling free() on a non-malloced pointer in success(). This caused errors for some people, but not for others. It should be fixed.
A bug was introduced in v1.3 where the queue size couldn't be changed after loading a saved state. This was corrected in v1.4.
A bug was introduced in v1.3 due to not specifying a return type for loadState(). This was corrected in v1.4.
LaundryPizza03 wrote: April 6th, 2020, 7:04 am qfind gave me some weird results on asymmetric. For example, some results at width 9 in B3578/S23 appear to be broken...

Hunting wrote: April 6th, 2020, 8:23 pm I'm getting failed ships in this rule...
This was almost certainly not really a bug, but rather the result of not providing a symmetry type. qfind does not have a default symmetry type, and in previous versions failure to specify a symmetry type appears to have resulted in a gutter-symmetric search with only one half of the ship being output. The program now throws an error if no symmetry type is provided.

Posted: **February 2nd, 2021, 4:54 pm**

How do I determine the equivalent of -fopenmp on my system?

Posted: **February 3rd, 2021, 12:37 am**

LaundryPizza03 wrote: February 2nd, 2021, 4:54 pm How do I determine the equivalent of -fopenmp on my system?

It would depend on your compiler. I suggest searching the web for how to use OpenMP with your compiler. If you figure it out, it could be helpful to other users if you post your solution here.

Posted: **March 2nd, 2021, 9:33 am**

qfind v2.0 released

Changes:

I added the ability to save and restore the depth-first extensions from the deepening stage. This makes the search a bit faster and makes dump files a bit larger. The -g option allows the user to set the minimum length at which the extensions are saved. The default length is 0, meaning that all extensions, no matter how short, are saved.
I removed the naive search order option. This option really had no practical use in qfind and generally just slowed the search down.
I reduced the default queue and hash table sizes.

As usual, please report any bugs or strange behavior you find.

Posted: **March 4th, 2021, 8:41 am**

Uh sorry as usual, a precompiled version on windows

Posted: **March 4th, 2021, 9:52 pm**

yujh wrote: March 4th, 2021, 8:41 am Uh sorry as usual, a precompiled version on windows

Try this:

qfind-v2.0-windows.zip: (277.11 KiB) Downloaded 204 times

There are two files, qfind.exe which has lookahead caching enabled and qfind-nc.exe which has caching disabled. Caching should probably be used in searches for speeds greater than c/5 and should be disabled otherwise. I should probably just update qfind so that you aren't required to compile two versions, but that's a project for another day.

These were compiled under Mingw-w64 using

Code: Select all

g++ qfind.cpp -static -O3 -fopenmp -o qfind

Posted: **March 14th, 2021, 5:41 am**

I've made a modified version of qfind to find a finite set of spaceships that can be used to construct all possible ships of a given period, translation, logical width, and symmetry type. Unfortunately, this is done very inelegantly, so it can only be used when the finite list of ships is small.

I strongly discourage people from downloading this version. Ordinary qfind is much better for actually finding ships. I'm only posting this here to show exactly how I obtained some recent results.

How it works:

Ordinarilly, qfind removes a partial result if that partial ends in rows that have been seen in another partial result of equal or lesser length. This program instead saves each of these partial results. A post-processing option allows it to construct ships that could be made with these partial results.

I had to modify how qfind removes partial results when gcd(period,translation) > 1. In this case, both gfind and ordinary qfind make simplifying assumptions that can potentially cause them to throw out partial results even when they don't actually contain rows that have already been seen. In practice, I think this almost never happens, but just to be sure, I had to retain all of these partials. This makes these types of searches take quite a bit longer and give many more duplicate results. For those reasons, I'm leaving the simplifying assumptions in ordinary qfind. This means that an ordinary qfind search for a gcd(period,translation) > 1 ship cannot be considered complete, even if it finds no spaceships (unless it is run with -h 0, which disables duplicate elimination).

How to use it:

You need two empty directories, "push" and "ship", in the same directory containing the program.
First run a search using normal input options. Edit: you need to turn off lookahead caching for this to work properly (use "-c 0" option).
After the search completes, run the program with the exact same options as the original search and the additional option -v. The ouput should be piped to a text file.
The output of this second run will be the finite list of RLE-encoded spaceships. They will likely need to be inspected by hand or run through apgsearch in order to separate closely-spaced but non-interacting ships.

Again, I strongly discourage people from using this program. I intend to run most of the reasonable searches in Conway's Game of Life. If you want a finite list of spaceships that can be used to construct all other spaceships of a given type, use knightt (or ikpx2?). If you just want a bunch of spaceships and don't care about the list being complete, use ordinary qfind or one of the many other available spaceship search programs.

If you do decide to use it, you should be aware that it saves an unreasonable number of smallish text files. For example, my run for 2c/8 logical-width 7 odd symmetric ships produced nearly 64000 files requiring over 120 megabytes.

Posted: **April 16th, 2021, 7:57 am**

I have forked qfind 2.0 to poke around with, but currently there is no software license associated with your qfind code on github.

Do you have plans to add a license?

Posted: **April 17th, 2021, 12:48 am**

dexter1 wrote: April 16th, 2021, 7:57 am I have forked qfind 2.0 to poke around with, but currently there is no software license associated with your qfind code on github.

Do you have plans to add a license?

The program is based on code by forum user zdr. I sent them a private message about licensing years ago, but they never read it, and I don't know how to contact them otherwise. I also used code by Tom Rokicki, David Eppstein, Paul Tooke, and Aidan F. Pierce. These other contributors would have to be contacted as well, although that's probably not too hard. I know that Tom and I would be willing to release our contributions under the MIT License.

Posted: **April 26th, 2021, 11:49 am**

Sokwe wrote: February 3rd, 2021, 12:37 am
LaundryPizza03 wrote: February 2nd, 2021, 4:54 pm How do I determine the equivalent of -fopenmp on my system?
It would depend on your compiler. I suggest searching the web for how to use OpenMP with your compiler. If you figure it out, it could be helpful to other users if you post your solution here.

I couldn't find anything online that works on and doesn't require Homebrew, LLVM, or some other item I don't have yet. I'm installing LLVM at the moment and then will try to compile OpenMP in my user directory using the directions at https://clang-omp.github.io.

Posted: **April 27th, 2021, 6:14 pm**

qfind sometimes outputs two spaceships which are actually the same spaceship.

Posted: **April 28th, 2021, 7:05 am**

cgoler2 wrote: April 27th, 2021, 6:14 pm qfind sometimes outputs two spaceships which are actually the same spaceship.

qfind should not print the same ship twice in a row, but if it will sometimes find a ship, then find a different ship, then find the first ship again, causing the first ship to be printed twice.

There are two reasons for this. First, if a ship is detected at depth n, then it will also be detected at depths n+i for 0<i<p+1 where p is the period. If there are two ships at depth n, then qfind will detect and print each p times. This p-fold detection occurs because terminal() first checks if the current pattern ends in p empty rows, and then checks if the pattern works the same way if p more empty rows are added. So terminal will detect a ship when the pattern ends in exactly p empty rows. The breadth-first stage will then add another empty row and terminal() will again detect a ship now ending with p+1 empty rows. This stops happening at depth n+p, because there are then 2*p empty rows, so the hashing detects this as matching the root node and eliminates it as a duplicate. This p-fold detection can be solved by only detecting a spaceship when terminal(qTail-1) returns true, but terminal(PARENT(qTail-1)) returns false.

The other reason ships are printed multiple time would presumably be more difficult to solve. By default qfind prints ships found in the depth-first step, which can cause ships to be found many times and in strange orders.

Posted: **April 28th, 2021, 7:35 am**

It does print the same spaceship twice in a row when I was searching for c/4 orthogonal spaceships with logical width 9 and gutter symettry.

ConwayLife.com

qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program

Re: qfind - a spaceship search program