## Neighbourhood simplifier

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

### Neighbourhood simplifier

If you have a 2-state Moore-neighbourhood pattern, this Golly script will convert it into an equivalent 8-state 4-neighbour pattern:

`import golly as gimport hashlibmagic_code = (0, 1, 2, 3, 4, 5, 6, 4, 6, 4, 3, 0, 1, 6, 5, 2)sq4 = lambda x : magic_code[(x & 3) | ((x >> 1) & 12)]sq9 = lambda y : (sq4(y), sq4(y >> 1), sq4(y >> 3), sq4(y >> 4))if (g.numstates() != 2):    g.exit('Pattern must be 2-state.')clist = g.getcells(g.getrect())g.addlayer()# Construct transition table:for i in xrange(512):    x = 5 * (i & 31)    y = 5 * (i >> 5)    for u in xrange(3):        for v in xrange(3):            g.setcell(x + u, y + v, (i >> (3 * v + u)) & 1)g.run(1)tt = [g.getcell(5 * (i & 31) + 1, 5 * (i >> 5) + 1) for i in xrange(512)]rulename = 'Moore2vn-' + hashlib.sha256(repr(tt)).hexdigest()[:12]with open(g.getdir('rules') + rulename + '.rule', 'w') as f:    f.write('@RULE %s\n' % rulename)    f.write('@TABLE\nn_states:8\nneighborhood:vonNeumann\nsymmetries:none\n\n')    for i in xrange(16):        (a, b, c, d) = (i & 1, (i >> 1) & 1, (i >> 2) & 1, (i >> 3) & 1)        f.write('0%d%d%d%d%d\n' % (7*a, 7*b, 7*d, 7*c, magic_code[i]))    for i in xrange(512):        (a, b, c, d) = sq9(i)        f.write('0%d%d%d%d%d\n' % (a, b, d, c, 7 * tt[i]))    for i in xrange(8):        f.write('%d00000\n' % i)g.new('Converted pattern')g.setrule(rulename)newcells = [(x-y, x+y, 7) for (x, y) in zip(clist[0::2], clist[1::2])]newcells = [x for l in newcells for x in l]if (len(newcells) % 2 == 0):    newcells += [0]g.putcells(newcells)g.fit()`

The resulting rule uses the restricted von Neumann neighbourhood, where a cell (x, y) can only exist at time t if (x, y, t) is even. Consequently, every live cell is always surrounded by 4 dead cells and always dies.

90% of the work in this script went into discovering the single line:

`magic_code = (0, 1, 2, 3, 4, 5, 6, 4, 6, 4, 3, 0, 1, 6, 5, 2)`

via an exhaustive computer search. Up to permuting the digits {1, 2, 3, 4, 5, 6}, there are only 200 distinct 'magic codes' which will work here. This can further be reduced to 25 isomorphism classes under rotations/reflections.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

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

### Re: Neighbourhood simplifier

calcyman wrote:If you have a 2-state Moore-neighbourhood pattern, this Golly script will convert it into an equivalent 8-state 4-neighbour pattern...

Seems to work nicely -- and for non-totalistic rules, too! I only tried a few, but the confidence level goes up quickly when it works for Just Friends and for B2cek3i/S12cei.

So are you back on the track of designing a replicator-metacell using this body-centered cubic lattice method? It would be a lot easier now with single-channel construction toolkits available, or on the way to being available. And it seems as if you've reduced the problem from a 16-state BCC automaton to an 8-state automaton that runs half as fast.

That's if I'm understanding and remembering right -- the 16-state model allowed you to step directly to the next tick, didn't it? I like this system better; it lets simulations look good in Golly, without a symmetry-breaking directional bias where the pattern drifts off diagonally as it evolves.

Might there be a way to do a similar trick with less than eight states?

dvgrn
Moderator

Posts: 5624
Joined: May 17th, 2009, 11:00 pm

### Re: Neighbourhood simplifier

dvgrn wrote:
calcyman wrote:If you have a 2-state Moore-neighbourhood pattern, this Golly script will convert it into an equivalent 8-state 4-neighbour pattern...

Seems to work nicely -- and for non-totalistic rules, too! I only tried a few, but the confidence level goes up quickly when it works for Just Friends and for B2cek3i/S12cei.

Thanks! I have yet to test it on anisotropic rules.

So are you back on the track of designing a replicator-metacell using this body-centered cubic lattice method?

Indeed. The phase detector I posted a while ago is also a prerequisite for building it.

It would be a lot easier now with single-channel construction toolkits available, or on the way to being available. And it seems as if you've reduced the problem from a 16-state BCC automaton to an 8-state automaton that runs half as fast.

...and occupies 4 times the area, yes.

That's if I'm understanding and remembering right -- the 16-state model allowed you to step directly to the next tick, didn't it?

Correct.

I like this system better; it lets simulations look good in Golly, without a symmetry-breaking directional bias where the pattern drifts off diagonally as it evolves.

The 16-state model doesn't have a directional bias, either. But I prefer the 8-state model since it doesn't pack multiple Life cells into a single target cell.

And, in any case, it only takes 1536 bytes to store the transition table as opposed to 16384 bytes.

Might there be a way to do a similar trick with less than eight states?

Not in a precisely analogous way, no. This rule schema was found by an *exhaustive* search.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

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

### Re: Neighbourhood simplifier

What does the magic code do?
I like making rules
fluffykitty

Posts: 573
Joined: June 14th, 2014, 5:03 pm

### Re: Neighbourhood simplifier

I don't understand why anybody would need this but cool
If you're the person that uploaded to Sakagolue illegally, please PM me.
`x = 17, y = 10, rule = B3/S23b2ob2obo5b2o\$11b4obo\$2bob3o2bo2b3o\$bo3b2o4b2o\$o2bo2bob2o3b4o\$bob2obo5bo2b2o\$2b2o4bobo2b3o\$bo3b5ob2obobo\$2bo5bob2o\$4bob2o2bobobo!`

(Check gen 2)

Saka

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

### Re: Neighbourhood simplifier

fluffykitty wrote:What does the magic code do?

It's a way to 'colour' the sixteen 2-by-2 tiles with 7 colours such that a 3-by-3 tile can be completely recovered from just knowing the colours of its four overlapping 2-by-2 corners.

That is to say, the states of all nine cells:

`a b cd e fg h i`

can be deduced from the colours of abde, bcef, degh, and efhi.

Doing this with 6 or fewer colours is absolutely impossible, and with 7 colours is difficult (there are only 200 distinct solutions, or 13 up to rotation/reflection).

Saka wrote:I don't understand why anybody would need this but cool

It makes building metacells easier: instead of having to deal with eight neighbours and the fact that some cells die and others survive, you have a 4-neighbour rule where every live cell dies in the next generation.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

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

### Re: Neighbourhood simplifier

B3/S23 gets converted to Moore2vn-e89a94bff785. Why such a cryptic rule name? Might be nicer to include the original rule in the new name; eg. Moore2vn-B3S23.

Andrew
Moderator

Posts: 742
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

### Re: Neighbourhood simplifier

which is Lua version of "Neighbourhood simplifier"?

PHPBB12345

Posts: 511
Joined: August 5th, 2015, 11:55 pm

### Re: Neighbourhood simplifier

Below is a Lua version of Adam's script. A bit longer but (I think) a bit easier to understand. Note that the new rule includes the original rule as a suffix (minus any colon stuff and any slashes).

`-- Lua version of Adam P. Goucher's neighborhood simplifier.local g = golly()local magic_code = {0, 1, 2, 3, 4, 5, 6, 4, 6, 4, 3, 0, 1, 6, 5, 2}local function sq4(x)    return magic_code[((x & 3) | ((x >> 1) & 12)) + 1]endlocal function sq9(y)    return sq4(y), sq4(y >> 1), sq4(y >> 3), sq4(y >> 4)endif g.numstates() ~= 2 then    g.exit('Pattern must be 2-state.')end-- get current rule, remove any suffix and any slasheslocal origrule = g.getrule()origrule = origrule:match("^(.+):") or origruleorigrule = origrule:gsub("/","")local clist = g.getcells(g.getrect())g.addlayer()-- Construct transition table:for i = 0, 511 do    local x = 5 * (i & 31)    local y = 5 * (i >> 5)    for u = 0, 2 do        for v = 0, 2 do            g.setcell(x + u, y + v, (i >> (3 * v + u)) & 1)        end    endendg.run(1)local tt = {}for i = 0, 511 do    tt[#tt+1] = g.getcell(5 * (i & 31) + 1, 5 * (i >> 5) + 1)endlocal rulename = 'Moore2vn-'..origrulelocal f = io.open(g.getdir('rules')..rulename..'.rule', 'w')if f then    f:write('@RULE '..rulename..'\n')    f:write('@TABLE\nn_states:8\nneighborhood:vonNeumann\nsymmetries:none\n\n')    for i = 0, 15 do        local a = i & 1        local b = (i >> 1) & 1        local c = (i >> 2) & 1        local d = (i >> 3) & 1        f:write(string.format('0%d%d%d%d%d\n', 7*a, 7*b, 7*d, 7*c, magic_code[i+1]))    end    for i = 0, 511 do        local a, b, c, d = sq9(i)        f:write(string.format('0%d%d%d%d%d\n', a, b, d, c, 7 * tt[i+1]))    end    for i = 0, 7 do        f:write(i..'00000\n')    end    f:close()else    g.exit('Failed to create .rule file!')endg.new('Converted pattern')g.setrule(rulename)if #clist > 0 then    local newcells = {}    for i = 1, #clist, 2 do        local x = clist[i]        local y = clist[i+1]        newcells[#newcells+1] = x-y        newcells[#newcells+1] = x+y        newcells[#newcells+1] = 7    end    if #newcells % 2 == 0 then        newcells[#newcells+1] = 0    end    g.putcells(newcells)endg.fit()`

Andrew
Moderator

Posts: 742
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

### Re: Neighbourhood simplifier

This is awesome!

Really. I totally agree with the possible usability when constructing unit cells. Cool!

Remark: it is easy to convert a 1D rule with ternary transition function on arbitrary finite element set S - S^3 -> S, to create an equivalent totalistic 1D rule "r" that has the same neighbourhood graph, uses set "T", where \$#T <= (\$#S)*3+1. See my post here with the "tricolouring trick":
http://conwaylife.com/forums/viewtopic.php?f=11&t=2598

And evil questions' time:

What about developing a hexagonal->triangular rule converter?

What about formalizing this method when simplifying mosaics on hyperbolic plane?

W\$((2*n%256)) -> permute+vonNeumann/hexagonal/triangular converter?

Posts: 346
Joined: May 7th, 2016, 8:53 am

### Re: Neighbourhood simplifier

I've edited Adam's script to fix a couple of minor problems:

* Replaced g.error (which doesn't exit the script) with g.exit (which does).

* Used g.numstates to check the number of states rather than the length of clist (which might be empty).

* No need to call g.setlayer after g.addlayer.

Andrew
Moderator

Posts: 742
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

### Re: Neighbourhood simplifier

`@RULE Moore2vn-B3S23@TABLEn_states:8neighborhood:vonNeumannsymmetries:none000000070001007002077003000074070075007076077074000706070704007703077700000771070776007775077772000000010000021000031000002000012000023000033007040010050010061010041017042010052017063017043010064120044120035120005127066120046127034127004127014130064137055137025137016137066137054137024130006200016200024200034207003200013207020207030200046210056217064217044210043217053210060210040210061320041327036327006327065327045327032327002320011337061337056337026330015337065330052330022330000040010040021040031047002040012047023047033040040050050057061057041050042057052050063050043050064160044167035167005167066167046167034167004160014147064147055147025140016147066140054140024140006240016247024247034240003247013240020240030240046257056250064250044250043250053250060250040250061367041367036367006360065367045360032360002360011347061340056340026340015340065340052340022340000460010460021460031467002460012467023467033460040440050447061447041440042447052440063440043440064530044537035537005537066537046537034537004530014507064507055507025500016507066500054500024500006660016667024667034660003667013660020660030660046647056640064640044640043640053640060640040640061437041437036437006430065437045430032430002430011407061400056400026400015400065400052400022400000410010417021417031410002417012410023410033410040467050460061460041460042460052460063460043460064557044557035557005550066557046550034550004550014527064520055520025520016520066520054520024520006617016610024610034610003610013610020610030610046660056660064660044660043660053660060660040660061457041450036450006450065450045450032450002450011420061420056420026420015420065420052420022420000600010600021600031607002600012607023607033600040610050617061617041610042617052610063610043610064420044427035427005427066427046427034427004420014437064437055437025430016437066430054430024430006300016307024307034300003307013300020300030300046317056310064310044310043310053310060310040310061027041027036027006020065027045020032020002020011037061030056030026030015030065030052030022030000640010647021647031640002647012640023640033640040657050650061650041650042650052650063650043650064467044467035467005460066467046460034460004460014447064440055440025440016440066440054440024440006347016340024340034340003340013340020340030340046350056350064350044350043350053350060350040350061067041060036060006060065060045060032060002060011040061040056040026040015040065040052040022040000160010167021167031160002167012160023160033160040147050140061140041140042140052140063140043140064637044637035637005630066637046630034630004630014607064600055600025600016600066600054600024600006567016560024560034560003560013560020560030560046540056540064540044540043540053540060540040540061237041230036230006230065230045230032230002230011200061200056200026200015200065200052200022200000117010110021110031110002110012110023110033110040160050160061160041160042160052160063160043160064657044650035650005650066650046650034650004650014620064620055620025620016620066620054620024620006510016510024510034510003510013510020510030510046560056560064560044560043560053560060560040560061250041250036250006250065250045250032250002250011220061220056220026220015220065220052220022220000000100000200000300000400000500000600000700000@TREEnum_states=8num_neighbors=4num_nodes=781 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 71 6 1 2 3 4 5 6 72 0 1 1 1 1 1 1 22 1 1 1 1 1 1 1 11 7 1 2 3 4 5 6 72 1 1 1 5 1 1 1 11 2 1 2 3 4 5 6 71 3 1 2 3 4 5 6 72 7 1 1 1 1 1 1 83 3 4 4 6 4 4 4 92 1 5 1 1 1 1 1 12 1 1 1 1 5 1 1 12 1 1 1 1 1 1 5 13 11 4 12 4 4 4 13 42 1 5 1 1 5 1 1 13 4 4 4 4 11 15 6 42 1 1 1 1 1 5 1 13 4 4 4 4 4 17 4 42 1 1 5 1 1 1 1 13 4 4 13 19 4 4 6 43 4 4 4 4 4 4 4 43 4 4 11 13 4 11 17 41 4 1 2 3 4 5 6 71 1 1 2 3 4 5 6 72 23 1 1 1 1 1 1 241 5 1 2 3 4 5 6 72 2 1 1 1 1 1 1 263 25 4 4 4 4 4 4 274 10 14 16 18 20 21 22 282 1 1 1 1 1 5 5 12 1 1 1 5 1 5 1 13 4 12 13 19 30 4 31 43 12 4 4 4 4 4 4 43 4 4 4 4 17 4 4 42 5 1 1 5 1 1 1 13 4 35 4 4 12 6 15 42 5 1 1 1 1 1 1 12 1 5 5 1 1 1 1 13 13 6 37 4 15 4 38 44 32 33 34 36 39 21 14 213 19 4 4 13 6 4 4 43 4 12 4 4 4 4 4 43 4 4 4 4 4 11 4 43 4 13 4 37 19 4 4 43 4 11 4 12 13 4 4 44 41 42 21 43 44 21 45 213 4 4 6 4 15 12 35 43 4 4 4 4 17 30 12 43 4 37 4 4 4 4 4 43 4 12 4 4 11 15 6 44 44 21 47 48 49 18 50 213 4 37 13 19 4 4 6 43 4 12 4 4 30 4 17 43 13 4 37 4 17 4 19 43 12 6 4 4 15 4 11 44 21 52 36 53 14 54 55 213 13 4 37 4 4 4 19 43 12 4 4 4 4 11 4 43 37 4 4 4 4 4 4 44 18 57 21 16 58 59 21 213 4 37 4 4 4 35 12 42 1 1 5 5 5 1 1 12 1 5 1 1 5 1 5 12 1 5 1 1 1 5 5 13 4 62 4 4 63 12 64 43 4 12 4 4 11 4 4 42 5 1 1 1 5 1 1 13 4 67 4 4 30 4 17 44 34 44 61 65 66 68 36 212 24 1 1 1 1 1 1 232 8 1 1 1 1 1 1 13 70 4 4 4 4 4 4 712 26 1 1 1 1 1 1 22 23 1 1 1 1 1 1 73 73 4 4 4 4 4 4 744 72 21 21 21 21 21 21 755 29 40 46 51 56 60 69 76`
Last edited by PHPBB12345 on November 11th, 2017, 11:09 am, edited 1 time in total.

PHPBB12345

Posts: 511
Joined: August 5th, 2015, 11:55 pm

### Re: Neighbourhood simplifier

I just discovered that Lua 5.3 supports bitwise operators (which makes it easier to convert Python code to Lua). I've edited the above Lua version of Adam's script to use bitwise operators.

Andrew
Moderator

Posts: 742
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

### Re: Neighbourhood simplifier

Here's a pattern and its associated rule that shows what calcyman's 0E0P metacell test seems to be doing at the moment -- emulating a single cell in B12345678/S012345678.

0e0p-replicator.zip
Single cell replicator, emulated at half speed as 8-state BCC automaton using calcyman's neighborhood-simplifier script

dvgrn
Moderator

Posts: 5624
Joined: May 17th, 2009, 11:00 pm

### Re: Neighbourhood simplifier

dvgrn wrote:Here's a pattern and its associated rule that shows what calcyman's 0E0P metacell test seems to be doing at the moment -- emulating a single cell in B12345678/S012345678.

My test is actually emulating a single cell in B2-an3-eiky4aiqw5ijnr6ak/S012ik3-acir4kqw5acq6ack7c8 -- so it should completely die out.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

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

### Re: Neighbourhood simplifier

calcyman wrote:
dvgrn wrote:Here's a pattern and its associated rule that shows what calcyman's 0E0P metacell test seems to be doing at the moment -- emulating a single cell in B12345678/S012345678.

My test is actually emulating a single cell in B2-an3-eiky4aiqw5ijnr6ak/S012ik3-acir4kqw5acq6ack7c8 -- so it should completely die out.

That's what you seemed to have said when I looked back to October 6th on the Discord thread. But that's

`x = 1, y = 1, rule = B2-an3-eiky4aiqw5ijnr6ak/S012ik3-acir4kqw5acq6ack7c8o!`

which stubbornly fails to die, or do anything interesting at all starting from a single cell, due to the lack of B1 and the presence of S0.

I ran the above through the neighborhood-simplifier script this morning, but just got the expected volatility-1 oscillator -- the pattern goes back to a single metacell every two ticks.

Therefore I remain very puzzled about the current 0E0P test pictured on Discord. It looks to me just like metatick 0.75+ in B12345678/S012345678, starting from one cell... but, um, I've been known to be wrong before, probably more often than I've been right.

EDIT: Yup, I was wrong about the B12345678/S012345678 rule, although the Discord screenshot _is_ exactly what that would look like also. I forgot about the detail that the intermediate-stage child metacells always construct all of the grandchild generation in all directions, and those structures are what accept signals from neighbors and then decide whether they should really be there or not. It seems like a lot of work to go to when apoptosis will usually end up removing most of the new metacells almost as soon as they're created, but it's a lot easier to do the neighbor signalling when there's a mechanism in the right place to collect the information.

The "should completely die out" phrase is a bit misleading -- every metacell dies after every half-metatick (and some of them die sooner than that), but the emulated single B2-an3-eiky4aiqw5ijnr6ak/S012ik3-acir4kqw5acq6ack7c8 cell will keep reappearing in the same location indefinitely.

dvgrn
Moderator

Posts: 5624
Joined: May 17th, 2009, 11:00 pm