Home  •  LifeWiki  •  Forums  •  Download Golly

## Does anyone have a script for canonising isotropic rules?

For scripts to aid with computation or simulation in cellular automata.

### Does anyone have a script for canonising isotropic rules?

In order to add isotropic rule support to apgluxe, I need a Python script which can:

(a) Convert any rule into canonical form;
(b) Produce the 512-bit transition table.

I understand this already must exist somewhere -- but where?
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

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

### Re: Does anyone have a script for canonising isotropic rules?

calcyman wrote:In order to add isotropic rule support to apgluxe, I need a Python script which can:

(a) Convert any rule into canonical form;
(b) Produce the 512-bit transition table.

I understand this already must exist somewhere -- but where?

I don't know if either one already exists, but here's a solution for (b) I wrote a few days ago to test something:
import re#Binary encoding of each isotropic configuration#Ordering is:#8 1 2#7 0 3#6 5 4#This could probably be changed by bit-shuffling if necessary.transitions = {    '0' : [0],    '1c': [64, 4, 16, 1],    '1e': [128, 2, 32, 8],    '2a': [192, 6, 48, 129, 12, 96, 3, 24],    '2c': [80, 20, 5, 65],    '2e': [160, 10, 40, 130],    '2i': [136, 34],    '2k': [144, 18, 36, 132, 9, 33, 66, 72],    '2n': [68, 17],    '3a': [224, 14, 56, 131],    '3c': [84, 21, 69, 81],    '3e': [168, 42, 138, 162],    '3i': [193, 7, 112, 28],    '3j': [194, 134, 176, 161, 44, 104, 11, 26],    '3k': [164, 74, 41, 146],    '3n': [208, 22, 52, 133, 13, 97, 67, 88],    '3q': [196, 70, 49, 145, 76, 100, 19, 25],    '3r': [200, 38, 50, 137, 140, 98, 35, 152],    '3y': [148, 82, 37, 73],    '4a': [240, 30, 60, 135, 15, 225, 195, 120],    '4c': [85],    '4e': [170],    '4i': [216, 54, 141, 99],    '4j': [202, 166, 178, 169, 172, 106, 43, 154],    '4k': [210, 150, 180, 165, 45, 105, 75, 90],    '4n': [209, 23, 116, 197, 29, 113, 71, 92],    '4q': [228, 78, 57, 147],    '4r': [232, 46, 58, 139, 142, 226, 163, 184],    '4t': [201, 39, 114, 156],    '4w': [198, 177, 108, 27],    '4y': [212, 86, 53, 149, 77, 101, 83, 89],    '4z': [204, 102, 51, 153],    '5a': [241, 31, 124, 199],    '5c': [234, 174, 186, 171],    '5e': [213, 87, 117, 93],    '5i': [248, 62, 143, 227],    '5j': [244, 94, 61, 151, 79, 229, 211, 121],    '5k': [214, 181, 109, 91],    '5n': [242, 158, 188, 167, 47, 233, 203, 122],    '5q': [236, 110, 59, 155, 206, 230, 179, 185],    '5r': [220, 118, 55, 157, 205, 103, 115, 217],    '5y': [218, 182, 173, 107],    '6a': [252, 126, 63, 159, 207, 231, 243, 249],    '6c': [250, 190, 175, 235],    '6e': [245, 95, 125, 215],    '6i': [221, 119],    '6k': [246, 222, 189, 183, 111, 237, 219, 123],    '6n': [238, 187],    '7c': [254, 191, 239, 251],    '7e': [253, 127, 223, 247],    '8' : [255]}transtable = [0]*512rulestring = "B3/S2-i34q" #Or input this somehow#Parse the rulestring:b, s = rulestring.split("/") #Separate B and S transitionsb, s = b[1:], s[1:] #Remove the characters 'B' and 'S'transgroup = re.compile(r"([0-8][a-zA-Z\-]*)") #Matches a group of isotropic transitions sharing the same outer-totalistic countb, s = re.findall(transgroup, b), re.findall(transgroup, s) #Divide into transition groups#Build first half of transition tablefor i in b:    # e.g. B3 or B2-an    if len(i) == 1 or i[1] == "-":        #Set all transitions with the given outer-totalistic count (possibly preemptively)        for j in transitions:            if j[0] == i[0]:                for k in transitions[j]:                    transtable[k] = 1    # e.g. B2ce    else:        #Set all given transitions in group        for j in i[1:]:            for k in transitions[i[0]+j]:                transtable[k] = 1    # e.g. B2-an    if len(i) > 1 and i[1] == "-":        #Unset all given transitions in group        for j in i[2:]:            for k in transitions[i[0]+j]:                transtable[k] = 0#Build second halffor i in s:    # e.g. B3 or B2-an    if len(i) == 1 or i[1] == "-":        #Set all transitions with the given outer-totalistic count (possibly preemptively)        for j in transitions:            if j[0] == i[0]:                for k in transitions[j]:                    transtable[k|256] = 1    # e.g. B2ce    else:        #Set all given transitions in group        for j in i[1:]:            for k in transitions[i[0]+j]:                transtable[k|256] = 1    # e.g. B2-an    if len(i) > 1 and i[1] == "-":        #Unset all given transitions in group        for j in i[2:]:            for k in transitions[i[0]+j]:                transtable[k|256] = 0#Print transition tableprint transtable

It's not fully tested, but it works for tlife at the very least (which was what I was using it for). Hopefully it's acceptable.
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: 1616
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: Does anyone have a script for canonising isotropic rules?

calcyman wrote:(a) Convert any rule into canonical form;
...
I understand this already must exist somewhere -- but where?

Don't think I've seen this as a Python script anywhere (except "Golly Python", that is). But obviously there's canonicalization code built into Golly... and it even has helpful comments! I think you might even call this canonical canonicalization code for isotropic rules. A translation to Python may be slightly painful, but it doesn't look impossible at least.

dvgrn
Moderator

Posts: 4656
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

### Re: Does anyone have a script for canonising isotropic rules?

What is the canonical form?
shouldsee

Posts: 403
Joined: April 8th, 2016, 8:29 am

### Re: Does anyone have a script for canonising isotropic rules?

shouldsee wrote:What is the canonical form?

From the Golly online help:
1. An underscore can be used instead of a slash, but the canonical version always uses a slash.
2. The lowercase letters are listed in alphabetical order. For example, B2nic/S will become B2cin/S.
3. A given rule is converted to its shortest equivalent version. For example, B2ceikn/S will become B2-a/S. If equivalent rules have the same length then the version without the minus sign is preferred. For example, B4-qjrtwz/S will become B4aceikny/S.
4. It's possible for a non-totalistic rule to be converted to a totalistic rule. If you supply all the letters for a specific neighbor count then the canonical version removes the letters. For example, B2aceikn3/S will become B23/S. (Note that B2-3/S is equivalent to B2aceikn3/S so will also become B23/S.)
5. If you supply a minus sign and all the letters for a specific neighbor count then the letters and the neighbor count are removed. For example, B2-aceikn3/S will become B3/S.
rowett
Moderator

Posts: 863
Joined: January 31st, 2013, 2:34 am
Location: UK

### Re: Does anyone have a script for canonising isotropic rules?

Thank you for the explanation, rowett.

I have tried to cut down the dependency of my script but a test set would definitely be helpful.

The script is unfinished:

1. The canonlise() function is not fully implemented yet. Currently no minus sign is allowed.
2. The 102 configurations are yet to be projected back to the original 512 configs. ( preferable as a separate set that deals with bitstrings explicitly, since 102-bitstring is equally legitimate as the 512 one )

kb_2dntca.py
test_alias = 'B13-ce2kS2e'identity = lambda x:xbase2bin=lambda data,scale,num_of_bits: bin(int(data, scale))[2:].zfill(num_of_bits);hex2bin=lambda hexdata,num_of_bits: base2bin(hexdata,16,num_of_bits);bin2hex = lambda bitstr:hex(int(bitstr,2)).lstrip('0x').rstrip('L')import itertools, collections, recount = collections.Counter# import numpy as np# import copy# import random# from astropy.convolution import convolve# convolve_int=lambda a,fir,method:np.around(convolve(a,fir,method)).astype(np.int);# import scipy.ndimage# convolve_int=lambda a,fir,method,**kwargs:scipy.ndimage.filters.convolve(a,fir,mode = method,**kwargs)hensellist=['b0_','b1c','b1e','b2a','b2c','b3i','b2e','b3a','b2k','b3n','b3j','b4a','s0_','s1c','s1e','s2a','s2c','s3i','s2e','s3a','s2k','s3n','s3j','s4a','b2i','b3r','b3e','b4r','b4i','b5i','s2i','s3r','s3e','s4r','s4i','s5i','b2n','b3c','b3q','b4n','b4w','b5a','s2n','s3c','s3q','s4n','s4w','s5a','b3y','b3k','b4k','b4y','b4q','b5j','b4t','b4j','b5n','b4z','b5r','b5q','b6a','s3y','s3k','s4k','s4y','s4q','s5j','s4t','s4j','s5n','s4z','s5r','s5q','s6a','b4e','b5c','b5y','b6c','s4e','s5c','s5y','s6c','b5k','b6k','b6n','b7c','s5k','s6k','s6n','s7c','b4c','b5e','b6e','s4c','s5e','s6e','b6i','b7e','s6i','s7e','b8_','s8_',];henselidx={k: v for v, k in enumerate(hensellist)}rca2ntca=[0, 1, 2, 3, 1, 4, 3, 5, 2, 3, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 13, 16, 15, 17, 14, 15, 18, 19, 20, 21, 22, 23, 2, 8, 6, 10, 3, 9, 7, 11, 24, 25, 26, 27, 25, 28, 27, 29, 14, 20, 18, 22, 15, 21, 19, 23, 30, 31, 32, 33, 31, 34, 33, 35, 1, 4, 8, 9, 36, 37, 38, 39, 3, 5, 10, 11, 38, 39, 40, 41, 13, 16, 20, 21, 42, 43, 44, 45, 15, 17, 22, 23, 44, 45, 46, 47, 8, 48, 49, 50, 38, 51, 52, 53, 25, 54, 55, 56, 57, 58, 59, 60, 20, 61, 62, 63, 44, 64, 65, 66, 31, 67, 68, 69, 70, 71, 72, 73, 2, 8, 24, 25, 8, 48, 25, 54, 6, 10, 26, 27, 49, 50, 55, 56, 14, 20, 30, 31, 20, 61, 31, 67, 18, 22, 32, 33, 62, 63, 68, 69, 6, 49, 26, 55, 10, 50, 27, 56, 26, 55, 74, 75, 55, 76, 75, 77, 18, 62, 32, 68, 22, 63, 33, 69, 32, 68, 78, 79, 68, 80, 79, 81, 3, 9, 25, 28, 38, 51, 57, 58, 7, 11, 27, 29, 52, 53, 59, 60, 15, 21, 31, 34, 44, 64, 70, 71, 19, 23, 33, 35, 65, 66, 72, 73, 10, 50, 55, 76, 40, 82, 59, 83, 27, 56, 75, 77, 59, 83, 84, 85, 22, 63, 68, 80, 46, 86, 72, 87, 33, 69, 79, 81, 72, 87, 88, 89, 1, 36, 8, 38, 4, 37, 9, 39, 8, 38, 49, 52, 48, 51, 50, 53, 13, 42, 20, 44, 16, 43, 21, 45, 20, 44, 62, 65, 61, 64, 63, 66, 3, 38, 10, 40, 5, 39, 11, 41, 25, 57, 55, 59, 54, 58, 56, 60, 15, 44, 22, 46, 17, 45, 23, 47, 31, 70, 68, 72, 67, 71, 69, 73, 4, 37, 48, 51, 37, 90, 51, 91, 9, 39, 50, 53, 51, 91, 82, 92, 16, 43, 61, 64, 43, 93, 64, 94, 21, 45, 63, 66, 64, 94, 86, 95, 9, 51, 50, 82, 39, 91, 53, 92, 28, 58, 76, 83, 58, 96, 83, 97, 21, 64, 63, 86, 45, 94, 66, 95, 34, 71, 80, 87, 71, 98, 87, 99, 3, 38, 25, 57, 9, 51, 28, 58, 10, 40, 55, 59, 50, 82, 76, 83, 15, 44, 31, 70, 21, 64, 34, 71, 22, 46, 68, 72, 63, 86, 80, 87, 7, 52, 27, 59, 11, 53, 29, 60, 27, 59, 75, 84, 56, 83, 77, 85, 19, 65, 33, 72, 23, 66, 35, 73, 33, 72, 79, 88, 69, 87, 81, 89, 5, 39, 54, 58, 39, 91, 58, 96, 11, 41, 56, 60, 53, 92, 83, 97, 17, 45, 67, 71, 45, 94, 71, 98, 23, 47, 69, 73, 66, 95, 87, 99, 11, 53, 56, 83, 41, 92, 60, 97, 29, 60, 77, 85, 60, 97, 85, 100, 23, 66, 69, 87, 47, 95, 73, 99, 35, 73, 81, 89, 73, 99, 89, 101];# rca2ntca=np.array(rca2ntca,np.int);#### Obsolete ####henseldict={'0': ['_'],            '1': ['c', 'e'],            '2': ['a', 'c', 'e', 'k', 'i', 'n'],            '3': ['i', 'a', 'n', 'j', 'r', 'e', 'c', 'q', 'y', 'k'],            '4': ['a', 'r', 'i', 'n', 'w', 'k', 'y', 'q', 't', 'j', 'z', 'e', 'c'],            '5': ['i', 'a', 'j', 'n', 'r', 'q', 'c', 'y', 'k', 'e'],            '6': ['a', 'c', 'k', 'n', 'e', 'i'],            '7': ['c', 'e'],            '8': ['_']}#### New tool ### hensel2ntca = {"b":                {"0": {"_": 0},                 "1": {"c": 1, "e": 2},                 "2": {"a": 3, "c": 4, "e": 6, "k": 8, "i": 24, "n": 36},                 "3": {"i": 5, "a": 7, "n": 9, "j": 10, "r": 25, "e": 26, "c": 37, "q": 38, "y": 48, "k": 49},                 "4": {"a": 11, "r": 27, "i": 28, "n": 39, "w": 40, "k": 50, "y": 51, "q": 52, "t": 54, "j": 55, "z": 57, "e": 74, "c": 90},                 "5": {"i": 29, "a": 41, "j": 53, "n": 56, "r": 58, "q": 59, "c": 75, "y": 76, "k": 82, "e": 91},                 "6": {"a": 60, "c": 77, "k": 83, "n": 84, "e": 92, "i": 96},                 "7": {"c": 85, "e": 97},                 "8": {"_": 100}               },                "s": {"0": {"_": 12},                      "1": {"c": 13, "e": 14},                      "2": {"a": 15, "c": 16, "e": 18, "k": 20, "i": 30, "n": 42},                      "3": {"i": 17, "a": 19, "n": 21, "j": 22, "r": 31, "e": 32, "c": 43, "q": 44, "y": 61, "k": 62},                      "4": {"a": 23, "r": 33, "i": 34, "n": 45, "w": 46, "k": 63, "y": 64, "q": 65, "t": 67, "j": 68, "z": 70, "e": 78, "c": 93},                      "5": {"i": 35, "a": 47, "j": 66, "n": 69, "r": 71, "q": 72, "c": 79, "y": 80, "k": 86, "e": 94},                      "6": {"a": 73, "c": 81, "k": 87, "n": 88, "e": 95, "i": 98},                      "7": {"c": 89, "e": 99},                      "8": {"_": 101}                    }              }subconf='_cekainyqjrtwz';p_NOTnumletter = re.compile(r'[^\da-zA-Z]')   # try:#     from data import *#     with open('tp','rb') as f:  # Python 3: open(..., 'rb')#        hdist, tst_data = pickle.load(f)#        hdist = np.array(hdist).reshape([512,512]);# except:#     print('[WARN]Not finding data.py')def invert(s):    '''    Invert a configuration according to hensel dict    (TBC) To be modified to include "-" sign explicitly    '''    num = s[0]    conf = henseldict[num]    return ''.join([num]+[x for x in conf if x not in s])def padsplit(s,pattern):    '''    Pad a string after index before split    Strip padding after split    '''#     pattern = '([bs])'#     s = test_alias.lower()    s = re.sub( pattern, '\\1 ',s)    lst = re.split( pattern,s)[1:]    return [x.strip() for x in lst]def ntuple(lst,n):    """ntuple([0,3,4,10,2,3], 2) => [(0,3), (4,10), (2,3)]       Group a list into consecutive n-tuples. Incomplete tuples are    discarded e.g.       >>> group(range(10), 3)    [(0, 1, 2), (3, 4, 5), (6, 7, 8)]        Source: http://code.activestate.com/recipes/303060-group-a-list-into-sequential-n-tuples/    """       return zip(*[lst[i::n] for i in range(n)])class kb_2dntca():    def __init__(self):        self.familyname='2dntca'        pass    def rulestr2alias(self, rulestr):        OUT = ''        # rulestr =  '000000000060031c61c67f86a0'        r=hex2bin(rulestr,102);        r=r[::-1];        rule=[i for i,x in enumerate(r) if x=='1'];#         print r        lst = [hensellist[i] for i in rule]        lst.sort()               d = collections.OrderedDict((('b',{}),('s',{}))) ### set default        #### group by B/S        d.update(            {k:list(gp) for k,gp in itertools.groupby(lst, lambda x:x[0])}               )        #### group by number        for k,lst in d.items():            d[k] = {k:list(gp) for k,gp in itertools.groupby(lst, lambda x:x[1])}                   for bs, dd in d.items():            OUT += bs            for k,lst in dd.items():                OUT += k + ''.join( conf[2] for conf in lst)        OUT = OUT.replace('_','')        alias = OUT        return alias    def alias2rulestr(self,alias):        ### Remove any "-" sign        alias = re.sub('(\d-[a-zA-Z]+)',lambda o:invert(o.group()),alias)        #### Remove suffix        alias = alias.split(':')[0]        ##### Remove things like _        alias = p_NOTnumletter.sub( '', alias).lower()        OUT = [0]*102                #### Actual conversion        idxs = []        bsdict = dict(ntuple(padsplit(alias.lower(),'([bs])'),2))        for bs, val in bsdict.items():            numdict = dict(ntuple(padsplit(val,'(\d)'),2))            for num,letters in numdict.items():                candidate = hensel2ntca.get(bs).get(num)                if len(letters)==0:                    idxs += candidate.values()                else:                    idxs += [candidate.get(let) for let in letters]        for i in idxs:            OUT[i] = 1-OUT[i]        bitstr=''.join(map(str,OUT[::-1]));        hexstr = bin2hex(bitstr).zfill(26)        return hexstr    def canonlise(self,alias):        alias = self.rulestr2alias(            self.alias2rulestr(alias)            )        return alias        pass    kb = kb_2dntca()print test_aliasprint kb.canonlise(test_alias)

BTW, should I expect the forum to support syntax highlighting?
shouldsee

Posts: 403
Joined: April 8th, 2016, 8:29 am

### Re: Does anyone have a script for canonising isotropic rules?

shouldsee wrote:The script is unfinished:

1. The canonlise() function is not fully implemented yet. Currently no minus sign is allowed.
2. The 102 configurations are yet to be projected back to the original 512 configs. ( preferable as a separate set that deals with bitstrings explicitly, since 102-bitstring is equally legitimate as the 512 one )

Since I wrote my last answer in this thread I've thrown together a few scripts that do these kinds of conversions.

Unfortunately they're mostly Lua scripts -- but maybe some of the lookup tables buried in them will be helpful anyway. In particular, this script sorts out which positions in the 512-bit string correspond with which isotropic bits.

-- Or at least half of them. Now I don't remember exactly how that script works, if it really does... probably that means I should rewrite it so that I at least can understand what's going on. I only have the "B" 512-bit MAPstring index numbers listed.

The 512-bit MAP string numbers for "S" are just the "B" index numbers plus 16 -- so for S7e, for example, the 512-bit string positions are 383,479,503,509:

{ "7e",367+16,463+16,487+16,493+16}

dvgrn
Moderator

Posts: 4656
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

### Re: Does anyone have a script for canonising isotropic rules?

dvgrn wrote:The 512-bit MAP string numbers for "S" are just the "B" index numbers plus 16 -- so for S7e, for example, the 512-bit string positions are 383,479,503,509:
{ "7e",367+16,463+16,487+16,493+16}

Thank you for the tip on B->S, this would indicates the centre bit is placed at 2^4. Hence I would assume the 512-bit comes from neighbourhood like:

0 1 2
3 4 5
6 7 8

raised to the power of 2? (We need to decide byrow or bycol but for 2dntca it's the same)

Anyway I can add a line to do the 512 conversion, say ntca2mooreca(). ( but please can I advocate for a change from the MAPer to mooreca? ntca2mapper() would make it quite confusing )
shouldsee

Posts: 403
Joined: April 8th, 2016, 8:29 am

### Re: Does anyone have a script for canonising isotropic rules?

shouldsee wrote:Thank you for the tip on B->S, this would indicates the centre bit is placed at 2^4. Hence I would assume the 512-bit comes from neighbourhood like:

0 1 2
3 4 5
6 7 8

raised to the power of 2?

Yes, except in the opposite order. See Rule integer on the LifeWiki.

dvgrn
Moderator

Posts: 4656
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

### Re: Does anyone have a script for canonising isotropic rules?

I should probably mention that I answered my own request about 6 months ago:

https://gitlab.com/apgoucher/lifelib/blob/master/avxlife/ntcanon.py
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

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

Return to Scripts

### Who is online

Users browsing this forum: No registered users and 1 guest