qfind - a spaceship search program

[Sokwe]

I added a new feature to qfind that allows it to exit the deepening step early when threads become idle, based on code by Alex Greason. This should make many searches run somewhat faster when using a large number of threads on machines with a large number of processors. My laptop, with its super advanced dual-core technology unfortunately doesn't see much benefit, but the improvement was noticeable on a laptop I borrowed that has 12 cores.

Alex, your original code would exit early partly based on the number of successful tasks (i.e., nodes where an extension was found), rather than simply the number of completed tasks (whether or not they had an extension). Do you remember why you wrote it this way? I simply required that three quarters of tasks be completed before the early exit, with no checking for successful tasks.

In addition to the early exit feature, I changed the default for the -q option to 15, as I found that it tended to run faster than the previous default of 20, at least for quick searches. I also changed the default number of threads to be one less than the number of logical processors detected by omp_get_num_procs().

I also fixed a few minor bugs that didn't affect the validity of any past searches. Most notably, I fixed a memory leak bug that would, on very rare occasions, cause qfind to exit early with the somewhat cryptic error message "no available extension indices". I also fixed the bug that caused strange output for the longest partial result when a search finished at an extremely shallow depth, as discussed here.

Here is a zip archive containing a Windows executable of the latest version of qfind for x86-64 CPUs:

qfind-v2.4b2-windows-x86_64.zip

(223.98 KiB) Downloaded 80 times

This was compiled under MinGW-w64 with the MSVCRT runtime library using the following command:

Code: Select all

gcc -static -std=c11 -fopenmp -march=x86-64 -O3 -o qfind qfind.c

If anyone has any trouble getting this to work on their machine, please let me know.

I'm also curious to know if anyone has any experience compiling portable binaries for macOS. I'd like to be able to provide such binaries, but I don't have a Mac, nor do I know anyone who would let me borrow theirs. I know there have been issues with getting OpenMP to work, requiring GCC to be installed with the Homebrew package manager.

Before I add any more new features to qfind, I intend to refactor the code to make it easier to maintain. By the time I make a proper release, I'll probably call this qfind v3.0, rather than qfind v2.4.

[Sylvani]

If you want thousands of spaceships per second, run this:

Code: Select all

qfind -v c/3 -w 6 -s even -r B3468/S35 -t 16 -q 16 -h 22 -i 5

[R2INT]

503 Service Unavailable error

I have run a full c/5 search with even symmetry and width 9. Here are all of the results:

Code: Select all

x = 249, y = 148, rule = B3/S23
8b2o21b2o18b6o17b2o17b6o17b2o17b6o16b2o17bo2bo17b4o16bo2bo17b4o$8b2o38b
ob8obo30bob8obo30bob8obo30b2ob2ob2o13bo6bo12b2ob2ob2o13bo6bo$6bob2obo
17bob2obo12bo12bo11bob2obo11bo12bo11bob2obo11bo12bo10bob2obo10b4o6b4o
10bo6bo9b4o6b4o10bo6bo$4b3o4b3o14b3o2b3o10bo4bo4bo4bo9b3o2b3o9bo4bo4b
o4bo9b3o2b3o9bo4bo4bo4bo8b3o2b3o8bob3o6b3obo6bo2bo2b2o2bo2bo5bob3o6b3o
bo6bo2bo2b2o2bo2bo$b2o12b2o7b4o2b4o2b4o7bo3bo4bo3bo6b4o2b4o2b4o6bo3bo
4bo3bo6b4o2b4o2b4o6bo3bo4bo3bo5b4o2b4o2b4o4bo4bo4bo4bo5b2o12b2o4bo4bo
4bo4bo5b2o12b2o$b2o2bob4obo2b2o7b2o4b4o4b2o10bobo2bobo9b2o4b4o4b2o9bo
bo2bobo9b2o4b4o4b2o9bobo2bobo8b2o4b4o4b2o8bobo2bobo13b3o2b3o12bobo2bo
bo13b3o2b3o$5bobo2bobo17bo2bo16bo2b2o2bo15bo2bo15bo2b2o2bo15bo2bo15bo
2b2o2bo14bo2bo14b3o2b3o13bob4obo12b3o2b3o13bob4obo$27b3o4b3o9bo3bobo2b
obo3bo8b3o4b3o8bo3bobo2bobo3bo8b3o4b3o8bo3bobo2bobo3bo7b3o4b3o12b2o2b
2o13b2ob4ob2o12b2o2b2o13b2ob4ob2o$4b2o6b2o11bo3bo4bo3bo7b2o12b2o6bo3b
o4bo3bo6b2o12b2o6bo3bo4bo3bo6b2o12b2o5bo3bo4bo3bo4b3o12b3o4b2o3bob2ob
o3b2o3b3o12b3o4b2o3bob2obo3b2o$b6o4b6o7bo4bo4bo4bo7b2o10b2o6bo4bo4bo4b
o6b2o10b2o6bo4bo4bo4bo6b2o10b2o5bo4bo4bo4bo5bo12bo6bobo10bobo5bo12bo6b
obo10bobo$bobo10bobo6b2o14b2o6bo12bo5b2o14b2o5bo12bo5b2o14b2o5bo12bo4b
2o14b2o4bo12bo8bo10bo7bo12bo8bo10bo$bob2o8b2obo6b2o14b2o5bo14bo4b2o14b
2o4bo14bo4b2o14b2o4bo14bo3b2o14b2o2b2o14b2o4b3o10b3o3b2o14b2o4b3o10b3o
$bob2o8b2obo7bo3bo6bo3bo6b3o10b3o5bo3bo6bo3bo5b3o10b3o5bo3bo6bo3bo5b3o
10b3o4bo3bo6bo3bo25bobo10bobo25bobo10bobo$2ob2o8b2ob2o29bobo8bobo28bo
bo8bobo28bobo8bobo26b3o8b3o6bobo10bobo5b3o8b3o6bobo10bobo$2obo10bob2o
8bo10bo13bo4bo12bo10bo12bo4bo12bo10bo12bo4bo11bo10bo8b2o8b2o7b2o12b2o
6b2o8b2o7b2o12b2o$bobo10bobo6b2ob2o8b2ob2o6bo2b2o4b2o2bo5b2ob2o8b2ob2o
5bo2b2o4b2o2bo5b2ob2o8b2ob2o5bo2b2o4b2o2bo4b2ob2o8b2ob2o4b6o2b6o8bo2b
o4bo2bo7b6o2b6o8bo2bo4bo2bo$3bo2b2o2b2o2bo11bo2b2o2b2o2bo10b2o2bo2bo2b
2o9bo2b2o2b2o2bo9b2o2bo2bo2b2o9bo2b2o2b2o2bo9b2o2bo2bo2b2o8bo2b2o2b2o
2bo29b5o2b5o29b5o2b5o$2bo4bo2bo4bo13b2o2b2o15b2o4b2o14b2o2b2o14b2o4b2o
14b2o2b2o14b2o4b2o13b2o2b2o14bo4bo12b2o2bo2bo2b2o11bo4bo12b2o2bo2bo2b
2o$8b2o20b4o17bo4bo16b4o16bo4bo16b4o16bo4bo15b4o14b2o4b2o12b4o2b4o11b
2o4b2o12b4o2b4o$7bo2bo20b2o15b2obob2obob2o14b2o14b2obob2obob2o14b2o14b
2obob2obob2o13b2o12bobobob2obobobo9bobo4bobo8bobobob2obobobo9bobo4bob
o$27b3o4b3o9b3o10b3o8b3o4b3o8b3o10b3o8b3o4b3o8b3o10b3o7b3o4b3o7bo2bo3b
2o3bo2bo7b3obo2bob3o6bo2bo3b2o3bo2bo7b3obo2bob3o$3b4o4b4o9b4ob2o2b2ob
4o5b2ob3o6b3ob2o4b4ob2o2b2ob4o4b2ob3o6b3ob2o4b4ob2o2b2ob4o4b2ob3o6b3o
b2o3b4ob2o2b2ob4o4bo4bob2obo4bo4b2o14b2o3bo4bob2obo4bo4b2o14b2o$3o2b2o
b2ob2o2b3o6b2o3bob2obo3b2o8b2o2b4o2b2o7b2o3bob2obo3b2o7b2o2b4o2b2o7b2o
3bob2obo3b2o7b2o2b4o2b2o6b2o3bob2obo3b2o4bob2o3b2o3b2obo4b2o3bo2b2o2b
o3b2o3bob2o3b2o3b2obo4b2o3bo2b2o2bo3b2o$2bo5b2o5bo10b2o8b2o9b2o10b2o8b
2o8b2o8b2o10b2o8b2o8b2o8b2o10b2o7b2o8b2o8bo10bo7bo3bo2b2o2bo3bo6bo10b
o7bo3bo2b2o2bo3bo$2obob3o2b3obob2o6bo3b3o2b3o3bo12bo2bo11bo3b3o2b3o3b
o11bo2bo11bo3b3o2b3o3bo11bo2bo10bo3b3o2b3o3bo7bo3b2o3bo9b3o2bo2bo2b3o
8bo3b2o3bo9b3o2bo2bo2b3o$2b3o3b2o3b3o11b10o12bo2bo2bo2bo11b10o11bo2bo
2bo2bo11b10o11bo2bo2bo2bo10b10o13b4o13bo10bo12b4o13bo10bo$2bo12bo9bo2b
o6bo2bo8b3o3b2o3b3o7bo2bo6bo2bo7b3o3b2o3b3o7bo2bo6bo2bo7b3o3b2o3b3o6b
o2bo6bo2bo6b3o8b3o9bo2bo2bo2bo8b3o8b3o9bo2bo2bo2bo$4b2o2b2o2b2o12b2o8b
2o9bo2bo6bo2bo8b2o8b2o8bo2bo6bo2bo8b2o8b2o8bo2bo6bo2bo7b2o8b2o8bo10bo
8bob2o2b2o2b2obo7bo10bo8bob2o2b2o2b2obo$4b10o12bo10bo11b3o4b3o10bo10b
o10b3o4b3o10bo10bo10b3o4b3o9bo10bo9b2o6b2o9bo3bo4bo3bo8b2o6b2o9bo3bo4b
o3bo$4bob2o2b2obo13bo8bo14bo4bo13bo8bo13bo4bo13bo8bo13bo4bo12bo8bo11b
2o4b2o12bobo4bobo11b2o4b2o12bobo4bobo$6bo4bo16b2o4b2o16bo2bo15b2o4b2o
15bo2bo15b2o4b2o15bo2bo14b2o4b2o11bo2bo2bo2bo13b2o2b2o12bo2bo2bo2bo13b
2o2b2o$7bo2bo19bo2bo16b3o2b3o15bo2bo15b3o2b3o15bo2bo15b3o2b3o14bo2bo15b
o4bo14bobo2bobo13bo4bo14bobo2bobo$5bobo2bobo14b2obo2bob2o14b2o2b2o13b
2obo2bob2o13b2o2b2o13b2obo2bob2o13b2o2b2o12b2obo2bob2o12bo4bo14bo2b2o
2bo13bo4bo14bo2b2o2bo$4b2ob4ob2o162bo2bo15bobo2bobo14bo2bo15bobo2bobo
$4b2ob4ob2o16bo2bo15b2o6b2o14bo2bo14b2o6b2o14bo2bo14b2o6b2o13bo2bo15b
6o14b2o4b2o13b6o14b2o4b2o$5bo6bo17b4o14b3o6b3o13b4o13b3o6b3o13b4o13b3o
6b3o12b4o12b3ob4ob3o9bobo6bobo8b3ob4ob3o9bobo6bobo$4b3o4b3o12b2obo4bo
b2o9b3o3b2o3b3o8b2obo4bob2o8b3o3b2o3b3o8b2obo4bob2o8b3o3b2o3b3o7b2obo
4bob2o7bo12bo7bo12bo6bo12bo7bo12bo$2bobo8bobo10b2o8b2o8b2o12b2o7b2o8b
2o7b2o12b2o7b2o8b2o7b2o12b2o6b2o8b2o6bo14bo5bo3bo6bo3bo4bo14bo5bo3bo6b
o3bo$bo14bo7bo2b2o6b2o2bo9b3o4b3o8bo2b2o6b2o2bo8b3o4b3o8bo2b2o6b2o2bo
8b3o4b3o7bo2b2o6b2o2bo4bo3b2ob2ob2o3bo5b2o12b2o4bo3b2ob2ob2o3bo5b2o12b
2o$b2ob2o6b2ob2o7b5o6b5o6b2obo8bob2o5b5o6b5o5b2obo8bob2o5b5o6b5o5b2ob
o8bob2o4b5o6b5o7b2o6b2o11b2o6b2o10b2o6b2o11b2o6b2o$4b2o6b2o11bo4b4o4b
o8b2o10b2o7bo4b4o4bo7b2o10b2o7bo4b4o4bo7b2o10b2o6bo4b4o4bo5b2o2bo6bo2b
2o5b2obo8bob2o4b2o2bo6bo2b2o5b2obo8bob2o$3b2ob6ob2o10bo3b6o3bo8bob10o
bo7bo3b6o3bo7bob10obo7bo3b6o3bo7bob10obo6bo3b6o3bo7bob2o4b2obo12b6o11b
ob2o4b2obo12b6o$b2obo8bob2o8bobob6obobo29bobob6obobo28bobob6obobo27bo
bob6obobo11b4o12bob10obo11b4o12bob10obo$5bo6bo38bo4bo36bo4bo36bo4bo35b
4o18b2o17b4o18b2o$51b6o36b6o36b6o34bo4bo15bob2obo14bo4bo15bob2obo$29b
6o15bobo2bobo14b6o14bobo2bobo14b6o14bobo2bobo13b6o13bo6bo13bo2b2o2bo12b
o6bo13bo2b2o2bo$5b8o15bob4obo15bo4bo14bob4obo14bo4bo14bob4obo14bo4bo13b
ob4obo13b2o2b2o14bo6bo13b2o2b2o14bo6bo$5b2o4b2o14bo8bo33bo8bo32bo8bo31b
o8bo33bo4bo35bo4bo$30bo2bo17b6o16bo2bo16b6o16bo2bo16b6o15bo2bo15b2o2b
2o15bob2obo14b2o2b2o15bob2obo$50b2ob2ob2o34b2ob2ob2o34b2ob2ob2o31b3ob
2ob3o12b2o4b2o11b3ob2ob3o12b2o4b2o$28bob4obo13bob2o2b2obo12bob4obo12b
ob2o2b2obo12bob4obo12bob2o2b2obo11bob4obo$27b2o6b2o33b2o6b2o32b2o6b2o
31b2o6b2o10bobo4bobo13b6o12bobo4bobo13b6o$27b3ob2ob3o12bo2bo2bo2bo11b
3ob2ob3o11bo2bo2bo2bo11b3ob2ob3o11bo2bo2bo2bo10b3ob2ob3o13bo2bo15b3o2b
3o14bo2bo15b3o2b3o$50b3o2b3o34b3o2b3o34b3o2b3o31b3o4b3o12bobo2bobo11b
3o4b3o12bobo2bobo$27b3o4b3o12bo2bo2bo2bo11b3o4b3o11bo2bo2bo2bo11b3o4b
3o11bo2bo2bo2bo10b3o4b3o13bo2bo14b2ob4ob2o13bo2bo14b2ob4ob2o$28bobo2b
obo15bo4bo14bobo2bobo14bo4bo14bobo2bobo14bo4bo13bobo2bobo12bobo2bobo15b
o2bo14bobo2bobo15bo2bo$28b3o2b3o35b3o2b3o34b3o2b3o33b3o2b3o$48b4o4b4o
30b4o4b4o30b4o4b4o28b4o4b4o10bobo4bobo9b4o4b4o10bobo4bobo$26b3o6b3o9b
obobo4bobobo8b3o6b3o8bobobo4bobobo8b3o6b3o8bobobo4bobobo7b3o6b3o7bobo
2bo2bo2bobo8b2obo4bob2o7bobo2bo2bo2bobo8b2obo4bob2o$25bo3b2o2b2o3bo9b
o4b2o4bo8bo3b2o2b2o3bo8bo4b2o4bo8bo3b2o2b2o3bo8bo4b2o4bo7bo3b2o2b2o3b
o6bo12bo7bo3b2o2b2o3bo6bo12bo7bo3b2o2b2o3bo$25bo3b2o2b2o3bo10b2o6b2o9b
o3b2o2b2o3bo9b2o6b2o9bo3b2o2b2o3bo9b2o6b2o8bo3b2o2b2o3bo9bo2b2o2bo11b
o10bo10bo2b2o2bo11bo10bo$24b2ob10ob2o9bob2o2b2obo8b2ob10ob2o8bob2o2b2o
bo8b2ob10ob2o8bob2o2b2obo7b2ob10ob2o3bo3b10o3bo6b12o5bo3b10o3bo6b12o$
24b2o12b2o9bo2b4o2bo8b2o12b2o8bo2b4o2bo8b2o12b2o8bo2b4o2bo7b2o12b2o7b
o8bo10b2ob2o2b2ob2o9bo8bo10b2ob2o2b2ob2o$24b3o10b3o8bo2bo4bo2bo7b3o10b
3o7bo2bo4bo2bo7b3o10b3o7bo2bo4bo2bo6b3o10b3o4bo3bo6bo3bo7b2o3b2o3b2o6b
o3bo6bo3bo7b2o3b2o3b2o$25bob2o6b2obo10b3o4b3o9bob2o6b2obo9b3o4b3o9bob
2o6b2obo9b3o4b3o8bob2o6b2obo7b4o4b4o9bo2bob2obo2bo8b4o4b4o9bo2bob2obo
2bo$25bo2bo6bo2bo7b5o6b5o7b2o2bo2bo2b2o7b5o6b5o7b2o2bo2bo2b2o7b5o6b5o
6b2o2bo2bo2b2o32bo4bo35bo4bo$26bo3bo2bo3bo8b2o12b2o11bo2bo11b2o12b2o11b
o2bo11b2o12b2o10bo2bo9b3o12b3o4bo4bo4bo4bo3b3o12b3o4bo4bo4bo4bo$25b2o
2b2o2b2o2b2o6bo2bobo6bobo2bo4bo14bo4bo2bobo6bobo2bo4bo14bo4bo2bobo6bo
bo2bo3bo14bo6bob2ob2ob2obo6bo4bo6bo4bo5bob2ob2ob2obo6bo4bo6bo4bo$24b2o
3bo4bo3b2o8bo10bo6b3o3bo4bo3b3o6bo10bo6b3o3bo4bo3b3o6bo10bo5b3o3bo4bo
3b3o2bo2b2o8b2o2bo4bob2o8b2obo3bo2b2o8b2o2bo4bob2o8b2obo$24b3o3bo2bo3b
3o8b2o8b2o6b2ob2ob6ob2ob2o6b2o8b2o6b2ob2ob6ob2ob2o6b2o8b2o5b2ob2ob6ob
2ob2o6bo8bo9b2o10b2o8bo8bo9b2o10b2o$24bobo10bobo10b8o13b2ob2ob2o13b8o
13b2ob2ob2o13b8o12b2ob2ob2o12b2o4b2o11b12o10b2o4b2o11b12o$26b2o8b2o9b
o3b2o2b2o3bo11bo4bo11bo3b2o2b2o3bo11bo4bo11bo3b2o2b2o3bo10bo4bo15b4o13b
3o2b2o2b3o12b4o13b3o2b2o2b3o$23b2o14b2o6b5o4b5o7bo4b4o4bo7b5o4b5o7bo4b
4o4bo7b5o4b5o6bo4b4o4bo5b3o4b2o4b3o6bo12bo5b3o4b2o4b3o6bo12bo$47b4o6b
4o28b4o6b4o28b4o6b4o28b3o4b3o8bo5bo2bo5bo7b3o4b3o8bo5bo2bo5bo$49bo8bo
8b2ob2o6b2ob2o8bo8bo8b2ob2o6b2ob2o8bo8bo7b2ob2o6b2ob2o26bo3bo4bo3bo27b
o3bo4bo3bo$71b2o4b2o15bo2bo15b2o4b2o15bo2bo14b2o4b2o12bobo2bobo12b2o6b
2o11bobo2bobo12b2o6b2o$71bobo2bobo14b2o2b2o14bobo2bobo14b2o2b2o13bobo
2bobo13b2o2b2o15b2o2b2o14b2o2b2o15b2o2b2o$73bo2bo16bo4bo16bo2bo16bo4b
o15bo2bo36b2o2b2o35b2o2b2o$74b2o40b2o39b2o15bo6bo14b2o2b2o13bo6bo14b2o
2b2o$71b8o10b3o8b3o10b8o10b3o8b3o9b8o31bo10bo29bo10bo$71b3o2b3o9b5o6b
5o9b3o2b3o9b5o6b5o8b3o2b3o8b4o2bo2bo2b4o5bo3bo6bo3bo4b4o2bo2bo2b4o5bo
3bo6bo3bo$67bob2o8b2obo4bo4bo6bo4bo4bob2o8b2obo4bo4bo6bo4bo3bob2o8b2o
bo3bo3b2o6b2o3bo4bo3bo6bo3bo3bo3b2o6b2o3bo4bo3bo6bo3bo$66bobo3bo4bo3b
obo3b4obo6bob4o3bobo3bo4bo3bobo3b4obo6bob4o2bobo3bo4bo3bobo2b2obo10bo
b2o3bo4b2o4b2o4bo2b2obo10bob2o3bo4b2o4b2o4bo$66b2obo2bo4bo2bob2o5b3o8b
3o5b2obo2bo4bo2bob2o5b3o8b3o4b2obo2bo4bo2bob2o5b2o8b2o6bo4bo6bo4bo5b2o
8b2o6bo4bo6bo4bo$69bo10bo9b2o3b2o3b2o9bo10bo9b2o3b2o3b2o8bo10bo12bo2b
o15bo6bo14bo2bo15bo6bo$69bo2bo4bo2bo14b2o14bo2bo4bo2bo14b2o13bo2bo4bo
2bo9bo3b2o3bo9bobo3b2o3bobo8bo3b2o3bo9bobo3b2o3bobo$72bob2obo12b3o6b3o
12bob2obo12b3o6b3o11bob2obo12bo8bo12bo2b2o2bo11bo8bo12bo2b2o2bo$69bob
3o2b3obo30bob3o2b3obo29bob3o2b3obo9bo3b2o3bo11bo8bo10bo3b2o3bo11bo8bo
$71b2ob2ob2o13b8o13b2ob2ob2o13b8o12b2ob2ob2o35b4o37b4o$72bo4bo15bo4bo
15bo4bo15bo4bo14bo4bo13b3o2b3o13b8o12b3o2b3o13b8o$71b2o4b2o13bo6bo13b
2o4b2o13bo6bo12b2o4b2o36b2o39b2o$72bo4bo15b2o2b2o15bo4bo15b2o2b2o14bo
4bo14b2o2b2o14bobo2bobo13b2o2b2o14bobo2bobo$72b2o2b2o16bo2bo16b2o2b2o
16bo2bo15b2o2b2o15bo2bo16b2o2b2o15bo2bo16b2o2b2o$73bo2bo16bo4bo16bo2b
o16bo4bo15bo2bo15bo4bo16bo2bo15bo4bo16bo2bo$72bo4bo16bo2bo16bo4bo16bo
2bo15bo4bo15b4o16b2o2b2o15b4o16b2o2b2o$73b4o38b4o37b4o17b2o39b2o$93bo
4bo36bo4bo35b4o37b4o$93b2o2b2o36b2o2b2o34b2o2b2o15b2o2b2o14b2o2b2o15b
2o2b2o$72b6o14b2o4b2o14b6o14b2o4b2o13b6o13bo6bo15bo2bo14bo6bo15bo2bo$
71bo2b2o2bo34bo2b2o2bo33bo2b2o2bo11bo8bo12b3o2b3o11bo8bo12b3o2b3o$71b
8o11bo10bo11b8o11bo10bo10b8o$71b3o2b3o10b2o10b2o10b3o2b3o10b2o10b2o9b
3o2b3o9b2o10b2o7b2o10b2o6b2o10b2o7b2o10b2o$69bobo6bobo8bo2b2o4b2o2bo8b
obo6bobo8bo2b2o4b2o2bo7bobo6bobo7bo2bo6bo2bo7b3o8b3o6bo2bo6bo2bo7b3o8b
3o$67b2ob2o6b2ob2o11bo2bo11b2ob2o6b2ob2o11bo2bo10b2ob2o6b2ob2o6bob2o4b
2obo8b2o2bo4bo2b2o7bob2o4b2obo8b2o2bo4bo2b2o$69bo10bo8bo4bo2bo4bo8bo10b
o8bo4bo2bo4bo7bo10bo7b3ob2o2b2ob3o12bo2bo11b3ob2o2b2ob3o12bo2bo$69bo2b
2o2b2o2bo9bobo2b2o2bobo9bo2b2o2b2o2bo9bobo2b2o2bobo8bo2b2o2b2o2bo8bob
o6bobo12b2o2b2o11bobo6bobo12b2o2b2o$69bo2b2o2b2o2bo8bobo8bobo8bo2b2o2b
2o2bo8bobo8bobo7bo2b2o2b2o2bo6bo4bob2obo4bo6b3o3b2o3b3o5bo4bob2obo4bo
6b3o3b2o3b3o$67b2o3bob2obo3b2o4b3o3bob2obo3b3o4b2o3bob2obo3b2o4b3o3bo
b2obo3b3o3b2o3bob2obo3b2o3bo2bo10bo2bo5bob2obo2bob2obo4bo2bo10bo2bo5b
ob2obo2bob2obo$67b3o3bo2bo3b3o5b2o3b2o2b2o3b2o5b3o3bo2bo3b3o5b2o3b2o2b
2o3b2o4b3o3bo2bo3b3o4bo4b2o2b2o4bo4bo4b2ob2ob2o4bo3bo4b2o2b2o4bo4bo4b
2ob2ob2o4bo$67bo4b2o2b2o4bo4b2o4b2o2b2o4b2o4bo4b2o2b2o4bo4b2o4b2o2b2o
4b2o3bo4b2o2b2o4bo3b2o4bo4bo4b2o8bo6bo7b2o4bo4bo4b2o8bo6bo$72bo4bo112b
3o3b2o2b2o3b3o23b3o3b2o2b2o3b3o$66b2o14b2o11b2o11b2o3bo6bo3b2o11b2o10b
2o3bo6bo3b2o30b4o37b4o$93bo4bo36bo4bo35b4o37b4o$89b2o2bo4bo2b2o11bo4b
o11b2o2bo4bo2b2o10bo4bo10b2o2b6o2b2o12bo2bo11b2o2b6o2b2o12bo2bo$88bo2b
10o2bo6b2o3b4o3b2o6bo2b10o2bo5b2o3b4o3b2o5bo2bo8bo2bo6b3o3b2o3b3o5bo2b
o8bo2bo6b3o3b2o3b3o$89b3o8b3o7b2o3bo2bo3b2o7b3o8b3o6b2o3bo2bo3b2o6b2o
bo6bob2o6bo4b6o4bo5b2obo6bob2o6bo4b6o4bo$90b3o6b3o8bo2b3o2b3o2bo8b3o6b
3o7bo2b3o2b3o2bo27bo4b4o4bo27bo4b4o4bo$90b2obob2obob2o12bob2obo12b2ob
ob2obob2o11bob2obo12bobo4bobo31bobo4bobo$90bo3b4o3bo12b6o12bo3b4o3bo11b
6o11b12o8bo3bo4bo3bo7b12o8bo3bo4bo3bo$94b4o13b3o6b3o13b4o12b3o6b3o9b2o
6b2o10b2obo4bob2o9b2o6b2o10b2obo4bob2o$89b3o8b3o7bobo8bobo7b3o8b3o6bo
bo8bobo5b3o10b3o6bobo2bo2bo2bobo5b3o10b3o6bobo2bo2bo2bobo$89b4o6b4o28b
4o6b4o47bo2bo2b2o2bo2bo27bo2bo2b2o2bo2bo$89bo3bo4bo3bo6b2o12b2o6bo3bo
4bo3bo5b2o12b2o7b3o4b3o8bo3bo6bo3bo7b3o4b3o8bo3bo6bo3bo$88b2o12b2o11b
o2bo11b2o12b2o10bo2bo10b6o4b6o8b2o6b2o7b6o4b6o8b2o6b2o$87bo5bo4bo5bo4b
6o4b6o4bo5bo4bo5bo3b6o4b6o3bo3b2o6b2o3bo4b2o12b2o3bo3b2o6b2o3bo4b2o12b
2o$108bo16bo23bo16bo3bo6b2o6bo5bo14bo4bo6b2o6bo5bo14bo$109b2o5b2o5b2o
25b2o5b2o5b2o11b2o18b4o17b2o18b4o$115bo2bo37bo2bo38b2o39b2o$174b2o4b2o
33b2o4b2o$174b2o4b2o13b2o4b2o12b2o4b2o13b2o4b2o$174b2o4b2o12bo2bo2bo2b
o11b2o4b2o12bo2bo2bo2bo$172bo2bo4bo2bo10bo2b4o2bo9bo2bo4bo2bo10bo2b4o
2bo$171bo5b2o5bo8b3o6b3o7bo5b2o5bo8b3o6b3o$172bo4b2o4bo29bo4b2o4bo$177b
2o18bo2bo17b2o18bo2bo$174bo6bo14b6o13bo6bo14b6o$174b2o4b2o13b3o2b3o12b
2o4b2o13b3o2b3o$197bo2bo37bo2bo$176bo2bo15b2o4b2o14bo2bo15b2o4b2o$169b
3obo8bob3o3b3o12b3o2b3obo8bob3o3b3o12b3o$170bo3bobo2bobo3bo4b3o3bo4bo
3b3o3bo3bobo2bobo3bo4b3o3bo4bo3b3o$170bobob3o2b3obobo5bob2o2bo2bo2b2o
bo4bobob3o2b3obobo5bob2o2bo2bo2b2obo$172b3obo2bob3o13bo2bo12b3obo2bob
3o13bo2bo$171b2o10b2o7b2obobo2bobob2o6b2o10b2o7b2obobo2bobob2o$174bo6b
o12b3o4b3o11bo6bo12b3o4b3o2$198b2o39b2o$197bo2bo37bo2bo!

As you can see, there are some duplicate spaceships that alternate between one spaceship and another.
For example, take this spaceship partial:

Code: Select all

x = 106, y = 54, rule = LifeHistory
F9B2A9BF9B2A9BF20BF20BF8B4A8BF$F9B2A9BF20BF8BA2BA8BF7B6A7BF6BA6BA6BF$
F7BAB2ABA7BF7BAB2ABA7BF6B2AB2AB2A6BF4BAB8ABA4BF6BA6BA6BF$F5B3A4B3A5BF
6B3A2B3A6BF3B4A6B4A3BF3BA12BA3BF3BA2BA2B2A2BA2BA3BF$F2B2A12B2A2BF2B4A
2B4A2B4A2BF2BAB3A6B3ABA2BF2BA4BA4BA4BA2BF2B2A12B2A2BF$F2B2A2BAB4ABA2B
2A2BF2B2A4B4A4B2A2BF2BA4BA4BA4BA2BF3BA3BA4BA3BA3BF6B3A2B3A6BF$F6BABA2B
ABA6BF8BA2BA8BF6BABA2BABA6BF6BABA2BABA6BF6BAB4ABA6BF$F20BF5B3A4B3A5BF
6B3A2B3A6BF6BA2B2A2BA6BF5B2AB4AB2A5BF$F5B2A6B2A5BF3BA3BA4BA3BA3BF7B2A
2B2A7BF2BA3BABA2BABA3BA2BF2B2A3BAB2ABA3B2A2BF$F2B6A4B6A2BF2BA4BA4BA4B
A2BFB3A12B3ABF2B2A12B2A2BF2BABA10BABA2BF$F2BABA10BABA2BFB2A14B2ABF3BA
12BA3BF3B2A10B2A3BF4BA10BA4BF$F2BAB2A8B2ABA2BFB2A14B2ABF3BA12BA3BF3BA
12BA3BF2B3A10B3A2BF$F2BAB2A8B2ABA2BF2BA3BA6BA3BA2BFB2A14B2ABF2BA14BA2B
F2BABA10BABA2BF$FB2AB2A8B2AB2ABF20BF20BF2B3A10B3A2BF2BABA10BABA2BF$FB
2ABA10BAB2ABF4BA10BA4BF3B3A8B3A3BF3BABA8BABA3BF2B2A12B2A2BF$F2BABA10B
ABA2BFB2AB2A8B2AB2ABF4B2A8B2A4BF7BA4BA7BF4BA2BA4BA2BA4BF$F4BA2B2A2B2A
2BA4BF4BA2B2A2B2A2BA4BF3B6A2B6A3BF3BA2B2A4B2A2BA3BF4B5A2B5A4BF$F3BA4B
A2BA4BA3BF7B2A2B2A7BF20BF4B2A2BA2BA2B2A4BF4B2A2BA2BA2B2A4BF$F9B2A9BF8B
4A8BF7BA4BA7BF6B2A4B2A6BF5B4A2B4A5BF$F8BA2BA8BF9B2A9BF6B2A4B2A6BF7BA4B
A7BF5BABA4BABA5BF$F20BF5B3A4B3A5BF3BABABAB2ABABABA3BF4B2ABAB2ABAB2A4B
F4B3ABA2BAB3A4BF$F4B4A4B4A4BF2B4AB2A2B2AB4A2BF2BA2BA3B2A3BA2BA2BF2B3A
10B3A2BFB2A14B2ABF$FB3A2B2AB2AB2A2B3ABF2B2A3BAB2ABA3B2A2BF2BA4BAB2ABA
4BA2BFB2AB3A6B3AB2ABFB2A3BA2B2A2BA3B2ABF$F3BA5B2A5BA3BF4B2A8B2A4BF2BA
B2A3B2A3B2ABA2BF4B2A2B4A2B2A4BF2BA3BA2B2A2BA3BA2BF$FB2ABAB3A2B3ABAB2A
BF2BA3B3A2B3A3BA2BF4BA10BA4BF3B2A10B2A3BF3B3A2BA2BA2B3A3BF$F3B3A3B2A3B
3A3BF5B10A5BF5BA3B2A3BA5BF8BA2BA8BF4BA10BA4BF$F3BA12BA3BF3BA2BA6BA2BA
3BF8B4A8BF5BA2BA2BA2BA5BF5BA2BA2BA2BA5BF$F5B2A2B2A2B2A5BF4B2A8B2A4BF3B
3A8B3A3BF3B3A3B2A3B3A3BF3BAB2A2B2A2B2ABA3BF$F5B10A5BF4BA10BA4BF4BA10B
A4BF3BA2BA6BA2BA3BF3BA3BA4BA3BA3BF$F5BAB2A2B2ABA5BF5BA8BA5BF5B2A6B2A5B
F5B3A4B3A5BF5BABA4BABA5BF$F7BA4BA7BF6B2A4B2A6BF6B2A4B2A6BF7BA4BA7BF7B
2A2B2A7BF$F8BA2BA8BF8BA2BA8BF5BA2BA2BA2BA5BF8BA2BA8BF6BABA2BABA6BF$F6B
ABA2BABA6BF5B2ABA2BAB2A5BF7BA4BA7BF6B3A2B3A6BF6BA2B2A2BA6BF$F5B2AB4AB
2A5BF20BF7BA4BA7BF7B2A2B2A7BF6BABA2BABA6BF$F5B2AB4AB2A5BF8BA2BA8BF8BA
2BA8BF20BF6B2A4B2A6BF$F6BA6BA6BF8B4A8BF7B6A7BF5B2A6B2A5BF4BABA6BABA4B
F$F5B3A4B3A5BF4B2ABA4BAB2A4BF4B3AB4AB3A4BF4B3A6B3A4BF3BA12BA3BF$F3BAB
A8BABA3BF4B2A8B2A4BF3BA12BA3BF3B3A3B2A3B3A3BF2BA3BA6BA3BA2BF$F2BA14BA
2BF2BA2B2A6B2A2BA2BF2BA14BA2BF2B2A12B2A2BF2B2A12B2A2BF$F2B2AB2A6B2AB2A
2BF2B5A6B5A2BF2BA3B2AB2AB2A3BA2BF5B3A4B3A5BF5B2A6B2A5BF$F5B2A6B2A5BF3B
A4B4A4BA3BF5B2A6B2A5BF2B2ABA8BAB2A2BF2B2ABA8BAB2A2BF$F4B2AB6AB2A4BF3B
A3B6A3BA3BF2B2A2BA6BA2B2A2BF3B2A10B2A3BF7B6A7BF$F2B2ABA8BAB2A2BF3BABA
B6ABABA3BF4BAB2A4B2ABA4BF3BAB10ABA3BF3BAB10ABA3BF$F6BA6BA6BF20BF8B4A8B
F20BF9B2A9BF$F20BF20BF8B4A8BF7BA4BA7BF7BAB2ABA7BF$F20BF7B6A7BF7BA4BA7B
F7B6A7BF6BA2B2A2BA6BF$F6B8A6BF6BAB4ABA6BF6BA6BA6BF6BABA2BABA6BF6BA6BA
6BF$F6B2A4B2A6BF6BA2B2A2BA6BF7B2A2B2A7BF7BA4BA7BF7BA4BA7BF$F20BF20BF20B
F20BF20BF$F20DF20DF20DF20DF20BF$F20.F20.F20.F20.F20.F$F20.F20.F20.F20.
F20.F$F20.F20.F20.F20.F20.F$F20.F20.F20.F20.F20.F!

On the rightmost phase, that is the first time that the program says it finds a spaceship. However, there is still the possibility of tagalongs (red lines below the spaceships) that the program has to search through before discarding future results. A possible bug is that it reports those other four spaceships, even though it was already reported on the last phase.

I think that this is the root cause of the 'duplicate spaceships' bug. Let me know if this is the case!

[Sokwe]

On the rightmost phase, that is the first time that the program says it finds a spaceship. However, there is still the possibility of tagalongs (red lines below the spaceships) that the program has to search through before discarding future results. A possible bug is that it reports those other four spaceships, even though it was already reported on the last phase.

I think that this is the root cause of the 'duplicate spaceships' bug. Let me know if this is the case!

When gcd(period,offset) = 1, qfind will only find the spaceship at the first occurrence. It does this by running terminal() twice: first on the newest node, and then on its parent. If terminal() returns true on the new node, but not its parent, then we have a new ship. If terminal() returns true on both, then we know the ship was already found at the parent node.

When gcd(period,offset) > 1, you will get outputs of the same ship in different phases (the number of such outputs will be period / gcd(period,offset)).

In your case, the duplicate spaceships are almost certainly caused by the fact that the search prints spaceships during the deepening step (use `./qfind --help` to see how to disable this feature). In such cases the double use of terminal() can't be applied, so the search can find the same spaceship each time it enters the deepening step. To prevent most of this duplicate output, qfind simply checks to see if the current pattern to print is identical to the last pattern that it printed. However, in your case there are two spaceships of similar length, so it finds one during the deepening step, then finds the other. Then when it enters the deepening step again it finds the first ship again, then the second ship again, resulting in duplicate output.

I intend to eventually fix this by properly storing past spaceship output in a hash table, but I've been busy with other projects, and I consider it a low priority.

[R2INT]

Quick thought expirement:
Suppose I search for c/2o in the rule Travelling T's (B3/S23-a5) with odd symmetry and logical width 6. With the default settings (-q 15), it finds these 19 spaceships:

Code: Select all

x = 294, y = 29, rule = B3/S23-a5
2bo5bo10bo7b4o3b4o7b4ob4o6b4o3b4o5b3o5b3o7b3o3b3o7b3o5b3o6b4o3b4o7b3o
5b3o6b3o5b3o5b3o5b3o5b4o3b4o6b3o3b3o6b3o3b3o6b2o5b2o5b3o3b3o7bo5bo7bo
5bo$2ob2ob2ob2o6b2ob2o6bob2ob2obo7b2obo3bob2o6bob2ob2obo7bo7bo7b2ob2o
b2ob2o7bo7bo8bob2ob2obo9bo7bo8bo7bo7bo7bo7bob2ob2obo6b2ob2ob2ob2o4b2o
b2ob2ob2o4b2ob2ob2ob2o3b2ob2ob2ob2o4b2ob2ob2ob2o3b2ob2ob2ob2o$bobo3bo
bo8bobo9b2ob2o9b2o7b2o8b2ob2o11b2ob2o9b2ob2ob2ob2o9b2ob2o12b2ob2o13b2o
b2o12b2ob2o11b2ob2o11b2ob2o8b2ob2ob2ob2o4b2ob2ob2ob2o4b2obo3bob2o3b2o
b2ob2ob2o5bobo3bobo5bobo3bobo$29bo5bo10bo5bo9bo5bo7bo3bobo3bo23bo3bob
o3bo8bo5bo9bo3bobo3bo6bo3bobo3bo5bo3bobo3bo7bo5bo$77b2obobob2o8b3o3b3o
8b2obobob2o26b2obobob2o8b2obobob2o7b2obobob2o23b3o3b3o6b3o3b3o8bo3bo7b
3o3b3o5bo3bobo3bo3bo3bobo3bo$64b3o9bobobobobobo6bo3bobo3bo6bobobobobo
bo10b3o11bobobobobobo6bobobobobobo5bobobobobobo9b3o9bo3bobo3bo4bo3bob
o3bo9bo8bo3bobo3bo5b3o3b3o5b3o3b3o$64bobo10bobo3bobo11bobo11bobo3bobo
11bobo12bobo3bobo8bobo3bobo7bobo3bobo10bobo13b3o12b3o12bobo11b3o9b2ob
obob2o5b2obobob2o$76b2ob2ob2ob2o8bobobobo8b2ob2ob2ob2o24b2ob2ob2ob2o6b
2ob2ob2ob2o5b2ob2ob2ob2o23b2obob2o8b2obob2o10bobo9b2obob2o11bo13bo$130b
o3bo62bo3bo12bobo12bobo26bobo11bobobo9bobobo$110b3ob3ob3o8b2o3b2o9b3o
b3ob3o6b3ob3ob3o5b3ob3ob3o7b2o3b2o11b3o12b3o10b2o3b2o9b3o$129b3ob3o60b
obobobo39bobobobo24bobo11bobo$130b5o60b2obobob2o10bobo12bobo12bobo11b
obo12bobo11bobo$130bobobo10b2o7b2o7b2o5b2o7b2o5b2o10bobo14bo12b2ob2o8b
2obobob2o9bo14bo13bo$146bo7bo8bo7bo8bo5bo11bobo11b2obob2o9b2ob2o11bob
o9b2obob2o9bobobo9bobobo$145bobo5bobo6bobo5bobo6bobo3bobo9b2ob2o8b2o7b
2o8b3o12bobo7b2o7b2o5b2obobob2o5b2obobob2o$194b4o3b4o6bobo3bobo10bo10b
o2bobo2bo5bobo3bobo5b2ob2ob2ob2o3b2ob2ob2ob2o$195bobo3bobo9b2ob2o11bo
bo8b3o5b3o6b2ob2o7b2ob2ob2ob2o3b2ob2ob2ob2o$212bo5bo7b9o5b2obo3bob2o5b
o5bo9b2ob2o9b2ob2o$214b3o8b2ob2ob2ob2o22bobo12bobo11bobo$225b2obobobo
b2o5b2o5b2o7bo3bo10b5o9bo3bo$228bo3bo7bob2o3b2obo5bobobobo11bo11b2ob2o
$228bobobo7bob2o3b2obo4bo2bobo2bo21bobobobo$241bo7bo5bo7bo7b7o6b3o3b3o
$240b2o7b2o6bo3bo8b2obobob2o6bo5bo$255b2o5b2o6b2o5b2o5bo7bo$272bo3bo7b
o2bobo2bo$286b2ob2o$285bobobobo$287bobo!

This search is simple enough that at the default settings, the queue never overflows. However, if I reduce the queue size, then duplicate spaceship prints begin to occur.

Code: Select all

-q 12: 19 spaceships
-q 11: 23 spaceships
-q 10: 28 spaceships
-q 9: 75 spaceships

Now, let's try --disable-deep-print for this test case.

Code: Select all

-q 12 --disable-deep-print: 19 spaceships
-q 11 --disable-deep-print: 22 spaceships
-q 10 --disable-deep-print: 24 spaceships
-q 9 --disable-deep-print: 40 spaceships

Weird. . . It seems to detect more distinct spaceships, and it also detects some psuedo spaceships. Take a look:

Code: Select all

x = 356, y = 70, rule = B3/S23-a5
b3o3b3o5b2o5b2o5b3o3b3o4bo7bo5bo5bo11bo5bo8b3o3b3o15bo5bo7b3o3b3o7bo5b
o8bo5bo8bo5bo9bo5bo7b3o3b3o7b3o3b3o7bo5bo8b3o3b3o6b3o3b3o6b3o3b3o7b3o
3b3o8bo5bo9b3o3b3o8b3o3b3o$2ob2ob2ob2o3b2ob2ob2ob2o3b2ob2ob2ob2o2b3o5b
3o2b2ob2ob2ob2o7b2ob2ob2ob2o5b2ob2ob2ob2o12b2ob2ob2ob2o4b2ob2ob2ob2o4b
2ob2ob2ob2o4b2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2o
b2ob2o4b2ob2ob2ob2o5b2ob2ob2ob2o4b2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2ob2ob
2o5b2ob2ob2ob2o6b2ob2ob2ob2o6b2ob2ob2ob2o$2ob2ob2ob2o3b2obo3bob2o3b2o
b2ob2ob2o2b2obo3bob2o3bobo3bobo9bobo3bobo6b2ob2ob2ob2o13bobo3bobo5b2o
b2ob2ob2o5bobo3bobo6bobo3bobo6bobo3bobo7bobo3bobo5b2ob2ob2ob2o5b2ob2o
b2ob2o5bobo3bobo6b2ob2ob2ob2o4b2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2ob2ob2o6b
obo3bobo7b2ob2ob2ob2o6b2ob2ob2ob2o$44b2ob2o$b3o3b3o7bo3bo7b3o3b3o4b2o
bobob2o3bo3bobo3bo7bo3bobo3bo6b3o3b3o13bo3bobo3bo5b3o3b3o5bo3bobo3bo4b
o3bobo3bo4bo3bobo3bo5bo3bobo3bo5b3o3b3o7b3o3b3o5bo3bobo3bo6b3o3b3o6b3o
3b3o6b3o3b3o7b3o3b3o6bo3bobo3bo7b3o3b3o8b3o3b3o$o3bobo3bo8bo8bo3bobo3b
o2bobobobobobo3b3o3b3o9b3o3b3o6bo3bobo3bo13b3o3b3o5bo3bobo3bo5b3o3b3o
6b3o3b3o6b3o3b3o7b3o3b3o5bo3bobo3bo5bo3bobo3bo5b3o3b3o6bo3bobo3bo4bo3b
obo3bo4bo3bobo3bo5bo3bobo3bo6b3o3b3o7bo3bobo3bo6bo3bobo3bo$4b3o11bobo
11b3o6bo3bobo3bo3b2obobob2o9b2obobob2o10b3o17b2obobob2o9b3o9b2obobob2o
6b2obobob2o6b2obobob2o7b2obobob2o9b3o13b3o9b2obobob2o10b3o12b3o12b3o13b
3o10b2obobob2o11b3o14b3o$2b2obob2o9bobo9b2obob2o22bo17bo12b2obob2o19b
o11b2obob2o11bo14bo14bo15bo11b2obob2o9b2obob2o11bo12b2obob2o8b2obob2o
8b2obob2o9b2obob2o12bo13b2obob2o10b2obob2o$4bobo25bobo6b2ob2ob2ob2o5b
obobo13bobobo12bobo19bobobo11bobo11bobobo10bobobo10bobobo11bobobo11bo
bo13bobo11bobobo12bobo12bobo12bobo13bobo12bobobo13bobo14bobo$4b3o9b2o
3b2o9b3o57b3o35b3o73b3o13b3o28b3o12b3o12b3o13b3o30b3o14b3o$16bobobobo
19bo3bo3bo7bobo15bobo36bobo27bobo12bobo12bobo13bobo43bobo75bobo$4bobo
11bobo11bobo7bo3bo3bo7bobo15bobo13bobo20bobo12bobo12bobo12bobo12bobo13b
obo12bobo13bobo12bobo13bobo12bobo12bobo13bobo13bobo14bobo14bobo$3b2ob
2o7b2obobob2o9bo25bo17bo15bo22bo14bo14bo14bo14bo15bo14bo15bo14bo15bo14b
o14bo15bo15bo16bo16bo$3b2ob2o10bobo9b2obob2o5b2o5b2o6bobobo13bobobo10b
2obob2o17bobobo9b2obob2o9bobobo10bobobo10bobobo11bobobo9b2obob2o9b2ob
ob2o9bobobo10b2obob2o8b2obob2o8b2obob2o9b2obob2o10bobobo11b2obob2o10b
2obob2o$4b3o11bobo7b2o7b2o5bo3bo6b2obobob2o9b2obobob2o6b2o7b2o13b2obo
bob2o5b2o7b2o5b2obobob2o6b2obobob2o6b2obobob2o7b2obobob2o5b2o7b2o5b2o
7b2o5b2obobob2o6b2o7b2o4b2o7b2o4b2o7b2o5b2o7b2o6b2obobob2o7b2o7b2o6b2o
7b2o$5bo9bo2bobo2bo5bobo3bobo4bo2bobo2bo3b2ob2ob2ob2o7b2ob2ob2ob2o6bo
bo3bobo13b2ob2ob2ob2o5bobo3bobo5b2ob2ob2ob2o4b2ob2ob2ob2o4b2ob2ob2ob2o
5b2ob2ob2ob2o5bobo3bobo7bobo3bobo5b2ob2ob2ob2o6bobo3bobo6bobo3bobo6bo
bo3bobo7bobo3bobo6b2ob2ob2ob2o7bobo3bobo8bobo3bobo$4bobo7b3o5b3o6b2ob
2o8bo3bo5b2ob2ob2ob2o7b2ob2ob2ob2o8b2ob2o15b2ob2ob2ob2o7b2ob2o7b2ob2o
b2ob2o4b2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2ob2ob2o7b2ob2o11b2ob2o7b2ob2ob2o
b2o8b2ob2o10b2ob2o10b2ob2o11b2ob2o8b2ob2ob2ob2o9b2ob2o12b2ob2o$b9o4b2o
bo3bob2o5bo5bo8bobo9b2ob2o13b2ob2o10bo5bo17b2ob2o9bo5bo9b2ob2o10b2ob2o
10b2ob2o11b2ob2o9bo5bo9bo5bo9b2ob2o10bo5bo8bo5bo8bo5bo9bo5bo10b2ob2o11b
o5bo10bo5bo$2ob2ob2ob2o21bobo9bo3bo9bobo15bobo13bobo20bobo12bobo12bob
o12bobo12bobo13bobo12bobo13bobo12bobo13bobo12bobo12bobo13bobo13bobo14b
obo14bobo$2obobobob2o4b2o5b2o7bo3bo5b3o5b3o5b5o13bo3bo11bo3bo18b5o10b
obobo10b5o10b5o10b5o11b5o10bobobo11bobobo10b5o11bobobo10bobobo10bobob
o11bobobo11b5o12bobobo12bobobo$3bo3bo6bob2o3b2obo5bobobobo5bobo3bobo8b
o15b2ob2o10bobobobo19bo14bo14bo14bo14bo15bo14bo15bo14bo15bo14bo14bo15b
o15bo16bo16bo$3bobobo6bob2o3b2obo4bo2bobo2bo36bobobobo8bo2bobo2bo31bo
3bo71bo3bo11bo3bo26bo3bo10bo3bo10bo3bo11bo3bo28bo3bo12bo3bo$15bo7bo5b
o7bo4bo7bo5b7o10b3o3b3o7bo7bo15b7o7b2obobob2o7b7o8b7o8b7o9b7o7b2obobo
b2o7b2obobob2o7b7o8b2obobob2o6b2obobob2o6b2obobob2o7b2obobob2o8b7o9b2o
bobob2o8b2obobob2o$14b2o7b2o6bo3bo10bo8b2obobob2o10bo5bo10bo3bo16b2ob
obob2o7bobobobo7b2obobob2o6b2obobob2o6b2obobob2o7b2obobob2o7bobobobo9b
obobobo7b2obobob2o8bobobobo8bobobobo8bobobobo9bobobobo8b2obobob2o9bob
obobo10bobobobo$29b2o5b2o6b2ob2o6b2o5b2o9bo7bo7b2o5b2o14b2o5b2o21b2o5b
2o6b2o5b2o6b2o5b2o7b2o5b2o37b2o5b2o69b2o5b2o$45bobo9bo3bo11bo2bobo2bo
32bo3bo9bo5bo9bo3bo10bo3bo10bo3bo11bo3bo9bo5bo9bo5bo9bo3bo10bo5bo8bo5b
o8bo5bo9bo5bo10bo3bo11bo5bo10bo5bo$75b2ob2o9b2o5b2o18bo13b3o13bo14bo14b
o15bo13b3o13b3o13bo14b3o12b3o12b3o13b3o14bo15b3o14b3o$74bobobobo8bo7b
o17bobo11b2ob2o11bobo12bobo12bobo13bobo11b2ob2o11b2ob2o11bobo12b2ob2o
10b2ob2o10b2ob2o11b2ob2o12bobo13b2ob2o12b2ob2o$76bobo9bobo5bobo15b2ob
2o25b2ob2o10b2ob2o10b2ob2o11b2ob2o41b2ob2o73b2ob2o$114b2ob2o10bo3bo10b
2ob2o10b2ob2o10b2ob2o11b2ob2o11bobo13bobo11b2ob2o12bobo12bobo12bobo13b
obo12b2ob2o13bobo14bobo$115b3o10b2o3b2o8b2o3b2o10b3o10b2o3b2o11b3o11b
obobo11bobobo11b3o12bobobo10bobobo10bobobo11bobobo12b3o13bobobo12bobo
bo$116bo11bobobobo8bobobobo11bo11bobobobo12bo14bo15bo14bo15bo14bo14bo
15bo15bo16bo16bo$115bobo9b2obobob2o9bobo12bobo12bobo13bobo10bo5bo9bo5b
o10bobo11bo5bo8bo5bo8bo5bo9bo5bo11bobo12bo5bo10bo5bo$112b9o9bobo9b2ob
obob2o6b9o6b2obobob2o7b9o5b2ob2ob2ob2o5b2ob2ob2ob2o5b9o6b2ob2ob2ob2o4b
2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2ob2ob2o6b9o7b2ob2ob2ob2o6b2ob2ob2ob2o$111b
2ob2ob2ob2o8bobo12bobo8b2ob2ob2ob2o8bobo9b2ob2ob2ob2o5bobo3bobo7bobo3b
obo5b2ob2ob2ob2o6bobo3bobo6bobo3bobo6bobo3bobo7bobo3bobo6b2ob2ob2ob2o
7bobo3bobo8bobo3bobo$111b2obobobob2o7b2ob2o11bobo8b2obobobob2o8bobo9b
2obobobob2o7bobobo11bobobo7b2obobobob2o8bobobo10bobobo10bobobo11bobob
o8b2obobobob2o9bobobo12bobobo$114bo3bo7b4o3b4o5bo2bobo2bo8bo3bo8bo2bo
bo2bo9bo3bo10bo3bo11bo3bo10bo3bo11bo3bo10bo3bo10bo3bo11bo3bo11bo3bo12b
o3bo12bo3bo$114bobobo8bobo3bobo5b3o5b3o7bobobo7b3o5b3o8bobobo11bobo13b
obo11bobobo12bobo12bobo12bobo13bobo12bobobo13bobo14bobo$141b2obo3bob2o
19b2obo3bob2o$202b3o5b3o5b3o5b3o20b3o5b3o4b3o5b3o4b3o5b3o5b3o5b3o23b2o
5b2o8b2o5b2o$146bo9b4o3b4o5b2o5b2o6b4o3b4o5bo7bo7bo7bo5b4o3b4o6bo7bo6b
o7bo6bo7bo7bo7bo6b4o3b4o6b2ob2ob2ob2o6b2ob2ob2ob2o$144b2ob2o8bob2ob2o
bo5bob2o3b2obo6bob2ob2obo8b2ob2o11b2ob2o8bob2ob2obo9b2ob2o10b2ob2o10b
2ob2o11b2ob2o9bob2ob2obo7b2obo3bob2o6b2obo3bob2o$145bobo11b2ob2o7bob2o
3b2obo8b2ob2o7bo3bobo3bo5bo3bobo3bo7b2ob2o8bo3bobo3bo4bo3bobo3bo4bo3b
obo3bo5bo3bobo3bo8b2ob2o$158bo5bo7bo7bo8bo5bo7b2obobob2o7b2obobob2o7b
o5bo8b2obobob2o6b2obobob2o6b2obobob2o7b2obobob2o8bo5bo11bo3bo12bo3bo$
171b2o7b2o20bobobobobobo5bobobobobobo20bobobobobobo4bobobobobobo4bobo
bobobobo5bobobobobobo27bo16bo$191b3o9bobo3bobo7bobo3bobo9b3o10bobo3bo
bo6bobo3bobo6bobo3bobo7bobo3bobo10b3o14bobo14bobo$191bobo8b2ob2ob2ob2o
5b2ob2ob2ob2o8bobo9b2ob2ob2ob2o4b2ob2ob2ob2o4b2ob2ob2ob2o5b2ob2ob2ob2o
9bobo14bobo14bobo2$218b3ob3ob3o7bo3bo8b3ob3ob3o4b3ob3ob3o4b3ob3ob3o5b
3ob3ob3o8bo3bo11b2o3b2o10b2o3b2o$235b2o3b2o71b2o3b2o11bo3bo12bo3bo$235b
3ob3o71b3ob3o12bobo14bobo$236b5o8b2o7b2o5b2o5b2o6b2o5b2o7b2o5b2o24bo7b
o8bo7bo$236bobobo9bo7bo6bo7bo7bo5bo9bo5bo8b2o5b2o8b2o5b2o8b2o5b2o$249b
obo5bobo4bobo5bobo5bobo3bobo7bobo3bobo7bo7bo7b3o5b3o6b3o5b3o$297b3ob3o
7bo9bo$298b2ob2o11bo3bo11b2o3b2o10b2o3b2o$298b2ob2o10b2o3b2o10bobobob
o10bobobobo$296b3o3b3o8bobobobo12bobo14bobo$295b2obo3bob2o6b2obobob2o
8b2obobob2o8b2obobob2o$295b2o7b2o9bobo14bobo14bobo$297bo5bo11bobo14bo
bo14bobo$314b2ob2o10bo2bobo2bo8bo2bobo2bo$311b4o3b4o6b3o5b3o6b3o5b3o$
312bobo3bobo7b2obo3bob2o6b2obo3bob2o2$333bo12b2o5b2o$331b2ob2o9bob2o3b
2obo$332bobo10bob2o3b2obo$346bo7bo$345b2o7b2o!

[Sokwe]

Suppose I search for c/2o in the rule Travelling T's (B3/S23-a5) with odd symmetry and logical width 6...

let's try --disable-deep-print for this test case.

Code: Select all

-q 12 --disable-deep-print: 19 spaceships
-q 11 --disable-deep-print: 22 spaceships
-q 10 --disable-deep-print: 24 spaceships
-q 9 --disable-deep-print: 40 spaceships

It seems to detect more distinct spaceships, and it also detects some psuedo spaceships.

With lower `-q` values, the search enters the deepening step more often and so more often removes nodes (groups of 2*period rows) from the search tree that are unreachable from the current set of leaves (these removals only occur at the end of the deepening step). A search that never enters the deepening step will never remove unreachable nodes. Note that an "unreachable" node may be part of a spaceship that was already output, or it may be part of a partial result that was eliminated either due to duplicate node detection or due to elimination during the deepening step. A newly added node could be equivalent to one of these unreachable nodes, but the hash table for duplicate node elimination points into the search tree to verify that a node is in fact a duplicate, and if these unreachable nodes were removed after a deepening step, a duplicate won't be detected. Therefore, the more often the search enters the deepening step, the more likely it will be that a duplicate node will not be detected as a duplicate. This can result in more spaceships being found, although they will typically be made up only of components found earlier in the search.

The reason it detects two spaceships following in close proximity is that the node representing the front of the following spaceship has already been removed due to being "unreachable", so when it finds a spaceship it's allowed to find that same front end again without eliminating it. Notice that if you select a completely blank row between these two spaceships, that row will never be blank for 2*period generations (in this case 4). This is because adding such nodes is prevented when terminal() returns true. These blank nodes are not eliminated by duplicate node elimination, despite matching the root node. This is why such blank nodes will never occur within a detected "spaceship", even when duplicate node elimination is turned off (`-h 0`).

[R2INT]

I think that this might be a reasonable approach to eliminate duplicate spaceships:

• A spaceship that is found outside the deepening step should always be printed, because it is guaranteed that it will not be visited again.
• If a spaceship is found during the deepening step, then only print it if the deepening step removes the branch. If the branch containing a spaceship is removed, the search will not visit that spaceship again.
• If the deepening step does not remove the branch, then do not print that spaceship, as it is guaranteed to visit that spaceship later in the search.

Here is some pseudocode to help you understand this:

Code: Select all

In deepening increment:
	Search for partial spaceships
	If complete spaceship detected: store it to a buffer
	If branch removed: print spaceships stored in buffer
	If branch kept: discard spaceships stored in buffer

In breadth-first search:
	If spaceship found: print spaceship

For period multiplied spaceships, the search prints the same spaceships multiple times in different phases. For example, a 2c/4 search could have these two partials, which, if they were both extended, would lead to duplicate prints of the x66:

Code: Select all

#C The marked rows represent where the search begins period multiplication.
x = 56, y = 31, rule = LifeHistory
47.A5.A$17.A5.A7.3A3.3A6.3A3.3A$.3A3.3A6.3A3.3A5.C2DC3DC2DC4.C2D2C.2C
2DC$DC2DCDC2DCD4.2C2DC.C2D2C4.B3.B.B3.B4.B.2B3.2B.B$B3.B.B3.B5.B2.B.B
2.B6.2B5.2B7.B5.B$2.B.B.B.B7.B7.B5.2B7.2B4.B2.B3.B2.B$2.B5.B7.2B5.2B6.
3B3.3B8.B3.B$2.2B3.2B8.B.B.B.B7.3B3.3B6.B.B3.B.B$3.2B.2B40.B3.B$3.2B.
2B9.B.B.B.B9.B3.B$2.B5.B9.B3.B10.B3.B9$47.A5.A$17.A5.A7.3A3.3A6.3A3.3A
$.3A3.3A6.3A3.3A5.DC2DCDC2DCD4.2C2DC.C2D2C$C2DC3DC2DC4.C2D2C.2C2DC4.B
3.B.B3.B5.B2.B.B2.B$B3.B.B3.B4.B.2B3.2B.B6.B.B.B.B7.B7.B$.2B5.2B7.B5.
B8.B5.B7.2B5.2B$2B7.2B4.B2.B3.B2.B6.2B3.2B8.B.B.B.B$.3B3.3B8.B3.B10.2B
.2B$.3B3.3B6.B.B3.B.B8.2B.2B9.B.B.B.B$18.B3.B9.B5.B9.B3.B$3.B3.B$3.B3.
B!

However, only the top one needs to be searched. This could be done by using canonicalization:

• In period multiplied searches, partials could be marked as not period multiplied.
• If that subperiodic partial encounters period multiplication, then the search can check the hash value obtained from the first period multiplied row for every 2 phases (assuming we are doing a 2c/4 search; see figure).
• If the hash value of the first phase is greater than the hash value of the second phase, then the partial will be eliminated.
• If the hash value of the first phase is equal to that of the second phase, then do not mark it as period multiplied.
• Otherwise, mark it as period multiplied. Partials with the full period do not need to use this deduplication.

For searches with a multiplication factor of 3 (e.g. 3c/6), the hash value of the first phase should be less than or equal to the hash value of the second phase and less than the third phase.

If I am correct, this logic should remove almost all duplicate spaceships, and period multiplied searches would experience a significant speedup since duplicate branches are not checked.

EDIT: Here is a psuedo c/6 spaceship outputted by qfind:

Code: Select all

x = 17, y = 27, rule = B3/S23-a5
2bo11bo$bobo9bobo$o2bo9bo2bo$b2o11b2o$3bo9bo$3b3o5b3o$3b2o7b2o$3b4o3b
4o$2b3o2bobo2b3o$2b3o2bobo2b3o$6b2ob2o2$6b5o$2bo3bobobo3bo$bobo9bobo$
o2bo9bo2bo$b2o11b2o$3bo9bo$3b3o5b3o$3b2o7b2o$3b4o3b4o$2b3o2bobo2b3o$2b
3o2bobo2b3o$6b2ob2o2$6b5o$6bobobo!

[LaundryPizza03]

I don't have OpenMP, how can I compile?

Code: Select all

qfind % gcc -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c
clang: error: unsupported option '-fopenmp'
clang: error: unsupported option '-fopenmp'
qfind % gcc -std=c11 -march=native -O3 -Wall -Wextra -o qfind qfind.c 
In file included from qfind.c:97:
./common.h:1590:6: error: conflicting types for 'setkey'
 1590 | void setkey(int h, int v) {
      |      ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdlib.h:260:7: note: previous declaration is here
  260 | void     setkey(const char *) __DARWIN_ALIAS(setkey);
      |          ^
qfind.c:215:32: error: too many arguments to function call, expected 1, have 2
  215 |                      setkey(k, 1);
      |                      ~~~~~~    ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdlib.h:260:7: note: 'setkey' declared here
  260 | void     setkey(const char *) __DARWIN_ALIAS(setkey);
      |          ^      ~~~~~~~~~~~~
qfind.c:225:14: error: too many arguments to function call, expected 1, have 2
  225 |    setkey(k, 0);
      |    ~~~~~~    ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdlib.h:260:7: note: 'setkey' declared here
  260 | void     setkey(const char *) __DARWIN_ALIAS(setkey);
      |          ^      ~~~~~~~~~~~~
3 errors generated.

[Sokwe]

I don't have OpenMP, how can I compile?

Code: Select all

...
__DARWIN_ALIAS(setkey)
...

qfind needs OpenMP for multithreaded searching, which is really an essential part of qfind. I'm assuming based on the presence of "DARWIN" in your error messages that you're on a Mac. In that case you will need to install Homebrew, which you can then use to install OpenMP. I have no experience with Macs, but I know other people have successfully compiled qfind in this way. If you try this, please let me know if you have any further trouble. I want to learn the potential pitfalls of compiling on a Mac. If it works without trouble, please like this post to let me know.

[LaundryPizza03]

I don't have OpenMP, how can I compile?

Code: Select all

...
__DARWIN_ALIAS(setkey)
...

qfind needs OpenMP for multithreaded searching, which is really an essential part of qfind. I'm assuming based on the presence of "DARWIN" in your error messages that you're on a Mac. In that case you will need to install Homebrew, which you can then use to install OpenMP. I have no experience with Macs, but I know other people have successfully compiled qfind in this way. If you try this, please let me know if you have any further trouble. I want to learn the potential pitfalls of compiling on a Mac. If it works without trouble, please like this post to let me know.

What is the name of the OpenMP brew formula?

[Sokwe]

What is the name of the OpenMP brew formula?

Unfortunately, I'm not familiar with Homebrew or MacOS, so I won't be much help. I assume there are guides somewhere on the internet. For example, I got this stackexchange post that seems relevant, but I can't test it. If you figure out what works (or even just what doesn't work), I would appreciate it if you could share the details here.

[LaundryPizza03]

What is the name of the OpenMP brew formula?

Unfortunately, I'm not familiar with Homebrew or MacOS, so I won't be much help. I assume there are guides somewhere on the internet. For example, I got this stackexchange post that seems relevant, but I can't test it. If you figure out what works (or even just what doesn't work), I would appreciate it if you could share the details here.

I followed the directions, but it can't find "omp.h". After installing with Brew, it requires an extra "-Xpreprocessor" flag.

Code: Select all

% gcc -std=c11 -Xpreprocessor -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c
In file included from qfind.c:97:
./common.h:15:13: fatal error: 'omp.h' file not found
   15 |    #include <omp.h>
      |             ^~~~~~~
1 error generated.

[Sokwe]

I followed the directions, but it can't find "omp.h". After installing with Brew, it requires an extra "-Xpreprocessor" flag.

Try instead to install gcc with Homebrew using the command `brew install gcc`. Then use the compiler with the version number attached (either gcc-15 of if that doesn't work, gcc-14), so your compilation command would look like this:

Code: Select all

gcc-15 -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c 

Apparently, macOS uses gcc as an alias for their own version of clang that doesn't include OpenMP. By installing gcc with Homebrew and using gcc-15 (or gcc-14?) instead of gcc, you will presumably avoid this issue. Please let me know if this works.

[hkoenig]

About seven years ago I hacked up apgnano to get it to compile under XCode and run on macOS. (Here's a posting from 14 months ago viewtopic.php?f=7&t=6809&p=200769&hilit ... aa#p200769, but it seems I didn't include the project.) Attached this time is a zip file of the project. I replaced OpenMP with GCD, which Apple still seems to support although they don't encourage new development with it. The app worked, but I was never able to use this to submit any hauls as I don't and won't have a Google account.

This is presented as is, and I make no guarantees that it still works. I did verify that the latest version of XCode will open the project file. To get a build, you will probably have to change the update the target settings.

apgnanoMac.zip

(168.52 KiB) Downloaded 57 times

In any case, this may give someone an idea of what they would need to do. Look for "#ifdef USE_OPEN_MP" and "#ifdef MACOSX" in main.cpp.

[LaundryPizza03]

I followed the directions, but it can't find "omp.h". After installing with Brew, it requires an extra "-Xpreprocessor" flag.

Try instead to install gcc with Homebrew using the command `brew install gcc`. Then use the compiler with the version number attached (either gcc-15 of if that doesn't work, gcc-14), so your compilation command would look like this:

Code: Select all

gcc-15 -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c 

Apparently, macOS uses gcc as an alias for their own version of clang that doesn't include OpenMP. By installing gcc with Homebrew and using gcc-15 (or gcc-14?) instead of gcc, you will presumably avoid this issue. Please let me know if this works.

New error:

Code: Select all

% gcc-15 -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c
In file included from qfind.c:97:
common.h:1590:6: error: conflicting types for 'setkey'; have 'void(int,  int)'
 1590 | void setkey(int h, int v) {
      |      ^~~~~~
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/stdlib.h:58,
                 from common.h:8:
/Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/_stdlib.h:255:10: note: previous declaration of 'setkey' with type 'void(const char *)'
  255 | void     setkey(const char *) __DARWIN_ALIAS(setkey);
      |          ^~~~~~
      

[Sokwe]

New error:

Code: Select all

% gcc-15 -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c
In file included from qfind.c:97:
common.h:1590:6: error: conflicting types for 'setkey'; have 'void(int,  int)'
 1590 | void setkey(int h, int v) {
      |      ^~~~~~
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/stdlib.h:58,
                 from common.h:8:
/Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/_stdlib.h:255:10: note: previous declaration of 'setkey' with type 'void(const char *)'
  255 | void     setkey(const char *) __DARWIN_ALIAS(setkey);
      |          ^~~~~~
      

Thanks for your valuable feedback. It appears that setkey is a stdlib function that qfind is attempting to redefine. I've updated the repository to change the name of this function. Please get the latest version and try compiling again.

[LaundryPizza03]

New error:

Code: Select all

% gcc-15 -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c
In file included from qfind.c:97:
common.h:1590:6: error: conflicting types for 'setkey'; have 'void(int,  int)'
 1590 | void setkey(int h, int v) {
      |      ^~~~~~
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/stdlib.h:58,
                 from common.h:8:
/Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/_stdlib.h:255:10: note: previous declaration of 'setkey' with type 'void(const char *)'
  255 | void     setkey(const char *) __DARWIN_ALIAS(setkey);
      |          ^~~~~~
      

Thanks for your valuable feedback. It appears that setkey is a stdlib function that qfind is attempting to redefine. I've updated the repository to change the name of this function. Please get the latest version and try compiling again.

This works now.

[Sylvani]

Modification to qfind's common.h that allows support for MAP rules (although they may be rotated/flipped somehow, IDK how to fix that without a separate script).

[LaundryPizza03]

Modification to qfind's common.h that allows support for MAP rules (although they may be rotated/flipped somehow, IDK how to fix that without a separate script).

Spaceships and partials are always returned oriented north, so you just need to check that the output orientation is correct.

[ThePlayzr]

Very strange max partial result glitch when I put in a speed that is above the speed limit for this rule (not that the speed limit for this rule is actually between c/3 and 2c/5:

[Sokwe]

Very strange max partial result glitch when I put in a speed that is above the speed limit for this rule.

This bug was fixed a while ago. The fact that the output says "21 September 2024" indicates that you're using an outdated version. You should upgrade either by compiling from source or using the latest pre-compiled Windows binary.

Also, it would be helpful in the future if you could simply copy-paste your input and output into a code box, rather than using a screenshot.

[Hippo.69]

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.

I am just reading the thread from the beginning, I do not know how it evolved ... so this could be already done ...

I would consider standardizing the ship output ... check all configurations in the period and choose the minimal one (the sorting does not matter much, even comparing rle's would be fine ... I would prefere equivalent to y flipped rle's so that tagalongs of the same ship would have the same start ... of course pushalongs start differently). If you are sure the ship would be discovered in all phases, you can filter output out if it is not the minimal version...

Actually when a decision to output only minimal versions of the ships would be made, you probably can early filter ship prefixes which are not minimal.

I have not experimented with ship searches ... I expect the branching factor is very high ... in that case iterative deepening could be the choice how to solve memory issues with a cost of a bit slower search.