Interpreting MCell's "general binary" rule family

Has something gone haywire? Let us know about it!
Post Reply
User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Interpreting MCell's "general binary" rule family

Post by Freywa » November 30th, 2018, 11:57 am

Golly 3.0 added support for MAP rules, which vastly extend classical totalistic and isotropic Life-like rules. It turns out that MAP rules are equivalent to MCell's "general binary" rules, but when loading an MCell pattern using one of these rules into Golly the file is rejected because no algorithm can load it.

Thus I make a Golly feature request here:
  • Add support for .mcl files using an MCell "general binary" rule
  • Convert them to MAP rules
  • Reduce them to isotropic/totalistic rules if possible
Here is an MCell file using Just Friends (B2-a/S12, from MCell's pattern archive):

Code: Select all

#MCell 4.00
#GAME General binary
#RULE C0,NM,Sa6ba3bab3a3bab3ab7a3bab3ab7ab15a3bab3ab7ab15ab31a3bab3ab7
#RULE ab15ab31ab63a,B5ab3abb6abbab12abbab3ab24abbab3ab7ab49abab3ab7ab1
#RULE 5ab95a
#BOARD 100x100
#SPEED 0
#WRAP 0
#CCOLORS 2
#D The rule is caled "Just Friends" because new cells are born from a pair
#D of parents, but not from ones which are "too intimate" with each other. 
#D A cell stays alive only if it has 1 or 2 live neighbors (in any position).
#D A cell is born only if it has exactly two live neighbors which are not
#D adjacent vertically or horizontally.
#D 
#D So in the following figure, the central cell is born if there are live
#D cells at any two cells marked ac, ad, ae, af, ag, bd, be, bf, bg, bh,
#D ce, cf, cg, ch, df, dg, dh, eg, eh, or fh.
#D    abc
#D    hid
#D    gfe
#D 
#D The rule has two small period 6 diagonal gliders, an interesting period
#D 236 cyclic oscillator, and a small c/3 orthogonal wickstretcher which
#D show up from random soups.  Lines of cells are stable.  Random soups tend
#D to quickly settle down into small clumps of lines.  But there are lots of
#D spaceships, wickstretchers, rakes, and glider guns which have been built.
#D 
#D Here is a glider loop whose period is not a multiple of the turning
#D oscillator's period! (Is this the first such reaction known in any
#D Life-like rule?)  Here are four gliders circulating with period 408.
#D 
#D David I. Bell, June 2000
#L 20.7A$$23.A$23.A$$21.A3.A$$23.A13$51.A$48.A..A$47.A.A.A$46.A4.A$47.A.A
#L .A$A47.A..A$A3.A36.A9.A$A5.A$A.A38.AA$A5.A$A3.A$A$$34.A$35.AA5$22.AA4.
#L A$28.3A$22.A6$27.A.A$27.A.A$27.A.A$$25.7A
The explanation of the general binary rule format on the MCell page is as follows:
The notation of General binary rules has the "C/N/S/B" form, where:
C - specifies the count of states in the rule (0..C-1).
N - specifies the neighborhood type: NM stands for Moore, NN for von Neumann.
S - specifies the compressed string defining the configurations where a cell survives.
B - specifies the compressed string defining the configurations where a cell is born.

Strings defining S and B parts specify the 0/1 state for every possible configuration. For enumerating all possible neighborhood configurations the "N,NE,E,SE,S,SW,W,NW" order is used. For example S010000...0 means "Survival on an alive N neighbor", B1100...0 means "Birth on no neighbors or on a single N neighbor". To make the S/B strings shorter a simple compression is used. 0s are represented as "a", 1s as "b". 3 and more occurrences of the same character are shortened by specifying the count of occurrences and a character.

Example
"Fallski" rule is defined as follows: "C48,NM,Sb255a,Babb189ab63a".
It has 48 states (0..47) and uses the Moore neighborhood. "Sb255a" means 1 and 255 0s (survival only on no alive neighbors). "Babb189ab63a" means 0,1,1, 189 0s, 1, 63 0s (birth on a single N or NE neighbor, or on W and NW neighbors).
Since Golly supports Generations MAP rules and von Neumann neighbourhoods, we can handle all parameters.

The "LogicRule" in MCell, defined by its general binary rule string

Code: Select all

C0,NM,S256a, B3ababb5abaab4ab3ab23ab16ab14ab15ab32ab62ab63a
is, with one stray transition, equivalent to the isotropic rule B2ae/S.
Last edited by Freywa on November 30th, 2018, 1:21 pm, edited 1 time in total.
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Interpreting MCell's "general binary" rule family

Post by Freywa » November 30th, 2018, 1:00 pm

As an interesting consequence of Golly supporting non-totalistic rules, Banks-I and Banks-III in the default rules collection of Golly are redundant. They are equivalent to the following QuickLife rule strings:

Code: Select all

Banks-I == MAPDhsddw == B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
Banks-III == B2ce3e4jr5cin6-en7c8/S012-ac3-cn4-eikny5-kr67c8
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

User avatar
Andrew
Moderator
Posts: 927
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Interpreting MCell's "general binary" rule family

Post by Andrew » November 30th, 2018, 7:08 pm

Freywa wrote:Add support for .mcl files using an MCell "general binary" rule
Golly already has some support for .mcl files that will help in this case. For example, the Just Friends file you provided can be loaded by Golly if a "#GOLLY B2-a/S12" line is inserted near the top:

Code: Select all

#MCell 4.00
#GOLLY B2-a/S12
#GAME General binary
#RULE C0,NM,Sa6ba3bab3a3bab3ab7a3bab3ab7ab15a3bab3ab7ab15ab31a3bab3ab7
#RULE ab15ab31ab63a,B5ab3abb6abbab12abbab3ab24abbab3ab7ab49abab3ab7ab1
#RULE 5ab95a
#BOARD 100x100
#SPEED 0
#WRAP 0
#CCOLORS 2
#D The rule is caled "Just Friends" because new cells are born from a pair
#D of parents, but not from ones which are "too intimate" with each other. 
#D A cell stays alive only if it has 1 or 2 live neighbors (in any position).
#D A cell is born only if it has exactly two live neighbors which are not
#D adjacent vertically or horizontally.
#D 
#D So in the following figure, the central cell is born if there are live
#D cells at any two cells marked ac, ad, ae, af, ag, bd, be, bf, bg, bh,
#D ce, cf, cg, ch, df, dg, dh, eg, eh, or fh.
#D    abc
#D    hid
#D    gfe
#D 
#D The rule has two small period 6 diagonal gliders, an interesting period
#D 236 cyclic oscillator, and a small c/3 orthogonal wickstretcher which
#D show up from random soups.  Lines of cells are stable.  Random soups tend
#D to quickly settle down into small clumps of lines.  But there are lots of
#D spaceships, wickstretchers, rakes, and glider guns which have been built.
#D 
#D Here is a glider loop whose period is not a multiple of the turning
#D oscillator's period! (Is this the first such reaction known in any
#D Life-like rule?)  Here are four gliders circulating with period 408.
#D 
#D David I. Bell, June 2000
#L 20.7A$$23.A$23.A$$21.A3.A$$23.A13$51.A$48.A..A$47.A.A.A$46.A4.A$47.A.A
#L .A$A47.A..A$A3.A36.A9.A$A5.A$A.A38.AA$A5.A$A3.A$A$$34.A$35.AA5$22.AA4.
#L A$28.3A$22.A6$27.A.A$27.A.A$27.A.A$$25.7A
The same approach is used in the .mcl files in Patterns/WireWorld. The advantage of this scheme is that the same file can be loaded by both Golly and MCell. So rather than wait for Golly to be modified (could be a very long wait!), maybe write a script to insert an appropriate "#GOLLY MAP..." line into all your .mcl files that use "General binary" rules.
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Interpreting MCell's "general binary" rule family

Post by Freywa » December 1st, 2018, 2:59 am

As it turns out, I'm a script kiddie and I wrote this script to auto-convert all the .mcl general binary files:

Code: Select all

#!/usr/bin/env python3.7
from glob import glob
import re
rule_re = re.compile(r"#RULE (.*)")
expansion_re = re.compile("(\d+)([ab])")
nl_re = re.compile(r"\n")
golly_re = re.compile(r"(?<=#GOLLY )(.*)")
b64table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

def replace_with_map(rulestr):
    count, neigh, surv, birth = [part[1:] for part in rulestr.split(',')]
    # expand birth and survival strings
    surv = expansion_re.sub(lambda m: int(m.group(1)) * m.group(2), surv)
    birth = expansion_re.sub(lambda m: int(m.group(1)) * m.group(2), birth)
    if neigh == 'M': # Moore
        bits = [0] * 516
        for n in range(512):
            # MAP bit positions      MCell bit positions
            # 8 7 6                  7 0 1
            # 5 4 3 -> 4'            6 x 2 -> y
            # 2 1 0                  5 4 3
            # MAP 85210367 = MCell 76543210
            map_bits = [n >> i & 1 for i in range(9)] # bits [0, 1, 2, ..., 8]
            mcell_position = sum(map_bits[v] << i for i, v in enumerate([7, 6, 3, 0, 1, 2, 5, 8]))
            bits[n] = 1 if (surv if map_bits[4] else birth)[mcell_position] == 'b' else 0
        mapchars = "".join([b64table[int("".join(str(bit) for bit in t6), 2)] for t6 in zip(*[iter(bits)] * 6)])
    if neigh == 'N': # von Neumann
        bits = [0] * 36
        for n in range(32):
            # MAP bit positions      MCell bit positions
            #   4                      0  
            # 3 2 1 -> 2'            3 x 1 -> y
            #   0                      2  
            # MAP 3014 = MCell 3210
            map_bits = [n >> i & 1 for i in range(5)] # bits [0, 1, 2, 3, 4]
            mcell_position = sum(map_bits[v] << i for i, v in enumerate([4, 1, 0, 3]))
            bits[n] = 1 if (surv if map_bits[2] else birth)[mcell_position] == 'b' else 0
        mapchars = "".join([b64table[int("".join(str(bit) for bit in t6), 2)] for t6 in zip(*[iter(bits)] * 6)])
    return "MAP" + mapchars + ("" if count == '0' else f"/{count}")

# change depending on where those .mcl files are
path_to_files = "/home/parclytaxel/Documents/Computing/golly-3.2-src/cPatterns/GenBinary"

files = glob(path_to_files + "/**/*.mcl", recursive=True)
for f in files:
    with open(f, 'r', encoding="latin-1") as ff: raw = ff.read()
    newstr = replace_with_map("".join(rule_re.findall(raw)))
    if "#GOLLY" in raw:
        processed = golly_re.sub(newstr, raw)
    else:
        processed = nl_re.sub(f"\n#GOLLY {newstr}\n", raw, 1)
    with open(f, 'w') as out: out.write(processed)
And I have found another bug. Golly cannot load this .mcl file (FractalBeads.mcl in the MCell pattern library):

Code: Select all

#MCell 4.00
#GOLLY MAPYAAAAA/4
#GAME General binary
#RULE C4,NN,S16a,Baabab11a
#BOARD 200x200
#SPEED 20
#WRAP 1
#D This CA belongs to a large family of what we might call "Sierpinski rules",
#D in virtue of the fact that they produce structures closely related to the
#D so-called Sierpinski gasket, a well-known classical fractal.
#D This particular rule propagates in the NW direction, but naturally
#D each of its three rotations propagates in a different corner
#D direction.  The considerable transmusical interest of this and other
#D Sierpinski rules has been the occasion for my dabbling with them.
#D 
#D The humble "dot", the simplest of the simple seeds, a font
#D of plenty under some rules and a complete bust under others.
#D ORBIT(FractalBeads) - Our dot initiates a classic Sierpinski dance.
#D (To see the Sierpinski gasket traced out by the "beads", just
#D increase the rule's cellsize.)  A simple transmusical  rendering of
#D the telocycle can be heard at http://jmge.net/camusic.htm.
#D ORBIT(CellFarm) - The planting may be boring but don't miss the
#D harvest :)
#D 
#D John Elliott.
#L A
Golly prints out the warning "Bug in readmcell code!" and then the general "file could not be loaded by any algorithm" warning. If I manually switch to the rule in question – MAPYAAAAA/4 – the program mistakenly adds a V to the end of the rulestring, and I can draw patterns and generate patterns as normal, but when I click the reset button three warnings show up:
  • The first and third warnings read "The rule "MAPYAAAAA/4V" is no longer valid! Using the default rule instead."
  • The second warning is the same "file could not be loaded by any algorithm" one.
Afterwards the rule is reset to the default 12/34/3.

The confusion must have been caused by the simultaneous use of the Generations algorithm, MAP strings and von Neumann neighbourhood – Golly is reading the slash that separates the MAP string from the count of states as another base64 character. This is evidenced by the fact that replacing MAPYAAAAA/4 with other von Neumann-MAP-Generations rulestrings like MAPLELEAF/150 and MAPOxford/3 give exactly the same problems.

(All three attributes must be present for the above bug to show up. Patterns like the one below still work fine:)

Code: Select all

x = 225, y = 113, rule = MAPLELEAF
57o111b57o$57o111b57o$57o111b57o$57o111b57o$57o111b57o$57o111b57o$57o
111b57o$57o111b57o$57o111b57o$57o111b57o$57o55bo55b57o$57o54b3o54b57o$
57o54b3o54b57o$57o53b5o53b57o$57o53b5o53b57o$57o52b7o52b57o$57o52b7o
52b57o$57o51b9o51b57o$57o51b9o51b57o$57o50b11o50b57o$57o49b13o49b57o$
57o49b13o49b57o$57o38bo9b15o9bo38b57o$57o38b3o7b15o7b3o38b57o$57o38b5o
4b17o4b5o38b57o$57o38b7ob19ob7o38b57o$57o38b35o38b57o$57o39b33o39b57o$
57o39b33o39b57o$57o39b33o39b57o$57o39b33o39b57o$57o39b33o39b57o$57o40b
31o40b57o$57o40b31o40b57o$57o40b31o40b57o$57o40b31o40b57o$57o29b2o9b
31o9b2o29b57o$57o28b4o9b29o9b4o28b57o$57o28b4o9b29o9b4o28b57o$57o28b5o
8b29o8b5o28b57o$57o13b4o11b6o7b29o7b6o11b4o13b57o$57o13b8o6b8o6b29o6b
8o6b8o13b57o$57o13b23o5b29o5b23o13b57o$57o14b23o5b27o5b23o14b57o$57o
14b24o4b27o4b24o14b57o$57o14b25o3b27o3b25o14b57o$57o14b26o2b27o2b26o
14b57o$57o15b81o15b57o$57o15b81o15b57o$57o15b81o15b57o$57o16b79o16b57o
$57o16b79o16b57o$57o16b79o16b57o$57o16b79o16b57o$57o17b77o17b57o$57o
16b79o16b57o$57o14b83o14b57o$57o12b87o12b57o$57o11b89o11b57o$57o12b87o
12b57o$57o13b85o13b57o$57o14b83o14b57o$57o15b81o15b57o$57o17b77o17b57o
$57o18b75o18b57o$57o19b73o19b57o$57o20b71o20b57o$57o22b67o22b57o$57o
23b65o23b57o$57o24b63o24b57o$57o25b61o25b57o$57o26b59o26b57o$57o28b55o
28b57o$57o29b53o29b57o$57o30b51o30b57o$57o31b49o31b57o$57o32b47o32b57o
$57o33b45o33b57o$57o33b45o33b57o$57o33b45o33b57o$57o32b47o32b57o$57o
32b47o32b57o$57o32b20ob5ob20o32b57o$57o32b13o9b3o9b13o32b57o$57o31b7o
16b3o16b7o31b57o$57o54b3o54b57o$57o54b3o54b57o$57o54b3o54b57o$57o54b3o
54b57o$57o54b3o54b57o$57o54b3o54b57o$57o54b3o54b57o$57o54b3o54b57o$57o
54b3o54b57o$57o54b3o54b57o$57o54b3o54b57o$57o53b4o54b57o$57o53b4o54b
57o$57o53b4o54b57o$57o53b4o54b57o$57o53b4o54b57o$57o53b5o53b57o$57o53b
5o53b57o$57o53b5o53b57o$57o53b5o53b57o$57o53b5o53b57o$57o111b57o$57o
111b57o$57o111b57o$57o111b57o$57o111b57o$57o111b57o$57o111b57o!
Attachments
GenBinary.zip
MCell's general binary collection, Golly-readable (except for the bug above in FractalBeads.mcl)
(42.39 KiB) Downloaded 285 times
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

User avatar
rowett
Moderator
Posts: 3814
Joined: January 31st, 2013, 2:34 am
Location: UK
Contact:

Re: Interpreting MCell's "general binary" rule family

Post by rowett » December 1st, 2018, 11:02 am

Freywa wrote:And I have found another bug
Thanks for reporting! I'll fix it shortly.

User avatar
rowett
Moderator
Posts: 3814
Joined: January 31st, 2013, 2:34 am
Location: UK
Contact:

Re: Interpreting MCell's "general binary" rule family

Post by rowett » December 6th, 2018, 3:25 am

rowett wrote:
Freywa wrote:And I have found another bug
Thanks for reporting! I'll fix it shortly.
This has been fixed and will be in the next released build.

Post Reply