## Extending apgcodes to larger patterns

For general discussion about Conway's Game of Life.

### Re: Extending apgcodes to larger patterns

Here's yet another suggestion: For long strings of spaces, use 0y followed by two base-36 digits. If the number of spaces is over 36^2, use 00y followed by 3 base-36 digits; over 36^3 --> 000y followed by 4 digits; etc. For long strings of newlines, use 0z followed by a base-36 digit, and extend as needed with more leading zeroes as above.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

A for awesome

Posts: 1287
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: Extending apgcodes to larger patterns

Living proof that a little knowledge is a dangerous thing.

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 577
Joined: July 27th, 2015, 2:06 pm

### Re: Extending apgcodes to larger patterns

Apple Bottom wrote:[xkcd]

I definitely agree. Sorry if I shouldn't have posted.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

A for awesome

Posts: 1287
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: Extending apgcodes to larger patterns

A for awesome wrote:I definitely agree. Sorry if I shouldn't have posted.

She's apples. It wasn't intended as criticism - and I do apologize if it came across as such -, just as an observation on how different, mutually-incompatible standards can arise.

As they say, perfect is the enemy of good -- and the road to hell is paved with good intentions.

Let's not overengineer apgcodes. They're good enough for what they do, the "greedy" extension is well-accepted and has desirable properties, and for extremely large patterns apgcodes are a poor fit anyway.
Living proof that a little knowledge is a dangerous thing.

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 577
Joined: July 27th, 2015, 2:06 pm

### Re: Extending apgcodes to larger patterns

I've implemented greedy apgcodes for larger patterns (including multistate patterns) in the upcoming v4.0 release, increasing the bounding box limit for oversized patterns from 40-by-40 to the following pair of constraints:

• (width + 2) * (height + 2) <= 10000;
• The resulting apgcode, without the prefix, cannot exceed 1280 bytes.

Apparently, Google App Engine increased their key length limit from 500 bytes to 1500 bytes; hence, these 1280-character apgcodes are fully compatible with Catagolue:

https://stackoverflow.com/a/33061526/5130486

I've tested the new apgcode generation on the spaghetti monster, and it agrees with the canonical form on the LifeWiki. I have yet to test multistate (e.g. Generations) patterns.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 1267
Joined: June 1st, 2009, 4:32 pm

### Re: Extending apgcodes to larger patterns

Generatioms is being added too??? Calcyman, is Catagolue EVER in say, 7+ years, going to support custom rules?
The Bugs Range 1 to 100 Project

Saka

Posts: 1773
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

### Re: Extending apgcodes to larger patterns

Saka wrote:Generatioms is being added too???

Yep, seems like Generatioms is getting added. Time to screan with joy.

BTW, would this allow for multistate Larger than Life rules? How about snoitareneG rules?
2c/n spaceships project (new)

Current priorities: see here
muzik

Posts: 2211
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

### Re: Extending apgcodes to larger patterns

calcyman wrote:I've implemented greedy apgcodes for larger patterns (including multistate patterns) in the upcoming v4.0 release [...]

I've tested the new apgcode generation on the spaghetti monster, and it agrees with the canonical form on the LifeWiki. I have yet to test multistate (e.g. Generations) patterns.

Excellent! Great news.

What about existing ov_* patterns, at least those in B3/S23? We have a couple of these -- about 22.5k ov_p46's, 20k ov_p177's, 8.8k ov_p24's, 2.6k ov_p30's, as well as about a dozen rare ov_p's and ov_s's.[1] Provided we still know what soups all these came from, we could re-identify them and re-file them using their proper extended apgcodes.

(That is, of course, IF we still have the soups. For the very common objects with thousands of appearances, where we only have 200 sample soup links and where hauls aren't available anymore, we might not.)

I'd be happy to help out, of course -- for both Life and other rules.

1. Including, apparently, an ov_s520 in C2_4, though looking at the soup I think that must've been a misclassification.
Living proof that a little knowledge is a dangerous thing.

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 577
Joined: July 27th, 2015, 2:06 pm

### Re: Extending apgcodes to larger patterns

The apgcode detection seems to work with Generations rules. I tried identifying the period-4 Brian's Brain spaceship:

x = 11, y = 5, rule = /2/3AB2.AB$AB.AB$.AB.A4.B$2.AB4.A.B$4.AB2.B!

using the following code:

    apg::lifetree<uint32_t, 6> lt4(500); // construct a 4-layer lifetree with 500MB of hashing memory    apg::pattern bb(&lt4, "AB2.AB$AB.AB$.AB.A4.B$2.AB4.A.B$4.AB2.B!", "g3b2s"); // initialise a pattern inside lt4 with Generations rule g3b2s    std::cerr << bb.apgcode() << std::endl; // compute and print the apgcode

which gives the apgcode xq4_3482h8a_03482lx8. (Yes, multistate apgcodes have multiple underscores, with each component giving a layer of the pattern. However, it's somewhat complicated as to how these layers map to Golly's state numbers, especially in the case of Generations rules.)

Saka wrote:Generatioms is being added too??? Calcyman, is Catagolue EVER in say, 7+ years, going to support custom rules?

It already does, inasmuch as it basically accepts anything that you choose to pass off as a rule name, symmetry type, and apgcode. If you make a search program which produces haul files for your favourite CA, then Catagolue will happily build a distributed census (as you discovered with Saka_Test).

The search program needn't even be a soup search: if you have a depth-first search program such as gfind or zfind, and you have a correspondence between positions in the search tree and alphanumeric strings (where prefixes correspond to ancestors), then you can conduct a distributed search for (say) width-20 c/6 spaceships using the existing Catagolue framework. If you incorporate all of zfind's command-line hyperparameters (period, offset, memory size, etc.) into the beginning of this string, then you can simply have a 'symmetry' called zfind whose tabulations will include things such as xq7, xq10, xq19 (potentially!), etc. And this will work without changing Catagolue in any way.

I'm surprised no-one has tried anything along these lines. The closest thing was my slow-salvo symmetry, but that was ugly in terms of implementation (indeed, I recall there was some non-deterministic element). Ideally every Catagolue-hosted search should be completely deterministic, with the 'randomness' only being present in the haul seed (as is the case for apgsearch).

As well as finding new spaceships in a systematic and distributed manner, it may help inform which combinations of hyperparameters are most effective for running zfind.

What you probably wanted to ask was:

is apgsearch EVER in say, 7+ years, going to support custom rules?

Maybe. The current progress on v4.0 has completely separated various levels of abstraction, so that you can write custom backends (as I've done for Generations, and will be doing for LtL). Any backend you write in this manner must take a 32-by-32 square of cells and return the 16-by-16 centre square after a number of generations (usually 1 for simplicity).

Once you've written that, it is automatically compatible with either of two containers (apg::pattern, which runs HashLife, and apg::upattern, which is based on vlife). So, provided you can write the C++ code to run a 32-by-32 square in your rule, the rest of the lifelib boilerplate code will be able to run unbounded universes efficiently in either a conventional or hashed manner. HashLife has the advantage that for regular patterns, it will eventually memoize all of the 32-by-32 tiles and never need to call your backend code again.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 1267
Joined: June 1st, 2009, 4:32 pm

### Re: Extending apgcodes to larger patterns

Interesting. Here's a little proposal. A global "Pattern Share" network. People can select a pattern and then upload it into the "PatterNet" symmetry of the rule and make a huge collection of stuff people want to share. Maybe they can make custom descriptions, and the community can "Like" objects to get them higher on the list. To prevent unwanted content, people should have an account (Not anonymous) and have:
-Contributed at least 50K soups to CGoL
-Searched at least 3 different rules
-Searched at least 1 "official" higher symmetry

Is Patternbook the next big Social Media? A few possible names:
-PatterNet
-CAbook
-Patterngram
-CIPNet (Catagolue International Pattern Network)
The Bugs Range 1 to 100 Project

Saka

Posts: 1773
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

### Re: Extending apgcodes to larger patterns

@Saka
This may disadvantage linear growth patterns as you have to use a soup because thumbnails don't work with them. (if you understand what I'm saying, it's kind of hard to express in words)
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)

B2-ac3i4a/S12

drc

Posts: 1489
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

### Re: Extending apgcodes to larger patterns

apgsearching one of those custom speeds/directions rules would be quite interesting.
2c/n spaceships project (new)

Current priorities: see here
muzik

Posts: 2211
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

### Re: Extending apgcodes to larger patterns

Would it be possible for replicators and quadratic growth patterns to be recognised and encoded like still lifes, oscillators and spaceships?

xr for one-dimensional replicators, xt for two-dimensional replicators, and yq for quadratic growth patterns.
2c/n spaceships project (new)

Current priorities: see here
muzik

Posts: 2211
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Previous