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!
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!