Apgcode

apgsearch and its search results database, Catagolue, use apgcodes to classify and denote patterns as follows. Most objects are stored as two alphanumeric strings separated by an underscore. The 'prefix' refers to everything before the underscore and may begin with:

• xs for a still life;
• xp for an oscillator;
• xq for a spaceship;
• yl for a periodic linearly growing object, such as a puffer or gun.

Oversize still lifes, oscillators, and spaceships, larger than 40 by 40, have a prefix beginning with ov_s, ov_p, or ov_q, respectively; extended (greedy) apgcodes may still be used to encode these patterns.

These are followed by a number. For still lifes (xs or ov_s), this is the population of the still life, while for the others it is the period of the object.

The codes for xs, xp, and xq are followed by an underscore, then a string (the 'suffix') which is a representation of the object in Extended Wechsler Format, described below. Codes for yl are followed by an underscore and additional information encoding higher-order periods of the pattern.

Objects which apgsearch cannot classify as above are denoted by one of:

• zz_EXPLOSIVE
• zz_LINEAR
• zz_QUADRATIC
• zz_REPLICATOR
• PATHOLOGICAL (e.g. high-period oscillators)

Extended Wechsler Format

This is an extension of a pattern notation developed by Allan Wechsler in 1992. A string of n characters in the set {0, 1, 2, ..., 8, 9, a, b, ..., v} denotes a strip of five rows, n columns wide. Each character denotes five cells in a vertical column corresponding to the bitstrings {'00000', '00001', '00010', ..., '01000', '01001', '01010', '01011', ... '11111'}. For instance, xq4_27deee6 corresponds to a HWSS:

The character 'z' separates contiguous five-row strips. For example, xs31_0ca178b96z69d1d96 is:

The characters 'w' and 'x' are used to abbreviate '00' and '000', respectively. So xp30_w33z8kqrqk8zzzx33 is the trans-queen-bee-shuttle:

(10 blank rows omitted)

Note that extraneous '0's at the ends of strips are not included.

Finally, the symbols {'y0', 'y1', y2', ..., 'yx', 'yy', 'yz'} correspond to runs of between 4 and 39 consecutive '0's. A good example is the quadpole on ship, xp2_31a08zy0123cko:

Canonical form

In order to enforce a canonical form, there are further rules regarding encoding:

• The leftmost column and uppermost row must each contain at least one live cell. (This gives a canonical position.)
• Any '0's on the ends of strips are ignored, and {'00', '000', '0000', '00000', ...} are always replaced with {'w', 'x', 'y0', 'y1', 'y2', ...}. (Theoretically, runs of more than 39 zeroes should be replaced by 'yz' followed by the coding for the remaining zeroes. At the moment apgsearch labels everything larger than 40-by-40 as 'oversized' and refuses to process it.)
• A canonical orientation and phase must be determined. For example, with the caterer (p3 oscillator with no symmetry), there are three phases and eight orientations, so we have 24 possible encodings. A total order on these encodings is defined as follows:
  • Shorter representations are preferred to longer representations;
  • For representations of the same length, lexicographical ASCII ordering is applied (and preference given to earlier strings).

This gives, for any still-life, oscillator or spaceship, an unambiguous canonical code to represent the patern. It has several desirable properties:

• Compression: it is much more compact than RLE or SOF for storing very small patterns, and often even beats the common name ('xp15_4r4z4r4' is shorter than 'pentadecathlon')!
• Character set: it only uses digits, lowercase letters and the underscore, so can be safely used in filenames and URLs.
• Human-readability: the prefix means that we can instantly see whether a particular object is a still-life (and if so, what size), oscillator (and if so, what period) or spaceship (and if so, what period). It also means that the string is instantly recognised as being an encoding of an object ('xp2_7' is obviously a blinker, whereas the digit 7 on its own with no extra context is ambiguous).

Adapting apgcodes to larger patterns

Different ways of extending apgcodes to patterns exceeding a 40 by 40 bounding box have been proposed. In their original form, apgcodes are not guaranteed to be able to encode larger patterns, due a lack of well-definedness for runs of 40 or more consecutive zeroes.

Extended ("greedy") apgcodes avoid this problem by stipulating that a run of n zeroes be encoded as follows:

1. If n is less than 40, the run is encoded as in regular apgcodes, using the characters w, x, and y0 .. yz as appropriate.
2. If n is equal to or greater than 40, the run is encoded as yz (representing the first 39 zeroes), following by the encoding for a run of n - 39 zeroes according to this definition.

That is to say:

This extension, which is used on the LifeWiki for larger patterns, retains compatibility with existing apgcode decoders. Adapting encoders to produce extended apgcodes is similarly straightforward.

Greedy apgcodes were adopted for apgsearch 4.x, subject to the following constraints:

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

Adapting apgcodes to multistate rules

Work is ongoing on extending apgcodes to multistate (Generations) rules. For this, apgcodes encoding still lifes, oscillators and spaceships will contain multiple suffixes, separated by underscores.

Each suffix will encode one 'layer' of the pattern, with patterns in an n-state rule having 2+⌈log₂(n-2)⌉ layers, where layer 0 is 'live', layer 1 is 'refractory', and the remaining layers implement a binary counter.

No explicit examples of such apgcodes have been given yet.

Limitations

apgcodes can be ambiguous if a rule is neither specified nor implicitly assumed, with the same code being assigned to different patterns evolving differently. For example, the code xp2_2a54 describes at least three different period-2 oscillators:

Evolution of xp2_2a54 across different rules

B3/S3 to B35678/S02345678	B34/S to B345678/S0245678	B4/S1 to B45678/S01245678