Thread for your CA software/algorithms ideas

[confocaloid]

Following several previous threads, here is a "community wishlist" thread for any ideas of CA algorithms and software that could be created.

It may be an idea for a script to be run inside Golly, or for an independent utility, or a stand-alone GUI application, or just an algorithm outline, or a "nice-to-have" feature request for an existing application or service that may or may not become an actual feature, etc.
of
To get this started (and to link to previous posts/threads):

* An utility that automatically generates a human-readable "text with numbers" description of a given pattern. It should work for a sufficiently wide class of patterns -- i.e. not just those objects whose apgcodes start with "x" (e.g. detect and describe a linear growth, a vanishing pattern, a glider synthesis, ..., distinguish between objects and constellations, ...)

* A simpler way to manually enter symmetric patterns in Golly/LifeViewer. For example, there's a polyomino-solving application FlatPoly2 (external link to the website); in that program, you can Ctrl+left click on a square (in a rectangular field) and the four symmetric squares are all grayed/ungrayed.

* A simpler way to know when the Catagolue synthesis for a given object was updated and what was the actual submitted synthesis each time. (I'm aware of Catagolue backups and update logs, and those are helpful, but do not solve the problem entirely -- it's still necessary to look through multiple pages to find the needed information. It would be nice to have a fully automated solution if that's possible.)

* viewtopic.php?p=162044#p162044 A simple intuitive way to maintain and share collections of patterns, without necessarily having a single central place where the collection is maintained. Probably there would be a dedicated file format "pattern collection" to simplify sharing updates, a way to automatically merge different versions of the same collection into a single collection file (while preserving any updates), and a sufficient set of available operations (list, browse, add, remove, find, export/import (to a stamp collection, to a list of RLEs, ...), ...)

Previous posts/threads:
* Searching algorithms (forum thread)
* A queryable database of known patterns of a certain type (oscillators, spaceships, ...) with associated information that cannot be derived from the pattern itself.
* Forum posting discord bot idea dump (forum thread)
* Ruletable format extensions proposal (forum thread)
* Puzzles and "Project von Neumann" (forum thread)

[PC101]

-A GUI program that makes caterpillar building easier.
-A program that automatically builds caterpillars.
By caterpillars I mean engineered spaceships that are similar to the spaceships that are self-constructing and self-supporting, like Gemeni, Shieldbug, Camelship, e.t.c.
https://conwaylife.com/wiki/Spaceship#E ... spaceships

[confocaloid]

A fast special-purpose tool to determine periods of high-period "chaotic" oscillators that are either confined to a small bounding box (like the White Whale in LongLife) or live in a small bounded universe (like this p313701632).

Crossposting from OCA talk:LongLife: the high-period oscillator in LongLife is period-160000346, and the given 75-cell pattern is not a phase of the oscillator but only a predecessor. The population equals 92 at T = 114375463, 274375809, ...

Code: Select all

#C T = 0 (top left), T = 114375463 (top right), T = 12822175 (bottom left),
#C T = 160000346 + 12822175 (bottom right).
#C The two patterns in the bottom row converge after one tick.
x = 49, y = 69, rule = B345/S5
8b2o27b4o2$6b2o2b2o23b3o3b2o2$4b2o6b2o19b2obo6b2o$31bo$2b2o10b2o16bo3b
2o7b2o$2o15bo12b2o15b2o$2bo13bo15bo4bo8bo$2o15b2o11b2o15b2o$2bo13bo15b
5o7b3o$2o15b2o11b2o15b2o$2bo13bo15bo10bo2bo$2o15b2o11b2o15b2o$2bo13bo
15bo11b3o$2o15b2o11b2o15b2o$2bo13bo15bo13bo$2o15b2o11b2o15b2o$2bo13bo
15bo13bo$2o15b2o11b2o15b2o$2bo13bo15bo12b2o$2o15bo12b2o$2bo11b2o16b2o
9b2o$2o29bo$2b2o8b2o19b2o6b2o2$4b2o4b2o23b6o2$6b4o27b2o12$7b4o26b4o2$
5b2o4b2o22b2o4b2o2$3b2o8b2o18b2o8b2o$bo29bo$2b15o15b15o$2o15b2o11b2o15b
2o$2b15o15b15o$2o15b2o11b2o15b2o$2b12ob2o15b12ob2o$2o15b2o11b2o15b2o$
2bobo3b5o3bo15b2o4b5o3bo$2o15b2o11b2o15b2o$2bobo2b7o2bo15bobo2b7o2bo$
2o15b2o11b2o15b2o$2bobo2b10o15bobo2b10o$2o15b2o11b2o15b2o$2b2o4b6o2bo
15b2o4b6o2bo$2o15b2o11b2o15b2o$2b4o7bob2o15b4o7bob2o$2o28b2o$2bo3b9o17b
o3b9o$bo29bo$3b2o6b2o20b2o6b2o2$5b2o2b2o24b2o2b2o2$7b2o28b2o!

When does this pattern become periodic? It hasn't stabilized for 770,000,000 generations:

Code: Select all

x = 16, y = 16, rule = B2-a3-ai4inrtwyz5-jky6-cn78/S3k4-jqt5-aer6-ac7
bobo5bob2ob2o$ob2o4bo4b2o$obobobo2bob5o$4bob2o3b5o$2b2o2b5o2b3o$4bobo
bo4b2o$o5bo2bobobo$3o4b2obo4bo$bobo5bobo3bo$3b2ob3obo3b2o$2o2b6o2bo$o
2bobo2bo2bob3o$b4o2b2o2bo$b2o2b3obo2bobo$2o4bo4b5o$3obobo3bo4bo!

[TYCF]

A tool to search through collections of patterns, run each pattern in a rule, and check if they are still a still life / oscillator / spaceship.

[haaaaaands]

that already exists: https://catagolue.hatsya.com/home
i know it isn't a program, but it can do it

[TYCF]

that already exists: https://catagolue.hatsya.com/home
i know it isn't a program, but it can do it

Yes, but you have identify each pattern.

[confocaloid]

A tool to search through collections of patterns, run each pattern in a rule, and check if they are still a still life / oscillator / spaceship.

You can census each pattern in a collection of RLEs using apgluxe.
https://gitlab.com/apgoucher/apgmera/-/ ... /README.md
Tutorials/Catagolue stdin symmetry

E.g. suppose you have the following six patterns in a file "patterns.txt":

Code: Select all

x = 3, y = 3, rule = B3/S23
b2o$2o$bo!

x = 6, y = 4, rule = B3/S23
bobo$o$bo2bo$3b3o!

x = 6, y = 4, rule = B3/S23
3b3o$2bo2bo$bo$o!

x = 7, y = 3, rule = B3/S23
bo$3bo$2o2b3o!

x = 7, y = 3, rule = B3/S23
bo$3bo$2o2b3o!

x = 6, y = 4, rule = B3/S23
4bo$4b2o$2ob2o$o!

Then it should be possible to census these patterns in an arbitrary rule (b3s23 in this example) roughly as follows:

Code: Select all

git clone https://gitlab.com/apgoucher/apgmera.git
cd apgmera
./recompile.sh --rule b3s23 --symmetry test_stdin
cd ..
./apgmera/apgluxe -t 1 -L 1 -n 1000000000 -i 1 < patterns.txt

If everything is correct then the program will print an output like this at the end:

Code: Select all

----------------------------------------------------------------------
6 soups completed.
143176 tiles processed.
Attempting to contact Catagolue...
Saving results to log.1698439386.k_4BpMMt7rP7qv.txt
Connection was successful.
New seed: k_Tdv9LbcFYSxw; iterations = 1; quitByUser = 1
Terminating...

The log file mentioned in the line "Saving results to..." (in this case "log.1698439386.k_4BpMMt7rP7qv.txt") contains the results, with apgcodes of occurring objects and headerless RLEs of sample soups.

Code: Select all

testing
[...]
@NUM_SOUPS 6
@NUM_OBJECTS 838

@CENSUS TABLE
xp2_7 233
xs4_33 228
xs6_696 161
xq4_153 81
xs5_253 47
xs7_2596 44
xs6_356 18
xs8_6996 9
xs4_252 6
xs6_25a4 4
xs8_69ic 2
xs7_25ac 2
xp2_7e 2
xs14_69bqic 1

@SAMPLE_SOUPIDS
[...]

[confocaloid]

Period/displacement detection for moving patterns and partials. The input is a pattern (puffer, rake, partial, etc). The output is a set of "guessed" most likely value(s) of (dx,dy)c/p.

[silversmith]

Period/displacement detection for moving patterns and partials. The input is a pattern (puffer, rake, partial, etc). The output is a set of "guessed" most likely value(s) of (dx,dy)c/p.

My CA program actually has something like this implemented, where you can select an area, then press a button which tells you the period and displacement of the selected pattern. For example, here is a Pi-Heptomino descendant, where you can click "More Options", then "Identify Pattern", and the program will provide some info about such a pattern, up to a period of 300.

[confocaloid]

This is meant to be two separate patterns running in two non-interacting toroidal universes, but shown on a single sheet. The file format could be structured to allow more than one pattern in a single file (possibly with different rules / topologies, and with associated metadata for each pattern in the file). Actions "Start/stop generating", "Next generation" could be used either for single patterns or for the whole sheet.

Code: Select all

#C patterns from https://conwaylife.com/forums/viewtopic.php?p=176406#p176406
x = 131, y = 78, rule = B3S23History
53.78D$53.D76BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD
$53.D76BD$53.D76BD$53.D21B2A53BD$53.D7BABA11B2A53BD$53.D8B2A66BD$53.D
8BA67BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD$44D9.D76BD$D42BD9.D76BD$D
2BA39BD9.D76BD$D3BA38BD9.D10B2A2B2AB2A57BD$DB3A38BD9.D10B2AB2A3B2A56B
D$D42BD9.D14B2AB2A57BD$D42BD9.D15B3A58BD$D7BA34BD9.D16BA59BD$D8BA33BD
9.D76BD$D6B3A33BD9.D13B2A15BA45BD$D42BD9.D14BA13BABA45BD$D42BD9.D11B
3A15B2A45BD$D12BA29BD9.D11BA64BD$D13BA28BD9.D76BD$D11B3A28BD9.D76BD$D
42BD9.D76BD$D42BD9.D76BD$D17BA24BD9.D76BD$D18BA23BD9.D76BD$D16B3A12BA
10BD9.D76BD$D29B3A10BD9.D76BD$D28BA13BD9.D76BD$D18B3A7B2A12BD9.D76BD$
D17BA3BA20BD9.D76BD$D16BA5BA19BD9.D76BD$D11B2A3BA5BA19BD9.D76BD$D11B
2A3B3AB3A6BA12BD9.D76BD$D30BA11BD9.D76BD$D28B3A11BD9.D48BA27BD$D42BD
9.D49B2A25BD$D15BA26BD9.D48B2A26BD$D14BABA17BA7BD9.D58B2A16BD$D15BA
19BA6BD9.D58B2A6B2A8BD$D33B3A6BD9.D66BA9BD$D42BD9.D59BA4BABA9BD$D42BD
9.D58B3A3B2A10BD$D39BA2BD9.D58BAB2A14BD$D40BABD9.D61B2A13BD$D38B3ABD
9.D58BAB2A14BD$D42BD9.D58B3A15BD$44D9.D59BA16BD$53.D76BD$53.D47B2A27B
D$53.D47B2A27BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD$53.D65BA
10BD$53.D66BA9BD$53.D64B3A9BD$53.D76BD$53.D76BD$53.D76BD$53.D76BD$53.
D76BD$53.D76BD$53.D76BD$53.78D!
#C [[ VIEWONLY ]]

[b-engine]

A Golly Python script to build a self-supporting spaceship based on crawler inputted (via RLE pasted in input box).

For example, if I input the (23,5)c/79 Herschel climber, then it will spit out waterbear or a similar spaceship.

[dvgrn]

A Golly Python script to build a self-supporting spaceship based on crawler inputted (via RLE pasted in input box).

For example, if I input the (23,5)c/79 Herschel climber, then it will spit out waterbear or a similar spaceship.

Heh, when someone writes a working Python script that does that, I'm going to be looking through the code very carefully to see where it calls an external AI -- ChatGPT 99.9 or some such. And then I'll finally have to admit that AI has arrived at human-level intelligence.

(Currently ChatGPT is still failing absolutely miserably when faced with even the simplest Conway's Life problems -- it's like trying to get ChatGPT to play chess. Basically it just makes up things that sound plausible, but never comes up with anything that actually works.)

The ability to build a waterbear starting just from its base reaction ... is not currently reducible to a practical algorithm. We could write something that could theoretically brute-force a solution, I suppose, but the sun will burn out before it's done processing.

[b-engine]

The ability to build a waterbear starting just from its base reaction ... is not currently reducible to a practical algorithm. We could write something that could theoretically brute-force a solution, I suppose, but the sun will burn out before it's done processing.

I think the what the script needs to do is just to add more crawlers and glider (occasionally xWSSes) to support the crawler inputted and themselves.

The input may can been get from the selection of the crawler.

[silversmith]

I think the what the script needs to do is just to add more crawlers and glider (occasionally xWSSes) to support the crawler inputted and themselves.

Well, you can always try writing a script to do what you want yourself. If it works, you would have your own tool custom built to solve your particular problem.

[Haycat2009]

A Golly Python script to build a self-supporting spaceship based on crawler inputted (via RLE pasted in input box).

For example, if I input the (23,5)c/79 Herschel climber, then it will spit out waterbear or a similar spaceship.

Frankly I think that it will most likely be in C++, and if it is true, I will try a Pi-heptomino and see if a 3c/10 spaceship come out. It is going to be insanely difficult, and I will not be surprised if it only works on quantum/biological computers.

[confocaloid]

[...]
The ability to build a waterbear starting just from its base reaction ... is not currently reducible to a practical algorithm. We could write something that could theoretically brute-force a solution, I suppose, but the sun will burn out before it's done processing.

More seriously, that might be reducible to a practical algorithm. It's just that such an algorithm is going to be complicated with multiple steps, generating and testing possibilities, and lots of annoying casework. Look carefully at what it is that humans do to build a waterbear, and write down every step in details, including what could go wrong, what was due to a lucky coincidence vs. what could be bruteforced, etc.

It is not very likely that someone will actually write a working program for that, but in principle I don't think that would require general AI, or "quantum computer", or anything like that. Just an usual computer with enough memory, and lots of domain specific knowledge, sometimes hard to write down exactly, but in principle could be written down so explicitly and unambiguously that a computer could do it, with little further help from a human expert.

[dvgrn]

[...]
The ability to build a waterbear starting just from its base reaction ... is not currently reducible to a practical algorithm. We could write something that could theoretically brute-force a solution, I suppose, but the sun will burn out before it's done processing.

More seriously, that might be reducible to a practical algorithm. It's just that such an algorithm is going to be complicated with multiple steps, generating and testing possibilities, and lots of annoying casework...

All totally true. It's only the pure brute-force version that's guaranteed not to ever become workable.

The "build a self-supporting spaceship out of this reaction" script will become not-vaporware as soon as someone comes up with all of those actual specific detailed ideas that can turn it into a practical algorithm.

Until that happens, though, it does seem like a very good example of vaporware.

[b-engine]

The "build a self-supporting spaceship out of this reaction" script will become not-vaporware as soon as someone comes up with all of those actual specific detailed ideas that can turn it into a practical algorithm.

Good question. I'd formed an idea of how it works:

1. The script will first find what can the crawler climbs based on the input (either selection or RLE input).
2. The script will try any combination of what can been placed at the front or back of the crawler.
3. The script will try to form a closed glider loop using the crawler.

If anyone have more details, please ask me. Also can someone help me write the Python script?

[dvgrn]

The "build a self-supporting spaceship out of this reaction" script will become not-vaporware as soon as someone comes up with all of those actual specific detailed ideas that can turn it into a practical algorithm.

Good question. I'd formed an idea of how it works:

1. The script will first find what can the crawler climbs based on the input (either selection or RLE input).
2. The script will try any combination of what can been placed at the front or back of the crawler.
3. The script will try to form a closed glider loop using the crawler.

If anyone have more details, please ask me. Also can someone help me write the Python script?

I'd like to make some kind of answer to this post rather than just ignoring it, but it's ... kind of difficult to explain how far these three points are from an implementable algorithm. It's hard to see how someone could help you write a Python script that does these things successfully.

Just a script that successfully handles item #1 would be a good accomplishment -- definitely within reach, but quite difficult if you want it to work generally for every possible crawler reaction that someone might put in.

The definition of the word "try" is the vaguest part of items #2 and #3. Each one of those items would need a full page of detailed explanation about how exactly the script would try to do these things.

By analogy...
If the original request was "I want to fly to the moon!", then the above three points are equivalent to

1) Build a rocket
2) Aim the rocket in exactly the right direction
3) Put fuel in the rocket, climb in, and push the "Go" button

As instructions go, these aren't _wrong_ or anything -- but in terms of actually getting to the moon, they lack a lot of really important details.

[b-engine]

I wrote a pseudocode about the caterpillar making script:

Code: Select all

Note: anything inside (( and )) is either input or variable. 

-

set ((crawler)) to ((selection)) (the pattern selected)
repeat until i = ((10))
      randomly place still life at ((crawler)) ((x,y)) + ((random ((-10,10)),random((-10,10))))
      If ((crawler)) reappears
            set ((crawler_list)) to ((the entire pattern))
            set i to ((i + 1))
randomly arrange ((crawler_list)) until a spaceship appears

However I don't have any idea of how to turn it into Python script.

[dvgrn]

I wrote a pseudocode about the caterpillar making script:
...
However I don't have any idea of how to turn it into Python script.

No one else is likely to have any more of an idea than you are, I'm afraid.

In particular, the pseudocode "randomly arrange ((crawler_list)) until a spaceship appears" still contains pretty much the entire unsolved problem.

That one line would probably need to be expanded out to the size of a Ph.D. dissertation (at least) before it could be implemented in Python -- and as others have mentioned, Python is probably too slow to be the right language to use for this project anyway.