3D Hensel/INT notation working group

[wirehead]

We already have Hensel notation for INT transitions. There is also MAP notation, which is acceptably short considering that there are only 2^9 = 512 unique transitions in a range-1 2D Moore neighborhood.

I'm currently working on a 3D cellular automata program (pre-pre-alpha, don't expect anything anytime soon) and I'm thinking of using a rule notation similar to Hensel.

In a range-1 3D Moore neighborhood, there are 2^27 = 134217728 unique transitions. MAP or anything like it is out of the question because of that enormous number. (For arbitrary rules, I'm thinking of letting the user enter an actual Turing-complete function in some programming language.)

For starters, there are 3 kinds of INT transitions with 1 live neighbor or 25 live neighbors: whether the odd-man cell is on a face, edge, or vertex of the center cell.

For 2-24 live neighbors, I have no idea. Much help would be appreciated.

Also, if you are able to share an implementation in either Javascript or Scheme, that would be immensely helpful.

Please note I am only thinking of 2 state rules. Any multi-state rule would be an extension to the final notation (probably some adaptation of Cyclotrons' format.)

[confocaloid]

A direct equivalent of Hensel notation is probably impractical for 3D. The LifeWiki page Isotropic non-totalistic rule gives 1426144 as the number of possible 3D isotropic range-1 Moore neighbourhood conditions, ignoring center cell. In comparison, there are only 51 possible 2D isotropic range-1 Moore neighbourhood conditions.

There are some smaller intermediate rulespaces between "3D outer-totalistic R1 Moore" (27 distinguishable conditions ignoring center cell) and "3D isotropic R1 Moore".
For example, if corners, edges and face centres are counted separately (this is analogous to the subset of 2D INT rules where the orthogonal neighbours are counted separately from the diagonal neighbours), then there are three independent counts (0..8 alive corners, 0..12 alive edges, 0..6 alive face centres), leading to 9x13x7 = 819 distinguishable conditions ignoring center cell. Maybe one could find a practical notation for this "layer-totalistic" rulespace.

...
An old interesting example is the subset of INT rules where the orthogonal neighbours are counted separately from the diagonal neighbours. In this case, the layers are the central cell itself (0..1), the orthogonal neighbours (0..4) and the diagonal neighbours (0..4), leading to 2 x 5 x 5 = 50 distinguishable conditions and 2^50 possible rule definitions.

This can be further extended to higher ranges, with the neighbourhood partitioned into layers either by the range or by the displacement. (In the latter case, a range-2 onion CA on the square grid could have up to 6 layers.)

Related:
CWCFSMNCA https://web.archive.org/web/20150422212 ... words.html
A discussion of rule formats https://web.archive.org/web/19990224055 ... /0007.html

Moore-neighbourhood, E^2 lattice:
There is a nontrivial set of cellular automata rules between isotropic nontotalistic and outer-totalistic set, where only the number of diagonal and orthogonal neigbours count. Using Hensel-notation, only the following rulestring parts are valid in a birth or survival section:

• 0 diagonal, 0 orthogonal: 0
• 1 d., 0 o.: 1c
• 0 d., 1 o.: 1e
• 2 d., 0 o.: 2cn
• 1 d., 1 o.: 2ak
• 0 d., 2 o.: 2ei
• 3 d., 0 o.: 3c
• 2 d., 1 o.: 3inqy
• 1 d., 2 o.: 3akjr
• 0 d., 3 o.: 3e
• ...

and so on.
Is it worth to list already investigated nontotalistic rules if they fit into the above category?

[H. H. P. M. P. Cole]

I have worked on a large rulespace before. It is the R3 Cross rulespace. Here is the code I used to generate all the transitions:

Code: Select all

def binary(a):
    return 2048*a[0]+1024*a[1]+512*a[2]+256*a[3]+128*a[4]+64*a[5]+32*a[6]+16*a[7]+8*a[8]+4*a[9]+2*a[10]+a[11]

def qt(a):
    return [a[3],a[4],a[5],a[11],a[10],a[9],a[2],a[1],a[0],a[6],a[7],a[8]]

def rf(a):
    return [a[0],a[1],a[2],a[8],a[7],a[6],a[5],a[4],a[3],a[9],a[10],a[11]]

def func(a):
    if a == 0:
        return 'B'
    if a == 1:
        return 'A'

import csv

file = open('transitions', 'w')

nums = []
rows = []

for a in range(0, 2):
    for b in range(0, 2):
        for c in range(0, 2):
            for d in range(0, 2):
                for e in range(0, 2):
                    for f in range(0, 2):
                        for g in range(0, 2):
                            for h in range(0, 2):
                                for i in range(0, 2):
                                    for j in range(0, 2):
                                        for k in range(0, 2):
                                            for l in range(0, 2):
                                                m = [a,b,c,d,e,f,g,h,i,j,k,l]
                                                num = binary(m)
                                                listoflists = [qt(m),qt(qt(m)),qt(qt(qt(m))),rf(m),qt(rf(m)),qt(qt(rf(m))),qt(qt(qt(rf(m))))]
                                                if num not in nums:
                                                    alive = a+b+c+d+e+f+g+h+i+j+k+l
                                                    rletrans = ('x = 1, y = 1, rule = B/S012345678History\n3.'+func(a)+'3.$3.'+func(b)+'3.$3.'+func(c)+'3.$'+func(d)+func(e)+func(f)+'C'+func(g)+func(h)+func(i)+'$3.'+func(j)+'3.$3.'+func(k)+'3.$3.'+func(l)+'3.!')
                                                    row = [alive, rletrans, num]
                                                    rows.append(row)
                                                    for number in listoflists:
                                                        nums.append(binary(number))

with open('transitions.csv', 'w', encoding='UTF8', newline='') as f:
    writer = csv.writer(f)
    for row in rows:
        writer.writerow(row)

Because of the twelve for-loops it is not remarkably efficient. However, you can modify this program to create all the 3D INT transitions.

Notation (Generalized Durnak-Cole, named after the two originators of the idea) is simple: if you need only one letter (the number of transitions with n cells is less than 26), it would be a.b.c.d., etc, if two letters (the number of transitions with n cells is less than 676) it would be aa.ab.ac.ad.ae., etc, etc. The transition's name is the base-26 representation of how lexicographically far the transition is in the set of transitions which have n cells, where n is the number of cells in the transition in question. a = 0, b = 1, and so on until z = 25. Separate transitions are marked by dots.

You can use computerese (letters) for transitions' birth and survival numbers: 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P. If we have de Vlieger's Argam then it would be a heck of a lot easier to differentiate transitions and birth/survival cell counts, but it would be much more difficult to type, and it won't show up on browser (unless a proposition is written to put Argam in Unicode).

An example rulestring would be B67aaaa.city/S567Oa.bP. (I am definitely estimating the number of letters needed to make this).

For symmetry, in my program I used the generators of the group D4. However, as you are working with 3D you can use the generators of O_h (cube symmetries) and concatenate them. You can also derive them as transformations of a list with 26 elements inside.

An alternative is to call the other cells by the 26 English letters: so for example a set of transitions will be a.aegilops.be.city.del, removing the need for B/S numbers.

However, I have other suggestions. I agree that the whole 3D INT thingamajig is impractical.

What we need is (Life-like)
- R1 3D vN (see cubes.io)
- R1 3D Cuboctahedral (6 face-cells + 12 edge-cells)
- R1 3D Cubic/Bays (proposed name for equivalent of Moore neighbourhood in 3D, named after Carter Bays, the originator of this idea).

Also, I like the Naszvadian idea of semi-totalistic transitions. We should write that as a triple of numbers, (a,b,c), where a can be no greater than 6, B no greater than 12, and C no greater than 8.

3D wishlist:
- 3D Logic Rule (2D B2ae/S) (two transitions, easy peasy - or not)
- 3D Margolus rules (on second thought this might work better in 4D)

[wirehead]

I think a good starting point would be to work in layers. Each layer would be notated using Hensel, and then some suffix to indicate which of the 8 rotations/reflections it is. Then the 3 could be concatenated. Obviously this can be simplified because (51*8)^3 = 67917312, greater than 1426144 (by a factor of exactly 47.623039468665155, not sure what the significance of this constant is, if any.)

I haven't though about this very thoroughly, but it's probably a good place to start.

[confocaloid]

[...] We should write that as a triple of numbers, (a,b,c), where a can be no greater than 6, B no greater than 12, and C no greater than 8.

Since 7 + 13 + 9 = 29 does not exceed 10 + 26 = 36, it is possible to use the digits and Latin letters to unambiguously refer to any "primitive requirement". For example:

• To require exactly 0, 1, ..., 12 alive edge-neighbours, write the corresponding symbol from the string '0123456789xyz'.
• To require exactly 0, 1, ..., 8 alive corner-neighbours, write the corresponding letter from the string 'cefghikmn'.
• To require exactly 0, 1, ... 6 alive face-neighbours, write the corresponding letter from the string 'pqrtuvw'.

So for example 'B4et' would mean that a new cell is born when there are exactly 4 alive edge-neighbours, exactly 1 alive corner-neighbour, and exactly 3 alive face-neighbours.

(Note: the use of X for 10, Y for 11 and Z for 12 follows the choice already used for the 12-cell triangular neighbourhood.
The letters 'b', 's', 'a', 'd' are not used for any "primitive requirements" to simplify parsing of rulestrings and rulespace definitions. For example, 'b4ets5gpaxfqdynw' can be unambiguously parsed as a rulespace definition 'B4et S5gp Axfq Dynw'.)
(Edit: see post6321, post25139, post48449 for the use of letters B, S, A, D to define rulespaces.)

A more complicated rulestring might look like this:

Code: Select all

b23f4gti5k-v6-kv7-ms0

This can be parsed as follows:

Code: Select all

B2 B3f B4gt B4i B5k-v B6-kv B7-m S0
# B3f = all possibilities of B3f? (i.e. B3fp B3fq B3fr B3ft B3fu B3fv B3fw)
# B5k-v = all possibilities of B5k? except B5kv
# B6-kv = all possibilities of B6?? except B6kv
# B7-m = all possibilities of B7?? except B7m?
# S0 = all possibilities of S0?? (i.e. a cell survives when there are
# no alive edge-neighbours, regardless of the states of other neighbours)

I think a good starting point would be to work in layers. Each layer would be notated using Hensel, and then some suffix to indicate which of the 8 rotations/reflections it is. Then the 3 could be concatenated. Obviously this can be simplified because (51*8)^3 = 67917312, greater than 1426144 (by a factor of exactly 47.623039468665155, not sure what the significance of this constant is, if any.)

I haven't though about this very thoroughly, but it's probably a good place to start.

One issue is that this loses/hides symmetry by arbitrary choices of layering/orientation: it is likely that most of rules to be explored will be invariant under 3D rotations/reflections. In addition, the top and bottom layers will have 9 cells each (including the central cell of the layer), while the middle layer will have only 8 cells (excluding the central cell of the 3x3x3 neighbourhood).

[wirehead]

One issue is that this loses/hides symmetry by arbitrary choices of layering/orientation: it is likely that most of rules to be explored will be invariant under 3D rotations/reflections. In addition, the top and bottom layers will have 9 cells each (including the central cell of the layer), while the middle layer will have only 8 cells (excluding the central cell of the 3x3x3 neighbourhood).

Well, I did think of that problem. You could just say that the bottom-middle-top layer approach would be just one canonical orientation and it could be oriented in any of the 48 (?) different orientations of something in 3D space (e.g left-middle-right, front-middle-back, top-middle-bottom, etc.) For the non-center-cell layers there could also be some suffix character to specify the state of the middle cell.

What I think I'm going to implement now is this "outer-orientation-totalistic" rule notation you described above.

Since 7 + 13 + 9 = 29 does not exceed 10 + 26 = 36, it is possible to use the digits and Latin letters to unambiguously refer to any "primitive requirement". For example:

• To require exactly 0, 1, ..., 12 alive edge-neighbours, write the corresponding symbol from the string '0123456789xyz'.
• To require exactly 0, 1, ..., 8 alive corner-neighbours, write the corresponding letter from the string 'cefghikmn'.
• To require exactly 0, 1, ... 6 alive face-neighbours, write the corresponding letter from the string 'pqrtuvw'.

So for example 'B4et' would mean that a new cell is born when there are exactly 4 alive edge-neighbours, exactly 1 alive corner-neighbour, and exactly 3 alive face-neighbours.

(Note: the use of X for 10, Y for 11 and Z for 12 follows the choice already used for the 12-cell triangular neighbourhood.
The letters 'b', 's', 'a', 'd' are not used for any "primitive requirements" to simplify parsing of rulestrings and rulespace definitions. For example, 'b4ets5gpaxfqdynw' can be unambiguously parsed as a rulespace definition 'B4et S5gp Axfq Dynw'.)

A more complicated rulestring might look like this:

Code: Select all

b23f4gti5k-v6-kv7-ms0

This can be parsed as follows:

Code: Select all

B2 B3f B4gt B4i B5k-v B6-kv B7-m S0
# B3f = all possibilities of B3f? (i.e. B3fp B3fq B3fr B3ft B3fu B3fv B3fw)
# B5k-v = all possibilities of B5k? except B5kv
# B6-kv = all possibilities of B6?? except B6kv
# B7-m = all possibilities of B7?? except B7m?
# S0 = all possibilities of S0?? (i.e. a cell survives when there are
# no alive edge-neighbours, regardless of the states of other neighbours)

One question: B and S I understand (birth and survival), but what do A and D stand for?

[squareroot12621]

One question: B and S I understand (birth and survival), but what do A and D stand for?

It's confocaloid's terminology:

I would say that second meaning is somewhat imprecise. Transitions are events such as B = birth, S = survival, A = abstain (a dead cell that remains dead), D = death, that are given by the previous and new states of a cell.

[confocaloid]

One question: B and S I understand (birth and survival), but what do A and D stand for?

The use of "A" and "D" to define rulespaces is actually old notation. It is not invented by me.
B stands for birth, S stands for survival, D stands for death (when a specific survival condition is prohibited), A stands for abstain (when a specific birth condition is prohibited).
So for example a012b3d0s8 can be used to refer to the set of rules where B3 and S8 are both present but B0, B1, B2, S0 are all absent.

[...] Rules with A0123B4* are unable to grow into vacuum over any positive curvature, but some can grow "inwards" if a hole is cut into a random starting state, ie. negative curvature still allows growth.

(* A = "abstain", to mark the absense of birth. Similarly, D = "death" is useful for specifying classes of rules with varying survival conditions.)

OP's question, reframed:
– A Life-like CA is defined by the presence of some birth/survival conditions and the absense of others.
– Any pattern (spaceship, oscillator, etc.) in a Life-like CA will require some of these conditions to function, but not necessarily all. For example, a blinker will only require the absence of B012 and the presence of B3 (in brief: B3,A012 — A being short for "abstain"), but the higher birth conditions are irrelevant. Similarly, S2 and D1 (short for "death") are required, but all other survival conditions are irrelevant.
– The complete set of conditions a pattern requires could be called the rulespace area that a pattern is native to.
– What, then, is the smallest oscillator native to the specific rule B3,A01245678/S23,D0145678?
[...]

It's true you can't shift diagonally with B1c and then orthogonally with B1e but you can move diagonally with B0 A*1c and then orthogonally with S7e.
Speaking of which, what's the status on non-totalistic B0 rules?

*A is short for abstain; in this case B1c is explicitly prohibited.

[H. H. P. M. P. Cole]

In summary:

3D INT is too complicated. Even R3 Cross has too many transitions (666), which is why I made a 'rulegolfer' program which is in actuality a database of R3 Cross transitions. Imagine handling the square or the cube of that number of transitions.

This will only be practical, say, 50 years in the future where we can easily download information in our minds. (This is a subjective point).

The Naszvadian idea, though, requires less memorization - it only needs you to know the number of faces, edges, and corners, and memorize only three sets of alphanumerics. I like this!

I'll digress for a moment and go to 3D LtL.

- Rn Bays/Cubic: the (2n+1)x(2n+1)x(2n+1) cube centered around the central cell (equiv. of Moore)
- Rn Octahedral: the (2n+1)x(2n+1)x(2n+1) octahedron centered around the central cell (equiv. of vN)
- Rn Cuboctahedral: the (2n+1)x(2n+1)x(2n+1) cuboctahedron centered around the central cell
- Rn Axial: three axes of length (2n+1) intersecting at the central cell (equiv. of Cross)

Even if we do complete 3D INT, how are we going to define speeds? I think (1,0,0) = orthogonal, (1,1,0) = diagonal, and (1,1,1) = paragonal. Beyond that I'm personally not sure.

EDIT: I have currently defined a few single-letter transitions (these are provisional names):
- 4a: 2x2 square
- 4e: Hensel 2e but extruded to 2 layers
- 4c: Hensel 2c but extruded to 2 layers
- 4t: using $ for 2D and # for 3D indent, it would be CA$A#A$.A! (tetrahedral)
- 4p: $.C#A.A2$A.A! (pyramidal)
where C is the central cell.

B4ac/S is B2ac/S but 3D, and B4ae/S is B2ae/S but 3D. B4aet/S also includes new 3D Margolus media. Speaking of which, Margolus media might work better in 4D.

[wirehead]

Even if we do complete 3D INT, how are we going to define speeds? I think (1,0,0) = orthogonal, (1,1,0) = diagonal, and (1,1,1) = paragonal. Beyond that I'm personally not sure.

Those are the directions. I am inclined to say that speeds are equal to just the Euclidean distance divided by the period (i.e. (1, 2, 3)c/3 the speed = sqrt(14)/3.)

[owen]

I am inclined to say that speeds are equal to just the Euclidean distance divided by the period (i.e. (1, 2, 3)c/3 the speed = sqrt(14)/3.)

This would allow speeds faster than c, and would be inconsistent with current usage. The glider, for example, is said to have a speed of c/4, not sqrt(2)c/4. I think using the maximum of the three displacements (aka Chebyshev distance) would make more sense (and is how the wiki page for "Speed" defines it: https://conwaylife.com/wiki/Speed). So a pattern with a "velocity" of (1, 2, 3)c/3 would have a "speed" of 3c/3 = c.

[wirehead]

I think using the maximum of the three displacements (aka Chebyshev distance) would make more sense ... So a pattern with a "velocity" of (1, 2, 3)c/3 would have a "speed" of 3c/3 = c.

Well, there could be a few different metrics. You could just as well use the Manhattan distance (in that case it would be 6c/3 == 2c). It's kind of like how, in 100 ticks, a glider will move from (0, 0) to (25, 25) -- this would make the glider have a "Manhattan speed" of c/2 -- similarly because the same signal could be sent by 2 XWSS'es (obviously c/2) that travel from (0, 0) to (0, 25) in 50 ticks and then to (25, 25) in another 50 ticks, given an impossible instantaneous XWSS reflector.

----------

The use of "A" and "D" to define rulespaces is actually old notation. It is not invented by me.
B stands for birth, S stands for survival, D stands for death (when a specific survival condition is prohibited), A stands for abstain (when a specific birth condition is prohibited).
So for example a012b3d0s8 can be used to refer to the set of rules where B3 and S8 are both present but B0, B1, B2, S0 are all absent.

So which takes precedence? Is b3s23a23d3 acting like regular Life (if the b and s take precedence) or like Anti-Life (if the a and d take precedence)? Or is this rule just invalid (i.e. a transition in b can't also appear in a and vice versa)?

[owen]

Well, there could be a few different metrics. You could just as well use the Manhattan distance (in that case it would be 6c/3 == 2c). It's kind of like how, in 100 ticks, a glider will move from (0, 0) to (25, 25) -- this would make the glider have a "Manhattan speed" of c/2 -- similarly because the same signal could be sent by 2 XWSS'es (obviously c/2) that travel from (0, 0) to (0, 25) in 50 ticks and then to (25, 25) in another 50 ticks, given an impossible instantaneous XWSS reflector.

Perhaps you could use the symbol "m" for this. So "c" = one unit of Chebyshev distance per generation and "m" = one unit of Manhattan distance per generation. (The fact that "Chebyshev" starts with "c" is a nice coincidence.) Then the glider would have a speed of m/2 = c/4.

[confocaloid]

The use of "A" and "D" to define rulespaces is actually old notation. It is not invented by me.
B stands for birth, S stands for survival, D stands for death (when a specific survival condition is prohibited), A stands for abstain (when a specific birth condition is prohibited).
So for example a012b3d0s8 can be used to refer to the set of rules where B3 and S8 are both present but B0, B1, B2, S0 are all absent.

So which takes precedence? Is b3s23a23d3 acting like regular Life (if the b and s take precedence) or like Anti-Life (if the a and d take precedence)? Or is this rule just invalid (i.e. a transition in b can't also appear in a and vice versa)?

A string where most or all of B, S, A, D are specified can be interpreted as a definition of a rulespace (set of rules), rather than a single rulestring. (See Rulespace#Excluded_conditions on the wiki.) One could also clarify directly by writing something like "the rulespace a012b3".
There is no precedence in this case, but a "rulespace-string" should not contain contradictory requirements (e.g. it is a contradiction if both B3 and A3 are specified in the same string).

• The example "a012b3d0s8" can be read as "[the set of] all rules with B3 and S8, but without either of B0, B1, B2, S0".
• The example "b3s23a23d3" could be read as "[the set of] all rules with B3, S2 and S3, but without either of B2, B3, S3". This is self-contradictory (e.g. specifying "S3" requires a cell with three alive neighbours to survive in every rule in the rulespace, but specifying "D3" requires a cell with three alive neighbours to die in every rule in the rulespace). Hence the defined set of rules is empty.

[wirehead]

• To require exactly 0, 1, ..., 12 alive edge-neighbours, write the corresponding symbol from the string '0123456789xyz'.
• To require exactly 0, 1, ..., 8 alive corner-neighbours, write the corresponding letter from the string 'cefghikmn'.
• To require exactly 0, 1, ... 6 alive face-neighbours, write the corresponding letter from the string 'pqrtuvw'.

...
A more complicated rulestring might look like this:

Code: Select all

b23f4gti5k-v6-kv7-ms0

This can be parsed as follows:

Code: Select all

B2 B3f B4gt B4i B5k-v B6-kv B7-m S0
# B3f = all possibilities of B3f? (i.e. B3fp B3fq B3fr B3ft B3fu B3fv B3fw)
# B5k-v = all possibilities of B5k? except B5kv
# B6-kv = all possibilities of B6?? except B6kv
# B7-m = all possibilities of B7?? except B7m?
# S0 = all possibilities of S0?? (i.e. a cell survives when there are
# no alive edge-neighbours, regardless of the states of other neighbours)

Ok... I've been thinking about the rule string thing, and here's what I understand. Correct me if I'm wrong:

• So everything after a B or an S, must be written in the order edges, corners, faces, and if it goes out of order, it starts a new "group".
• If a group omits an entire category, it's assumed to be everything in the category (a wildcard). (Question: What about a group like "12uw" where corners is omitted but faces aren't? Is this equivalent to "12cefghikmnuw" ?)
• For the whole B or S condition to be true any one of the groups must be true (i.e. they are reduced using boolean OR).
• For a group to be true, the counts of types of neighbors must be included in the counts permitted for that group. For example, your "3f" expands to "3fpqrtuvw" and "7-m" expands to "7cefghiknpqrtuvw" using the second bullet point. (Question: How would you rulegolf something like "0123456789xycefghikmp" where the edge-neighbors is everything minus something? I think it would probably be "-z-np" -- but is it allowed to start with a dash?)
• If a cell is "off" it uses the "B" groups, otherwise it uses the "S" groups, and if any match the cell becomes "on" in the next tick, else it becomes "off".

On the second question's bullet point: AntiLife, which the wiki says is B0123478/S01234678 -- could it be also written B-56/S-5 ?

[confocaloid]

• To require exactly 0, 1, ..., 12 alive edge-neighbours, write the corresponding symbol from the string '0123456789xyz'.
• To require exactly 0, 1, ..., 8 alive corner-neighbours, write the corresponding letter from the string 'cefghikmn'.
• To require exactly 0, 1, ... 6 alive face-neighbours, write the corresponding letter from the string 'pqrtuvw'.

...

So everything after a B or an S, must be written in the order edges, corners, faces, and if it goes out of order, it starts a new "group".

I suspect that it is possible to avoid "hard-coding" any particular ordering of the three categories (i.e. edges/corners/faces or corners/faces/edges etc.), and even allow to use different orderings in different parts of the same rulestring. A rulestring can still be read left-to-right unambiguously.

Specifically, if the birth part is nonempty, then the character after "b" determines which of three categories comes first in the birth part. Split the birth part into as many segments as possible, where each segment begins with a character from the same category as the character after "b". For each of those segments, the second character (if present) determines which of two remaining categories comes before the other in this particular segment.
If there are no characters from some category at all, then that category of neighbours does not affect outcome in any way.
For example:

Code: Select all

b23f4gti5tgisp2qrf = b2 b3f b4gti b5tgi sp2 sq srf = b2 b3f b4gt b4i b5tg b5ti sp2 sq srf
bcevi2s1cevi2 = bc bev bi2 s1c s1ev s1i s2

If a group omits an entire category, it's assumed to be everything in the category (a wildcard). (Question: What about a group like "12uw" where corners is omitted but faces aren't? Is this equivalent to "12cefghikmnuw" ?)

Suppose the birth part is "12uw" (e.g. "b12uws0123456789xyz"). The first character after "b" is '1', which belongs to the category "edge-neighbours". Split the birth part into segments, where each segment begins with a character from the same category: "b1, b2uw".
The segment "b1" cannot be split further.
In the segment "b2uw", the character after "b2" is 'u', which belongs to the category "face-neighbours". So this segment can be rewritten as "b2(u, w) = b2u b2w".
Since there are no characters from the category "corner-neighbours" in this example, corner-neighbours are completely ignored and do not affect outcome.

Now, suppose the birth part is instead "12cefghikmnuw" (e.g. "b12cefghikmnuws"). Again, the first character after "b" belongs to the category "edge-neighbours", so the birth part can be rewritten as "b(1, 2cefghikmnuw) = b1 b2cefghikmnuw".
The segment "b1" cannot be simplified further.
In the segment "b2cefghikmnuw", the character after "b2" is 'c', which belongs to the category "corner-neighbours". So this segment can be rewritten as "b2(c, e, f, g, h, i, k, m, nuw) = b2c b2e b2f b2g b2h b2i b2k b2m b2nuw". All of those except the last part cannot be further simplified. The part "b2nuw" can be further rewritten as "b2nuw = b2n(u, w) = b2nu b2nw".

So the two examples are not equivalent:

• b12uw = b1 b2u b2w (the only births on 2 edge-neighbours are when there are either 4 or 6 face-neighbours).
• b12cefghikmnuw = b1 b2c b2e b2f b2g b2h b2i b2k b2m b2nu b2nw (in case there are 2 edge-neighbours, a cell is always born unless there are 8 corner-neighbours, and also born when there are 8 corner-neighbours and either 4 or 6 face-neighbours).
• The latter example can be equivalently rewritten: "b12cefghikmnuw = b12-npqrtv".

For the whole B or S condition to be true any one of the groups must be true (i.e. they are reduced using boolean OR).

Yes, the string is a disjunction ("b1 or b2nw"), while each segment like "b2nw" is a conjunction ("2" and "n" and "w).

For a group to be true, the counts of types of neighbors must be included in the counts permitted for that group. For example, your "3f" expands to "3fpqrtuvw" and "7-m" expands to "7cefghiknpqrtuvw" using the second bullet point. (Question: How would you rulegolf something like "0123456789xycefghikmp" where the edge-neighbors is everything minus something? I think it would probably be "-z-np" -- but is it allowed to start with a dash?)

Corrections:
I think eliminating the negation in "7-m" would give "7cefghikn", without need to mention face-neighbours explicitly.

If the birth part is "b0123456789xycefghikmp", that can be rewritten as

Code: Select all

b0123456789xycefghikmp
= b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 bx bycefghikmp
= b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 bx byc bye byf byg byh byi byk bymp

The only cases where birth does not happen would be "ym-p" (equivalent to "ymq ymr ymt ymu ymv ymw"), "yn", "z".
So it is possible to simplify, and instead of "b0123456789xycefghikmp" write "b-ymqrtuvwnz", or equivalently "b-zynmqrtuvw".

If a cell is "off" it uses the "B" groups, otherwise it uses the "S" groups, and if any match the cell becomes "on" in the next tick, else it becomes "off".

I think that's correct.

[wirehead]

If the birth part is "b0123456789xycefghikmp", that can be rewritten as

Code: Select all

b0123456789xycefghikmp
= b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 bx bycefghikmp
= b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 bx byc bye byf byg byh byi byk bymp

The only cases where birth does not happen would be "ym-p" (equivalent to "ymq ymr ymt ymu ymv ymw"), "yn", "z".
So it is possible to simplify, and instead of "b0123456789xycefghikmp" write "b-ymqrtuvwnz", or equivalently "b-zynmqrtuvw".

What I was intentding with b0123456789xycefghikmp was that birth should occur in any case, except if there are 12 edge-neighbors, or 8 corner-neighbors, or any face-neighbors. How would that string be notated?

Also, how would I parse "b-zynmqrtuvw"? Does the "-" bind more tightly than the groups? A couple rules about where to insert parenthesis would help. For example, I now understand that "b0123cef" expands to "b(0 | 1 | 2 | 3cef)" which in turn expands to "b(0 | 1 | 2 | 3(c | e | f))", but where do the negatives come in?

EDIT: I have currently defined a few single-letter transitions (these are provisional names):
- 4a: 2x2 square
- 4e: Hensel 2e but extruded to 2 layers
- 4c: Hensel 2c but extruded to 2 layers
- 4t: using $ for 2D and # for 3D indent, it would be CA$A#A$.A! (tetrahedral)
- 4p: $.C#A.A2$A.A! (pyramidal)
where C is the central cell.

Also, I've been thinking about all of the possible transitions, and it is simple enough to do only the 3 categories of neighbor based on distance (1, sqrt2, and sqrt3) using rotations and reflections. So we would only have to define relations between the layers.

It looks like you're also suggesting to use # as the layer separator in 3D-RLE. I was thinking of / but it's open for discussion.

[confocaloid]

What I was intentding with b0123456789xycefghikmp was that birth should occur in any case, except if there are 12 edge-neighbors, or 8 corner-neighbors, or any face-neighbors. How would that string be notated?

If I understand correctly, either of the following strings would work for the birth part:

• bp0-n1-n2-n3-n4-n5-n6-n7-n8-n9-nx-ny-n
  ("p" = 0 face-neighbours, "-n" = except if there are 8 corner-neighbours. Can be partitioned as "bp0-n bp1-n bp2-n bp3-n bp4-n bp5-n bp6-n bp7-n bp8-n bp9-n bpx-n bpy-n".)
• bp0cefghikm1cefghikm2cefghikm3cefghikm4cefghikm5cefghikm6cefghikm7cefghikm8cefghikm9cefghikmxcefghikmycefghikm
  (Same as previous, but does not use subtraction of conditions.)
• bpc-ze-zf-zg-zh-zi-zk-zm-z
  (Same approach as the first two examples, but now the ordering is "face, corner, edge" instead of "face, edge, corner".)
• bpc0123456789xye0123456789xyf0123456789xyg0123456789xyh0123456789xyi0123456789xyk0123456789xym0123456789xy
  (Same as previous, but does not use subtraction of conditions.)

Also, how would I parse "b-zynmqrtuvw"? Does the "-" bind more tightly than the groups?

Ignoring "b" (that denotes start of the birth part of the rulestring), this is "-zynmqrtuvw". Since it begins with "-" without any preceding letters/digits, all possible conditions are included, except those described after "-".
I parse the string "zynmqrtuvw" as "zy(nm(qrtuvw))" -- in this case the ordering is "edges, corners, faces":

Code: Select all

zynmqrtuvw
zy(nm(qrtuvw))
z OR yn OR ymq OR ymr OR ymt OR ymu OR ymv OR ymw

So the meaning of "b-zynmqrtuvw" would be that a cell is always born, unless at least one of the following is true:

• 12 alive edge-neighbours ("z")
• 11 alive edge-neighbours AND 8 alive corner-neighbours ("yn")
• 11 alive edge-neighbours AND 7 alive corner-neighbours AND at least one alive face-neighbour ("ymq", ..., "ymw")

A couple rules about where to insert parenthesis would help. For example, I now understand that "b0123cef" expands to "b(0 | 1 | 2 | 3cef)" which in turn expands to "b(0 | 1 | 2 | 3(c | e | f))", but where do the negatives come in?

You could simplify "bzynmqrtuvw" to "bzynm-p" (which would parse "b(z OR yn OR ym-p)").

Hard to say whether it is worth it to allow more than one negation in a single branch, but e.g. you could simplify "b-zynmqrtuvw" to "b-zynm-p".
Another example: "b2-n-w" would mean "b2 excluding b2n-w", where "b2n-w" in turn would mean "b2n excluding b2nw".
In other words, "b2-n-w" could be rewritten as "b2-npqrtuv" (note that each of 'pqrtuvw' belongs to the category of face-neighbours, unlike '2' and 'n'), or equivalently "b2cefghikmnw" (avoiding negations).

Edit: more examples:

Code: Select all

b0123cef           b(0 OR 1 OR 2 OR 3c OR 3e OR 3f)
b0123cef-w         b(0 OR 1 OR 2 OR 3c OR 3e OR (3f AND NOT 3fw))
b0123ce-wf         b(0 OR 1 OR 2 OR 3c OR (3e AND NOT 3ew) OR 3f)
b0123-cef          b(0 OR 1 OR 2 OR (3 AND NOT (3c OR 3e OR 3f)))
b-0123cef          birth unless (0 OR 1 OR 2 OR 3c OR 3e OR 3f)
b-0123-c-wef-w     birth unless (0 OR 1 OR 2 OR (3 AND NOT ((3c AND NOT 3cw) OR 3e OR (3f AND NOT 3fw))))

[confocaloid]

I think the grammar can be written as follows (please reply if you see any problems with it):

Code: Select all

<E>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "x" | "y" | "z"
<C>  ::= "c" | "e" | "f" | "g" | "h" | "i" | "k" | "m" | "n"
<F>  ::= "p" | "q" | "r" | "t" | "u" | "v" | "w"

<list-3-E>   ::= <E> | <E> <list-3-E>
<list-3-C>   ::= <C> | <C> <list-3-C>
<list-3-F>   ::= <F> | <F> <list-3-F>

<part-2-E>   ::= "" | <list-3-E> | "-" <list-3-E>
<part-2-C>   ::= "" | <list-3-C> | "-" <list-3-C>
<part-2-F>   ::= "" | <list-3-F> | "-" <list-3-F>

<list-2-EC>  ::= <E> <part-2-C> | <E> <part-2-C> <list-2-EC>
<list-2-EF>  ::= <E> <part-2-F> | <E> <part-2-F> <list-2-EF>
<list-2-CE>  ::= <C> <part-2-E> | <C> <part-2-E> <list-2-CE>
<list-2-CF>  ::= <C> <part-2-F> | <C> <part-2-F> <list-2-CF>
<list-2-FE>  ::= <F> <part-2-E> | <F> <part-2-E> <list-2-FE>
<list-2-FC>  ::= <F> <part-2-C> | <F> <part-2-C> <list-2-FC>
<list-2-E>   ::= <list-2-CF> | <list-2-FC>
<list-2-C>   ::= <list-2-EF> | <list-2-FE>
<list-2-F>   ::= <list-2-EC> | <list-2-CE>

<part-1-E>   ::= "" | <list-2-E> | "-" <list-2-E>
<part-1-C>   ::= "" | <list-2-C> | "-" <list-2-C>
<part-1-F>   ::= "" | <list-2-F> | "-" <list-2-F>

<list-1-E>   ::= <E> <part-1-E> | <E> <part-1-E> <list-1-E>
<list-1-C>   ::= <C> <part-1-C> | <C> <part-1-C> <list-1-C>
<list-1-F>   ::= <F> <part-1-F> | <F> <part-1-F> <list-1-F>               
<list-1>     ::= <list-1-E> | <list-1-C> | <list-1-F>

<part-0>     ::= "" | <list-1> | "-" <list-1>
<rulestring> ::= "b" <part-0> "s" <part-0>

A randomly generated rulestring:

Code: Select all

b-u-ch1589ym-049yn-12356xyw-6-fin8zfhins5-m8-rcentmv9x-cqrwk-qyfqtugrvi-pqu

The result:

Code: Select all

b-u-ch1589ym-049yn-12356xyw-6-fin8zfhin
s5-m8-rcentmv9x-cqrwk-qyfqtugrvi-pqu

birth    when  NOT (   u AND NOT (   c
                                  OR h AND (1 OR 5 OR 8 OR 9 OR y)
                                  OR m AND NOT (0 OR 4 OR 9 OR y)
                                  OR n AND NOT (1 OR 2 OR 3 OR 5 OR 6 OR x OR y))
                    OR w AND NOT (   6 AND NOT (f OR i OR n)
                                  OR 8
                                  OR z AND (f OR h OR i OR n)))
survival when     5 AND NOT m
               OR 8 AND NOT (   r AND (c OR e OR n)
                             OR t AND m
                             OR v)
               OR 9
               OR x AND NOT (   c AND (q OR r OR w)
                             OR k AND NOT q)
               OR y AND (   f AND (q OR t OR u)
                         OR g AND (r OR v)
                         OR i AND NOT (p OR q OR u))

[wirehead]

I think the grammar can be written as follows (please reply if you see any problems with it):

Code: Select all

<E>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "x" | "y" | "z"
<C>  ::= "c" | "e" | "f" | "g" | "h" | "i" | "k" | "m" | "n"
<F>  ::= "p" | "q" | "r" | "t" | "u" | "v" | "w"

<list-3-E>   ::= <E> | <E> <list-3-E>
<list-3-C>   ::= <C> | <C> <list-3-C>
<list-3-F>   ::= <F> | <F> <list-3-F>

<part-2-E>   ::= "" | <list-3-E> | "-" <list-3-E>
<part-2-C>   ::= "" | <list-3-C> | "-" <list-3-C>
<part-2-F>   ::= "" | <list-3-F> | "-" <list-3-F>

<list-2-EC>  ::= <E> <part-2-C> | <E> <part-2-C> <list-2-EC>
<list-2-EF>  ::= <E> <part-2-F> | <E> <part-2-F> <list-2-EF>
<list-2-CE>  ::= <C> <part-2-E> | <C> <part-2-E> <list-2-CE>
<list-2-CF>  ::= <C> <part-2-F> | <C> <part-2-F> <list-2-CF>
<list-2-FE>  ::= <F> <part-2-E> | <F> <part-2-E> <list-2-FE>
<list-2-FC>  ::= <F> <part-2-C> | <F> <part-2-C> <list-2-FC>
<list-2-E>   ::= <list-2-CF> | <list-2-FC>
<list-2-C>   ::= <list-2-EF> | <list-2-FE>
<list-2-F>   ::= <list-2-EC> | <list-2-CE>

<part-1-E>   ::= "" | <list-2-E> | "-" <list-2-E>
<part-1-C>   ::= "" | <list-2-C> | "-" <list-2-C>
<part-1-F>   ::= "" | <list-2-F> | "-" <list-2-F>

<list-1-E>   ::= <E> <part-1-E> | <E> <part-1-E> <list-1-E>
<list-1-C>   ::= <C> <part-1-C> | <C> <part-1-C> <list-1-C>
<list-1-F>   ::= <F> <part-1-F> | <F> <part-1-F> <list-1-F>               
<list-1>     ::= <list-1-E> | <list-1-C> | <list-1-F>

<part-0>     ::= "" | <list-1> | "-" <list-1>
<rulestring> ::= "b" <part-0> "s" <part-0>

It looks well-formed off the top of my head.

I'll see what I can do in making a function to actually parse that into an AST with OR and AND nodes.

[wirehead]

Also, sorry for the double post, but I think the terminology here needs to be clarified.

There are 3 types of neighbors, which so far have been called "face", "corner", and "edge", corresponding to neighbors that center-to-center are 1, sqrt(3), and sqrt(2) cells away respectively from the center cell. However, "corner" is a bit confusing. Looking side-on along one of the axes, a sqrt(2) neighbor is on the corner of the square, but most people would say that the corners of the cubes are touching in the case of the sqrt(3) neighbors.

I think the names we should be using are "face", "vertex", and "edge", which seems like the more math-y terms for the relations.

Also, for a name of the string format, who should it be named after? Nasvadi? Confocaloid? Or could we just call it some impersonal thing like "FEVstring"?

[confocaloid]

Also, sorry for the double post, but I think the terminology here needs to be clarified.

My reason for "faces, edges, corners":
"How can I switch 2 yellow corners that are on the same face of a 3x3 cube?"

Or could we just call it some impersonal thing like "FEVstring"?

An impersonal thing would certainly be better. The basic idea of "layer-totalistic" rules is very old (in 2D it can be implemented via weighted neighbourhoods; see also links below). The specific grammar I suggested is just one possibility.

Related:
CWCFSMNCA https://web.archive.org/web/20150422212 ... words.html
A discussion of rule formats https://web.archive.org/web/19990224055 ... /0007.html

[confocaloid]

I think the grammar can be written as follows (please reply if you see any problems with it):

Code: Select all

...

It looks well-formed off the top of my head.

I'll see what I can do in making a function to actually parse that into an AST with OR and AND nodes.

Here is a quick&dirty Python 3 script (non-Golly). It is a REPL to parse and "explain" strings that conform to <part-0> in the grammar above.
Warning/disclaimer: this is not really reusable for parsing, not tested thoroughly, and there are no validity checks. The only purpose of writing this was to double-check that the notation makes sense.

Code: Select all

# Untested, incomplete, almost certainly buggy, you have been warned.
# Permission is hereby granted to reuse this code snippet for any purpose without restriction.
import re

EDGES   = "0123456789xyz"
CORNERS = "cefghikmn"
FACES   = "pqrtuvw"

def test_no_invalid_characters(inp):
   allowed = set(EDGES + CORNERS + FACES + "-")
   invalid = "".join(sorted(set(c for c in inp if c not in allowed)))
   if len(invalid) > 0:
      print("invalid characters: [{}]'".format(invalid))
      return False
   return True

def read_part2(inp, level2, level1):
   if len(inp) == 0:
      return (False, ())
   neg = False
   if inp[0] == "-":
      neg = True
      inp = inp[1:]
      if len(inp) == 0:
         return None
   for case in [EDGES, CORNERS, FACES]:
      if (case != level1) and (case != level2) and (inp[0] in case):
        return (neg, tuple(inp))
   return None

def read_list2(inp, level2, level1):
   pat = ""
   for case in [EDGES, CORNERS, FACES, "-"]:
      if (case != level1) and (case != level2):
         pat = pat + case
   pat = "([{}])([{}]*)".format(level2, pat)
   ans = []
   for m in re.finditer(pat, inp):
      p = read_part2(m.group(2), level2, level1)
      if p is None:
         return None
      ans.append((m.group(1), p))
   return tuple(ans)

def read_part1(inp, level1):
   if len(inp) == 0:
      return (False, ())
   neg = False
   if inp[0] == "-":
      neg = True
      inp = inp[1:]
      if len(inp) == 0:
         return None
   for case in [EDGES, CORNERS, FACES]:
      if (case != level1) and (inp[0] in case):
        ans = read_list2(inp, case, level1)
        if ans is None:
           return None
        return (neg, ans)
   return None

def read_list1(inp, level1):
   pat = ""
   for case in [EDGES, CORNERS, FACES, "-"]:
      if case != level1:
         pat = pat + case
   pat = "([{}])([{}]*)".format(level1, pat)
   ans = []
   for m in re.finditer(pat, inp):
      p = read_part1(m.group(2), level1)
      if p is None:
         return None
      ans.append((m.group(1), p))
   return tuple(ans)

def read_part0(inp):
   if len(inp) == 0:
      return (False, ())
   neg = False
   if inp[0] == "-":
      neg = True
      inp = inp[1:]
      if len(inp) == 0:
         return None
   for case in [EDGES, CORNERS, FACES]:
      if inp[0] in case:
        ans = read_list1(inp, case)
        if ans is None:
           return None
        return (neg, ans)
   return None

def parse_part0(inp):
   inp = inp.strip().lower()
   if test_no_invalid_characters(inp):
      return read_part0(inp)
   return None

def print_list2(r):
   head, tail = r
   neg, lst = tail
   if len(lst) == 0:
      print("{}".format(head), end = "")
      return
   print("{} AND ".format(head), end = "")
   if neg:
      print("NOT ", end = "")
   print("( {} )".format(" OR ".join(lst)), end = "")

def print_list1(r):
   head, tail = r
   neg, lst = tail
   if len(lst) == 0:
      print("{}".format(head), end = "")
      return
   print("{} AND ".format(head), end = "")
   if neg:
      print("NOT (   ", end = "")
   else:
      print("    (   ", end = "")
   print_list2(lst[0])
   if len(lst) >= 2:
      for l in lst[1:]:
         print("")
         print("                    OR ", end = "")
         print_list2(l)
   print(" )", end = "")

def print_part0(r):
   neg, lst = r
   if len(lst) == 0:
      return
   if neg:
      print(" NOT (   ", end = "")
   else:
      print("         ", end = "")
   print_list1(lst[0])
   if len(lst) >= 2:
      for l in lst[1:]:
         print("")
         print("      OR ", end = "")
         print_list1(l)
   if neg:
      print(" )", end = "")

def help():
   print("Available commands:")
   print("   ? <part-0>           Parse a string")
   print("   exit, quit           Exit the read-eval-print loop")
   print("   help                 Print this help")

def main():
   running = True
   while running:
      print(">>> ", end = "")
      inp = input().strip()
      if inp.startswith("?"):
         ans = parse_part0(inp[1:])
         if ans is None:
            print("invalid input")
         else:
            print_part0(ans)
            print("")
      elif (inp.lower() == "help"):
         help()
      elif (inp.lower() == "quit") or (inp.lower() == "exit"):
         running = False

main()

Sample session:

Code: Select all

# python3 repldemo.py
>>> help
Available commands:
   ? <part-0>           Parse a string
   exit, quit           Exit the read-eval-print loop
   help                 Print this help
>>> ? 123
         1
      OR 2
      OR 3
>>> ? 1ring2fire
         1 AND     (   r AND ( i OR n OR g ) )
      OR 2 AND     (   f
                    OR i AND ( r )
                    OR e )
>>> ? -u-ch1589ym-049yn-12356xyw-6-fin8zfhin
 NOT (   u AND NOT (   c
                    OR h AND ( 1 OR 5 OR 8 OR 9 OR y )
                    OR m AND NOT ( 0 OR 4 OR 9 OR y )
                    OR n AND NOT ( 1 OR 2 OR 3 OR 5 OR 6 OR x OR y ) )
      OR w AND NOT (   6 AND NOT ( f OR i OR n )
                    OR 8
                    OR z AND ( f OR h OR i OR n ) ) )
>>> ? 5-m8-rcentmv9x-cqrwk-qyfqtugrvi-pqu
         5 AND NOT (   m )
      OR 8 AND NOT (   r AND ( c OR e OR n )
                    OR t AND ( m )
                    OR v )
      OR 9
      OR x AND NOT (   c AND ( q OR r OR w )
                    OR k AND NOT ( q ) )
      OR y AND     (   f AND ( q OR t OR u )
                    OR g AND ( r OR v )
                    OR i AND NOT ( p OR q OR u ) )
>>> ? p0cefghikm1cefghikm2cefghikm3cefghikm4cefghikm5cefghikm6cefghikm7cefghikm8cefghikm9cefghikmxcefghikmycefghikm
         p AND     (   0 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 1 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 2 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 3 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 4 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 5 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 6 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 7 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 8 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR 9 AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR x AND ( c OR e OR f OR g OR h OR i OR k OR m )
                    OR y AND ( c OR e OR f OR g OR h OR i OR k OR m ) )
>>> ? pc0123456789xye0123456789xyf0123456789xyg0123456789xyh0123456789xyi0123456789xyk0123456789xym0123456789xy    
         p AND     (   c AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR e AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR f AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR g AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR h AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR i AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR k AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y )
                    OR m AND ( 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 OR 7 OR 8 OR 9 OR x OR y ) )
>>> ? -zynmqrtuvw
 NOT (   z
      OR y AND     (   n
                    OR m AND ( q OR r OR t OR u OR v OR w ) ) )
>>> exit

[wirehead]

Here is a quick&dirty Python 3 script (non-Golly). It is a REPL to parse and "explain" strings that conform to <part-0> in the grammar above.
Warning/disclaimer: this is not really reusable for parsing, not tested thoroughly, and there are no validity checks. The only purpose of writing this was to double-check that the notation makes sense.

Code: Select all

...

I modified it to print out the rule parsed into a Scheme-ish expression I haven't been able to break it in a way that your explainer can't be broken in, and so far it seems to line up:

Code: Select all

>>> ?1ring2fire
Scheme: (or (and (test '1) (and (test 'r) (or (test 'i) (test 'n) (test 'g)))) (and (test '2) (or (test 'f) (and (test 'i) (test 'r)) (test 'e)))) 
Explanation:
         1 AND     (   r AND ( i OR n OR g ) )
      OR 2 AND     (   f
                    OR i AND ( r )
                    OR e )

See if you can break it and lmk if it ever crashes or produces incorrect output. I still need to revise it to produce the most optimal terms. (It still produces (and X (and Y Z)) when it could be outputting (and X Y Z).)

Here is the script

Code: Select all

# Untested, incomplete, almost certainly buggy, do not reuse, you have been warned.
import re

EDGES = "0123456789xyz"
CORNERS = "cefghikmn"
FACES = "pqrtuvw"


def test_no_invalid_characters(inp):
    allowed = set(EDGES + CORNERS + FACES + "-")
    invalid = "".join(sorted(set(c for c in inp if c not in allowed)))
    if len(invalid) > 0:
        print(f"invalid characters: [{invalid}]")
        return False
    return True


def read_part2(inp, level2, level1):
    if len(inp) == 0:
        return (False, ())
    neg = False
    if inp[0] == "-":
        neg = True
        inp = inp[1:]
        if len(inp) == 0:
            return None
    for case in [EDGES, CORNERS, FACES]:
        if case != level1 and case != level2 and inp[0] in case:
            return (neg, tuple(inp))
    return None


def read_list2(inp, level2, level1):
    pat = ""
    for case in [EDGES, CORNERS, FACES, "-"]:
        if case != level1 and case != level2:
            pat = pat + case
    pat = "([{}])([{}]*)".format(level2, pat)
    ans = []
    for m in re.finditer(pat, inp):
        p = read_part2(m.group(2), level2, level1)
        if p is None:
            return None
        ans.append((m.group(1), p))
    return ans


def read_part1(inp, level1):
    if len(inp) == 0:
        return (False, ())
    neg = False
    if inp[0] == "-":
        neg = True
        inp = inp[1:]
        if len(inp) == 0:
            return None
    for case in [EDGES, CORNERS, FACES]:
        if case != level1 and inp[0] in case:
            ans = read_list2(inp, case, level1)
            if ans is None:
                return None
            return (neg, ans)
    return None


def read_list1(inp, level1):
    others = "".join(filter(lambda z: z != level1,
                     [EDGES, CORNERS, FACES, "-"]))
    pat = f"([{level1}])([{others}]*)"
    ans = []
    for m in re.finditer(pat, inp):
        p = read_part1(m.group(2), level1)
        if p is None:
            return None
        ans.append((m.group(1), p))
    return ans


def read_part0(inp):
    if len(inp) == 0:
        return (False, ())
    neg = False
    if inp[0] == "-":
        neg = True
        inp = inp[1:]
        if len(inp) == 0:
            return None
    for case in [EDGES, CORNERS, FACES]:
        if inp[0] in case:
            ans = read_list1(inp, case)
            if ans is None:
                return None
            return (neg, ans)
    return None


def parse_part0(inp):
    inp = inp.strip().lower()
    if test_no_invalid_characters(inp):
        return read_part0(inp)
    return None


def print_list2(r):
    head, tail = r
    neg, lst = tail
    if len(lst) == 0:
        print("{}".format(head), end="")
        return
    print("{} AND ".format(head), end="")
    if neg:
        print("NOT ", end="")
    print("( {} )".format(" OR ".join(lst)), end="")


def print_list1(r):
    head, tail = r
    neg, lst = tail
    if len(lst) == 0:
        print("{}".format(head), end="")
        return
    print("{} AND ".format(head), end="")
    if neg:
        print("NOT (   ", end="")
    else:
        print("    (   ", end="")
    print_list2(lst[0])
    if len(lst) >= 2:
        for l in lst[1:]:
            print("")
            print("                    OR ", end="")
            print_list2(l)
    print(" )", end="")


def print_part0(r):
    neg, lst = r
    if len(lst) == 0:
        return
    if neg:
        print(" NOT (   ", end="")
    else:
        print("         ", end="")
    print_list1(lst[0])
    if len(lst) >= 2:
        for l in lst[1:]:
            print("")
            print("      OR ", end="")
            print_list1(l)
    if neg:
        print(" )", end="")


def make_bool_term(items, name):
    items = list(filter(None, items))
    if len(items) > 1:
        return "(%s %s)" % (name, " ".join(items))
    if not items:
        return ""
    return items[0]


def make_case(x):
    return "(test '%s)" % x


def to_scheme4(parts):
    if parts:
        return make_bool_term(map(make_case, parts), "or")


def to_scheme3(parts):
    part, (inverted, inner) = parts
    inner = to_scheme4(inner)
    if inverted:
        inner = "(not %s)" % inner
    return make_bool_term((make_case(part), inner), "and")


def to_scheme2(parts):
    inverted, inner = parts
    if not inner:
        return None
    inner = make_bool_term(map(to_scheme3, inner), "or")
    if inverted:
        return "(not %s)" % inner
    return inner


def to_scheme1(part):
    case, next = part
    case = make_bool_term((make_case(case), to_scheme2(next)), "and")
    return case


def to_scheme0(parts):
    inverted, inner = parts
    inner = make_bool_term(map(to_scheme1, inner), "or")
    if inverted:
        return "(not %s)" % inner
    return inner


def help():
    print("Available commands:")
    print("   ? <part-0>           Parse a string")
    print("   exit, quit           Exit the read-eval-print loop")
    print("   help                 Print this help")


def main():
    running = True
    while running:
        print(">>> ", end="")
        inp = input().strip()
        if inp.startswith("?"):
            ans = parse_part0(inp[1:])
            if ans is None:
                print("invalid input")
            else:
                print("Scheme:", to_scheme0(ans), "\nExplanation:")
                print_part0(ans)
                print("")
        elif inp.lower() == "help":
            help()
        elif inp.lower() == "quit" or inp.lower() == "exit":
            running = False


main()

[confocaloid]

See if you can break it and lmk if it ever crashes or produces incorrect output.

One thing that I noticed is that entering the empty string causes "IndexError: list index out of range". (Empty string would be valid e.g. in a rule without any survival conditions.)