Neighbourhood simplifier

Post by **calcyman** » September 25th, 2016, 1:44 pm

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

Code: Select all

# neighborhood-simplifier-Python3.py
import golly as g
import hashlib

magic_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 range(512):
    x = 5 * (i & 31)
    y = 5 * (i >> 5)
    for u in range(3):
        for v in range(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 range(512)]
rulename = 'Moore2vn-' + hashlib.sha256(repr(tt).encode()).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 range(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 range(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 range(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()

Original Python2 version:

Code: Select all

# neighborhood-simplifier-Python2.py
import golly as g
import hashlib

magic_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:

Code: Select all

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.

Post by **dvgrn** » September 26th, 2016, 11:41 am

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?

Post by **calcyman** » September 26th, 2016, 2:30 pm

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.

fluffykitty · Post by **fluffykitty** » December 7th, 2016, 9:54 pm

What does the magic code do?

Saka · Post by **Saka** » December 8th, 2016, 3:09 am

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

Post by **calcyman** » December 8th, 2016, 5:50 am

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:

Code: Select all

a b c
d e f
g 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.

Post by **Andrew** » December 8th, 2016, 8:38 pm

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.

PHPBB12345 · Post by **PHPBB12345** » December 8th, 2016, 11:27 pm

which is Lua version of "Neighbourhood simplifier"?

Post by **Andrew** » December 9th, 2016, 2:24 am

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).

Code: Select all

-- 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]
end
local function sq9(y)
    return sq4(y), sq4(y >> 1), sq4(y >> 3), sq4(y >> 4)
end

if g.numstates() ~= 2 then
    g.exit('Pattern must be 2-state.')
end

-- get current rule, remove any suffix and any slashes
local origrule = g.getrule()
origrule = origrule:match("^(.+):") or origrule
origrule = 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
    end
end
g.run(1)
local tt = {}
for i = 0, 511 do
    tt[#tt+1] = g.getcell(5 * (i & 31) + 1, 5 * (i >> 5) + 1)
end

local rulename = 'Moore2vn-'..origrule

local 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!')
end

g.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)
end
g.fit()

Naszvadi · Post by **Naszvadi** » December 9th, 2016, 2:54 am

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?

Post by **Andrew** » December 9th, 2016, 5:09 am

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.

PHPBB12345 · Post by **PHPBB12345** » December 9th, 2016, 8:11 pm

Code: Select all

@RULE Moore2vn-B3S23
@TABLE
n_states:8
neighborhood:vonNeumann
symmetries:none

000000
070001
007002
077003
000074
070075
007076
077074
000706
070704
007703
077700
000771
070776
007775
077772
000000
010000
021000
031000
002000
012000
023000
033007
040010
050010
061010
041017
042010
052017
063017
043010
064120
044120
035120
005127
066120
046127
034127
004127
014130
064137
055137
025137
016137
066137
054137
024130
006200
016200
024200
034207
003200
013207
020207
030200
046210
056217
064217
044210
043217
053210
060210
040210
061320
041327
036327
006327
065327
045327
032327
002320
011337
061337
056337
026330
015337
065330
052330
022330
000040
010040
021040
031047
002040
012047
023047
033040
040050
050057
061057
041050
042057
052050
063050
043050
064160
044167
035167
005167
066167
046167
034167
004160
014147
064147
055147
025140
016147
066140
054140
024140
006240
016247
024247
034240
003247
013240
020240
030240
046257
056250
064250
044250
043250
053250
060250
040250
061367
041367
036367
006360
065367
045360
032360
002360
011347
061340
056340
026340
015340
065340
052340
022340
000460
010460
021460
031467
002460
012467
023467
033460
040440
050447
061447
041440
042447
052440
063440
043440
064530
044537
035537
005537
066537
046537
034537
004530
014507
064507
055507
025500
016507
066500
054500
024500
006660
016667
024667
034660
003667
013660
020660
030660
046647
056640
064640
044640
043640
053640
060640
040640
061437
041437
036437
006430
065437
045430
032430
002430
011407
061400
056400
026400
015400
065400
052400
022400
000410
010417
021417
031410
002417
012410
023410
033410
040467
050460
061460
041460
042460
052460
063460
043460
064557
044557
035557
005550
066557
046550
034550
004550
014527
064520
055520
025520
016520
066520
054520
024520
006617
016610
024610
034610
003610
013610
020610
030610
046660
056660
064660
044660
043660
053660
060660
040660
061457
041450
036450
006450
065450
045450
032450
002450
011420
061420
056420
026420
015420
065420
052420
022420
000600
010600
021600
031607
002600
012607
023607
033600
040610
050617
061617
041610
042617
052610
063610
043610
064420
044427
035427
005427
066427
046427
034427
004420
014437
064437
055437
025430
016437
066430
054430
024430
006300
016307
024307
034300
003307
013300
020300
030300
046317
056310
064310
044310
043310
053310
060310
040310
061027
041027
036027
006020
065027
045020
032020
002020
011037
061030
056030
026030
015030
065030
052030
022030
000640
010647
021647
031640
002647
012640
023640
033640
040657
050650
061650
041650
042650
052650
063650
043650
064467
044467
035467
005460
066467
046460
034460
004460
014447
064440
055440
025440
016440
066440
054440
024440
006347
016340
024340
034340
003340
013340
020340
030340
046350
056350
064350
044350
043350
053350
060350
040350
061067
041060
036060
006060
065060
045060
032060
002060
011040
061040
056040
026040
015040
065040
052040
022040
000160
010167
021167
031160
002167
012160
023160
033160
040147
050140
061140
041140
042140
052140
063140
043140
064637
044637
035637
005630
066637
046630
034630
004630
014607
064600
055600
025600
016600
066600
054600
024600
006567
016560
024560
034560
003560
013560
020560
030560
046540
056540
064540
044540
043540
053540
060540
040540
061237
041230
036230
006230
065230
045230
032230
002230
011200
061200
056200
026200
015200
065200
052200
022200
000117
010110
021110
031110
002110
012110
023110
033110
040160
050160
061160
041160
042160
052160
063160
043160
064657
044650
035650
005650
066650
046650
034650
004650
014620
064620
055620
025620
016620
066620
054620
024620
006510
016510
024510
034510
003510
013510
020510
030510
046560
056560
064560
044560
043560
053560
060560
040560
061250
041250
036250
006250
065250
045250
032250
002250
011220
061220
056220
026220
015220
065220
052220
022220
000000
100000
200000
300000
400000
500000
600000
700000

@TREE
num_states=8
num_neighbors=4
num_nodes=78
1 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
1 6 1 2 3 4 5 6 7
2 0 1 1 1 1 1 1 2
2 1 1 1 1 1 1 1 1
1 7 1 2 3 4 5 6 7
2 1 1 1 5 1 1 1 1
1 2 1 2 3 4 5 6 7
1 3 1 2 3 4 5 6 7
2 7 1 1 1 1 1 1 8
3 3 4 4 6 4 4 4 9
2 1 5 1 1 1 1 1 1
2 1 1 1 1 5 1 1 1
2 1 1 1 1 1 1 5 1
3 11 4 12 4 4 4 13 4
2 1 5 1 1 5 1 1 1
3 4 4 4 4 11 15 6 4
2 1 1 1 1 1 5 1 1
3 4 4 4 4 4 17 4 4
2 1 1 5 1 1 1 1 1
3 4 4 13 19 4 4 6 4
3 4 4 4 4 4 4 4 4
3 4 4 11 13 4 11 17 4
1 4 1 2 3 4 5 6 7
1 1 1 2 3 4 5 6 7
2 23 1 1 1 1 1 1 24
1 5 1 2 3 4 5 6 7
2 2 1 1 1 1 1 1 26
3 25 4 4 4 4 4 4 27
4 10 14 16 18 20 21 22 28
2 1 1 1 1 1 5 5 1
2 1 1 1 5 1 5 1 1
3 4 12 13 19 30 4 31 4
3 12 4 4 4 4 4 4 4
3 4 4 4 4 17 4 4 4
2 5 1 1 5 1 1 1 1
3 4 35 4 4 12 6 15 4
2 5 1 1 1 1 1 1 1
2 1 5 5 1 1 1 1 1
3 13 6 37 4 15 4 38 4
4 32 33 34 36 39 21 14 21
3 19 4 4 13 6 4 4 4
3 4 12 4 4 4 4 4 4
3 4 4 4 4 4 11 4 4
3 4 13 4 37 19 4 4 4
3 4 11 4 12 13 4 4 4
4 41 42 21 43 44 21 45 21
3 4 4 6 4 15 12 35 4
3 4 4 4 4 17 30 12 4
3 4 37 4 4 4 4 4 4
3 4 12 4 4 11 15 6 4
4 44 21 47 48 49 18 50 21
3 4 37 13 19 4 4 6 4
3 4 12 4 4 30 4 17 4
3 13 4 37 4 17 4 19 4
3 12 6 4 4 15 4 11 4
4 21 52 36 53 14 54 55 21
3 13 4 37 4 4 4 19 4
3 12 4 4 4 4 11 4 4
3 37 4 4 4 4 4 4 4
4 18 57 21 16 58 59 21 21
3 4 37 4 4 4 35 12 4
2 1 1 5 5 5 1 1 1
2 1 5 1 1 5 1 5 1
2 1 5 1 1 1 5 5 1
3 4 62 4 4 63 12 64 4
3 4 12 4 4 11 4 4 4
2 5 1 1 1 5 1 1 1
3 4 67 4 4 30 4 17 4
4 34 44 61 65 66 68 36 21
2 24 1 1 1 1 1 1 23
2 8 1 1 1 1 1 1 1
3 70 4 4 4 4 4 4 71
2 26 1 1 1 1 1 1 2
2 23 1 1 1 1 1 1 7
3 73 4 4 4 4 4 4 74
4 72 21 21 21 21 21 21 75
5 29 40 46 51 56 60 69 76

Post by **Andrew** » January 6th, 2017, 6:06 pm

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.

Post by **dvgrn** » October 25th, 2018, 9:20 am

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; (1.43 KiB) Downloaded 372 times

Post by **calcyman** » October 25th, 2018, 5:01 pm

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.

Post by **dvgrn** » October 25th, 2018, 6:26 pm

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

Code: Select all

x = 1, y = 1, rule = B2-an3-eiky4aiqw5ijnr6ak/S012ik3-acir4kqw5acq6ack7c8
o!

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.

ConwayLife.com

Neighbourhood simplifier

Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier

Re: Neighbourhood simplifier