Lejkin's Polystate Life

For discussion of other cellular automata.
Post Reply
User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Lejkin's Polystate Life

Post by Apple Bottom » September 1st, 2017, 2:50 pm

Last night, I spotted Nicolay Beluchenko's page on polystate Life, as created by Boris Lejkin:
Nicolay Beluchenko wrote: Boris Lejkin has offered the following alternative of Life with several alive states: Rule S23/B3 is fulfilled for cells of each ON state irrespective of others. If the dead cell has 3 neighbours in state A and 3 neighbours in state B birthes of a new cell do not happen.
In other words: each live state, together with the shared dead state, forms its own B3/S23 CA, and if a cell would get born in two different of these state-CAs (which obviously cannot happen: the cell cannot have two states at once in the next generation, at least not until someone comes up with some kind of quantum CA), it gets born in neither.

I thought this was interesting. Golly doesn't support it natively, but it should be easy enough to use RuleLoader, right? But these files will get fairly big as the number of states grows, it's easy to introduce mistakes, and besides, I'm lazy. So I thought, why not have a script generate these?

It didn't stop there; there's no reason to do all this for just Conway Life. The script I'd like to share (attached) therefore generates polystate versions of arbitrary outer-totalistic rules.

To run it, you'll need:
  • Perl;
  • the Algorithm::Combinatorics module, from CPAN;
  • the List::Compare::Functional module, also from CPAN.
Install the CPAN modules the usual way ("cpan install Algorithm::Combinatorics List::Compare::Functional" if your distro doesn't package them), then run the script like this:

Code: Select all

$ perl polystatelife_rule.pl --states 4 --rule b36s125
Creating rule Polystate_B36S125_4...
Writing birth conditions...............................................................
Writing death conditions.................................................................................................................................................................................................................................................................................
Rule written in 0.01 seconds.
I have NOT tested this extensively (and haven't really tested non-Life rules at all), and would NOT AT ALL be surprised if this contains bugs, but the patterns from Beluchenko's page that I tried in Golly with the resulting rules worked.

I'd be very interested to hear feedback. (And to answer the obvious question right away: I don't plan on adapting this to non-totalistic rules, but if you want to do it, consider the script to be GPL3'ed and be my guest.)
Attachments
Polystate_B3S23_3.rule
(1.84 KiB) Downloaded 93 times
polystatelife_rule.zip
(2.78 KiB) Downloaded 67 times
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
toroidalet
Posts: 1035
Joined: August 7th, 2016, 1:48 pm
Location: my computer
Contact:

Re: Lejkin's Polystate Life

Post by toroidalet » September 2nd, 2017, 11:33 am

Synthesis of a 44-cell multistate still life in 12 gliders:

Code: Select all

x = 18, y = 34, rule = Polystate_B3S23_3
15.A$15.A.A$15.2A2$2.A$A.A$.2A4$3.B6.B$4.B6.B$2.3B4.3B$6.B6.B$5.B6.B$
5.3B4.3B3$5.3A4.3A$5.A6.A$6.A6.A$2.3A4.3A$4.A6.A$3.A6.A4$.2B$B.B$2.B
2$15.2B$15.B.B$15.B!
"Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life."

-Terry Pratchett

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Lejkin's Polystate Life

Post by Apple Bottom » September 2nd, 2017, 4:01 pm

toroidalet wrote:Synthesis of a 44-cell multistate still life in 12 gliders:
Hey, cool! Now all we need is support for these rules in apgsearch. ;)

BTW, I noticed that more people grabbed the example rule file I included than the script itself, so in order to make it easier for people to explore these rules I've included all the generated rules files for B3/S23, up to 10 states.[1]

If anyone would like to see a different file, say for a different base rule or using a different number of states, but cannot run the script for whatever reason, let me know and I'll generate it.

1. This is an archive-within-an-archive, apologies for that. The reason is simply that the forum will allow neither a) xz-compressed files, nor b) files over 256 KB (the ZIP archive was 710). Talk about tools working against rather than for the user!
Attachments
Polystate_B3S23_3-10.zip
(141.53 KiB) Downloaded 69 times
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

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

Re: Lejkin's Polystate Life

Post by Saka » September 2nd, 2017, 11:13 pm

This might make a synth

Code: Select all

x = 17, y = 14, rule = Polystate_B3S23_3
5.2B$2A3.2B$2A3$3.2A2B$3.2A2B$11.3A$10.A2.A$10.A2.A$11.2A2$15.2A$15.
2A!
Airy Clave White It Nay

Code: Select all

x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!
(Check gen 2)

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

Re: Lejkin's Polystate Life

Post by Andrew » October 8th, 2019, 8:10 pm

Below is a script based on NewCA.lua in Golly 3.3 that can be used to explore Polystate rules. Hit alt-R (option-R on a Mac) to create a random pattern in a random rule.

Save the following script as Polystate.lua:

Code: Select all

--[[
This script lets you explore Boris Lejkin's Polystate CA using
the rule syntax defined by Apple Bottom here:

http://conwaylife.com/forums/viewtopic.php?f=11&t=3078&start=0

Author: Andrew Trevorrow (andrew@trevorrow.com), Oct 2019.
--]]

local g = golly()
local gp = require "gplus"
local split = gp.split
local rand = math.random

require "gplus.NewCA"
SCRIPT_NAME = "Polystate"
DEFAULT_RULE = "Polystate_B3S23_3"
RULE_HELP = [[
This script lets you explore Boris Lejkin's Polystate CA.
Rule strings are of the form Polystate_BbSs_n where
b is the list of birth counts (1 to 8), s is the list of
survival counts (0 to 8), and n is the number of states (2 to 256).
]]

-- the following are non-local so a startup script can change them
DEFWD, DEFHT = 500, 500         -- default grid size
aliases = {}                    -- none for now

--------------------------------------------------------------------------------

NextPattern = function() end    -- set by ParseRule to NextOneState or NextMultiState
local births, survivals         -- set by ParseRule and used in NextPattern

function ParseRule(newrule)
    -- Parse the given rule string.
    -- If valid then return nil, the canonical rule string,
    -- the width and height of the grid, and the number of states.
    -- If not valid then just return an appropriate error message.
    
    if #newrule == 0 then
        newrule = DEFAULT_RULE  -- should be a valid rule!
    else
        -- check for a known alias
        local rule = aliases[newrule]
        if rule then
            newrule = rule
        elseif newrule:find(":") then
            -- try without the suffix
            local p, s = split(newrule,":")
            rule = aliases[p]
            if rule then newrule = rule..":"..s end
        end
    end
    
    local prefix, suffix = split(newrule:upper(),":")
    
    -- check for a valid prefix
    local b, s, n = prefix:match("^POLYSTATE_B([1-8]*)S([0-8]*)_(%d+)$")
    if not (b and s and n) then
        return "The rule syntax must be Polystate_BbSs_n\n"..
               "where b lists the birth counts (1 to 8),\n"..
               "s lists the survival counts (0 to 8),\n"..
               "and n is the number of states (2 to 256)."
    end
    n = tonumber(n)
    if n < 2 or n > 256 then
        return "The number of states must be from 2 to 256."
    end
    
    -- check for a valid suffix like T50 or T50,30
    local wd, ht = DEFWD, DEFHT
    if suffix then
        if suffix:find(",") then
            wd, ht = suffix:match("^T(%d+),(%d+)$")
        else
            wd = suffix:match("^T(%d+)$")
            ht = wd
        end
        wd = tonumber(wd)
        ht = tonumber(ht)
        if wd == nil or ht == nil then
            return "Rule suffix must be Twd,ht or Twd."
        end
    end
    if wd < 10 then wd = 10 elseif wd > 2000 then wd = 2000 end
    if ht < 10 then ht = 10 elseif ht > 2000 then ht = 2000 end
    
    -- given rule is valid
    
    -- set births and survivals for use in NextPattern
    births = {}
    survivals = {}
    local bc, sc = "", ""   -- canonical B and S strings
    for i = 0, 8 do
        if b:find(tostring(i)) then births[i] = 1; bc = bc..i end
        if s:find(tostring(i)) then survivals[i] = 1; sc = sc..i end
    end
    
    if n > 2 then
        NextPattern = NextMultiState
    else
        NextPattern = NextOneState
    end

    -- create the canonical form of the given rule
    local canonrule = "Polystate_B"..bc.."S"..sc.."_"..n..":T"..wd..","..ht
    
    return nil, canonrule, wd, ht, n
end

--------------------------------------------------------------------------------

function NextOneState(currcells, minx, miny, maxx, maxy)
    -- Create the next pattern where currcells is a one-state cell array.
    
    local newcells = {}         -- cell array for the new pattern (one-state)
    local newlen = 0            -- length of newcells
    local ecount = {}           -- keys are x,y coords for empty neighbor counts
    local gridwd = maxx-minx+1
    local get = g.getcell
    
    for i = 1, #currcells, 2 do
        local x = currcells[i]
        local y = currcells[i+1]
        local xm1 = x-1
        local xp1 = x+1
        local ym1 = y-1
        local yp1 = y+1
        
        -- might need to wrap edges
        if xm1 < minx then xm1 = maxx end
        if xp1 > maxx then xp1 = minx end
        if ym1 < miny then ym1 = maxy end
        if yp1 > maxy then yp1 = miny end

        -- calculate offsets needed to create keys for ecount
        local xm1off =  xm1-minx
        local xoff   =  x  -minx
        local xp1off =  xp1-minx
        local ym1off = (ym1-miny) * gridwd
        local yoff   = (y  -miny) * gridwd
        local yp1off = (yp1-miny) * gridwd
        
        local xm1_ym1 = xm1off + ym1off
        local x___ym1 = xoff   + ym1off
        local xp1_ym1 = xp1off + ym1off
        local xm1_y   = xm1off + yoff
        local xp1_y   = xp1off + yoff
        local xm1_yp1 = xm1off + yp1off
        local x___yp1 = xoff   + yp1off
        local xp1_yp1 = xp1off + yp1off
        
        local n = 0
        if get(xm1, ym1) > 0 then n = n + 1 else ecount[xm1_ym1] = (ecount[xm1_ym1] or 0) + 1 end
        if get(x  , ym1) > 0 then n = n + 1 else ecount[x___ym1] = (ecount[x___ym1] or 0) + 1 end
        if get(xp1, ym1) > 0 then n = n + 1 else ecount[xp1_ym1] = (ecount[xp1_ym1] or 0) + 1 end
        if get(xm1, y  ) > 0 then n = n + 1 else ecount[xm1_y  ] = (ecount[xm1_y  ] or 0) + 1 end
        if get(xp1, y  ) > 0 then n = n + 1 else ecount[xp1_y  ] = (ecount[xp1_y  ] or 0) + 1 end
        if get(xm1, yp1) > 0 then n = n + 1 else ecount[xm1_yp1] = (ecount[xm1_yp1] or 0) + 1 end
        if get(x  , yp1) > 0 then n = n + 1 else ecount[x___yp1] = (ecount[x___yp1] or 0) + 1 end
        if get(xp1, yp1) > 0 then n = n + 1 else ecount[xp1_yp1] = (ecount[xp1_yp1] or 0) + 1 end
        if survivals[n] then
            -- this live cell survives
            newlen = newlen+1 ; newcells[newlen] = x
            newlen = newlen+1 ; newcells[newlen] = y
        end
    end
    
    -- now add births to newcells using the empty neighbor counts created above
    for k,v in pairs(ecount) do
        if births[v] then
            newlen = newlen+1 ; newcells[newlen] = minx + (k % gridwd)
            newlen = newlen+1 ; newcells[newlen] = miny + (k // gridwd)
        end
    end

    -- delete the old pattern and add the new pattern
    g.putcells(currcells, 0, 0, 1, 0, 0, 1, "xor")
    g.putcells(newcells)
    
    return newcells     -- return the new pattern
end

--------------------------------------------------------------------------------

function NextMultiState(currcells, minx, miny, maxx, maxy)
    -- Create the next pattern where currcells is a multi-state cell array.
    
    local newcells = {}         -- cell array for the new pattern (multi-state)
    local newlen = 0            -- length of newcells
    local emptycells = {}       -- keys are x,y coords for empty cells next to at least one live cell
    local gridwd = maxx-minx+1
    local maxstate = g.numstates() - 1
    local get = g.getcell

    local currlen = #currcells  -- multi-state so odd number
    -- ignore any padding int at end of currcells
    if currlen % 3 > 0 then currlen = currlen - 1 end
    
    for i = 1, currlen, 3 do
        local x = currcells[i]
        local y = currcells[i+1]
        local state = currcells[i+2]
        
        local xm1 = x-1
        local xp1 = x+1
        local ym1 = y-1
        local yp1 = y+1
        -- might need to wrap edges
        if xm1 < minx then xm1 = maxx end
        if xp1 > maxx then xp1 = minx end
        if ym1 < miny then ym1 = maxy end
        if yp1 > maxy then yp1 = miny end

        -- calculate offsets needed to create keys for emptycells
        local xm1off =  xm1-minx
        local xoff   =  x  -minx
        local xp1off =  xp1-minx
        local ym1off = (ym1-miny) * gridwd
        local yoff   = (y  -miny) * gridwd
        local yp1off = (yp1-miny) * gridwd
        
        local xm1_ym1 = xm1off + ym1off
        local x___ym1 = xoff   + ym1off
        local xp1_ym1 = xp1off + ym1off
        local xm1_y   = xm1off + yoff
        local xp1_y   = xp1off + yoff
        local xm1_yp1 = xm1off + yp1off
        local x___yp1 = xoff   + yp1off
        local xp1_yp1 = xp1off + yp1off
        
        local n1 = get(xm1, ym1)
        local n2 = get(x  , ym1)
        local n3 = get(xp1, ym1)
        local n4 = get(xm1, y  )
        local n5 = get(xp1, y  )
        local n6 = get(xm1, yp1)
        local n7 = get(x  , yp1)
        local n8 = get(xp1, yp1)

        -- count the number of neighbors with the same state
        local n = 0
        if n1 > 0 then if n1 == state then n = n + 1 end else emptycells[xm1_ym1] = 0 end
        if n2 > 0 then if n2 == state then n = n + 1 end else emptycells[x___ym1] = 0 end
        if n3 > 0 then if n3 == state then n = n + 1 end else emptycells[xp1_ym1] = 0 end
        if n4 > 0 then if n4 == state then n = n + 1 end else emptycells[xm1_y  ] = 0 end
        if n5 > 0 then if n5 == state then n = n + 1 end else emptycells[xp1_y  ] = 0 end
        if n6 > 0 then if n6 == state then n = n + 1 end else emptycells[xm1_yp1] = 0 end
        if n7 > 0 then if n7 == state then n = n + 1 end else emptycells[x___yp1] = 0 end
        if n8 > 0 then if n8 == state then n = n + 1 end else emptycells[xp1_yp1] = 0 end
        
        if survivals[n] then
            -- this live cell survives
            newlen = newlen+1 ; newcells[newlen] = x
            newlen = newlen+1 ; newcells[newlen] = y
            newlen = newlen+1 ; newcells[newlen] = state
        end
    end
    
    -- now go thru emptycells and add any births to newcells
    for k,v in pairs(emptycells) do
        local x = minx + (k % gridwd)
        local y = miny + (k // gridwd)
        local xm1 = x-1
        local xp1 = x+1
        local ym1 = y-1
        local yp1 = y+1
        -- might need to wrap edges
        if xm1 < minx then xm1 = maxx end
        if xp1 > maxx then xp1 = minx end
        if ym1 < miny then ym1 = maxy end
        if yp1 > maxy then yp1 = miny end

        local n1 = get(xm1, ym1)
        local n2 = get(x  , ym1)
        local n3 = get(xp1, ym1)
        local n4 = get(xm1, y  )
        local n5 = get(xp1, y  )
        local n6 = get(xm1, yp1)
        local n7 = get(x  , yp1)
        local n8 = get(xp1, yp1)
        
        local scount = {}
        for s = 1, maxstate do
            scount[s] = 0
        end
        if n1 > 0 then scount[n1] = scount[n1] + 1 end
        if n2 > 0 then scount[n2] = scount[n2] + 1 end
        if n3 > 0 then scount[n3] = scount[n3] + 1 end
        if n4 > 0 then scount[n4] = scount[n4] + 1 end
        if n5 > 0 then scount[n5] = scount[n5] + 1 end
        if n6 > 0 then scount[n6] = scount[n6] + 1 end
        if n7 > 0 then scount[n7] = scount[n7] + 1 end
        if n8 > 0 then scount[n8] = scount[n8] + 1 end

        local possible = {}
        local posslen = 0
        for s = 1, maxstate do
            if births[ scount[s] ] then
                -- a possible birth (if it's the only one)
                posslen = posslen + 1
                if posslen > 1 then break end
                possible[posslen] = s
            end
        end
        if posslen == 1 then
            -- we have a birth
            newlen = newlen+1 ; newcells[newlen] = x
            newlen = newlen+1 ; newcells[newlen] = y
            newlen = newlen+1 ; newcells[newlen] = possible[posslen]
        end
    end
    
    if newlen > 0 then
        -- ensure length of newcells is odd
        if newlen & 1 == 0 then newlen = newlen+1 ; newcells[newlen] = 0 end
    end

    -- delete the old pattern and add the new pattern
    g.putcells(currcells, 0, 0, 1, 0, 0, 1, "xor")
    g.putcells(newcells)
    
    return newcells     -- return the new pattern
end

--------------------------------------------------------------------------------

-- override the SetColors function
function SetColors()
    g.setcolors( {0,0,0,0} )                -- state 0 is black
    g.setcolors( {255,255,0, 255,0,0 } )    -- live cells go from yellow to red
end

--------------------------------------------------------------------------------

-- startup script can redefine this
function RandomRule()
    local rand = math.random
    local b = ""
    local s = ""
    for i = 1, 8 do if rand(0,1) > 0 then b = b..i end end
    for i = 0, 8 do if rand(0,1) > 0 then s = s..i end end
    return "Polystate_B"..b.."S"..s.."_"..rand(2,256)
end

--------------------------------------------------------------------------------

-- allow alt-R to create a random pattern with a random rule
local saveHandleKey = HandleKey
function HandleKey(event)
    local _, key, mods = split(event)
    if key == "r" and mods == "alt" then
        SetRule(RandomRule())
        RandomPattern()
    else
        -- pass the event to the original HandleKey
        saveHandleKey(event)
    end
end

--------------------------------------------------------------------------------

-- and away we go...
StartNewCA()

User avatar
toroidalet
Posts: 1035
Joined: August 7th, 2016, 1:48 pm
Location: my computer
Contact:

Re: Lejkin's Polystate Life

Post by toroidalet » October 8th, 2019, 11:52 pm

11G synthesis of Saka's pattern:

Code: Select all

x = 71, y = 60, rule = Polystate_B3S23_3
4$61.B$60.B$60.3B7$4.B$5.B$3.3B$7.B$6.B$6.3B2$.2A$.2A4$3.2A2.2B50.A$
2.A.A2.B.B48.A$4.A2.B50.3A4$35.2B$30.2A3.2B$30.2A3$33.2A2B$33.2A2B3$
36.2A$37.2A$36.A6.3A$43.A$44.A4$50.2A$50.A.A$50.A!
Cool catalysis:

Code: Select all

x = 7, y = 7, rule = Polystate_B3S23_3
.B$2.B2.2B$3B2.2B2$4.A$3.A.A$4.A!
"Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life."

-Terry Pratchett

Post Reply