Database of all known patterns

[hotdogPi]

Sokwe suggested it here:

It would be wonderful to have a server-side script rejecting known patterns.

In my opinion, there's nothing wrong with accidentally posting a known pattern. It can sometimes reveal new insights about the pattern or how to find similar patterns. What I fear the most is someone deciding not to post an interesting pattern or observation about a pattern because they think it's probably known.

That being said, we do desperately need a queryable database of known oscillators and spaceships. It's become very difficult to check whether or not a given pattern is new.

Start with jslife's collection, the wiki collection, Mark Niemiec's p2 and p3s, all 3980 patterns in census.rle, the 5×5 rotor collection, and the ECC conduit collection.

Run through everything in Life, LifeHistory, and LifeSuper with no state-6 cells that exists as a code block on the forum. Initial bounding box must be within 400×400. Exclude sandbox threads that are labeled "game", but include the rest (e.g. JP21's sandbox is quite useful). First determine what interacts by running it via LifeHistory, using "cluster" rather than "connected" (e.g. rock tubs are still part of the same cluster and shouldn't be separated), except the "4 times as wide as it is high" glider synthesis criterion should be considered on the whole thing instead of each part. Separate non-interacting parts. Classify it here:

Oscillator: It's an oscillator.
Agar/Wick: It's an oscillator or spaceship on a bounded grid that doesn't work if it's not bounded.
Spaceship: It's a spaceship.
Glider gun: It's a glider gun.
Infinite growth: Infinite growth other than glider guns. (The tetrational diehard will probably be misclassified here.)
Eater: The end is a subset of the beginning, but it doesn't end with a vacuum.
Conduit: For the first 50 generations, the number of combined births and deaths is less than 50 for every generation, the birth/death region for generation 7 is within 12×12 (this allows ghost Herschels), the population never becomes less than initial minus 10 for the first 50 generations, it never settles for the first 50 generations, and there is no initial 5×5 region with more than 16 on cells. Eater and oscillator take priority over this. "50 generations" can be replaced with "20 generations" if it's in LifeHistory and there are between 5 and 10 state-3/state-5 cells that are all within 5×5 and no other state 3/5. This will lead to some false positives and negatives, but it's the best I can think of. Unfortunately, periodic conduits using sparkers will be missed here.
Synthesis: Starts with at least 4 gliders (or other spaceships) or with at least 2 and a central object that's a single cluster, and there can't be anything behind the bounding box of any inward gliders, OR contains at least 8 gliders and is at least 4 times as wide as it is high (this is for staged syntheses). In both cases, if its bounding box increases past the initial bounding box on either axis, it's disqualified from this category.
Spaceship partial, puffer/rake: Check generations 2-12. If, for any of them, the front 2/3 or the back 2/3 is identical to the original but shifted (and it's not a full spaceship), include it in "puffer/rake" if it continues for at least 5x generations and the full spaceship (rather than just most of it) plus something extra appears at least once where x is the spaceship height and "spaceship partial" otherwise. The initial pattern must have at least 20 cells.
Methuselah: Lasts for at least 2,000 generations and has an initial population of 15 or less, or 20,000+ within 20×20. Spaceship partial has priority over this.
Soup: Begins with 16×16, 20×20, 31×31, 32×31, or 32×32, its density is between 40% and 60%, and it contains no 5×5 region of ON or OFF cells within that box. Methuselah takes priority over this.
Miscellaneous: Everything else. Anything that's a still life, dies within 10 generations, or becomes a still life that's at least as common as a half-bakery or a TL/HF/fleet/bakery within 10 generations can be deleted.

You can probably also use which thread it's in to help, although that isn't infallible.

Post-processing:
For oscillators and glider guns, if it's period 4 or greater, remove anything that's larger in both dimensions and population (that's three variables) than another oscillator with the same rotor. (This won't get everything, especially with sparkers as catalysts.) Don't do this for the "soup search results" thread.
For methuselahs and "miscellaneous", any pattern that is a later generation of another one is deleted unless the later one has a smaller population.

[dvgrn]

... First determine what interacts by running it via LifeHistory, using "cluster" rather than "connected" (e.g. rock tubs are still part of the same cluster and shouldn't be separated), except the "4 times as wide as it is high" glider synthesis criterion should be considered on the whole thing instead of each part. Separate non-interacting parts...

Where else is the "4 times as wide as it is high" glider synthesis criterion discussed? EDIT: Ah, I see it in the list lower down. It's not clear how well that will work -- there are lots of pre-Catagolue syntheses posted that don't exactly follow the current convention for incremental syntheses.

There's a little problem that seems likely to throw a lot of stamp collections into "Miscellaneous", or maybe "Methuselah". How long do you run each pattern?

For example, as long as you don't run this stamp collection for too long, the pieces can be reliably separated. Otherwise the "0" and "5" labels start looking like part of some random subset of the turners.

That's a relatively well-behaved example. There are examples that get really messy if you wait long enough, and examples that use gray cells as separators, and examples that are very big but do eventually end up being validly connected (and then they stop working)...

And then there are stamp-collection cases where you have to stop quite quickly after you start to avoid cross-contamination. There are lots of hard-to-separate patterns in jslife-moving that are like that, if I remember right, but that problem is definitely not limited to jslife.

[confocaloid]

...

That being said, we do desperately need a queryable database of known oscillators and spaceships. It's become very difficult to check whether or not a given pattern is new.

This can be done with a Catagolue stdin symmetry, which should be named what_is_known_stdin.

I did try to write a script to scrape the forums for patterns, though it didn't go too far.

Using a Catagolue stdin symmetry would be a limited solution.

First, it would work only for things that are reliably recognized by apgsearch (i.e. still lifes, oscillators, spaceships, and probably some infinite growths). Hence many patterns would be missed and would need a separate database. The complexity of designing and implementing that separate database would probably be significantly higher, to the point that once implemented, there would be little point in keeping also a Catagolue stdin census -- probably it would be relatively easy to cover everything in one database, eliminating the dependency on a separate Catagolue tabulation.

More significantly, Catagolue stdin symmetry does not seem to reliably preserve the "when" information -- even if a pattern got there, it is not always possible to determine when the pattern appeared in the tabulation (and the actual discovery might be earlier than the submission date). Any other discovery information (e.g. notes about who discovered the pattern, how it was discovered, what tools were used, and so on) is simply lost.

I think it would be very helpful to have a queryable database that is sufficiently flexible to record historical information and some details of how patterns were found, as well as previous versions of patterns that were record-holders at some point. I do understand this is not too likely to happen due to the complexity, but such a database would be useful.

[Sokwe]

This is certainly more ambitious than what I had imagined. Each pattern type would really need its own database containing data relevant to that pattern type. I discussed some of what I would like to see in an oscillator database here.

It might be easiest to start with a single pattern type (like oscillators) and create a working, queryable database for it.

[squareroot12621]

Besides this, there should be a collection of patterns that are incorrectly classified by the system and are hardcoded into specific categories. For example, the R-pentomino is universally defined as a methuselah, but it isn't classified as such by the system (it falls ≈900 generations short).

Edit: Also, Catagolue's C2_[?] soups would be disqualified from the "Soup" category for pretty obvious reasons.

Edit 2: This would be classified as both an eater and a soup:

Code: Select all

x = 16, y = 16, rule = B3/S23
ob2ob2o2b2ob2obo$b14o$16o$16o$b14o$5ob4ob5o$6o4b6o$b5ob2ob5o$b5ob2ob5o
$6o4b6o$5ob4ob5o$b14o$16o$16o$b14o$ob2ob2o2b2ob2obo!

Edit 3: Whoops, forgot about the density condition. This should work, though:

Code: Select all

x = 16, y = 16, rule = B3/S23
ob2ob2o2b2ob2obo$2b12o$7o2b7o$3o4b2o4b3o$b2o10b2o$3o2b6o2b3o$3o2bo4bo
2b3o$bobobob2obobobo$bobobob2obobobo$3o2bo4bo2b3o$3o2b6o2b3o$b2o10b2o
$3o4b2o4b3o$7o2b7o$2b12o$ob2ob2o2b2ob2obo!

[hotdogPi]

For an oscillator-only update to jslife:

Do you think getting the following via script and removing the duplicates would get pretty much everything?

1. existing jslife
2. b3s23osc, which has discovery information
3. web scraper on oscillator discussion thread and SKOP106+ thread; ignore those that aren't oscillators (and don't turn into them); can assume the poster is the discoverer and the date is accurate unless another username is in the post
4. the various hassler pages on the wiki, which usually have discovery information
5. "oscillator spam collection" Discord thread, again with username and date of discovery being the user and date posted
6. my discoveries pages on the wiki (which is undated unfortunately)

My stamp collection generator program can automatically create a stamp collection once the list of oscillators of a given period is given as input, although it sorts by height rather than similarity.

Pseudocode:

Code: Select all

oscs = []
oscs += add_from_jslife()
oscs += add_from_b3s23osc()
for thread in ("oscillator_discussion", "skop"):
	for post in thread:
		oscs += add_each_rle_in_text(post)
for wikipage in ("hf", "r", "pi", "c", "b", "wing", "prepulsar", "sparker7", "sparker8", "sparker9", "sparker10",
				"hdp1","hdp15","hdp22","hdp31","hdp43","hdp61","hdp101"):
	oscs += add_each_rle_in_text(wikipage)
for wikipage in ("volatile5", "volatile6", "volatile7", "volatile8"):
	oscs += add_each_apgcode(wikipage)
for post in discord_oscillator_spam_collection:
	oscs += add_each_rle_in_text(post)
new_jslife_rle = [None] * 1001
for period in range(3,1000):
	relevant_oscs = filter(oscs, oscs[1] == period)
	relevant_oscs = remove_duplicate_rotors(relevant_oscs)
	new_jslife_rle[period] = create_stamp_collection(relevant_oscs) 

[Chris857]

Hopefully the "Synthesising Oscillators" forum thread wouldn't have anything not in the others, but it seems possible. Also "Soup search results" once in a while has something that I'm not certain gets posted elsewhere, but most of what I can remember probably has a wiki page (like the various Charity Engine discoveries)

Would guns (including capped versions) be something separate?

[confocaloid]

(Sorry if any of this is obvious)

3. web scraper on oscillator discussion thread and SKOP106+ thread; ignore those that aren't oscillators (and don't turn into them); can assume the poster is the discoverer and the date is accurate unless another username is in the post

Sometimes posts are edited several times on a later date to add more patterns (i.e. the assumption of accurate date will sometimes fail).
It may be better to have an explicit distinction between "discovered by N" (where N may be unknown) and "posted by N".

4. the various hassler pages on the wiki, which usually have discovery information

I'd expect some errors in discovery information/descriptions on the wiki.

[hotdogPi]

Here's a stamp collection of the entire new database (except for the 2700 and 15240). Duplicates and ridiculously long wicks haven't been removed yet.

EDIT: Updated as described in the next post.

[hotdogPi]

This actually happened two days ago, but Carson Cheng removed the same-population stator variants at p19 and below. There are still a lot of rotor variants that will have to be deleted manually. The "two beacons" and "four beacons" in the p2 section were also removed.

The download above has been replaced just now.

There was also a slight modification to the program as to sorting low periods by population: p2 up to 17 cells, p3 to 21, p4 to 24, p5 to 28, p6 to 32, and p7 to 38. Note that this is the generation 0 (i.e. canonical apgcode) population, not the minimum; there's an 18P3 that doesn't make the list because it begins in the wrong phase.

[hotdogPi]

Here's the updated stamp collection with deduplication complete.