Rulesrc: Finding rules for a spaceship

For scripts to aid with computation or simulation in cellular automata.
User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Rulesrc: Finding rules for a spaceship

Post by Rhombic » August 14th, 2017, 10:58 am

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


The current version of Rulesrc is in this post:
Re: Rulesrc


Related scripts:
progRulesrc: Progressively broadens search giving good results for high-depth predictions
iterRulesrc: Lists non-equivalent results for highly productive starting patterns (e.g. b-heptomino)
-------------------------------------------------------------------------------------------------------------------
The other way round as usual and with a great filter to reduce the possibilities from all non-totalistic possibilities.
A few months ago this must have been posted by Naszvadi:

Code: Select all

# Rule computation script for use with Golly.
# Author: Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.

# Gives the maximal family of rules that a still life, oscillator, or spaceship
# works under. Must be called while the rule is set of one such family
# For example, to find out what rules a glider works in, first set the rule
# to Life or HighLife, not Seeds.
# Handles nontotalistic rules, too, so it needs Golly 2.8 or newer.

import golly as g
from glife import validint
from string import replace

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 = replace(result, '4aceijknqrtwyz', '4')
    result = replace(result, '3aceijknqry', '3')
    result = replace(result, '5aceijknqry', '5')
    result = replace(result, '2aceikn', '2')
    result = replace(result, '6aceikn', '6')
    result = replace(result, '1ce', '1')
    result = 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('Enter the period:', '', '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))
ruleres = rulestringopt(ruleres)
g.show(ruleres)
Regardless of its initial use, there is a very interesting side use. A partial spaceship-like thing that you have of 3 generations, like, say, this:

Code: Select all

x = 6, y = 7, rule = B3/S23
2b2o$bo2bo$2o2b2o$b4o$bo2bo2$2b2o!
I mean, it clearly doesn't work. However, the same evolution for 3 generations happens with the rules B3aijk/S2aek3aiq - B2cin34ceijknqrtyz5ceijknqry678/S0234ceiknqrwyz5acejknqry6ceik78
In this case that's a lot. In other better examples there will only be about 2000 rules or so.
A script to just evolve the pattern for 1000 generations in every single rule (where those initial steps are preserved) and check whether it's a spaceship, then save it to an output file, seems a very easy way to find new spaceships.
Last edited by Rhombic on October 13th, 2017, 11:32 am, edited 5 times in total.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 14th, 2017, 7:02 pm

Good idea! I bet the output file can also include rules that which it is an oscillator with period, maybe >2. I WOULD write a script but I am currently waiting for school...

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Finding rules for a spaceship

Post by gameoflifemaniac » August 15th, 2017, 7:25 am

Is the script Lua or Python?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 15th, 2017, 7:40 am

gameoflifemaniac wrote:Is the script Lua or Python?
I dont know who you are asking but I will answer it anyway because thats how I roll.
I code in python, but there are useful python to lua converters because they are super similar.

If you are asking about the script in Rhombic's post, it's clearly python.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Finding rules for a spaceship

Post by wildmyron » August 16th, 2017, 3:57 am

This script contains the core of the search script I've been developing to find small spaceships which is what AforAmpere and I have been using to find many of the 3 and 4 cell spaceships in the 5s project thread. It searches through randomly generated isotropic rules to find one in which a given pattern is a spaceship (or optionally an oscillator) and stops when it finds one. A minimum period can be set independently for spaceships and oscillators. The testRule() function in this cut down version does essentially the same as bijoscar() in apgsearch. I did consider changing the pattern equality test to a hash equality test as used in bijoscar(), but the performance difference is pretty small when the population of the pattern of interest is low, particularly as equality tests are pretty rare events in the usual running of this script.

Code: Select all

# searchRules.py  Search for rules in which a given pattern is a spaceship
# Author: Arie Paap, Aug 2017
#
# Search for isotropic rules where a specified pattern is a spaceship or 
# oscillator. Optimised to search rules which are most likely to contain small
# ships. Search ends when a ship is found.

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 = 3
# Maximum period to test the pattern for
maxGen = 1000
# Maximum population in any phase
maxPop = 300
# Allow search for oscillators
bOsc = True

# Generate a random isotropic rule which is likely to allow spaceships to exist
# Adaptation of a script by Dave Green http://conwaylife.com/forums/viewtopic.php?p=43545#p43545
# ----------------------------------------------------------

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

# Remove B0 and B1 conditions
isotropiclistB.remove("0")
isotropiclistB.remove("1c")
isotropiclistB.remove("1e")

# 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 ="B"
    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+='/S'
    # S0 is best used when the test pattern is sparse / has a low population
    if random.random()<0.5: rulestr+='0' 
    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 = map(abs, v)
    return min(v), max(v)

# 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 xrange(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 ()
    
# 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('searchRules')

for ii in itertools.count(0,1):
    result = testRule(randIsoRule())
    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:
In light of AforAwesome's 4-cell B1e ship I'm thinking it might be worth allowing B1e in the random rule generation (perhaps less frequently than other transitions)
Last edited by wildmyron on August 16th, 2017, 4:51 am, edited 1 time in total.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 16th, 2017, 4:20 am

wildmyron wrote:This script contains the core of the search script I've been developing to find small spaceships which is what AforAmpere and I have been using to find many of the 3 and 4 cell spaceships in the 5s project thread...

Code: Select all

script
Ah, I was wondering how AforAmpere was finding those!

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Finding rules for a spaceship

Post by muzik » August 16th, 2017, 7:42 am

Been waiting for that script for a while now.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Finding rules for a spaceship

Post by AforAmpere » August 16th, 2017, 8:10 am

This is actually different than the script I have, in that this one searches for one pattern, but the one I use searches forever, will that one be posted?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 16th, 2017, 8:21 am

AforAmpere wrote:This is actually different than the script I have, in that this one searches for one pattern, but the one I use searches forever, will that one be posted?
Please do post. And can someone make a mod so it searches for a specific speed (like (4,7)3c/56 or something)?

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Finding rules for a spaceship

Post by wildmyron » August 16th, 2017, 10:11 am

AforAmpere wrote:This is actually different than the script I have, in that this one searches for one pattern, but the one I use searches forever, will that one be posted?
I really wanted to clean up the output further before posting it and provide a collection of all the ships found so far along with it, but I think I'll post something before I get to that point (this week - I promise) so everyone can see the results. There really are a lot of small ships in the isotropic rule space and there's no point hiding them.
Saka wrote:Please do post. And can someone make a mod so it searches for a specific speed (like (4,7)3c/56 or something)?
It's not possible to search efficiently for a specific speed with this kind of algorithm - one phase of the ship has to be a predetermined pattern in whichever rule is being tested so unless there just happens to be a rule with that pattern as a ship of that speed nothing will be found. You can of course highlight results that meet certain criteria, and what I'm hoping to do is get this script to a point where it will be able to record improvements to the 5s project whenever they are discovered.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 16th, 2017, 10:13 pm

Idea: The script should see if the rule can actually support ships before testing them.

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

Re: Finding rules for a spaceship

Post by toroidalet » August 16th, 2017, 10:43 pm

How would I make this not find oscillators as well? (The search usually finds oscillators instead of spaceships)
Any sufficiently advanced software is indistinguishable from malice.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 16th, 2017, 10:46 pm

toroidalet wrote:How would I make this not find oscillators as well? (The search usually finds oscillators instead of spaceships)
set bOsc to false

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Finding rules for a spaceship

Post by wildmyron » August 16th, 2017, 11:46 pm

Saka wrote:Idea: The script should see if the rule can actually support ships before testing them.
Do you know of a simple test for this beyond the logic which is already used in the rule generation function? I don't think it would be worthwhile doing this for this version of the script which only tests one pattern in the rule. When testing a set of patterns in each rule it's probably more beneficial.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » August 16th, 2017, 11:50 pm

wildmyron wrote: Do you know of a simple test for this beyond the logic which is already used in the rule generation function? I don't think it would be worthwhile doing this for this version of the script which only tests one pattern in the rule. When testing a set of patterns in each rule it's probably more beneficial.
You could test if the generated rule has one of B2ac3i and one of B2e3a. I dont know how to do this though because I am a python newb and mostly make turtle scripts and number calculators. :| :? (Imagine the 2 smilies as one combination smiley.)

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Finding rules for a spaceship

Post by wildmyron » August 17th, 2017, 1:36 am

Saka wrote:You could test if the generated rule has one of B2ac3i and one of B2e3a.
I remember there being some discussion about required birth conditions for spaceships to exist - can someone point me to where it was? As written, the above condition is too strict. Two counter examples:

Code: Select all

x = 3, y = 3, rule = B2aik/S
obo$2bo$o!

Code: Select all

x = 2, y = 3, rule = B1e5i/S2a
2o$o$2o!
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm

Re: Finding rules for a spaceship

Post by drc » August 17th, 2017, 11:09 am

wildmyron wrote:me to where it was? As written, the above condition is too strict. Two counter examples
Maybe it should be more like this:
Must have at least B2a OR B1e OR ((one or both of B2c3i) AND (one or both of B2e3a))
The first two being both disableable.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Finding rules for a spaceship

Post by Rhombic » August 19th, 2017, 2:11 pm

Interesting script, but its generalist trend has to swim through millions of rules with very different evolutions from the original intention. I'll attempt to use that script and blend it with choices within the allowed B/S conditions to improve the selectivity.

PS. even apart from that first bit, some kind of neighbourhood correlation (heuristic) could be used to optimise the brute-force search; i.e. if you have

Code: Select all

ooo
ooo
oo.
there must be survival conditions.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Finding rules for a spaceship

Post by Rhombic » August 24th, 2017, 10:31 am

YES!
I joined the two scripts together and the results are impressive enough! Now you can tune the search of the spaceships to a more definite set of rules than just "any". Intuition will allow shorter searches. The script could be tuned to attempt to attempt first a higher number of identical generations and then keep cutting down until it just makes a generic search. That should be feasible.

For now, this should be fun enough to play with!

Code: Select all

# Rulesrc.py
#
# Arie Paap, Aug 2017
# Nathaniel Johnston (nathaniel@nathanieljohnston.com), June 2009.
# Updated by: Peter, NASZVADI (), June 2017.
# 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 = 3
# Maximum period to test the pattern for
maxGen = 1000
# Maximum population in any phase
maxPop = 300
# Allow search for oscillators
bOsc = False


import golly as g
from glife import validint
from string import replace

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 = replace(result, '4aceijknqrtwyz', '4')
    result = replace(result, '3aceijknqry', '3')
    result = replace(result, '5aceijknqry', '5')
    result = replace(result, '2aceikn', '2')
    result = replace(result, '6aceikn', '6')
    result = replace(result, '1ce', '1')
    result = 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 = map(abs, v)
    return min(v), max(v)

# 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 xrange(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 ()
    
# 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 "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')

Example: diagonal spaceship found by limiting the evolution of the pre-fleet to that of the initial first 4 generations in CGoL:

Code: Select all

x = 4, y = 4, rule = B2n3-ckny4-aijqt5jkq6aek7c/S23-j4cijtz5-cijy6-n7
2o$obo$b2o$3bo!
Very good results! Here, a shillelagh ship:

Code: Select all

x = 3, y = 5, rule = B3aijr4kt5e6n/S02-n3-eiqy4nz5-einr6-ak7c
2o$obo$2bo$bo$b2o!
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Finding rules for a spaceship

Post by muzik » August 24th, 2017, 1:50 pm

Tried using this script and found my first ship, a 5c/28:

Code: Select all

x = 3, y = 2, rule = B2cen3acr4j5cq7e8/S02-c3cekny4jt5cekn6-ek7e
obo$bo!
This beats the current ship of the respective speed in the 5s project in terms of minimum bounding box:

Code: Select all

x = 4, y = 3, rule = B2cin3ackny4ant5kry6i7e/S02i3r4acjz5qr6n
3bo$o$3bo!

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Finding rules for a spaceship

Post by muzik » August 27th, 2017, 11:24 am

Could the script be changed somehow so that generating at least one set birth condition (B1e, B2a, B2c, B3i) is mandatory?

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Finding rules for a spaceship

Post by Rhombic » September 4th, 2017, 6:04 am

muzik wrote:Could the script be changed somehow so that generating at least one set birth condition (B1e, B2a, B2c, B3i) is mandatory?
It already does! Ironically, this resulted in an even greater enhancement of the searching speed on top of the one achieved by narrowing down the search tree.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Finding rules for a spaceship

Post by muzik » September 4th, 2017, 3:52 pm

Don't really get how that counts as ironic, but okay.

Anyways, can we get a few more people searching to see if this pattern (or derivatives thereof, by placing the blocks farther apart) is a spaceship in any rule, allowing for another adjustable-spaceship-speed rule?

Code: Select all

x = 16, y = 4, rule = B/S012345678
2o$2o4bo7b2o$6b2o6b2o$6bo!

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Finding rules for a spaceship

Post by Saka » September 4th, 2017, 7:12 pm

muzik wrote: Anyways, can we get a few more people searching to see if this pattern
I'll do it today after school

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Finding rules for a spaceship

Post by muzik » September 4th, 2017, 7:22 pm

Yeah I've searched about 20 million rules and no success so far, so maybe stuff needs to be adjusted.

Post Reply