qfind - a spaceship search program

For scripts to aid with computation or simulation in cellular automata.
User avatar
Drelectron8
Posts: 92
Joined: March 5th, 2023, 4:54 am
Location: Queenstown, Singapore

Re: qfind - a spaceship search program

Post by Drelectron8 » June 15th, 2024, 10:34 am

Sokwe wrote:
May 19th, 2024, 2:28 am
Drelectron8 wrote:
May 19th, 2024, 2:21 am
Oh, my goodness, thanks so much for helping me bro!
Does qfind appear to be working properly now? With the example input given above, the output should look like this:

Code: Select all

qfind v2.3 by Matthias Merzenich, 19 March 2023
Input: qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 1


Rule: B3/S23
Period: 10
Offset: 1
Width:  5
Symmetry: even
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Lookahead caching disabled
Number of threads: 2
Starting search
Queue full, depth 9, deepening 3, 131k/165k -> 70k/96k
Queue full, depth 9, deepening 6, 131k/174k -> 59k/82k
Queue full, depth 10, deepening 8, 131k/185k -> 46k/85k
Queue full, depth 13, deepening 8, 131k/391k -> 46k/177k
Queue full, depth 15, deepening 9, 131k/365k -> 47k/191k
Queue full, depth 16, deepening 11, 131k/360k -> 39k/171k
Queue full, depth 18, deepening 12, 131k/342k -> 41k/180k
Queue full, depth 19, deepening 14, 131k/358k -> 35k/165k
...
Remember that it can be very useful to send the output to a file. To do this, add " > filename.txt" to the end of your input line, where "filename" is the name of the desired output file. For example, by giving the following input:

Code: Select all

qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2 > output.txt
a file called "output.txt" containing the program output will be created in the same folder as qfind.exe.

Run "qfind --help" to see a full list of options.
Does the search also work for strobing rules? It doesn't seem like it can, am I missing something?

Code: Select all

x = 4, y = 4, rule = B01356/S012345
ob2o$2obo2$obo!
#C [[ THEME Book AUTOFIT LAYERS 5 DEPTH 0.50 ]]
OCA:Wickstretcher And The Parasites← Check this cool rule out!

Wickstretcher And The Parasites forums. ← Check the forums as well!

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

Re: qfind - a spaceship search program

Post by Sokwe » June 15th, 2024, 6:28 pm

Drelectron8 wrote:
June 15th, 2024, 10:34 am
Does the search also work for strobing rules? It doesn't seem like it can, am I missing something?
Unfortunately, qfind does not support strobing rules. qfind uses a lookup table to extend partial results, and the change in edge conditions in strobing rules would require a substantial rework of the lookup table construction, so I don't plan to add support any time soon.
-Matthias Merzenich

User avatar
Drelectron8
Posts: 92
Joined: March 5th, 2023, 4:54 am
Location: Queenstown, Singapore

Re: qfind - a spaceship search program

Post by Drelectron8 » June 15th, 2024, 7:40 pm

Sokwe wrote:
June 15th, 2024, 6:28 pm
Drelectron8 wrote:
June 15th, 2024, 10:34 am
Does the search also work for strobing rules? It doesn't seem like it can, am I missing something?
Unfortunately, qfind does not support strobing rules. qfind uses a lookup table to extend partial results, and the change in edge conditions in strobing rules would require a substantial rework of the lookup table construction, so I don't plan to add support any time soon.
Are there any search programs that do support strobing rules you would like to recommend me?

Code: Select all

x = 4, y = 4, rule = B01356/S012345
ob2o$2obo2$obo!
#C [[ THEME Book AUTOFIT LAYERS 5 DEPTH 0.50 ]]
OCA:Wickstretcher And The Parasites← Check this cool rule out!

Wickstretcher And The Parasites forums. ← Check the forums as well!

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

Re: qfind - a spaceship search program

Post by Sokwe » June 15th, 2024, 9:37 pm

Drelectron8 wrote:
June 15th, 2024, 7:40 pm
Are there any search programs that do support strobing rules you would like to recommend me?
I'm not sure which programs support strobing rules. I know gfind supports Life-like strobing rules although it's a bit buggy. You could try rlifesrc, ikpx 2.2, LLSSS, and LLS to see if any of them do what you want.
-Matthias Merzenich

User avatar
Drelectron8
Posts: 92
Joined: March 5th, 2023, 4:54 am
Location: Queenstown, Singapore

Re: qfind - a spaceship search program

Post by Drelectron8 » June 17th, 2024, 7:47 am

Sokwe wrote:
June 15th, 2024, 9:37 pm
Drelectron8 wrote:
June 15th, 2024, 7:40 pm
Are there any search programs that do support strobing rules you would like to recommend me?
I'm not sure which programs support strobing rules. I know gfind supports Life-like strobing rules although it's a bit buggy. You could try rlifesrc, ikpx 2.2, LLSSS, and LLS to see if any of them do what you want.
Okay, so I've been using rlifesrc for a while now, and I noticed, does this program search for just oscillators or spaceships and oscillators? Because it looks like there isn't a single spaceship that I found yet from this search program, it just keeps on giving oscillators.

Code: Select all

x = 4, y = 4, rule = B01356/S012345
ob2o$2obo2$obo!
#C [[ THEME Book AUTOFIT LAYERS 5 DEPTH 0.50 ]]
OCA:Wickstretcher And The Parasites← Check this cool rule out!

Wickstretcher And The Parasites forums. ← Check the forums as well!

User avatar
confocaloid
Posts: 3524
Joined: February 8th, 2022, 3:15 pm

Re: qfind - a spaceship search program

Post by confocaloid » June 17th, 2024, 8:25 am

Drelectron8 wrote:
June 17th, 2024, 7:47 am
[...]
Okay, so I've been using rlifesrc for a while now, and I noticed, does this program search for just oscillators or spaceships and oscillators? Because it looks like there isn't a single spaceship that I found yet from this search program, it just keeps on giving oscillators.
I can find the turtle in B3/S23, by going to Settings and setting width 13, height 12, period 3, dx 1, dy 0, then clicking "Apply settings" and "Start".

This is probably offtopic in this thread. Is there an existing forum thread for rlifesrc-related questions/issues?

User avatar
Drelectron8
Posts: 92
Joined: March 5th, 2023, 4:54 am
Location: Queenstown, Singapore

Re: qfind - a spaceship search program

Post by Drelectron8 » June 17th, 2024, 9:11 am

confocaloid wrote:
June 17th, 2024, 8:25 am
Drelectron8 wrote:
June 17th, 2024, 7:47 am
[...]
Okay, so I've been using rlifesrc for a while now, and I noticed, does this program search for just oscillators or spaceships and oscillators? Because it looks like there isn't a single spaceship that I found yet from this search program, it just keeps on giving oscillators.
I can find the turtle in B3/S23, by going to Settings and setting width 13, height 12, period 3, dx 1, dy 0, then clicking "Apply settings" and "Start".

This is probably offtopic in this thread. Is there an existing forum thread for rlifesrc-related questions/issues?
It works! Thanks so much for helping me!

Code: Select all

x = 4, y = 4, rule = B01356/S012345
ob2o$2obo2$obo!
#C [[ THEME Book AUTOFIT LAYERS 5 DEPTH 0.50 ]]
OCA:Wickstretcher And The Parasites← Check this cool rule out!

Wickstretcher And The Parasites forums. ← Check the forums as well!

User avatar
DroneBetter
Posts: 109
Joined: December 1st, 2021, 5:16 am
Location: The UK (a delightful place)
Contact:

Re: qfind - a spaceship search program

Post by DroneBetter » June 21st, 2024, 2:34 pm

With the search

Code: Select all

./qfind -k -r B36/S245 -p 8 -y 2 -q 19 -t 8 -s o -w 5 -m 6144
qfind returns (many duplicates of) two spaceships, xq8_wh8r8hz08pl0lp8zx727zx9l9z08ld5dl8z02ve0ev2z2mtxtm2z047efe74 and xq8_04qh4hq4zgeqxqegz0mmd0dmmz014bsb41z0odvkvdozw1k8k1z0suorouszxg4gzw3btb3zce01010ecz27cxc72z1pusgsup1z3deb3bed3z23d555d32zwor1roz0oatbtaoz654x456zcrrc0crrcz42k8g8k24zx8i8z0gej2jegzwoo9ooz046pfp64zcettltteczxk3kz08cn1nc8zw6aca6zw20302, but the second is actually xq8_37n303n73z34s4g4s43zxorozwt9m9tzwc9e9czw7t5t7z266565662zxlhlz02qf6fq2zwi535izx333 (which it doesn't find) behind a p4 spaceship with which it never interacts. Is qfind to be considered nonexhaustive for period-multiplied searches?
That concludes my post (I hope you liked it)

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

Re: qfind - a spaceship search program

Post by Sokwe » June 21st, 2024, 3:02 pm

DroneBetter wrote:
June 21st, 2024, 2:34 pm
Is qfind to be considered nonexhaustive for period-multiplied searches?
Unfortunately ordinary qfind can be buggy when gcd(period,displacement) > 1, unless you turn off duplicate elimination with "-h 0" (see this post for details). A period-multiplied search can only be considered exhaustive if there are no ships (even at periods dividing the full period) and "-h 0" is used.

Even when gcd(period,displacement) = 1, qfind is not exhaustive (i.e., it doesn't necessarily find all ships) unless there are no ships. This is because duplicate elimination can discard pushalongs. So a qfind search can only be considered exhaustive when there are no ships to find.

I wrote a version of qfind that, when used properly, is exhaustive (available here), but it can really only be used when there are a very small number of spaceships to find (otherwise it will generate an unfathomably large number of small files). For each duplicate partial result it eliminates, it saves that partial to a file. Once the search is complete, it can be run with an alternate parameter to process all the files and construct a "basis" of spaceships, a set of spaceships such that every possible set of rows contained in a spaceship of that width is represented in a spaceship from the set. Unfortunately, this set will have tons of duplicates, including many, many spaceships following other spaceships.
-Matthias Merzenich

Post Reply