Comprehensively analyzing a pattern across rules

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
LaundryPizza03
Posts: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Comprehensively analyzing a pattern across rules

Post by LaundryPizza03 » March 27th, 2020, 7:42 am

Motivated by a project to revive David Eppstein's glider database, I decided to commision two spinoff projects: one for oscillators, and the other for NT ships.

The latter led me to an intriguing question: How do I enumerate every single object tht evolves from a particular pattern without rummaging through all 2^102 rules? The answer is to handle the evolutionary pathways like a tree where every branch point represents a change in a transition (Fig. 1), and each node represents an entire rulespace. This eliminates a lot of redundancy for small patterns in the early phases.

Code: Select all

#C Fig. 1: Partial evolutionary tree for obo$bo!.
x = 41, y = 83, rule = B/S012345678
32b5o$31bo5bo$30bo7bo$30bo7bo$30bo3bo3bo$30bo7bo$30bo3bo3bo$30bo7bo$
31bo5bo$30bob5o$29bo$28bo$27bo$26bo$25bo$18b5obo7b5o$17bo5bo7bo5bo$16b
o7bo5bo7bo$16bo3bo3bo5bo7bo$16bo2b3o2bo5bo7bo$16bo2bobo2b7o2bobo2bo$
16bo7bo5bo3bo3bo$16bo7bo5bo7bo$17bo5bo7bo5bo$16bob5o9b5o$15bo$14bo$13b
o$12bo$11bo$4b5obo7b5o9b5o$3bo5bo7bo5bo7bo5bo$2bo7bo5bo7bo5bo7bo$2bo7b
o5bo7bo5bo2bobo2bo$2bo2bobo2bo5bo2b3o2bo5bo3bo3bo$2bo3bo3b7o3bo3b7o7bo
$2bo7bo5bo7bo5bo7bo$2bo7bo5bo7bo5bo7bo$3bo5bo7bo5bo7bo5bo$4b5obo7b5o9b
5o$11bo$12bo$13bo$14bo$15bo$16bob5o9b5o$17bo5bo7bo5bo$16bo7bo5bo7bo$
16bo3bo3bo5bo7bo$16bo2b3o2b7o7bo$16bo2b3o2bo5bo2bobo2bo$16bo7bo5bo3bo
3bo$16bo7bo5bo7bo$17bo5bo7bo5bo$18b5obo7b5o$25bo$26bo$27bo$28bo$29bo$
30bob5o$31bo5bo$30bo7bo$30bo7bo$30bo2b3o2bo$30bo2b3o2bo$30bo3bo3bo$30b
o7bo$31bo5bo$32b5o3$38bo$39bo$41o$39bo$10b5o23bo$12bo3bo$12bo5b4o3b3o$
12bo3bobobobobo3bo$12bo3bobobobob4o$12bo3bobobobobo$12bo3bobobobo2b4o!
At each node of this tree, we determine which transitions affect the subsequent evolution of the pattern and methodically select one of the branches, essentially scanning the tree in a depth-first manner. We stop when the pattern vanishes or becomes periodic, or when the scanner reaches a depth limit to ignore explosions.

An example application is when enumerating every low-period ship of a particular shape. When I executed a procedure similar to the one just described, I determined that there are exactly 114 p2 ships with shape obo$bo!. They're listed here in the format of the glider DB.

Code: Select all

::B2a3e/S1c2c3e:B2-ce3-ai45678/S012-a3-i45678:2:0:1:3:2:obo$bo!
::B2e3i/S1c2ce:B2-ac3-e45-i678/S012-a34-i5678:2:0:-1:3:2:obo$bo!
::B2e3ei/S2ac:B2-ac3-a45678/S01e23-ei45678:2:0:-1:3:2:obo$bo!
::B2c3ae/S1c3e:B2-ae3-i45678/S012-ac3-i45678:2:0:1:3:2:obo$bo!
::B2ce3i/S1e2c:B2-a3-en4-t5678/S1e2-i345678:2:0:-1:3:2:obo$bo!
::B2ce3ei/S2ac:B2-a34-a5678/S023-e4-t5678:2:0:-1:3:2:obo$bo!
::B2ce3e/S1c2a:B2-a3-a45-i678/S012-c3-ij45-y678:2:0:-1:3:2:obo$bo!
::B2ce3ae/S1c2c6c:B2-a3-i45678/S0123-a4-a5-i678:2:0:1:3:2:obo$bo!
::B2ce3ei/S1c2c3a:B2-a3-a45678/S0123-i4-a5-i6-c78:2:0:-1:3:2:obo$bo!
::B02k4t/S2c:B02-ce3-ei4-a5-aj678/S1e2345-ai6-a7e:2:0:-1:3:2:obo$bo!
::B02k3i/S1c:B02akn3-e4-at5-ej6-e78/S12-c345-ai6-a7e:2:0:-1:3:2:obo$bo!
::B03e4n/S0:B02aik3-i4-at5-a678/S01e2-c345-ae6-a7e:2:0:1:3:2:obo$bo!
::B03e5r/S1c2i:B02-ce3-iq4-at5-j6-ei78/S01c2-c345-ai6-a7e:2:0:1:3:2:obo$bo!
::B03e5r/S1c2c3e:B02-ce34-qt5-j6-ei78/S012-a3-i45-ai6-a7e:2:0:1:3:2:obo$bo!
::B02e6i/S2ck:B02-ac3-ei4-n5-an6-k78/S01e2-i345-i6-ae7e:2:0:-1:3:2:obo$bo!
::B02e4t5i/S1c2c:B02-c3-e45-er6acn78/S012-a3-k4-i5-i6-ae7e:2:0:1:3:2:obo$bo!
::B02e6i/S1c2c3k:B02-c3-e4-t5-eir6-ek78/S012-a34-i5-i6-ae7e:2:0:-1:3:2:obo$bo!
::B02e3e6i/S2c3q:B02-c3-a4-nt5-an6-k78/S01e23-ei45-i6-ae7e:2:0:-1:3:2:obo$bo!
::B02c3eq4t/S2c:B02-e3-i4-a5-aj678/S02-i34-t5-a6-ac7e:2:0:-1:3:2:obo$bo!
::B02c3e6a/S1c3e:B02-e3-q4-at5-j6-e78/S012-ac345-ai6ekn7e:2:0:1:3:2:obo$bo!
::B02c3e6a/S1c2c4e:B02-e34-qt5-j6-e78/S0123-i45-ai6ekn7e:2:0:1:3:2:obo$bo!
::B02ce3y4a/S:B02-ik3-e4-n5-aen678/S01e2-c3-i45-i6ikn7e:2:0:1:3:2:obo$bo!
::B02ce4at/S2c:B023-en4-n5-an6-ik78/S01e2-ik3-i45-i6ikn7e:2:0:1:3:2:obo$bo!
::B02ce6i/S2ck:B023-en4-ant5-an6-k78/S01e2-i3-i45-i6ikn7e:2:0:-1:3:2:obo$bo!
::B02ce6i/S1c2c3k:B023-e45-nr6ain78/S0123-n4-i5-ei6ikn7e:2:0:-1:3:2:obo$bo!
::B02ce5n6c/S1c2c:B023-e45-r6acn78/S0123-kn4-i5-ei6ikn7e:2:0:1:3:2:obo$bo!
::B02ce3e6i/S2c3q:B0234-an5-an6-k78/S01e23-e4-t5-i6ikn7e:2:0:-1:3:2:obo$bo!
::B02ce3e6a/S1c5y:B02345-einr6-ek78/S012-c3-jq45-i6kn7e:2:0:1:3:2:obo$bo!
::B02ce3e5e/S1c3q:B02345-inr6cin78/S012-c3-j45-iy6kn7e:2:0:-1:3:2:obo$bo!
::B02ce3e6i/S1c2c4q:B02345-r6cin78/S01234-a5-i6kn7e:2:0:-1:3:2:obo$bo!
::B01e4y/S2c4t:B01e2-ce3-eky45-i6-a7e8/S0234-n5-a6-c:2:0:-1:3:2:obo$bo!
::B01e4y/S1c3i:B01e2-ce3-ey4-i5-i6-a7c/S012-ce345-ar6-c:2:0:-1:3:2:obo$bo!
::B01e5k/S1c2c4t:B01e2-ce3-e45-y6-a7c/S0123-ky45-ar6-c:2:0:-1:3:2:obo$bo!
::B01e3e/S2c3y5e:B01e2-ce34-j5-ei6-ac7e8/S01e2-i34-nt5-a6-c:2:0:1:3:2:obo$bo!
::B01e3e5e/S2c4t:B01e2-ce34-j5-i6-ac7e8/S01e2-i3-y4-n5-ae6-c:2:0:1:3:2:obo$bo!
::B01e3e5e/S1c3i:B01e2-ce34-t5-i6-a7/S012-c3-e4-i5-ar6-ci:2:0:-1:3:2:obo$bo!
::B01e3e/S1c4i6i:B01e2-ce34-t5-ei6-a7/S012-c3-ei45-ar6-c:2:0:1:3:2:obo$bo!
::B01e3e/S1c2c5y6i:B01e2-ce3456-ae7/S01234-jt5-ar6-c:2:0:1:3:2:obo$bo!
::B01e2e4c/S4n:B01e2-c3-e45-i6-c7e8/S01e2-c3-c45-e6-ce:2:0:1:3:2:obo$bo!
::B01e2e/S2c4y6i:B01e2-c3-e4-j5-ei6-c7e8/S01e23-e4-n5-e6-ce:2:0:-1:3:2:obo$bo!
::B01e2e5e/S2c4n:B01e2-c3-e4-j5-i6-c7e8/S01e23-e4-y5-e6akn:2:0:1:3:2:obo$bo!
::B01e2e6i/S1c5r:B01e2-c3-e45-y6-c/S012-c3-e4-y5-e6akn:2:0:1:3:2:obo$bo!
::B01e2e/S1c4y5e:B01e2-c3-e45-y6-ci/S012-c3-e45-r6akn:2:0:-1:3:2:obo$bo!
::B01e2e3e/S1c5e:B01e2-c3456-c7e/S012-c34-e56akn:2:0:-1:3:2:obo$bo!
::B01e2c4t/S2c5j:B01e2-e3-e4-ky5-i6-a7e8/S0234-nt5-ai6-c:2:0:1:3:2:obo$bo!
::B01e2c4y/S2c4t:B01e2-e3-e4-kt5-i6-a7e8/S0234-n5-aij6-c:2:0:-1:3:2:obo$bo!
::B01e2c4y/S1c3i:B01e2-e3-ey45-i6-a7/S012-c3-j45-ar6-ck:2:0:-1:3:2:obo$bo!
::B01e2c6c/S1c2c6k:B01e2-e3-e45-k6-a7/S0123-y4-kt5-ar6-c:2:0:1:3:2:obo$bo!
::B01e2c5k/S1c2c4t:B01e2-e3-e456-ac7/S0123-y4-k5-ar6-ck:2:0:-1:3:2:obo$bo!
::B01e2c3e5e/S1c3i:B01e2-e34-t5-i6-a7/S012-c34-r5-air6-c:2:0:-1:3:2:obo$bo!
::B01e2ce5e/S5j:B01e23-e4-j56-c7e8/S01e2-c3-c45-ei6-ce:2:0:1:3:2:obo$bo!
::B01e2ce6i/S2c5j:B01e23-e45-y6-c7e8/S01e23-e4-y5-ei6akn:2:0:1:3:2:obo$bo!
::B01e2ce/S2c4y6i:B01e23-e45-y6-ci7e8/S01e23-e45-eij6-ce:2:0:-1:3:2:obo$bo!
::B01e2ce7e/S1c6k:B01e23-e45-y6-c7e/S012-c34-jy5-e6akn:2:0:1:3:2:obo$bo!
::B01e2ce/S1c4y5e:B01e23-e45-y6-c/S012-c34-j56an:2:0:-1:3:2:obo$bo!
::B01e2ce3e/S1c5e:B01e23456-c7e/S012-c345-c6akn:2:0:-1:3:2:obo$bo!
::B01c4a/S:B01c2-ce3-aei45-i678/S01e2-c345-ai6-a:2:0:1:3:2:obo$bo!
::B01c4r5i/S1c:B01c2akn3-e4-c5-en6-c78/S012-c345-ai6-ae:2:0:-1:3:2:obo$bo!
::B01c2i5n/S1c:B01c2-ce3-e4-cr5-ei6-c78/S012-c345-ai6-ae:2:0:1:3:2:obo$bo!
::B01c5e/S1c6a:B01c2akn3-e4-cr5-in6-c78/S012-c345-ai6-e:2:0:2:3:2:obo$bo!
::B01c5e/S1c2c6a:B01c2-ce3-e45-cn6-c78/S0123-c4-c5-i6-e:2:0:2:3:2:obo$bo!
::B01c3e5j/S0:B01c2-ce3-y4-qt5-i678/S01e2-c345-ai6-a:2:0:1:3:2:obo$bo!
::B01c3e4t/S6a:B01c2-ce3-y4-q5-ij678/S1e2-c345-ai6:2:0:2:3:2:obo$bo!
::B01c3e5q6c/S2c:B01c2-ce34-ty5-ij678/S023-y45-ai6-ae:2:0:-1:3:2:obo$bo!
::B01c3e5j/S1e2c:B01c2-ce34-ty5-iq6-c78/S01e23-y45-ai6-ae:2:0:1:3:2:obo$bo!
::B01c3e4t/S2c6a:B01c2-ce34-y5-ijq6-c78/S023-y45-ai6-e:2:0:2:3:2:obo$bo!
::B01c3e6k/S1c2c3e:B01c2-ce3456aek78/S01234-y5-ei6-ae:2:0:1:3:2:obo$bo!
::B01c3e6i/S1c2c6a:B01c2-ce3456aei78/S0123-e4-y5-ei6-e:2:0:2:3:2:obo$bo!
::B01c2e7e/S3a:B01c2-c3-ein4-ai56-a78/S01e2-c345-ai6-a:2:0:-1:3:2:obo$bo!
::B01c2e8/S2c4r:B01c2-c3-ei4-an56-a78/S01e234-i5-ai6-a:2:0:-1:3:2:obo$bo!
::B01c2e8/S1c2c5c:B01c2-c3-e45-ein67e8/S01234-n5-i6ckn:2:0:-1:3:2:obo$bo!
::B01c2e5in/S1c2c:B01c2-c3-e45-e67e/S01234-n5-ci6ckn:2:0:1:3:2:obo$bo!
::B01c2e5e/S1c2c6a:B01c2-c3-e45-in67e/S01234-n5-ci6-ei:2:0:2:3:2:obo$bo!
::B01c2e3e7e/S4q:B01c2-c34-kt5-jy6-a78/S01e2-c345-ai6-a:2:0:-1:3:2:obo$bo!
::B01c2e3e8/S2c5q:B01c2-c34-t5-j6-a78/S01e23-i45-aiy6-a:2:0:-1:3:2:obo$bo!
::B01c2e3e6k/S1c4i:B01c2-c3456-i8/S012-c34-k5-iq6-ae:2:0:1:3:2:obo$bo!
::B01c2e3e8/S1c2c6n:B01c2-c3456-ik7e8/S012345-ij6-ae:2:0:-1:3:2:obo$bo!
::B01c2e3e6i/S1c2c6a:B01c2-c3456-k7e/S012345-ij6-en:2:0:2:3:2:obo$bo!
::B01c2c4r5i/S1c:B01c2-e3-e4-c56-c78/S012-c3-c45-ae6-ce:2:0:-1:3:2:obo$bo!
::B01c2c3e6a/S1e:B01c2-e3-y4-qy5-i678/S01e2-c34-t5-a6-c:2:0:1:3:2:obo$bo!
::B01c2c3e5q6c/S2c:B01c2-e345-ei6-a78/S01e2-i3-y4-t5-a6-ce:2:0:-1:3:2:obo$bo!
::B01c2c3e6a/S2ci:B01c2-e345-eiq6-c78/S01e23-y4-t5-a6-ce:2:0:1:3:2:obo$bo!
::B01c2c3e7c/S1c3e:B01c2-e345-eiq6-c78/S012-c34-y5-a6akn:2:0:1:3:2:obo$bo!
::B01c2c3e5iq/S1c:B01c2-e345-e6-c7e8/S012-c3-e4-y5-a6akn:2:0:-1:3:2:obo$bo!
::B01c2c3e7c/S1c2c4e:B01c2-e3456-cn78/S012345-e6akn:2:0:1:3:2:obo$bo!
::B01c2ce7e/S3a:B01c23-ey4-iy5-i6-a78/S01e2-c3-i45-a6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce3y5i/S:B01c23-e4-iy56-a7c8/S01e2-c3-ai45-a6-ac:2:0:1:3:2:obo$bo!
::B01c2ce8/S2c4r:B01c23-e4-t5-ei6-a78/S01e23-i4-i5-a6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce4t5i/S2c:B01c23-e45-e6-a7/S01e23-i4-ir5-a6-ac:2:0:1:3:2:obo$bo!
::B01c2ce7e/S1c4r:B01c23-e45-y6-ci7e8/S012-c34-y5-e6ikn:2:0:-1:3:2:obo$bo!
::B01c2ce5y6c/S1c:B01c23-e456-i8/S012-c34-ry5-e6ikn:2:0:1:3:2:obo$bo!
::B01c2ce8/S1c2c5c:B01c23-e456-c7e8/S012345-e6akn:2:0:-1:3:2:obo$bo!
::B01c2ce6c/S1c2c:B01c23-e4567e/S012345-ce6akn:2:0:1:3:2:obo$bo!
::B01c2ce3e7e/S4q:B01c2345-ky6-a78/S01e2-c3-y4-t5-a6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce3e8/S2c5q:B01c23456-ae78/S01e234-t5-ay6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce3e8/S1c2c6n:B01c234567e8/S0123456akn:2:0:-1:3:2:obo$bo!
::B015a/S5i:B012-ce3-ei4-a5-i678/S01e2-c345-a6-a:2:0:-1:3:2:obo$bo!
::B016a/S2c6c:B012-ce3-ey45-ij678/S01e23-i45-a6-a:2:0:-1:3:2:obo$bo!
::B013y/S2c5a:B012-ce3-e45-ij6-a78/S01e23-i456-ac:2:0:1:3:2:obo$bo!
::B016a/S1c5i:B012-ce3-e4-i5-e67c8/S012-c34-a56-a:2:0:-1:3:2:obo$bo!
::B015y/S1c2c6a:B012-ce3-e4568/S012345-ej6-c:2:0:1:3:2:obo$bo!
::B017c/S1c2c6c:B012-ce3-e45-y67c8/S012345-ej6-a:2:0:-1:3:2:obo$bo!
::B013e6e/S5i:B012-ce34-t5-n6-c78/S01e2-c3456-ae:2:0:-1:3:2:obo$bo!
::B013e7e/S2c6c:B012-ce3456-ck78/S01e23-y4-t56-ae:2:0:-1:3:2:obo$bo!
::B013e/S2c3y6e:B012-ce3456-ck7c8/S01e234-t56-ac:2:0:1:3:2:obo$bo!
::B013e7e/S1c5i:B012-ce3456-i7/S012-c34-i5-n6-a:2:0:-1:3:2:obo$bo!
::B012e5e/S2c5a:B012-c3-e45-i6-a78/S01e2345-i6-a:2:0:1:3:2:obo$bo!
::B012e3e/S2c5e6e:B012-c3456-c7e8/S01e23456-c:2:0:1:3:2:obo$bo!
::B012c6a/S2c6c:B012-e3-e4-t56-e78/S01e23-i45-i6-a:2:0:-1:3:2:obo$bo!
::B012c6a/S1c5i:B012-e3-e45-ei678/S012-c345-a6-a:2:0:-1:3:2:obo$bo!
::B012c7c/S1c2c6c:B012-e3-e456-c78/S012345-e6-e:2:0:-1:3:2:obo$bo!
::B012c3e/S3i7e:B012-e34-t56-ae78/S01e2-c345-i6-ac7e:2:0:1:3:2:obo$bo!
::B012c3e6e/S5i:B012-e34-t56-a78/S01e2-c3-i456-ac:2:0:-1:3:2:obo$bo!
::B012ce5e/S6a:B0123-e45-i6-a78/S01e2-c345-ai6:2:0:1:3:2:obo$bo!
One helpful tool would be to fix certain transitions and focus only on those rules. An important shortcut would be to skip certain rules (e.g. those with B1c) by default.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Comprehensively analyzing a pattern across rules

Post by Naszvadi » March 27th, 2020, 8:11 am

LaundryPizza03 wrote:
March 27th, 2020, 7:42 am
Motivated by a project to revive David Eppstein's glider database, I decided to commision two spinoff projects: one for oscillators, and the other for NT ships.

The latter led me to an intriguing question: How do I enumerate every single object tht evolves from a particular pattern without rummaging through all 2^102 rules? The answer is to handle the evolutionary pathways like a tree where every branch point represents a change in a transition (Fig. 1), and each node represents an entire rulespace. This eliminates a lot of redundancy for small patterns in the early phases.

Code: Select all

#C Fig. 1: Partial evolutionary tree for obo$bo!.
x = 41, y = 83, rule = B/S012345678
32b5o$31bo5bo$30bo7bo$30bo7bo$30bo3bo3bo$30bo7bo$30bo3bo3bo$30bo7bo$
31bo5bo$30bob5o$29bo$28bo$27bo$26bo$25bo$18b5obo7b5o$17bo5bo7bo5bo$16b
o7bo5bo7bo$16bo3bo3bo5bo7bo$16bo2b3o2bo5bo7bo$16bo2bobo2b7o2bobo2bo$
16bo7bo5bo3bo3bo$16bo7bo5bo7bo$17bo5bo7bo5bo$16bob5o9b5o$15bo$14bo$13b
o$12bo$11bo$4b5obo7b5o9b5o$3bo5bo7bo5bo7bo5bo$2bo7bo5bo7bo5bo7bo$2bo7b
o5bo7bo5bo2bobo2bo$2bo2bobo2bo5bo2b3o2bo5bo3bo3bo$2bo3bo3b7o3bo3b7o7bo
$2bo7bo5bo7bo5bo7bo$2bo7bo5bo7bo5bo7bo$3bo5bo7bo5bo7bo5bo$4b5obo7b5o9b
5o$11bo$12bo$13bo$14bo$15bo$16bob5o9b5o$17bo5bo7bo5bo$16bo7bo5bo7bo$
16bo3bo3bo5bo7bo$16bo2b3o2b7o7bo$16bo2b3o2bo5bo2bobo2bo$16bo7bo5bo3bo
3bo$16bo7bo5bo7bo$17bo5bo7bo5bo$18b5obo7b5o$25bo$26bo$27bo$28bo$29bo$
30bob5o$31bo5bo$30bo7bo$30bo7bo$30bo2b3o2bo$30bo2b3o2bo$30bo3bo3bo$30b
o7bo$31bo5bo$32b5o3$38bo$39bo$41o$39bo$10b5o23bo$12bo3bo$12bo5b4o3b3o$
12bo3bobobobobo3bo$12bo3bobobobob4o$12bo3bobobobobo$12bo3bobobobo2b4o!
At each node of this tree, we determine which transitions affect the subsequent evolution of the pattern and methodically select one of the branches, essentially scanning the tree in a depth-first manner. We stop when the pattern vanishes or becomes periodic, or when the scanner reaches a depth limit to ignore explosions.

An example application is when enumerating every low-period ship of a particular shape. When I executed a procedure similar to the one just described, I determined that there are exactly 114 p2 ships with shape obo$bo!. They're listed here in the format of the glider DB.

Code: Select all

::B2a3e/S1c2c3e:B2-ce3-ai45678/S012-a3-i45678:2:0:1:3:2:obo$bo!
::B2e3i/S1c2ce:B2-ac3-e45-i678/S012-a34-i5678:2:0:-1:3:2:obo$bo!
::B2e3ei/S2ac:B2-ac3-a45678/S01e23-ei45678:2:0:-1:3:2:obo$bo!
::B2c3ae/S1c3e:B2-ae3-i45678/S012-ac3-i45678:2:0:1:3:2:obo$bo!
::B2ce3i/S1e2c:B2-a3-en4-t5678/S1e2-i345678:2:0:-1:3:2:obo$bo!
::B2ce3ei/S2ac:B2-a34-a5678/S023-e4-t5678:2:0:-1:3:2:obo$bo!
::B2ce3e/S1c2a:B2-a3-a45-i678/S012-c3-ij45-y678:2:0:-1:3:2:obo$bo!
::B2ce3ae/S1c2c6c:B2-a3-i45678/S0123-a4-a5-i678:2:0:1:3:2:obo$bo!
::B2ce3ei/S1c2c3a:B2-a3-a45678/S0123-i4-a5-i6-c78:2:0:-1:3:2:obo$bo!
::B02k4t/S2c:B02-ce3-ei4-a5-aj678/S1e2345-ai6-a7e:2:0:-1:3:2:obo$bo!
::B02k3i/S1c:B02akn3-e4-at5-ej6-e78/S12-c345-ai6-a7e:2:0:-1:3:2:obo$bo!
::B03e4n/S0:B02aik3-i4-at5-a678/S01e2-c345-ae6-a7e:2:0:1:3:2:obo$bo!
::B03e5r/S1c2i:B02-ce3-iq4-at5-j6-ei78/S01c2-c345-ai6-a7e:2:0:1:3:2:obo$bo!
::B03e5r/S1c2c3e:B02-ce34-qt5-j6-ei78/S012-a3-i45-ai6-a7e:2:0:1:3:2:obo$bo!
::B02e6i/S2ck:B02-ac3-ei4-n5-an6-k78/S01e2-i345-i6-ae7e:2:0:-1:3:2:obo$bo!
::B02e4t5i/S1c2c:B02-c3-e45-er6acn78/S012-a3-k4-i5-i6-ae7e:2:0:1:3:2:obo$bo!
::B02e6i/S1c2c3k:B02-c3-e4-t5-eir6-ek78/S012-a34-i5-i6-ae7e:2:0:-1:3:2:obo$bo!
::B02e3e6i/S2c3q:B02-c3-a4-nt5-an6-k78/S01e23-ei45-i6-ae7e:2:0:-1:3:2:obo$bo!
::B02c3eq4t/S2c:B02-e3-i4-a5-aj678/S02-i34-t5-a6-ac7e:2:0:-1:3:2:obo$bo!
::B02c3e6a/S1c3e:B02-e3-q4-at5-j6-e78/S012-ac345-ai6ekn7e:2:0:1:3:2:obo$bo!
::B02c3e6a/S1c2c4e:B02-e34-qt5-j6-e78/S0123-i45-ai6ekn7e:2:0:1:3:2:obo$bo!
::B02ce3y4a/S:B02-ik3-e4-n5-aen678/S01e2-c3-i45-i6ikn7e:2:0:1:3:2:obo$bo!
::B02ce4at/S2c:B023-en4-n5-an6-ik78/S01e2-ik3-i45-i6ikn7e:2:0:1:3:2:obo$bo!
::B02ce6i/S2ck:B023-en4-ant5-an6-k78/S01e2-i3-i45-i6ikn7e:2:0:-1:3:2:obo$bo!
::B02ce6i/S1c2c3k:B023-e45-nr6ain78/S0123-n4-i5-ei6ikn7e:2:0:-1:3:2:obo$bo!
::B02ce5n6c/S1c2c:B023-e45-r6acn78/S0123-kn4-i5-ei6ikn7e:2:0:1:3:2:obo$bo!
::B02ce3e6i/S2c3q:B0234-an5-an6-k78/S01e23-e4-t5-i6ikn7e:2:0:-1:3:2:obo$bo!
::B02ce3e6a/S1c5y:B02345-einr6-ek78/S012-c3-jq45-i6kn7e:2:0:1:3:2:obo$bo!
::B02ce3e5e/S1c3q:B02345-inr6cin78/S012-c3-j45-iy6kn7e:2:0:-1:3:2:obo$bo!
::B02ce3e6i/S1c2c4q:B02345-r6cin78/S01234-a5-i6kn7e:2:0:-1:3:2:obo$bo!
::B01e4y/S2c4t:B01e2-ce3-eky45-i6-a7e8/S0234-n5-a6-c:2:0:-1:3:2:obo$bo!
::B01e4y/S1c3i:B01e2-ce3-ey4-i5-i6-a7c/S012-ce345-ar6-c:2:0:-1:3:2:obo$bo!
::B01e5k/S1c2c4t:B01e2-ce3-e45-y6-a7c/S0123-ky45-ar6-c:2:0:-1:3:2:obo$bo!
::B01e3e/S2c3y5e:B01e2-ce34-j5-ei6-ac7e8/S01e2-i34-nt5-a6-c:2:0:1:3:2:obo$bo!
::B01e3e5e/S2c4t:B01e2-ce34-j5-i6-ac7e8/S01e2-i3-y4-n5-ae6-c:2:0:1:3:2:obo$bo!
::B01e3e5e/S1c3i:B01e2-ce34-t5-i6-a7/S012-c3-e4-i5-ar6-ci:2:0:-1:3:2:obo$bo!
::B01e3e/S1c4i6i:B01e2-ce34-t5-ei6-a7/S012-c3-ei45-ar6-c:2:0:1:3:2:obo$bo!
::B01e3e/S1c2c5y6i:B01e2-ce3456-ae7/S01234-jt5-ar6-c:2:0:1:3:2:obo$bo!
::B01e2e4c/S4n:B01e2-c3-e45-i6-c7e8/S01e2-c3-c45-e6-ce:2:0:1:3:2:obo$bo!
::B01e2e/S2c4y6i:B01e2-c3-e4-j5-ei6-c7e8/S01e23-e4-n5-e6-ce:2:0:-1:3:2:obo$bo!
::B01e2e5e/S2c4n:B01e2-c3-e4-j5-i6-c7e8/S01e23-e4-y5-e6akn:2:0:1:3:2:obo$bo!
::B01e2e6i/S1c5r:B01e2-c3-e45-y6-c/S012-c3-e4-y5-e6akn:2:0:1:3:2:obo$bo!
::B01e2e/S1c4y5e:B01e2-c3-e45-y6-ci/S012-c3-e45-r6akn:2:0:-1:3:2:obo$bo!
::B01e2e3e/S1c5e:B01e2-c3456-c7e/S012-c34-e56akn:2:0:-1:3:2:obo$bo!
::B01e2c4t/S2c5j:B01e2-e3-e4-ky5-i6-a7e8/S0234-nt5-ai6-c:2:0:1:3:2:obo$bo!
::B01e2c4y/S2c4t:B01e2-e3-e4-kt5-i6-a7e8/S0234-n5-aij6-c:2:0:-1:3:2:obo$bo!
::B01e2c4y/S1c3i:B01e2-e3-ey45-i6-a7/S012-c3-j45-ar6-ck:2:0:-1:3:2:obo$bo!
::B01e2c6c/S1c2c6k:B01e2-e3-e45-k6-a7/S0123-y4-kt5-ar6-c:2:0:1:3:2:obo$bo!
::B01e2c5k/S1c2c4t:B01e2-e3-e456-ac7/S0123-y4-k5-ar6-ck:2:0:-1:3:2:obo$bo!
::B01e2c3e5e/S1c3i:B01e2-e34-t5-i6-a7/S012-c34-r5-air6-c:2:0:-1:3:2:obo$bo!
::B01e2ce5e/S5j:B01e23-e4-j56-c7e8/S01e2-c3-c45-ei6-ce:2:0:1:3:2:obo$bo!
::B01e2ce6i/S2c5j:B01e23-e45-y6-c7e8/S01e23-e4-y5-ei6akn:2:0:1:3:2:obo$bo!
::B01e2ce/S2c4y6i:B01e23-e45-y6-ci7e8/S01e23-e45-eij6-ce:2:0:-1:3:2:obo$bo!
::B01e2ce7e/S1c6k:B01e23-e45-y6-c7e/S012-c34-jy5-e6akn:2:0:1:3:2:obo$bo!
::B01e2ce/S1c4y5e:B01e23-e45-y6-c/S012-c34-j56an:2:0:-1:3:2:obo$bo!
::B01e2ce3e/S1c5e:B01e23456-c7e/S012-c345-c6akn:2:0:-1:3:2:obo$bo!
::B01c4a/S:B01c2-ce3-aei45-i678/S01e2-c345-ai6-a:2:0:1:3:2:obo$bo!
::B01c4r5i/S1c:B01c2akn3-e4-c5-en6-c78/S012-c345-ai6-ae:2:0:-1:3:2:obo$bo!
::B01c2i5n/S1c:B01c2-ce3-e4-cr5-ei6-c78/S012-c345-ai6-ae:2:0:1:3:2:obo$bo!
::B01c5e/S1c6a:B01c2akn3-e4-cr5-in6-c78/S012-c345-ai6-e:2:0:2:3:2:obo$bo!
::B01c5e/S1c2c6a:B01c2-ce3-e45-cn6-c78/S0123-c4-c5-i6-e:2:0:2:3:2:obo$bo!
::B01c3e5j/S0:B01c2-ce3-y4-qt5-i678/S01e2-c345-ai6-a:2:0:1:3:2:obo$bo!
::B01c3e4t/S6a:B01c2-ce3-y4-q5-ij678/S1e2-c345-ai6:2:0:2:3:2:obo$bo!
::B01c3e5q6c/S2c:B01c2-ce34-ty5-ij678/S023-y45-ai6-ae:2:0:-1:3:2:obo$bo!
::B01c3e5j/S1e2c:B01c2-ce34-ty5-iq6-c78/S01e23-y45-ai6-ae:2:0:1:3:2:obo$bo!
::B01c3e4t/S2c6a:B01c2-ce34-y5-ijq6-c78/S023-y45-ai6-e:2:0:2:3:2:obo$bo!
::B01c3e6k/S1c2c3e:B01c2-ce3456aek78/S01234-y5-ei6-ae:2:0:1:3:2:obo$bo!
::B01c3e6i/S1c2c6a:B01c2-ce3456aei78/S0123-e4-y5-ei6-e:2:0:2:3:2:obo$bo!
::B01c2e7e/S3a:B01c2-c3-ein4-ai56-a78/S01e2-c345-ai6-a:2:0:-1:3:2:obo$bo!
::B01c2e8/S2c4r:B01c2-c3-ei4-an56-a78/S01e234-i5-ai6-a:2:0:-1:3:2:obo$bo!
::B01c2e8/S1c2c5c:B01c2-c3-e45-ein67e8/S01234-n5-i6ckn:2:0:-1:3:2:obo$bo!
::B01c2e5in/S1c2c:B01c2-c3-e45-e67e/S01234-n5-ci6ckn:2:0:1:3:2:obo$bo!
::B01c2e5e/S1c2c6a:B01c2-c3-e45-in67e/S01234-n5-ci6-ei:2:0:2:3:2:obo$bo!
::B01c2e3e7e/S4q:B01c2-c34-kt5-jy6-a78/S01e2-c345-ai6-a:2:0:-1:3:2:obo$bo!
::B01c2e3e8/S2c5q:B01c2-c34-t5-j6-a78/S01e23-i45-aiy6-a:2:0:-1:3:2:obo$bo!
::B01c2e3e6k/S1c4i:B01c2-c3456-i8/S012-c34-k5-iq6-ae:2:0:1:3:2:obo$bo!
::B01c2e3e8/S1c2c6n:B01c2-c3456-ik7e8/S012345-ij6-ae:2:0:-1:3:2:obo$bo!
::B01c2e3e6i/S1c2c6a:B01c2-c3456-k7e/S012345-ij6-en:2:0:2:3:2:obo$bo!
::B01c2c4r5i/S1c:B01c2-e3-e4-c56-c78/S012-c3-c45-ae6-ce:2:0:-1:3:2:obo$bo!
::B01c2c3e6a/S1e:B01c2-e3-y4-qy5-i678/S01e2-c34-t5-a6-c:2:0:1:3:2:obo$bo!
::B01c2c3e5q6c/S2c:B01c2-e345-ei6-a78/S01e2-i3-y4-t5-a6-ce:2:0:-1:3:2:obo$bo!
::B01c2c3e6a/S2ci:B01c2-e345-eiq6-c78/S01e23-y4-t5-a6-ce:2:0:1:3:2:obo$bo!
::B01c2c3e7c/S1c3e:B01c2-e345-eiq6-c78/S012-c34-y5-a6akn:2:0:1:3:2:obo$bo!
::B01c2c3e5iq/S1c:B01c2-e345-e6-c7e8/S012-c3-e4-y5-a6akn:2:0:-1:3:2:obo$bo!
::B01c2c3e7c/S1c2c4e:B01c2-e3456-cn78/S012345-e6akn:2:0:1:3:2:obo$bo!
::B01c2ce7e/S3a:B01c23-ey4-iy5-i6-a78/S01e2-c3-i45-a6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce3y5i/S:B01c23-e4-iy56-a7c8/S01e2-c3-ai45-a6-ac:2:0:1:3:2:obo$bo!
::B01c2ce8/S2c4r:B01c23-e4-t5-ei6-a78/S01e23-i4-i5-a6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce4t5i/S2c:B01c23-e45-e6-a7/S01e23-i4-ir5-a6-ac:2:0:1:3:2:obo$bo!
::B01c2ce7e/S1c4r:B01c23-e45-y6-ci7e8/S012-c34-y5-e6ikn:2:0:-1:3:2:obo$bo!
::B01c2ce5y6c/S1c:B01c23-e456-i8/S012-c34-ry5-e6ikn:2:0:1:3:2:obo$bo!
::B01c2ce8/S1c2c5c:B01c23-e456-c7e8/S012345-e6akn:2:0:-1:3:2:obo$bo!
::B01c2ce6c/S1c2c:B01c23-e4567e/S012345-ce6akn:2:0:1:3:2:obo$bo!
::B01c2ce3e7e/S4q:B01c2345-ky6-a78/S01e2-c3-y4-t5-a6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce3e8/S2c5q:B01c23456-ae78/S01e234-t5-ay6-ac:2:0:-1:3:2:obo$bo!
::B01c2ce3e8/S1c2c6n:B01c234567e8/S0123456akn:2:0:-1:3:2:obo$bo!
::B015a/S5i:B012-ce3-ei4-a5-i678/S01e2-c345-a6-a:2:0:-1:3:2:obo$bo!
::B016a/S2c6c:B012-ce3-ey45-ij678/S01e23-i45-a6-a:2:0:-1:3:2:obo$bo!
::B013y/S2c5a:B012-ce3-e45-ij6-a78/S01e23-i456-ac:2:0:1:3:2:obo$bo!
::B016a/S1c5i:B012-ce3-e4-i5-e67c8/S012-c34-a56-a:2:0:-1:3:2:obo$bo!
::B015y/S1c2c6a:B012-ce3-e4568/S012345-ej6-c:2:0:1:3:2:obo$bo!
::B017c/S1c2c6c:B012-ce3-e45-y67c8/S012345-ej6-a:2:0:-1:3:2:obo$bo!
::B013e6e/S5i:B012-ce34-t5-n6-c78/S01e2-c3456-ae:2:0:-1:3:2:obo$bo!
::B013e7e/S2c6c:B012-ce3456-ck78/S01e23-y4-t56-ae:2:0:-1:3:2:obo$bo!
::B013e/S2c3y6e:B012-ce3456-ck7c8/S01e234-t56-ac:2:0:1:3:2:obo$bo!
::B013e7e/S1c5i:B012-ce3456-i7/S012-c34-i5-n6-a:2:0:-1:3:2:obo$bo!
::B012e5e/S2c5a:B012-c3-e45-i6-a78/S01e2345-i6-a:2:0:1:3:2:obo$bo!
::B012e3e/S2c5e6e:B012-c3456-c7e8/S01e23456-c:2:0:1:3:2:obo$bo!
::B012c6a/S2c6c:B012-e3-e4-t56-e78/S01e23-i45-i6-a:2:0:-1:3:2:obo$bo!
::B012c6a/S1c5i:B012-e3-e45-ei678/S012-c345-a6-a:2:0:-1:3:2:obo$bo!
::B012c7c/S1c2c6c:B012-e3-e456-c78/S012345-e6-e:2:0:-1:3:2:obo$bo!
::B012c3e/S3i7e:B012-e34-t56-ae78/S01e2-c345-i6-ac7e:2:0:1:3:2:obo$bo!
::B012c3e6e/S5i:B012-e34-t56-a78/S01e2-c3-i456-ac:2:0:-1:3:2:obo$bo!
::B012ce5e/S6a:B0123-e45-i6-a78/S01e2-c345-ai6:2:0:1:3:2:obo$bo!
One helpful tool would be to fix certain transitions and focus only on those rules. An important shortcut would be to skip certain rules (e.g. those with B1c) by default.
There is a getallrules.py and getallrulesnt.py among the python scripts delivered with golly, they could be used in a batch in order to determine supported rules of a given pattern. Don't invent wheel!

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Comprehensively analyzing a pattern across rules

Post by Hunting » March 27th, 2020, 10:17 am

Well... I did the exactly same thing in the early days of the childish SRSS (Some Really Small Spaceships) project, except I excluded B0 and B2a, as that project is designed for rule-golfing. This thread in fact made me frustrated.

User avatar
LaundryPizza03
Posts: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Comprehensively analyzing a pattern across rules

Post by LaundryPizza03 » May 10th, 2020, 2:06 am

Here's a pseudocode for the basic script:

Code: Select all

#C Initial conditions (t=0)
pattern P;
list of transitions (e.g. B0, S4t, S7c), "102" for short;

#C Search parameters
integer searchDepth; #Maximum number of generations to search
integer maxPop;

#C Result stats, self-explanatory
integer nShips;
integer nOsc;

START:
	treeNode(0, P, {}, {}); #Start here
	report "(nOsc) oscillators and (nShips) ships found matching pattern (P)";
	STOP;

treeNode(integer t; pattern P'; list minrule; list avoidedTransitions):
	if P' is congruent to P;
		record oscillator/spaceship; #C Works from minrule to 102-avoidedTransitions
		if spaceship: increment nShips;
		if oscillator: increment nOsc;
		STOP;
	if t = searchDepth: STOP; #C This line will not be reached if a periodic pattern is found;
	if population > maxPop: STOP; #C Skip patterns that get too big (presumed explosions)

	perturbTransitions := (all neighborhoods present in P') - avoidedTransitions - minrule;
	for each integer 0 <= i <= 2^size(perturbTransitions):
		list fixTo1 = (encode bits of i as subset of perturbTransitions);
		list fixTo0 = perturbTransitions - fixOn;
		newMinrule = minrule + fixTo1; #C Disjoint union, by assumption
		newAvoidedTransitions = avoidedTransitions + fixTo0;
		if minRule has constantly expanding patterns (B1c, B1e2a, etc.):
			SKIP; #C These rules contain no oscillators or spaceships;
		else:
			P'' := advance P' according to newMinrule;
			treeNode(t+1; P''; newMinRule; newAvoidedTransitions); #C Recursive step
We represent the isotropic transitions by 102 tokens and specify a rulespace as two disjoint subsets of transitions: one representing the minrule, and the other representing the transitions not in the maxrule. At each node in the evolutionary tree, we select those transitions in the rulespace that will affect the next generation; then each node a the next level will correspond to a 2-coloring of those "perturb" transitions. We stop when the pattern becomes periodic, a certain generation is reached, or the pattern grows too big. (For complex patterns over large numbers of generations, it's better to use a rulesrc-family script.)

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Comprehensively analyzing a pattern across rules

Post by LaundryPizza03 » June 6th, 2020, 3:16 pm

I'm in a debugging phase, and after sorting out a large number of crashes and inconsistencies, the recursive function seems to be overwriting the b and s parameters at lower levels of recursion, so the transitions accumulate throughout the run. It's also repeating a lot of branches, likely for the same reason. The other methods in the class, including the local sub-method subseq, otherwise work as intended. Does anyone know what's going on? I'm new to Python, so the source of the overwriting is not obvious. Many of the variables in the pseudocode above, such as time t, are now purely local or parameters of the function.

Code: Select all

# The iteration process, which explores the evolutionary tree of possible outcomes
# Parameters: time t, current pattern P, minrule (b,s), avoided transitions (a,d)
def treeNode(t,P,b,s,a,d):
    global searchDepth, maxpop, P0
    global f
    
    g.reset()
    g.setrule(toRule(b,s))
    g.run(t)
    f.write('\t'*t + g.getrule() + '\n')
    f.flush()
    
    #g.show("Debug 113: P = {0}, actual = {1}, rule = {2}".format(P, g.getcells(g.getrect()), g.getrule()))
    assert g.getcells(g.getrect()) == P
    assert g.getgen() == str(t)
    
    if int(g.getpop()) > maxpop: return None #Stop if pattern becomes too big
    if int(g.getpop()) == 0: return None #Empty patterns stay empty
    
    #Shorthand: B('1c') returns true iff B1c is on; A('1c') == not B('1c')
    B = lambda C: C in b
    S = lambda C: C in s
    A = lambda C: not B(C)
    D = lambda C: not S(C)
    
    #Future: Add support for skipping rules that expand incessantly
    if B('0c') & S('8c'): return None
    
    #g.show("Debug 128: b,s = ({0}, {1}); a,d = ({2}, {3})".format(b,s,a,d))
    perturb = findBranches(P, b, s, a, d)
    numBranches = 2**len(perturb)
    
    #Given a list A of items, draw a sublist based on the bits of i
    def subseq(A,i):
        S = []
        for j in range(len(A)):
            if i & 2**j: S.append(A[j])
        return S
    
    if t >= searchDepth: return None #Stop at the depth limit
    for i in range(numBranches):
        
        setOn = set(subseq(perturb, i)) #Draw a subset of the elements of perturb, which will all be set to on
        setOff = set(perturb) - setOn #Complement of setOn in perturb
        g.setrule(toRule(addTrans(b, s, setOn)[0],addTrans(b, s, setOn)[1]))
        Pp = g.evolve(P, 1)
        treeNode(t+1, Pp, addTrans(b, s, setOn)[0], addTrans(b, s, setOn)[1], addTrans(a, d, setOff)[0], addTrans(a, d, setOff)[1]) #Recurse
        
f = open("debugPath.txt", 'w')
treeNode(0, P0, set(), set(), set(), set()) #Start in B/S with all transitions unknown
f.close()
Partial output for obo$bo! with searchDepth of 1 generation:

Code: Select all

B/S
	B/S
	B3e/S
	B2e3e/S
	B2e3e/S
	B2e3e/S2c
	B2e3e/S2c
	B2e3e/S2c
	B2e3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B2ce3e/S2c
	B1e2ce3e/S2c
	B1e2ce3e/S2c
	...
Should look like:

Code: Select all

B/S
	B/S
	B3e/S
	B2e/S
	B2e3e/S
	B/S2c
	B3e/S2c
	B2e3e/S2c
	...
Another example: same shape, but with searchDepth 2:

Code: Select all

B/S
	B/S
	B3e/S
		B3e/S
		B3e/S0
	B2e3e/S0
		B2e3e/S0
	B2e3e/S0
		B2e3e/S0
	B2e3e/S02c
		B2e3e/S02c
		B2e3e/S02c3i
		B2e3ei/S02c3i
		B2e3ei/S02c3i
		B2e3ei/S02c3ei
		B2e3ei/S02c3ei
		B2e3ei/S02c3ei
		B2e3ei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02c3ei
		B2e3aei/S02ac3ei
		B2e3aei/S02ac3ei
		B2e3aei/S02ac3ei
		B2e3aei/S02ac3ei
		B2e3aei/S02ac3ei
		B2e3aei/S02ac3ei
		...

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Comprehensively analyzing a pattern across rules

Post by LaundryPizza03 » June 6th, 2020, 11:27 pm

UPDATE: This method seems to be overwriting b and s

Code: Select all

def addTrans(b,s,add):
    if add == set(): return b,s #Cannot iterate over the empty set
    bp,sp = b,s
    for T in add:
        if len(T) != 3: raise RuntimeError("each transition must be of the form Bxx or Sxx: {0}".format(T))
        
        if T[0] == 'B': bp.add(T[1:]) #B1c is automatically truncated to 1c; B0c becomes 0c
        elif T[0] == 'S': sp.add(T[1:]) #Same here, but for survival
        else: raise RuntimeError("each transition must be of the form Bxx or Sxx: {0}".format(T))
    return bp,sp

#Test program for addTrans
b = {'1c', '2a'}
s = {'2a', '2c', '3e'}
print("Before addTrans: b,s = {0}".format((b,s)))
print("addTrans B4c, S0c, giving: b,s = {0}".format(addTrans(b,s,{'B4c','S0c'})))
print("After addTrans: b,s = {0}".format((b,s)))

Code: Select all

Before addTrans: b,s = ({'2a', '1c'}, {'2c', '2a', '3e'})
addTrans B4c, S0c, giving: b,s = ({'2a', '4c', '1c'}, {'2c', '2a', '3e', '0c'})
After addTrans: b,s = ({'2a', '4c', '1c'}, {'2c', '2a', '3e', '0c'})
Changing the method to

Code: Select all

def addTrans(b,s,add):
    if add == set(): return b,s #Cannot iterate over the empty set
    bp = set()
    sp = set()
    for T in add:
        if len(T) != 3: raise RuntimeError("each transition must be of the form Bxx or Sxx: {0}".format(T))
        
        if T[0] == 'B': bp.add(T[1:]) #B1c is automatically truncated to 1c; B0c becomes 0c
        elif T[0] == 'S': sp.add(T[1:]) #Same here, but for survival
        else: raise RuntimeError("each transition must be of the form Bxx or Sxx: {0}".format(T))
    return b|bp, s|sp
solves the problem.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Comprehensively analyzing a pattern across rules

Post by LaundryPizza03 » June 7th, 2020, 1:51 am

lemon41625 helpfully pointed out that we could use a file based on searchRule-matchPatt2.py, so the above effort was unnecessary.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2297
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Comprehensively analyzing a pattern across rules

Post by LaundryPizza03 » March 16th, 2021, 6:03 pm

So AforAmpere recently released a C++ script called EnumPattEvo that uses exactly this funtion.

Here is the complete list of all non-B0 patterns with shape obo$bo! and period at most 6. There were 21644 oscillators and 81093 spaceships. Of the 21644 oscillators...
  • 1 has period 1
  • 10 have period 2
  • 31 have period 3
  • 235 have period 4
  • 1810 have period 5
  • 19557 have period 6
Of the 81093 spaceships...
  • 3 move up at speed c/2o, and 6 move down.
  • 18 move up at c/3o, and 29 move down.
  • 69 move up at 2c/4o, and 171 move down.
  • 141 move up at c/4o, and 241 move down.
  • 9 move up at 3c/5o.
  • 281 move up at 2c/5o, and 843 move down.
  • 1118 move up at c/5o, and 1678 move down.
  • 2 move up at 4c/6o.
  • 4342 move up at 3c/6o, and 9641 move down.
  • 11212 move up at 2c/6o, and 15519 move down.
  • 17224 move up at c/6o, and 18546 move down.
Attachments
obo$bo!.txt
102737 unique patterns
(5.67 MiB) Downloaded 113 times

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

Post Reply