Rulesrc: Finding rules for a spaceship

[Saka]

I have an idea of a script very similar to this but looks for a rule where a pattern becomes another.
If your input pattern is this (Blue=selected)

Code: Select all

x = 10, y = 4, rule = LifeHistory
A2B$3B$B2A5.2A$B2A5.2A!

It will ask you "What is the space between the boxes?", and you enter 5, it will count 5 cells from the right edge of the box and "copy" the selection there:

Code: Select all

x = 11, y = 16, rule = LifeHistory
A2B5.3B$3B5.3B$B2A5D2AB$B2A5.2AB$5.D$4.3D$3.D.D.D$5.D$5.D$5.D2$4.3D$
4.D$4.3D$6.D$4.3D!

Now I know you can't have 2 selections at once, but you can save each selection as a cell list or something.
The script will then take the first selection and run it in a bunch of different rules and try to find it. It would also use the g.note function to note how many generations it takes from pattern a to b.

This could be useful for finding reactions such as

Code: Select all

x = 17, y = 7, rule = LifeHistory
BA5B3.7B$2BA4B3.7B$3A4B3.7B$7B3.7B$7B3.7B$5B2A3.3B2A2B$5B2A3.3B2A2B!

[muzik]

Suggestion: The script could output its results to Catagolue by submitting them under a "rulesrc" pseudosymmetry under the rule the ship was found in.

[Naszvadi]

Greetings!

Neat Rulesrc, grats+thnx!

My attempt to kill the party is a process proposal for a complex glider/osc finder application:

1. generate list of bounded patterns that are sorted (e.g. (greater dim:smaller dim:bitmap-in-integer)
2. 1. iterating on list:recurse on a pattern evolving it and branching on used hensel notatitions between each recursion steps. Stopping criteria is:
   2. reaching maximal recursion depth (pattern with current rulemask remain uncategorized - usually in exploding rules)
   3. evolving into a _smaller_ pattern - e.g. using a function defined at pattern list generation
   4. reaching a loop

This will certainly be faster than inspecting 2**102 rules (excluding some trivial cases, but there would be still exponentially many rules)

Well, I published a pattern generator in the forum, but is still buggy. Its C version is hopefully not

Further improvements may cover automated wikibot feeding, haul comparison input generators etc.

[Rhombic]

Towards a Progressive Rulesrc
A self-correcting Rulesrc would be interesting enough to attempt to find cell configurations, but one of the initial steps is to allow variation in the number of identical generations. Note that this yields similar and not necessarily identical ships, but for many purposes it's good enough. The idealised script should be able to identify good leads, allowing much quicker finds of interesting spaceships from decent inputs.

The following example already gives surprisingly good results for such a terribly hand-waving algorithm!! But I really hope you don't think I'm wasting your time, since it shows how that little addition, still far away from the optimum, already gives promising results.

Code: Select all

# progRulesrc.py
#
# Expanded from Rulesrc by Rhombic, Sep 2017.
# 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
from glife import validint
from string import replace

def Rulesrc(familytree,maxiteration):
    g.select(g.getrect())
    if not g.empty():
        g.clear(0)
    g.putcells(cell_list)
    # 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

    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 = str(familytree)
    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("")
        if ii > maxiteration:
            return
            
    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.exit(description)
    else:
        g.show('No results found')

M=g.getstring('How many generations to use as base:', '', 'Rules calculator')
D=g.getstring('Set depth:','100000')
D=int(D)
cell_list=g.getcells(g.getrect())
while 1:
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-1)),2*D)
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-2)),4*D)
    Rulesrc(M,D)
    M=str(int(M)-1)

After a given depth at a number of generations, it attempts widening the search, then narrowing it*(please read the asterisk later) in case there's a good lead, and otherwise widening it further. This is as bad an implementation of the original idea as I can imagine being possible. I know. It's just to have a preliminary proof of how effective it is nonetheless!

* The way it narrows it back would have been nice if and only if the new attempted nth generation was interesting. This script just does it with whichever rule it got to at generation D, so it has a 1/D chance of having chosen the best one, which really is awful. Optimising this will make results faster by about 2 orders of magnitude, I should imagine.

Proof of Concept and Further Goals
The easiest proof that my idea has any validity whatsoever would be by trying to find copperhead in the discovered phase, with 10 generations in rule B34k/S23. Even a depth 100 immediately gives an answer very quickly (the recommended depth should be higher, in general).
With the original Rulesrc, trying with 8 generations would have yielded nothing and trying with 4 generations would have taken somewhat longer. Bear in mind this was a single-point defect in the rule, so the change won't be as noticeable.
In any case, trying 1D spaceships with a very optimistic number of generations (11-13) and depth of 10000 gave very quick results with minor changes in the evolution.

The main objectives now are the following:
1) to change the number of generations kept in a more justified way than the current absurdity
2) to narrow down in a more justified way, ideally with a scoring system for the failed spaceships
3) to try specific neighbourhood changes based on a heuristic estimate (i.e. to avoid leaving [o.o] dots behind in a B.../S0... search, try a B2i transition)

Please, feel free to play around with the script and to comment on how you find it. It's still terribly suboptimal, but we'll work on it.

[drc]

Towards a Progressive Rulesrc
A self-correcting Rulesrc would be interesting enough to attempt to find cell configurations, but one of the initial steps is to allow variation in the number of identical generations. Note that this yields similar and not necessarily identical ships, but for many purposes it's good enough. The idealised script should be able to identify good leads, allowing much quicker finds of interesting spaceships from decent inputs.

I like this! I found this cool 9c/849 orthogonal with it (in a non-explosive rule), so it's certainly not useless:

Code: Select all

x = 12, y = 3, rule = B2ik3-qy4eknrt5aek6in/S2-a3ijqy4aqt5aen7e8
3o7bo$obo6b3o$3o7bo!

[Saka]

I'm not exactly understanding the progressive rulesrc. What does it mean by progressive? What is "base generation"? I don't get it, sorry.

[Rhombic]

I'm not exactly understanding the progressive rulesrc. What does it mean by progressive? What is "base generation"? I don't get it, sorry.

Base generation is the maximum initial generations you want to keep identical, for a start.

Since the last generations might have been wrong due to a slight mistake when defining them (think messing up a copperhead in B34k/S23, which would be a shame), the only answer so far was widening the search by starting with fewer generation constraints. However, in the event that there was in fact a ship with the very tight constraints, it would be a shame to make the search last for so long.

Do realise that Rulesrc is much more likely to find spaceships tht works in many many rules instead of endemic ones, because it's down to the luck of choosing the only rule the spaceship works in. Narrowing down the search is crucial. Ideally, this could be done in a more intelligent way (using a scoring function), but so far it just does this:

Code: Select all

while 1:
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-1)),2*D)
    Rulesrc(M,D)
    Rulesrc(str(max(1,int(M)-2)),4*D)
    Rulesrc(M,D)
    M=str(int(M)-1)

Where Rulesrc(A,B) is performing a Rulesrc with A generations for B rules.

Scoring Functions
For now, line 4 of that excerpt has a major problem. The idea is to narrow it down after having widened it. However, one can clearly see that this extra generation will be a random pick from all the D ones explored. In some cases, this will imply wrongly narrowing down the search to a rule that might be explosive, which is a crazy waste of time and effort.
The quality of a "partial rule find" spaceship should be assessed, and there is a great benefit from doing so: when the search is narrowed, it is narrowed exclusively to high-potential rules. This is what we want, because Rulesrc is otherwise a brute-force search if you allow it to make a broad search regardless.
Heuristic neighbourhood correlation could be very useful!! If the last forced generation has an interacting dot spark, if allowed, maybe S0 is a good approach. If the spaceship is at risk of becoming D4 symmetric if a section becomes a spark, then we should limit the search space to rules where that part is NOT a spark.

Other Additions to Include
If the number of rules <= search depth, then, instead of generating random rules, cycle through each of the possible rules and return after going through all of them.
That way, if a pattern works in B36a/S23-k - B36an8/S234ce8, it's much shorter to go through 64 rules instead of repeating random rules 2000 times.

[muzik]

Could this script be extended to non-totalistic Generations?

[Saka]

what about a faster version of the original searchRules but with rule-that-supports-spaceships logic and progrulesrc logic?

[muzik]

Is "amount of generations to remain unchanged" just a confusingly verbose version of "minimum period"?

[Rhombic]

Is "amount of generations to remain unchanged" just a confusingly verbose version of "minimum period"?

Yes and no... I mean, that's a clear implication of the fact that, otherwise, there would have been an impossible subperiod repeat for a higher period spaceship. However, I wanted to state the fact that it's trying to find a spaceship that preserves those generations, more than the fact that it will obviously need a higher period. I hope that makes sense. Any new wordings appreciated.

Does someone know how to make a decent scoring function? i.e. one that could detect non-explosive rules (so the pattern doesn't grow wildly) and that could potentially involve a translation of a potential predecessor (so that the pattern has reached a possible parent/have a few common cells).

[Rhombic]

Crude script to find patterns that evolve to a high population in a rule, very poor logic.
It addresses a couple of issues though:
- If the population tends to be very high and very similar regardless of the original starting pattern, you are facing an explosive rule.
- If the improvements on the best result tail off very quickly and at a low population, the rule is probably too static.

Code: Select all

import golly as g

class maxpop:
    def __init__(self):
        self.pop=0
        self.patt=[]
    def compare(self,other):
        g.select(g.getrect())
        g.clear(0)
        g.putcells(other)
        g.run(3000)
        comp=int(g.getpop())
        g.select(g.getrect())
        g.clear(0)
        g.putcells(self.patt)
        g.run(3000)
        newpop=int(g.getpop())
        if comp>newpop:
            return 1
        else: return 0

best=maxpop()
candidate=maxpop()
while 1:
    g.select([0,0,7,7])
    g.randfill(50)
    candidate.patt=g.getcells(g.getrect())
    g.run(2000)
    if int(g.getpop())>best.pop:
        candidate.pop=int(g.getpop())
        if best.compare(candidate.patt)==1:
            best.pop=candidate.pop
            best.patt=candidate.patt
    g.show("New highest population is %d. Press any key to show current best." %best.pop)
    g.select(g.getrect())
    try:
        g.clear(0)
    except: pass
    event = g.getevent()
    if event.startswith("key"):
        g.new('Result')
        g.putcells(best.patt)
        g.exit()

This could be used, once improved upon, to classify whether a rule where a spaceship has been found is good enough or not. If not, a search of rules where the spaceship works could attempt to find a less explosive one, starting from the fewest B/S conditions. Let me know what you think, its potential uses apart from progRulesrc merging, etc.

EDIT: g.setclipstr() removed

[drc]

Crude script to find patterns that evolve to a high population in a rule, very poor logic.

It copies weird stuff to my clipboard:

Code: Select all

[0, 0, 1, 0, 2, 0, 1, 1, 2, 1, 3, 1, 4, 1, 6, 1, 0, 2, 1, 2, 4, 2, 0, 3, 2, 3, 3, 3, 4, 3, 6, 3, 1, 4, 3, 4, 1, 5, 4, 5, 6, 5, 0, 6, 1, 6, 3, 6, 5, 6]

[Rhombic]

Allowing oscillator searches for Rulesrc gives more impressive results than I had expected initially... higher order symmetries tend to be prolific.
Proof by searching with 9 generations kept, a novel p35:

Code: Select all

x = 8, y = 8, rule = B3-cky4eiq5kny6aci/S2-n3-eij4inr5-cijk6c78
4o2b2o$4o2b2o$6b2o$6b2o$2o$2o$2o2b4o$2o2b4o!

EDIT: an unbelievable xp110

Code: Select all

x = 17, y = 5, rule = B34ijqrz5ckry6c7c8/S23-cky4y5c6n
9bo$2o7b2o4b2o$2o8b2o3b2o$9b2o$9bo!

[muzik]

Have you considered adapting this to allow non-isotropic rules? There's some freaky slopes out there just waiting to be tapped into

[toroidalet]

I don't want to sound annoying by suggesting a lot of things, but (and this is probably extremely trivial) could Rulesrc be modified to just look for repetitions of the starting pattern (for finding guns, puffers and replicators)?

[drc]

I don't want to sound annoying by suggesting a lot of things, but (and this is probably extremely trivial) could Rulesrc be modified to just look for repetitions of the starting pattern (for finding guns, puffers and replicators)?

+1

Added bonus if you get to choose which one(s)

[Rhombic]

New script that lists results for particularly productive pattern/condition pairs.
Lists the results in a text file with rule, displacement, period (for a given initial pattern that is also written to the text file).
This script does NOT exit once a result is found, and restarts itself to keep searching, so many 3 cell ships can be found like this without the need to copy each one individually.
The spaceships listed are always in minimal rule form - see the defined function setminrule(arguments)

iterRulesrc

Code: Select all

# iterRulesrc.py
#
# This version of Rulesrc (available: ConwayLife.com) aims to improve search efficiency for productive patterns+conditions.
# The results get listed to iterRulesrc_results.txt and the search is cancelled by pressing any key.

# 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
from glife import validint
from string import replace
import random

GENERATION_STRING=g.getstring('To stop this script, press any key at any point.\nHow many generations to remain unchanged:', '', 'Rules calculator')

def setminrule(RULE, DX, DY, PERIOD):
    # 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

    g.setrule(RULE)

    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 = PERIOD
    numsteps = PERIOD
    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))
    ruleres = rulestringopt(ruleres)
    g.setrule(ruleres)
    RESULT = [ruleres, DX, DY, PERIOD]
    return RESULT


def Rulesrc():
    # 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 = GENERATION_STRING
    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)
        Spaceship = setminrule(str(g.getrule()), dx, dy, period)
        return Spaceship
    else:
        g.show('No results found')

textfile=open("iterRulesrc_results.txt","w+")
g.select(g.getrect())
g.copy()
textfile.write("\n"+g.getclipstr()+"\n\n")
ListRules = set()
while 1:
    newrule=Rulesrc()
    event = g.getevent()
    if event.startswith("key"):
        break
    if newrule[0] not in ListRules:
        ListRules.add(newrule[0])
        textfile.write(newrule[0]+"\t("+str(newrule[1])+","+str(newrule[2])+")/\t"+str(newrule[3])+"\n")
textfile.close()
g.exit("We have found %d results, found in your rule folder as iterRulesrc_results.txt. Thank you for your patience." % len(ListRules))

Proof of results, for a fairly narrowed-down search: with 3 transitions for

Code: Select all

x = 4, y = 1, rule = B2ce3j/S01e
2obo!

gives this result after a few minutes

Code: Select all

x = 4, y = 1, rule = B2ce3j/S01e
2obo!

B2cek3jry4irt5e6c7e/S01e4ct5iy7e	(1,0)/	9
B2cek3ij4i5i/S01e4n	(3,0)/	7
B2cek3jkqry4ijktw5akny6c/S01e2e3jr4iqz5ry6i8	(2,0)/	20
B2cek3j4ik5n6a7e/S01e2n4aejnrt5cij6acik7e8	(2,0)/	11
B2cek3ijqy4iqrwz5ir6c/S01e2ikn4intw5cinqry6ci	(3,0)/	15
B2cek3jr4i5iy/S01e2e3cq4ein7e	(3,0)/	14
B2cekn3ijry4ijnt6c7e/S01e2in3n4in5c6k	(2,0)/	17
B2ce3jnqr4ijr5q7e/S01e2k3eq	(2,0)/	12
B2cek3jnry4inr5e6c8/S01e	(1,0)/	8
B2cek3cjqry4ar5iy6c8/S01e2kn6k	(1,0)/	19
B2cek3jr4i/S01e4n5y7e	(1,0)/	8
B2cek3ijry4ijk5c/S01e2i3q4cin5ij	(3,0)/	9

[AforAmpere]

Is there a way to have the script constantly update the text file, or have it tell how many ships have been found while it is running?

[wildmyron]

Here's my current version of the search script. It's still far from what I'd like it to be, but I think there's some useful bits that you guys can use. In particular I updated testrule() to include a naive stability test which gives a decent speed improvement when maxGen is set to large values. There's also a small change to giveRLE() for performance reasons and I've simplified randIsoRule() to use a fixed probability. It includes my version of setminisorule which has a lot of redundant code (c.f. the rule range testing code) and also heavily derived from getallisorule.py.

The search script outputs all results to a file, and a second script can be used to filter those results and output a file with a sorted list of (mostly) unique ships. The search script appends to it's output file, but the filter script overwrites its output file.

searchRule-matchPatt.zip

(8.18 KiB) Downloaded 360 times

Edit: From Misc discoveries thread:

Use this script to import ships in the scripts output format into Golly

Code: Select all

# display_ship.py
# This script will take a string representing a ship with some additional metadata,
# and display it in the current layer
# It first checks the clipboard for a valid string and then requests input if necessary
# There is minimal error checking
# ship format: ['pop', 'rule', 'dx', 'dy', 'period', 'rle']

import golly as g

def parseshipstr(shipstr):
    if not shipstr[0] in '123456789':
        return
    ship = shipstr.split(', ')
    if not len(ship) == 6:
        return
    return ship

shipstr = g.getclipstr()
ship = parseshipstr(shipstr)
if not ship:
    shipstr = g.getstring('Enter ship string:')
ship = parseshipstr(shipstr)
if not ship:
    g.exit('Invalid ship string: ' + shipstr)
   
rulestr = ship[1].strip()
shiprle = ship[5].strip()

g.new('')
g.setrule(rulestr)
g.putcells(g.parse(shiprle))

[wildmyron]

I just found out that I didn't create the zipfile correctly and several files were missing. Please download again from the post above if you would like to use the filtering script mentioned in the post.

[Rhombic]

Expanded version of iterRulesrc to support both oscillator and spaceship searches, here as iterAllRulesrc:

Code: Select all

# iterAllRulesrc.py
#
# For both oscillator and spaceship searches, iterRulesrc algorithm.
# This version of Rulesrc (available: ConwayLife.com) aims to improve search efficiency for productive patterns+conditions.
# The results get listed to iterAllRulesrc_results.txt and the search is cancelled by pressing any key.

# Expanded from Rulesrc
# 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
from glife import validint
from string import replace
import random

GENERATION_STRING=g.getstring('To stop this script, press any key at any point.\nHow many generations to remain unchanged:', '', 'Rules calculator')

def setminrule(RULE, DX, DY, PERIOD):
    # 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

    g.setrule(RULE)

    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 = PERIOD
    numsteps = PERIOD
    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))
    ruleres = rulestringopt(ruleres)
    g.setrule(ruleres)
    g.run(0)
    RESULT = [str(g.getrule()), DX, DY, PERIOD]
    return RESULT


def Rulesrc():
    # 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


    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 = GENERATION_STRING
    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):
            Oscillator = setminrule(str(g.getrule()),0,0,result[0])
            return Oscillator
        elif (len(result) == 3):
            dx, dy, period = result
            dy, dx = minmaxofabs( (dx, dy) )
            Spaceship = setminrule(str(g.getrule()), dx, dy, period)
            return Spaceship
        else:
            g.exit('Unrecognised pattern')
        g.show(description)    
    else:
        g.show('No results found')

textfile=open("iterAllRulesrc_results.txt","w+")
g.select(g.getrect())
g.copy()
textfile.write("\n"+g.getclipstr()+"\n\n")
ListRules = set()
while 1:
    newrule=Rulesrc()
    event = g.getevent()
    if event.startswith("key"):
        break
    if newrule[0] not in ListRules:
        ListRules.add(newrule[0])
        textfile.write(newrule[0]+"\t("+str(newrule[1])+","+str(newrule[2])+")/\t"+str(newrule[3])+"\n")
textfile.close()
g.exit("We have found %d results, found in your rule folder as iterRulesrc_results.txt. Thank you for your patience." % len(ListRules))

EDIT: could someone point out a way to make this addition to iterRulesrc?:
- When a spaceship is found with the current constraints, find what rules it works in (easy)
- Do not search rules where that spaceship is valid from that point onwards

Issues: you cannot do it by combinations because you'd end up with a list of 10^16 rules or so

What can be done?

[wildmyron]

EDIT: could someone point out a way to make this addition to iterRulesrc?:
- When a spaceship is found with the current constraints, find what rules it works in (easy)
- Do not search rules where that spaceship is valid from that point onwards

Issues: you cannot do it by combinations because you'd end up with a list of 10^16 rules or so

What can be done?

This is readily doable for some cases, but I think for the general case of excluding all rules which any of the previously found results works in it will be slower to test whether or not to search the rule than it is to just search the rule. There are two readily apparent options to restrict the rules to search - both are based on generating the rule and then test if it should be skipped. They are probably easiest to implement with the rule represented as a list of rule elements which can be easily tested against.

• For the rulespace with a spaceship to exclude: determine the rule elements to exclude. This is the set of rule elements which are allowed for the ship in addition to the required elements for the base search. Then for the rule to be tested: check if all the optional elements are in the list of rule elements for the excluded rulespace - if they are then skip. It would be possible to have multiple exclude lists, but this could become unmanageable fairly quickly.
• Maintain a set with excluded rules - For every rulespace to be excluded: generate all combinations of the optional allowed rule elements and store them in the set (preferably as a string or tuple). Then for the rule to be tested: check if the optional rule element combination is in the set - if it is then skip the rule. Because elements of a set are hashed (and therefore need to be hashable), testing a candidate rule will be quick. But for large rulespaces to exclude the memory requirements will grow quickly.

I think you would need to have a very specific use case for this to be worthwhile implementing and doing. For example: using searchRule-matchPatt.py to search for ships which match the first 3 or 4 generations there are very few duplicate ships found by the script. This means that the vast majority of rules tested don't match one of the rules disallowed by the above idea. Some very rough numbers: Searching about 10,000,000 rules will give 300-500 results. Of these less than 10 will be duplicates. That means that for 9,999,990 of the rules tested the time taken to test if the rule should be skipped is wasted, as opposed to the time gained by not testing the 10 rules where a duplicate ship was found.

I don't want to sound annoying by suggesting a lot of things, but (and this is probably extremely trivial) could Rulesrc be modified to just look for repetitions of the starting pattern (for finding guns, puffers and replicators)?

I don't see this as a trivial modification to the current Rulesrc scripts. The pattern detection for all of them is contained in the function testRule() which really does little more than the following:

• Store the initial pattern and population
• run the pattern for fixed number of generations
• At every generation: if the current population matches the initial population, then
  • Get the current pattern and test if it is equal to the initial pattern
  • If it is, then return the successful result

In order to look for repetitions of the starting pattern, the initial pattern would need to be tested against subsections of the current pattern. So then you need to break up the pattern into suitable subsections, or use cross correlation or some other pattern matching technique. You also want a way to determine when to do this, rather than doing it at every generation (possible though, but much slower).

Alternatively the search could just look for linear growth of any kind. I haven't attempted something like this because I haven't really had a strong desire to find any particular category of linear growth. It seems to me that there are several design considerations in doing this to give a program which does something that apgsearch doesn't already do. First off, what is the search space? How do you want to constrain the search so that explosive rules don't bog it down, but the search will still find interesting results. Then you have to determine the method to detect linear growth when it happens. One option for this is readily available - the linearlyse() function from apgsearch (along with the deepperiod() function).

It's certainly possible to cobble together a script which will find something, even if it isn't particularly performant. Here's a brief outline:

• set up the search paramaters
  • candidate pattern (or patterns)
  • candidate rule (or rulespace)
  • test run parameters (how long to run pattern, max period, etc.)
• inside a loop:
  • Initialise layer with candidate rule and pattern
  • run pattern for fixed gen
  • call linearlyse()
  • test the return value - if it starts with 'y' then break out of the loop
• restore layer to state with initial pattern and rule which resulted in linear growth

[wildmyron]

I've published an updated version of searchRule-MatchPatt

It is available from the 5S collection folder on my Google Drive. To use the new version: place a copy of searchRule-MatchPatt2.py and sss.py from the linked folder in your Golly scripts folder (or other suitable location). Load a pattern in the current Golly layer. This pattern will be the target pattern, but if you don't set stabCycles to 0 then the results won't necessarily have a phase which matches this pattern exactly. You will also either need to set import5S to False or include a copy of the three 5S collection *.sss.txt files in the same folder as the script. Run the script and specify a number of generations to match. The script will search the rulespace determined by the min and max rules of the target patterns' evolution. The rulespace is searched pseudo-randomly and the search will finish when the rulespace has been completely searched.

I don't have time to provide further details at the moment, so here is a brief changelog:

Differences from searchRule-matchPatt.py:
- Press 'q' to stop searching (instead of aborting with 'Esc')
- Uses routines from sss.py library to analyse small patterns in isotropic
2-state rules
- Maintains record of found spaceship speeds to avoid reporting duplicate
results
- Optionally allows pattern to be run for a short stabilisation time prior
to testing for periodicity
- Optionally loads previously found speeds from output file at start of
search
- Optionally also load ships from 5S project into record of known speeds
- Random rule generator uses an iterator which pseudo randomly scans the
entire rulespace

Have fun!

P.S. There is also a version of searchRule-MatchPatt-linear.py in the linked folder. It attempts to run a search for linear growth patterns along the lines of the algorithm I described in my Oct 2017 post above. I haven't used it for a long time so I can't remember the details, but I do remember that it's not particularly efficient.

[wildmyron]

Some comments about the available options in searchRule-matchPatt2.py:

• I tried to keep all the options that might be useful at the top of the script. The only exception is the stability options - because I made it dependent on the number of generations matched. That's probably not necessary and I'm not even sure it's a good idea.
• The default options are tailored to contributing to the 5S project, for other purposes it is worthwhile adjusting the options. I hope all the comments are clear
• The options to exclude duplicate results work as follows:
  • bUniqueSpeeds - If True, matchPatt2 will keep track of the smallest ship of each speed found so far. Only the first ship of each speed and any subsequent smaller ones will be written to the results file. The list of found speeds will be prepopulated with the results from the results file.
    - If False, all ships matching the criteria will be recorded - including the same ship found in multiple rules. NOTE - the minpop recorded in this case may be wrong because it is the population at the time of detection.
  • ignoreResults - The deluge of identical ships when there is one ship in many rules can be mitigated by adding the speed of that ship to this list.
  • bImport5S - If True, all the ships in the 5S collection will be added to the list of found speeds. (The three *.sss.txt files which make up the collection must be in the same folder as the matchPatt2 script.)
• StabCheckP can be left as it is, it's not really a search option. It is intended to allow the testRule function to detect when the target pattern evolves into periodic debris after the initial stabilisation phase. This is most useful with stabGen = 0 and very large maxGen (i.e. 10000). I'm not sure it's actually that helpful though.

Feedback on other options to add to the search and object detection code is welcome, particularly regarding priority of the following items I've been considering:

• Always canonise ships before writing them to the results file
• Ensure the result from sss.canon5Sship truly is canonical (currently not the case for asymmetric ships and ships which have multiple phases with the minimum population and minimal bounding box)
• Keep a list of foundShips in addition to foundSpeeds. This would enable deduplication of results based on ships rather than speeds.
• Support saving state of the pseudorandom rule generator (and loading it) to be able to continue a search.
• Record the rule range of found ships (most likely only those that work in a large number of rules) and use it to avoid testing the rules in that range. There's a Memory - CPU time tradeoff here for as yet unknown performance benefit.
• Decouple the rulespace matching from the target pattern
• Support searching multiple patterns in each rule (this was actually how an early, unpublished version of searchRules.py worked, but it's remained mostly unused since the rulespace matching feature was introduced by Rhombic)