genfind: Search for spaceships in multi-state rules

For scripts to aid with computation or simulation in cellular automata.
Post Reply
Rocknlol
Posts: 125
Joined: April 15th, 2012, 9:06 am

genfind: Search for spaceships in multi-state rules

Post by Rocknlol » December 15th, 2020, 4:12 am

I've been sitting on this for a while but the code isn't getting any more readable so I'm releasing this now with some minor clean-ups.

genfind is a gfind derivative able to search for (currently only orthogonal) ships in multi-state rules in range-1 Moore (it can do about up to six states). It's admittedly a fair bit slower than other gfind-likes, but makes up for it in the breadth of rules it can search for.

You can download the latest version of genfind here.

genfind has both compile-time and run-time parameters. Compile-time parameters include tree and table sizes, width, and the rule, all of which you can modify in rule.cpp. If you have a POSIX OS or a compatibility layer like WSL, you can then compile it with "make". Run-time parameters include period, displacement, and symmetry. Pass those in as follows:

Code: Select all

./genfind <displacement> <period> <symmetry>
For symmetry, "0" is asymmetric, "1" is odd-width bilaterally symmetric, and "2" is even-width bilaterally symmetric. For example, the following search with the rule set to Life and the width set to at least 6 would find the Turtle:

Code: Select all

./genfind 1 3 2
Do note that for asymmetric searches the width in rule.cpp will be one higher than the actual width of the search.

Here is a showcase of some of the rules genfind can find spaceships for:

Code: Select all

x = 94, y = 22, rule = Symbiosis
2.2A13.2A40.B.B.B.B.B$59.B.B.B.B.B$2.A5.2B.2B5.A40.B7.B$3.2A11.2A13.A
2.2A5.2A2.A16.B.B$4.A4.B.B4.A15.3A7.3A15.B.B.B.B$.A5.B.3B.B5.A13.A2.
2B.2B2.A15.B2.B.B2.B$.A3.A.B5.B.A3.A40.B.B.B.B$3.A.A.B5.B.A.A17.B5.B
15.B4.B.B4.B$2A.A.A2.B3.B2.A.A.2A15.B3.B15.B.B.B.B.B.B.B.B14.2A.2A$4.
2A3.3B3.2A20.3B17.3B.2B.2B.3B14.A5.A$A3.A11.A3.A40.B3.B20.A.A$A.A.A.A
7.A.A.A.A14.A5.A39.2A3.A.A3.2A$.2A.A.A.A.A.A.A.A.2A13.A2.A3.A2.A13.A.
2A.A.A.2A.A11.2A2.A3.A2.2A$.2A.A.A7.A.A.2A11.2A3.A3.A3.2A10.A5.A.A5.A
10.4A5.4A$4.A.A.2A.2A.A.A19.A3.A16.2A3.A.A3.2A$3.2A.A.A3.A.A.2A13.A4.
A3.A4.A12.A3.A.A3.A13.2A.A.A.A.2A$5.2A7.2A19.2A3.2A18.2A3.2A16.3A.A.
3A$6.A7.A18.A.A5.A.A$5.2A7.2A16.3A7.3A17.3A21.A.A$6.2A.A.A.2A18.A2.A
3.A2.A17.A3.A16.B.B5.B.B$7.3A.3A20.3A3.3A19.A.A18.B2.3A2.B$8.A3.A22.A
5.A21.A19.B7.B!

Code: Select all

x = 52, y = 17, rule = inbredLife
2.A7.A$2.A7.A$.A9.A$2.A7.A$3.A.A.A.A$4.2A.2A14.A.A3.A.A$3.A.A.A.A13.
2A.A.A.2A$2.2A.A.A.2A12.2A.A.A.2A$3.A.A.A.A17.A$4.AB.BA17.A.A$4.A3.A$
5.3A16.2A.A.2A$A.A7.A.A11.A5.A14.4A$3.A5.A$3.A5.A15.A3.A12.A.A4.A.A$A
2.A5.A2.A13.3A14.A6.A$.3A5.3A14.3A14.B6.B!

Code: Select all

x = 12, y = 18, rule = Brew
2.C6.C$C.C6.C.C$.C8.C$.C8.C$5.2B$.2B6C2B$.2A6C2A$.B8AB$2.CB4CBC$2.A6B
A$2.A6BA$2.CBA2CABC$2.2AB2AB2A$.C.2A2C2A.C$BACA4BACAB$.2A6B2A$.2A.A2B
A.2A$5.2A!

Code: Select all

x = 138, y = 16, rule = Custom-Rule-1
128.2B5.2B$128.2A5.2A$129.2A3.2A$72.B3.B52.2A3.2A$72.2A.2A$72.2A.2A
52.2B3.2B$18.2A17.2A32.A2B.2BA49.B3A3.3AB$19.B17.B33.3A.3A18.BA.ABA3.
ABA.AB16.2A2.B.B2.2A$19.AB15.BA31.2A2.A.A2.2A17.2A.A2B.2BA.2A18.B.2A.
2A.B$19.3AB.B7.B.B3A32.B2AB.B2AB18.2AB3A.3AB2A20.5A$24.A7.A18.B.B16.
3AB.B3A22.BA.AB25.ABA$22.3AB5.B3A15.2A44.B3.AB3.BA3.B21.A$23.B2A.A.A.
2AB15.3A43.A2.A2.BA.AB2.A2.A$.AB20.2AB.3B.B2A15.2ABAB18.2A.2A19.2A4BA
.A4B2A20.3A$AB22.A.2AB2A.A17.3A19.A3BA19.2A.ABA3.ABA.2A20.3A$3A25.A
22.A21.3A24.A5.A25.A!
These two patterns were found with versions of genfind that I'm hoping to later incorporate into the public branch: A 2c/25 ship in Rule 2166637080 and a 2c/5 ship in NaiveLife:
wargo.png
wargo.png (17.55 KiB) Viewed 1774 times

Code: Select all

x = 23, y = 73, rule = NaiveLifeEmulated
23E$E21.E$E.B19.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E
21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.
E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E8.A.A.
2A7.E$E7.2A.A.A8.E$E10.A.A.A6.E$E9.2A.A.2A5.E$E8.A12.E$E7.A.A.4A6.E$E
6.2A.A.A.2A6.E$E9.A.A.A7.E$E6.2A.A3.A2.A4.E$E7.A.A2.5A4.E$E6.2A.3A9.E
$E5.A.A.A2.4A5.E$E5.A.A.A.A.A7.E$E4.2A.A3.A9.E$E7.2A.A.2A7.E$E4.2A.2A
.A2.A7.E$E4.A.2A2.A.2A7.E$E9.2A.A.2A5.E$E10.A.A8.E$E9.2A.A8.E$E10.A.
2A7.E$E10.A10.E$E9.2A.2A7.E$E21.E$E21.E$E10.2A.2A6.E$E14.2A5.E$E9.A4.
2A5.E$E8.3A10.E$E6.A5.5A4.E$E5.A.5A9.E$E5.A15.E$E21.E$E9.A.2A8.E$E8.A
3.2A7.E$E21.E$E21.E$E21.E$E21.E$23E!
Now, please do keep in mind that the code in its current state is a big mess, and that it might be healthier to think of it as a prototype or a proof-of-concept rather than as a full-fledged search program. That being said, I'm hoping everyone can find some cool stuff with this!

Post Reply