Rulesrc: Finding rules for a spaceship

For scripts to aid with computation or simulation in cellular automata.
User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » April 3rd, 2022, 3:32 pm

wwei47 wrote:
April 3rd, 2022, 3:15 pm
LaundryPizza03 wrote:
April 3rd, 2022, 3:07 pm
Then what explains why this object, which is a predecessor to a 3c/10o spaceship, turned up a false positive for c/3o?

Code: Select all

x = 3, y = 3, rule = B012en3ek4ciknqtz5cny8/S02-kn4aeint5ij6k
2bo$o$2bo!
What cycle detection algorithm is rulesrc using?

Code: Select all

# Test a pattern in the given rule to determine if it reappears
def testRule(rulestr):
    r = g.getrect()
    if r:
        g.select(r)
        g.clear(0)
    g.putcells(testPatt)
    g.setrule(rulestr)
    for ii in range(maxGen):
        g.run(1)
        pop = int(g.getpop())
        if (pop < minPop or pop > maxPop):
            break
        elif (pop == testPop):
            # Test for periodicity
            r = g.getrect()
            if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                period = ii+1
                if (r[0] == 0 and r[1] == 0 ):
                    # Oscillator (reject if low period or bOsc is False)
                    if bOsc and period >= minP:
                        return (period, )
                elif ( period >= minShipP ):
                    # Spaceship (reject if low period)
                    return (r[0], r[1], period) 
                break # Pattern is a low period oscillator or spaceship
    return ()
It's clear that there is no phase criterion for B0 rules, but not why it returns false positives.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
wwei47
Posts: 1648
Joined: February 18th, 2021, 11:18 am

Re: Rulesrc: Finding rules for a spaceship

Post by wwei47 » April 3rd, 2022, 3:38 pm

LaundryPizza03 wrote:
April 3rd, 2022, 3:32 pm

Code: Select all

# Test a pattern in the given rule to determine if it reappears
def testRule(rulestr):
    r = g.getrect()
    if r:
        g.select(r)
        g.clear(0)
    g.putcells(testPatt)
    g.setrule(rulestr)
    for ii in range(maxGen):
        g.run(1)
        pop = int(g.getpop())
        if (pop < minPop or pop > maxPop):
            break
        elif (pop == testPop):
            # Test for periodicity
            r = g.getrect()
            if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                period = ii+1
                if (r[0] == 0 and r[1] == 0 ):
                    # Oscillator (reject if low period or bOsc is False)
                    if bOsc and period >= minP:
                        return (period, )
                elif ( period >= minShipP ):
                    # Spaceship (reject if low period)
                    return (r[0], r[1], period) 
                break # Pattern is a low period oscillator or spaceship
    return ()
It's clear that there is no phase criterion for B0 rules, but not why it returns false positives.
What is testPop?
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » April 3rd, 2022, 3:45 pm

wwei47 wrote:
April 3rd, 2022, 3:38 pm
LaundryPizza03 wrote:
April 3rd, 2022, 3:32 pm

Code: Select all

# Test a pattern in the given rule to determine if it reappears
def testRule(rulestr):
    r = g.getrect()
    if r:
        g.select(r)
        g.clear(0)
    g.putcells(testPatt)
    g.setrule(rulestr)
    for ii in range(maxGen):
        g.run(1)
        pop = int(g.getpop())
        if (pop < minPop or pop > maxPop):
            break
        elif (pop == testPop):
            # Test for periodicity
            r = g.getrect()
            if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                period = ii+1
                if (r[0] == 0 and r[1] == 0 ):
                    # Oscillator (reject if low period or bOsc is False)
                    if bOsc and period >= minP:
                        return (period, )
                elif ( period >= minShipP ):
                    # Spaceship (reject if low period)
                    return (r[0], r[1], period) 
                break # Pattern is a low period oscillator or spaceship
    return ()
It's clear that there is no phase criterion for B0 rules, but not why it returns false positives.
What is testPop?
It is the population of the initial pattern.

Code: Select all

# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
wwei47
Posts: 1648
Joined: February 18th, 2021, 11:18 am

Re: Rulesrc: Finding rules for a spaceship

Post by wwei47 » April 3rd, 2022, 3:53 pm

LaundryPizza03 wrote:
April 3rd, 2022, 3:45 pm
It is the population of the initial pattern.

Code: Select all

# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])
Hm. I'm not sure what's going on here. Maybe there's something causing the pattern to be pasted into generation 1?
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » April 3rd, 2022, 4:28 pm

wwei47 wrote:
April 3rd, 2022, 3:53 pm
LaundryPizza03 wrote:
April 3rd, 2022, 3:45 pm
It is the population of the initial pattern.

Code: Select all

# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])
Hm. I'm not sure what's going on here. Maybe there's something causing the pattern to be pasted into generation 1?
Thanks, this is indeed what was happening. This version should fix the bug:

Code: Select all

# Rulesrc.py
#
# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# Updated by: LaundryPizza03, March 2021.
# Updated by: LaundryPizza03, April 2022.
# Grafted by Rhombic, Aug 2017.

import golly as g
import itertools
import random

# Search parameters

# Stop if pattern is a ship with this minimum period
minShipP = 1
# Stop if pattern is an oscillator with this minimum period
minP = 2
# Maximum period to test the pattern for
maxGen = 1000
# Maximum population in any phase
maxPop = 300
# Allow search for oscillators
bOsc = True


import golly as g
from glife import validint

Hensel = [
    ['0'],
    ['1c', '1e'],
    ['2a', '2c', '2e', '2i', '2k', '2n'],
    ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
    ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
    ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
    ['6a', '6c', '6e', '6i', '6k', '6n'],
    ['7c', '7e'],
    ['8']
]

# Python versions < 2.4 don't have "sorted" built-in
try:
    sorted
except NameError:
    def sorted(inlist):
        outlist = list(inlist)
        outlist.sort()
        return outlist

# --------------------------------------------------------------------

def chunks(l, n):
    for i in range(0, len(l), n):
        yield l[i:i+n]

# --------------------------------------------------------------------

def rulestringopt(a):
    result = ''
    context = ''
    lastnum = ''
    lastcontext = ''
    for i in a:
        if i in 'BS':
            context = i
            result += i
        elif i in '012345678':
            if (i == lastnum) and (lastcontext == context):
                pass
            else:
                lastcontext = context
                lastnum = i
                result += i
        else:
            result += i
    result = str.replace(result, '4aceijknqrtwyz', '4')
    result = str.replace(result, '3aceijknqry', '3')
    result = str.replace(result, '5aceijknqry', '5')
    result = str.replace(result, '2aceikn', '2')
    result = str.replace(result, '6aceikn', '6')
    result = str.replace(result, '1ce', '1')
    result = str.replace(result, '7ce', '7')
    return result

clist = []
rule = g.getrule().split(':')[0]

fuzzer = rule + '9'
oldrule = rule
rule = ''
context = ''
deletefrom = []
for i in fuzzer:
    if i == '-':
        deletefrom = [x[1] for x in Hensel[int(context)]]
    elif i in '0123456789/S':
        if deletefrom:
            rule += ''.join(deletefrom)
            deletefrom = []
        context = i
    if len(deletefrom) == 0:
        rule += i
    elif i in deletefrom:
        deletefrom.remove(i)
rule = rule.strip('9')

if not (rule[0] == 'B' and '/S' in rule):
    g.exit('Please set Golly to a Life-like rule.')

if g.empty():
    g.exit('The pattern is empty.')

s = g.getstring('How many generations to remain unchanged:', '', 'Rules calculator')
if not validint(s):
    g.exit('Bad number: %s' % s)

numsteps = int(s)
if numsteps < 1:
    g.exit('Period must be at least 1.')

g.select(g.getrect())
g.copy()
s = int(s)

for i in range(0,s):
    g.run(1)
    clist.append(list(chunks(g.getcells(g.getrect()), 2)))
    mcc = min(clist[i])
    clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

g.show('Processing...')

ruleArr = rule.split('/')
ruleArr[0] = ruleArr[0].lstrip('B')
ruleArr[1] = ruleArr[1].lstrip('S')

b_need = []
b_OK = []
s_need = []
s_OK = []

context = ''
fuzzed = ruleArr[0] + '9'
for i in fuzzed:
    if i in '0123456789':
        if len(context) == 1:
            b_need += Hensel[int(context)]
            b_OK += Hensel[int(context)]
        context = i
    elif context != '':
        b_need.append(context[0] + i)
        b_OK.append(context[0] + i)
        context += context[0]
context = ''
fuzzed = ruleArr[1] + '9'
for i in fuzzed:
    if i in '0123456789':
        if len(context) == 1:
            s_need += Hensel[int(context)]
            s_OK += Hensel[int(context)]
        context = i
    elif context != '':
        s_need.append(context[0] + i)
        s_OK.append(context[0] + i)
        context += context[0]

for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
    if not i in b_OK:
        b_OK.append(i)
        execfor = 1
        # B0 and nontotalistic rulestrings are mutually exclusive
        try:
            g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
        except:
            b_OK.remove(i)
            execfor = 0
        for j in range(0, s * execfor):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    b_OK.remove(i)
                    break
            except:
                b_OK.remove(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        b_OK.sort()

    if not i in s_OK:
        s_OK.append(i)
        execfor = 1
        # B0 and nontotalistic rulestrings are mutually exclusive
        try:
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
        except:
            s_OK.remove(i)
            execfor = 0
        for j in range(0, s * execfor):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    s_OK.remove(i)
                    break
            except:
                s_OK.remove(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        s_OK.sort()

    if i in b_need:
        b_need.remove(i)
        g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
        for j in range(0, s):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    b_need.append(i)
                    break
            except:
                b_need.append(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        b_need.sort()

    if i in s_need:
        s_need.remove(i)
        g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
        for j in range(0, s):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    s_need.append(i)
                    break
            except:
                s_need.append(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        s_need.sort()

g.setrule(oldrule)
ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need)) + \
    ' - B' + ''.join(sorted(b_OK)) + '/S' + ''.join(sorted(s_OK))
g.show(rulestringopt(ruleres))

ruleB="B"+''.join(sorted(b_need))
ruleS="S"+''.join(sorted(s_need))
isotropiclistB = sorted(b_OK)
isotropiclistS = sorted(s_OK)

# Remove B0 and B1 conditions
for wrongvalues in ["0","1c","1e"]:
    if wrongvalues in isotropiclistB:
        isotropiclistB.remove(wrongvalues)

# Generate a random isotropic rule which is likely to allow spaceships to exist
def randIsoRule():
    # Birth conditions
    prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
    rulestr = ruleB
    for elem in isotropiclistB:
        if random.random()<prob: rulestr+=elem
    # Ensure rule has a chance of supporting ships
    if len(rulestr) == 1:
        # Add a random rule element
        rulestr+=random.choice(isotropiclistB)
    if not rulestr[1] in '23':
        # Add two random 2x or 3x rule elements
        rulestr+=random.choice(isotropiclistB[:16])
        rulestr+=random.choice(isotropiclistB[:16])
    
    # Survival conditions (force S0 for dot survival)
    prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
    rulestr+='/'+ruleS
    for elem in isotropiclistS:
        if random.random()<prob: rulestr+=elem
    return(rulestr)
    
# ----------------------------------------------------------

# Return the minimum and maximum of the absolute value of a list of numbers
def minmaxofabs(v):
    v = list(map(abs, v))
    return min(v), max(v)

# Test a pattern in the given rule to determine if it reappears
def testRule(rulestr):
    g.reset() #Prevents pasting in an odd generation
    r = g.getrect()
    if r:
        g.select(r)
        g.clear(0)
    g.putcells(testPatt)
    g.setrule(rulestr)
    for ii in range(maxGen):
        g.run(1)
        pop = int(g.getpop())
        if (pop < minPop or pop > maxPop):
            break
        elif (pop == testPop):
            if ("B0" in rulestr) and int(g.getgen()) % 2 == 1: continue #Odd and even generations are distinct in B0
            # Test for periodicity
            r = g.getrect()
            if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                period = ii+1
                if (r[0] == 0 and r[1] == 0 ):
                    # Oscillator (reject if low period or bOsc is False)
                    if bOsc and period >= minP:
                        return (period, )
                elif ( period >= minShipP ):
                    # Spaceship (reject if low period)
                    return (r[0], r[1], period) 
                break # Pattern is a low period oscillator or spaceship
    return ()
    
# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

if bOsc: minPop = 2 # Patterns with 0, or 1 cells can not be oscillators
else: minPop = 3 # Patterns with 0, 1, or 2 cells can not be ships

g.new('spRulesrc')

for ii in itertools.count(0,1):
    if bOsc==False:
        while 1:
            j=randIsoRule()
            if "1e" in j: break
            if "2a" in j: break
            if "2c" in j: break
            if "3i" in j: break
    else:
        j=randIsoRule()
    result = testRule(j)
    if result:
        # Interesting pattern found
        break
    if (ii % 1000 == 0):
        g.select([])
        g.show('%d candidate rules tested for interesting patterns' % (ii))
        g.update()
        g.new("")
        
g.new('Search result')
if result:
    g.putcells(testPatt)
    if (len(result) == 1):
        # Pattern is an oscillator
        description = 'Found oscillator with period = %d' % result
    elif (len(result) == 3):
        dx, dy, period = result
        dy, dx = minmaxofabs( (dx, dy) )
        if dy == 0:
            description = 'Found orthogonal spaceship with speed = %dc/%d' % (dx, period)
        elif dy == dx:
            description = 'Found diagonal spaceship with speed = %dc/%d' % (dx, period)
        else:
            description = 'Found knightship with speed = (%d, %d)c/%d' % (dx, dy, period)
    else:
        g.exit('Unrecognised pattern')
    g.show(description)
else:
    g.show('No results found')
    

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: Rulesrc: Finding rules for a spaceship

Post by LaundryPizza03 » April 24th, 2022, 2:38 pm

LaundryPizza03 wrote:
April 3rd, 2022, 4:28 pm
wwei47 wrote:
April 3rd, 2022, 3:53 pm
LaundryPizza03 wrote:
April 3rd, 2022, 3:45 pm
It is the population of the initial pattern.

Code: Select all

# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])
Hm. I'm not sure what's going on here. Maybe there's something causing the pattern to be pasted into generation 1?
Thanks, this is indeed what was happening. This version should fix the bug:

Code: Select all

# Rulesrc.py
#
# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# Updated by: LaundryPizza03, March 2021.
# Updated by: LaundryPizza03, April 2022.
# Grafted by Rhombic, Aug 2017.

import golly as g
import itertools
import random

# Search parameters

# Stop if pattern is a ship with this minimum period
minShipP = 1
# Stop if pattern is an oscillator with this minimum period
minP = 2
# Maximum period to test the pattern for
maxGen = 1000
# Maximum population in any phase
maxPop = 300
# Allow search for oscillators
bOsc = True


import golly as g
from glife import validint

Hensel = [
    ['0'],
    ['1c', '1e'],
    ['2a', '2c', '2e', '2i', '2k', '2n'],
    ['3a', '3c', '3e', '3i', '3j', '3k', '3n', '3q', '3r', '3y'],
    ['4a', '4c', '4e', '4i', '4j', '4k', '4n', '4q', '4r', '4t', '4w', '4y', '4z'],
    ['5a', '5c', '5e', '5i', '5j', '5k', '5n', '5q', '5r', '5y'],
    ['6a', '6c', '6e', '6i', '6k', '6n'],
    ['7c', '7e'],
    ['8']
]

# Python versions < 2.4 don't have "sorted" built-in
try:
    sorted
except NameError:
    def sorted(inlist):
        outlist = list(inlist)
        outlist.sort()
        return outlist

# --------------------------------------------------------------------

def chunks(l, n):
    for i in range(0, len(l), n):
        yield l[i:i+n]

# --------------------------------------------------------------------

def rulestringopt(a):
    result = ''
    context = ''
    lastnum = ''
    lastcontext = ''
    for i in a:
        if i in 'BS':
            context = i
            result += i
        elif i in '012345678':
            if (i == lastnum) and (lastcontext == context):
                pass
            else:
                lastcontext = context
                lastnum = i
                result += i
        else:
            result += i
    result = str.replace(result, '4aceijknqrtwyz', '4')
    result = str.replace(result, '3aceijknqry', '3')
    result = str.replace(result, '5aceijknqry', '5')
    result = str.replace(result, '2aceikn', '2')
    result = str.replace(result, '6aceikn', '6')
    result = str.replace(result, '1ce', '1')
    result = str.replace(result, '7ce', '7')
    return result

clist = []
rule = g.getrule().split(':')[0]

fuzzer = rule + '9'
oldrule = rule
rule = ''
context = ''
deletefrom = []
for i in fuzzer:
    if i == '-':
        deletefrom = [x[1] for x in Hensel[int(context)]]
    elif i in '0123456789/S':
        if deletefrom:
            rule += ''.join(deletefrom)
            deletefrom = []
        context = i
    if len(deletefrom) == 0:
        rule += i
    elif i in deletefrom:
        deletefrom.remove(i)
rule = rule.strip('9')

if not (rule[0] == 'B' and '/S' in rule):
    g.exit('Please set Golly to a Life-like rule.')

if g.empty():
    g.exit('The pattern is empty.')

s = g.getstring('How many generations to remain unchanged:', '', 'Rules calculator')
if not validint(s):
    g.exit('Bad number: %s' % s)

numsteps = int(s)
if numsteps < 1:
    g.exit('Period must be at least 1.')

g.select(g.getrect())
g.copy()
s = int(s)

for i in range(0,s):
    g.run(1)
    clist.append(list(chunks(g.getcells(g.getrect()), 2)))
    mcc = min(clist[i])
    clist[i] = [[x[0] - mcc[0], x[1] - mcc[1]] for x in clist[i]]

g.show('Processing...')

ruleArr = rule.split('/')
ruleArr[0] = ruleArr[0].lstrip('B')
ruleArr[1] = ruleArr[1].lstrip('S')

b_need = []
b_OK = []
s_need = []
s_OK = []

context = ''
fuzzed = ruleArr[0] + '9'
for i in fuzzed:
    if i in '0123456789':
        if len(context) == 1:
            b_need += Hensel[int(context)]
            b_OK += Hensel[int(context)]
        context = i
    elif context != '':
        b_need.append(context[0] + i)
        b_OK.append(context[0] + i)
        context += context[0]
context = ''
fuzzed = ruleArr[1] + '9'
for i in fuzzed:
    if i in '0123456789':
        if len(context) == 1:
            s_need += Hensel[int(context)]
            s_OK += Hensel[int(context)]
        context = i
    elif context != '':
        s_need.append(context[0] + i)
        s_OK.append(context[0] + i)
        context += context[0]

for i in [iter2 for iter1 in Hensel for iter2 in iter1]:
    if not i in b_OK:
        b_OK.append(i)
        execfor = 1
        # B0 and nontotalistic rulestrings are mutually exclusive
        try:
            g.setrule(rulestringopt('B' + ''.join(b_OK) + '/S' + ruleArr[1]))
        except:
            b_OK.remove(i)
            execfor = 0
        for j in range(0, s * execfor):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    b_OK.remove(i)
                    break
            except:
                b_OK.remove(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        b_OK.sort()

    if not i in s_OK:
        s_OK.append(i)
        execfor = 1
        # B0 and nontotalistic rulestrings are mutually exclusive
        try:
            g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_OK)))
        except:
            s_OK.remove(i)
            execfor = 0
        for j in range(0, s * execfor):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    s_OK.remove(i)
                    break
            except:
                s_OK.remove(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        s_OK.sort()

    if i in b_need:
        b_need.remove(i)
        g.setrule(rulestringopt('B' + ''.join(b_need) + '/S' + ruleArr[1]))
        for j in range(0, s):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    b_need.append(i)
                    break
            except:
                b_need.append(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        b_need.sort()

    if i in s_need:
        s_need.remove(i)
        g.setrule(rulestringopt('B' + ruleArr[0] + '/S' + ''.join(s_need)))
        for j in range(0, s):
            g.run(1)
            try:
                dlist = list(chunks(g.getcells(g.getrect()), 2))
                mcc = min(dlist)
                dlist = [[x[0] - mcc[0], x[1] - mcc[1]] for x in dlist]
                if not(clist[j] == dlist):
                    s_need.append(i)
                    break
            except:
                s_need.append(i)
                break
        g.new('')
        g.paste(0, 0, 'or')
        g.select(g.getrect())
        s_need.sort()

g.setrule(oldrule)
ruleres = 'B' + ''.join(sorted(b_need)) + '/S' + ''.join(sorted(s_need)) + \
    ' - B' + ''.join(sorted(b_OK)) + '/S' + ''.join(sorted(s_OK))
g.show(rulestringopt(ruleres))

ruleB="B"+''.join(sorted(b_need))
ruleS="S"+''.join(sorted(s_need))
isotropiclistB = sorted(b_OK)
isotropiclistS = sorted(s_OK)

# Remove B0 and B1 conditions
for wrongvalues in ["0","1c","1e"]:
    if wrongvalues in isotropiclistB:
        isotropiclistB.remove(wrongvalues)

# Generate a random isotropic rule which is likely to allow spaceships to exist
def randIsoRule():
    # Birth conditions
    prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
    rulestr = ruleB
    for elem in isotropiclistB:
        if random.random()<prob: rulestr+=elem
    # Ensure rule has a chance of supporting ships
    if len(rulestr) == 1:
        # Add a random rule element
        rulestr+=random.choice(isotropiclistB)
    if not rulestr[1] in '23':
        # Add two random 2x or 3x rule elements
        rulestr+=random.choice(isotropiclistB[:16])
        rulestr+=random.choice(isotropiclistB[:16])
    
    # Survival conditions (force S0 for dot survival)
    prob = random.random()*0.55+0.05 # Random number between 0.05 and 0.6
    rulestr+='/'+ruleS
    for elem in isotropiclistS:
        if random.random()<prob: rulestr+=elem
    return(rulestr)
    
# ----------------------------------------------------------

# Return the minimum and maximum of the absolute value of a list of numbers
def minmaxofabs(v):
    v = list(map(abs, v))
    return min(v), max(v)

# Test a pattern in the given rule to determine if it reappears
def testRule(rulestr):
    g.reset() #Prevents pasting in an odd generation
    r = g.getrect()
    if r:
        g.select(r)
        g.clear(0)
    g.putcells(testPatt)
    g.setrule(rulestr)
    for ii in range(maxGen):
        g.run(1)
        pop = int(g.getpop())
        if (pop < minPop or pop > maxPop):
            break
        elif (pop == testPop):
            if ("B0" in rulestr) and int(g.getgen()) % 2 == 1: continue #Odd and even generations are distinct in B0
            # Test for periodicity
            r = g.getrect()
            if testPatt == g.transform(g.getcells(r),-r[0],-r[1]):
                period = ii+1
                if (r[0] == 0 and r[1] == 0 ):
                    # Oscillator (reject if low period or bOsc is False)
                    if bOsc and period >= minP:
                        return (period, )
                elif ( period >= minShipP ):
                    # Spaceship (reject if low period)
                    return (r[0], r[1], period) 
                break # Pattern is a low period oscillator or spaceship
    return ()
    
# Set up the search with the current pattern
testRect = g.getrect()
testPop = int(g.getpop())
testPatt = g.transform(g.getcells(testRect),-testRect[0],-testRect[1])

if bOsc: minPop = 2 # Patterns with 0, or 1 cells can not be oscillators
else: minPop = 3 # Patterns with 0, 1, or 2 cells can not be ships

g.new('spRulesrc')

for ii in itertools.count(0,1):
    if bOsc==False:
        while 1:
            j=randIsoRule()
            if "1e" in j: break
            if "2a" in j: break
            if "2c" in j: break
            if "3i" in j: break
    else:
        j=randIsoRule()
    result = testRule(j)
    if result:
        # Interesting pattern found
        break
    if (ii % 1000 == 0):
        g.select([])
        g.show('%d candidate rules tested for interesting patterns' % (ii))
        g.update()
        g.new("")
        
g.new('Search result')
if result:
    g.putcells(testPatt)
    if (len(result) == 1):
        # Pattern is an oscillator
        description = 'Found oscillator with period = %d' % result
    elif (len(result) == 3):
        dx, dy, period = result
        dy, dx = minmaxofabs( (dx, dy) )
        if dy == 0:
            description = 'Found orthogonal spaceship with speed = %dc/%d' % (dx, period)
        elif dy == dx:
            description = 'Found diagonal spaceship with speed = %dc/%d' % (dx, period)
        else:
            description = 'Found knightship with speed = (%d, %d)c/%d' % (dx, dy, period)
    else:
        g.exit('Unrecognised pattern')
    g.show(description)
else:
    g.show('No results found')
    
EDIT: Also,lowering the minpop to 1 allows the finding of 1-cell oscillators in B0 rules, such as this p10:

Code: Select all

x = 1, y = 1, rule = B03iq4c5aceky6i/S1e23ek4aeiqrty5-aciq6e7e
o!

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

Post Reply