Triviality Tester

[Rhombic]

trivialhunter.py
This WIP script so far calculates the subperiods for each cell and outputs them to a txt file. g.show if trivial or non-trivial.
The main idea for the next step is to separate xp4 and xp2, for example, that are "on" a still life yet don't interact, something that Oscillizer cannot do (I mean, you can obviously see it by looking at it, but that's not what I mean).
How?
After looking at a few examples, I've noticed that for any subperiod=S cell in a fully non-trivial oscillator, there always is a polyplet that connects that cell to a full period cell so that every cell in that polyplet has a period > 1.
It sounds like a bit of a mouthful but if you look at it with an example you'll quickly see what I mean.
That's the tricky bit of the script, but it would end up being the more useful part.
Anyway, here's what I have so far and the comments at the bottom explain what I need help with.

Code: Select all

# trivialhunter.py
# Author: Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.
# For future development see the comments at the bottom.

import golly as g

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1
p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = []
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1: g.show("Trivial oscillator, with a maximum cell period of "+str(maxp)+".")
else: g.show("Non-trivial oscillator.")
File.close()

# OK, next step is the following:
# For a non-trivial oscillator:
#   For each cell that does NOT oscillate full period:
#   Try to find a polyplet path from that cell to any full-period cell
#   EXCLUSIVELY through period>1 cells (that is, a polyplet through state 0 is useless)
# Why, Ed, isn't that just a waste of time?
# No, because that way you can separate trivial xp(a*b)--xp(a) interactions,
# which the current script is unable to do. e.g. blocker on beacon

[dvgrn]

# For a non-trivial oscillator:
# For each cell that does NOT oscillate full period:
# Try to find a polyplet path from that cell to any full-period cell
# EXCLUSIVELY through period>1 cells (that is, a polyplet through state 0 is useless)
# Why, Ed, isn't that just a waste of time?
# No, because that way you can separate trivial xp(a*b)--xp(a) interactions,
# which the current script is unable to do. e.g. blocker on beacon

Would it work to start with each cell that does oscillate at the full period, and recursively add period>1 neighbors to your list, until no more neighboring cells are period >1?

That seems a little easier than tracking from a non-full-period cell to a full-period one, and I think it would have the same effect as what you describe.

I can't think of any cases where a period 3 section might directly neighbor a period 4 section which might neighbor a period 12 cell, so that all those cells would get marked, but somehow the period 3 section doesn't interact with the period 4 section.

But at higher periods I'm not so sure. It's certainly possible for, say, a sparky p30 to never really interact with a sparky p15, even though their reaction envelopes overlap fairly deeply. Do you want to do anything special about weird cases like that?

[Rhombic]

But at higher periods I'm not so sure. It's certainly possible for, say, a sparky p30 to never really interact with a sparky p15, even though their reaction envelopes overlap fairly deeply. Do you want to do anything special about weird cases like that?

I'll try to do what you said.
As for that last bit, I had entirely overlooked it! That is a very good point and would account for, among other examples, all the trivial xp160 combinations in tlife. I don't know how to treat these cases. Maybe with a condition that for every oscillating cell, at least one neighbour has to be alive in the same generation as that cell, or in an adjacent generation? Would that work?

[dvgrn]

I'll try to do what you said.

To be a little more specific:

• start with two lists: List A, "AlreadyChecked", containing all cell coordinates that oscillate at the full period, and List E, "Edge", a copy of List A to start out. Technically sets would be faster than lists, or dictionaries are rumored to be even faster -- but simple Python lists will work, and you might only notice the difference if you're analyzing things like OTCA metapixels.
• For each of the eight neighbors of each cell in List E, check if it oscillates at p>1. If so, and if it's not already in List A, add it to List A and also to a new List E'.
• When all of List E has been checked, replace List E with List E'. Repeat the previous step until List E' comes up empty.
• List A now holds all periodic cells that are connected to a full-period cell. Any periodic cells not in this list must be disconnected "trivial" oscillators.

As for that last bit, I had entirely overlooked it! That is a very good point and would account for, among other examples, all the trivial xp160 combinations in tlife. I don't know how to treat these cases. Maybe with a condition that for every oscillating cell, at least one neighbour has to be alive in the same generation as that cell, or in an adjacent generation? Would that work?

Not quite, I think. Are you wanting to make this work for any Life-like rule, or maybe isotropic non-totalistic rules too, since you mentioned tlife? It's hard to think of all the cases when it isn't just B3/S23.

The effect of a neighboring spark is often a birth suppression rather than a birth, so cells that are never ON can still be a connected part of an oscillator. Does that mean that in something like this p208 oscillator, only half of the Rich's p16 would be counted as participating, and the other half would be "trivial"? That doesn't seem so good.

Code: Select all

x = 41, y = 34, rule = LifeHistory
2.2A8.2A$2B2AB8.A7.A$2B2A9.A.AB3.A.A12.2AB$2BAB10.2AB2.2BAB11.B3A$.AB
AB5.2A4.3B.2B12.B2A.A$.AB2A4.B2AB3.4B.4B2.3B4.2B.A.A$2.4B3.3B4.12B2A
2B.B2.A2.A$2.4B2.B.B5.11BA2BA3B3.2A$.B2A2B.15B2A4B2A5B$2.2A2.15BA2BA
10B$6.15BA2BA10B$6.16BABA10B2.2A$6.28B.2B2AB$2.2A3.18B5.B.B2.2B2A$.A
2.A2.B.16B4.3B3.2BAB$.A.A.2B4.3B2.4B.3BA3.B2AB4.ABAB$2.A.2AB12.2B.3BA
3.2A5.AB2A$3.3AB11.BA2B.3AB10.4B$3.B2A12.A.A3.4B9.4B$19.A5.4B7.B2A2B$
16.B5.B.6B7.2A$15.3B3.10B$13.4BA3.A4B2.4B$12.4BA.A.A.A4B2.4B$12.5B2A.
2A5B3.4B$12.7B.7B4.4B$12.7B.7B5.4B$12.B5AB.B5AB6.4B$12.BAB4A.4ABAB7.
3B$12.B2ABABA.ABAB2AB9.B2A$12.2BABA.A.A.ABA2B9.BA.A$13.2B3A3.3A2B13.A
$15.BAB3.BAB15.2A$16.B5.B!
#C [[ THUMBNAIL THUMBSIZE 2 ]]

To avoid that, you'd have to either extend the analysis to neighbors-of-neighbors -- dangerous, because that could incorrectly decide that things like two 3ob3o! blinkers were interacting -- or add OFF cells to the analysis if their neighbor counts change.

I guess in general, an OFF neighbor of an oscillating cell should also be counted as oscillating if there's at least one generation where its neighbor count goes above a birth condition for the rule.

That's only going to work for Life-like rules, though -- how can that be extended to isotropic rules without causing coding nightmares?

[All this is tangential to the problem of overlapping sparky oscillators that don't really interact at all -- but it seems relevant because it's possible for two oscillators to interact non-trivially even if there are no cells where "at least one neighbour is alive in the same generation as that cell, or in an adjacent generation". The interaction can involve birth suppression just as well. The two oscillators have to be the same period for that to happen, though... I think.]

[Rhombic]

I've added the second part and after looking for the error for a long while, I have no clue as to where the problem is.
Basically, if the script initially thinks that the oscillator is not trivial, it will continue (because there's no point if it has already been proved to be trivial). However, when it does, it always states "trivial with a X-cell oscillating outlier", with X always far larger than what it could ever be.
Can someone point out where the bug is?
After this, the only thing that would be left to do would be some ingenious way to see whether two sparky oscillators are actually interacting or not (and I'll think I'll do that by separating each and running them to see whether all the cells behave identically when separate). There's no point in doing that until this is fixed though. But getting closer to a reliable triviality-identifier script, I guess.

Code: Select all

# trivialhunter.py
# Author: Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.

import golly as g
import re

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1
p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = []
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
triv2=0
cellcount=0
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1:
    g.exit("Trivial oscillator, with a maximum cell period of %d." % maxp)
else:
    g.show("Apparent non-trivial oscillator.")
    maxp = p
File.close()
D=open("cell_periods.txt","r").readlines()
Dprime=[]
AlreadyChecked=[]
Edge=[]
for line in xrange(len(D)-1):
    case=re.split("\t",D[line+1])
    if case[2]==str(maxp):
        AlreadyChecked.append(case[0]+","+case[1])
        Edge.append(case[:2])
    Dprime.append(case[0]+","+case[1])
Edgeprime=["foo","bar"]
while len(Edgeprime):
    Edgeprime[:]=[]
    for cell in xrange(len(Edge)/2):
        for dx in range(3):
            for dy in range(3):
                if dx+dy:
                    cellq=D[Dprime.index(str(int(Edge[2*cell]+dx))+","+str(int(Edge[2*cell+1])+dy))]
                    if re.split("\t",cellq)[3]!="1":
                        compensatingforlistsandstringsandwhatnot=cellq[0]+","+cellq[1]
                        if compensatingforlistsandstringsandwhatnot not in AlreadyChecked:
                            AlreadyChecked.append(cellq[0]+","+cellq[1])
                            Edgeprime.append(cellq[:2])
    Edge=Edgeprime
for hunt in xrange(len(Dprime)):
    if Dprime[hunt] not in AlreadyChecked:
        triv2=1
        cellcount+=1
if triv2==1: g.show("Trivial oscillator, with a %d-cell oscillating outlier." % cellcount)
else: g.show("Non-trivial oscillator... until we optimise the script.") 

EDIT: Dave, so far, the code allows any two-state rule (including MAP rules). Two state because of the way I've been treating the cells in the lists; otherwise, it would be for any rule whatsoever.

[dvgrn]

Basically, if the script initially thinks that the oscillator is not trivial, it will continue (because there's no point if it has already been proved to be trivial). However, when it does, it always states "trivial with a X-cell oscillating outlier", with X always far larger than what it could ever be.
Can someone point out where the bug is?

To find it, add this line after your definition of the case variable, and then try analyzing something:

Code: Select all

    g.note(str(case)); g.exit()

The silly readlines() function leaves the newline characters at the end of each string, so your comparisons with str(maxp) are always failing, and AlreadyChecked probably never gets anything added to it.

There may be other bugs, I haven't checked. I'd be tempted to throw out the mysterious "foo", "bar" and just do something like this:

Code: Select all

Edgeprime=[]
while 1:
  ...
  if Edgeprime==[]: break

EDIT: Dave, so far, the code allows any two-state rule (including MAP rules). Two state because of the way I've been treating the cells in the lists; otherwise, it would be for any rule whatsoever.

I suppose until you add code to include key always-OFF cells in the analysis (by checking the periodicity of their neighbor counts, maybe?) there aren't any subtle assumptions that can creep in about the rule being totalistic.

[Rhombic]

I don't want to cram this thread with posts about this script, so if you consider suitable to move all the posts to a separate thread, so be it - just let me know and I'll delete at least this last one and create a new thread (or moderators should probably be able to do so too).
I have changed all bits that had bugs in them, and there were quite a few that I found while sorting out the one you mentioned. However, still no luck at all. I'll have a better look at it tomorrow.
For now, I'll leave the script here in case someone who is also learning Python wants to have a go. Once I sort it out I'll update it here.

Code: Select all

# trivialhunter.py
# Author: Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.

import golly as g
import re

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1
p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = []
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
triv2=0
cellcount=0
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1:
    g.exit("Trivial oscillator, with a maximum cell period of %d." % maxp)
else:
    g.show("Apparent non-trivial oscillator.")
    maxp = p
File.close()
D=open("cell_periods.txt","r").readlines()
Dprime=[]
AlreadyChecked=[]
Edge=[]
for line in xrange(len(D)-1):
    case=re.split("\t",D[line+1])
    case[2]=case[2][:len(case[2])-1]
    if case[2]==str(maxp):
        AlreadyChecked.append(case[0]+","+case[1])
        Edge.append(case[:2])
    Dprime.append(case[0]+","+case[1])
Edgeprime=[]
while 1:
    Edgeprime[:]=[]
    for cell in xrange(len(Edge)):
        for dx in range(3):
            for dy in range(3):
                if dx+dy:
                    if str(int(Edge[cell][0])+dx)+","+str(int(Edge[cell][1])+dy) in Dprime:
                        cellq=D[Dprime.index(str(int(Edge[cell][0])+dx)+","+str(int(Edge[cell][1])+dy))]
                        if re.split("\t",cellq)[2][:len(re.split("\t",cellq)[2])-1]!="1":
                            cflasawn=cellq[0]+","+cellq[1]
                            if cflasawn not in AlreadyChecked:
                                AlreadyChecked.append(cellq[0]+","+cellq[1])
                                Edgeprime.append(cellq[:2])
    Edge=Edgeprime
    if Edgeprime==[]: break
for hunt in xrange(len(Dprime)):
    if Dprime[hunt] not in AlreadyChecked and re.split("\t",D[hunt])[2][:len(re.split("\t",D[hunt])[2])-1]!=1:
        triv2=1
        cellcount+=1
if triv2==1: g.show("Trivial oscillator, with a %d-cell oscillating outlier." % cellcount)
else: g.show("Non-trivial oscillator... until we optimise the script.") 

[dvgrn]

For now, I'll leave the script here in case someone who is also learning Python wants to have a go. Once I sort it out I'll update it here.

Moved as suggested. Suddenly "here" and "this thread" don't mean what they meant a moment ago, but don't worry about it, just put a working copy in the Golly Scripts thread, assuming it does eventually get to a working state.

I haven't managed another round of debugging, because of tripping over some trivia:

Code: Select all

for line in xrange(len(D)-1):
    case=re.split("\t",D[line+1])
    case[2]=case[2][:len(case[2])-1]
    if case[2]==str(maxp):
        AlreadyChecked.append(case[0]+","+case[1])
        Edge.append(case[:2])
    Dprime.append(case[0]+","+case[1])

If you're going to do tricks like the -1 and +1 in the first line, a # skip the header line comment would be nice. Here are a couple of changes to make it easier to read -- or I think so, anyway:

Code: Select all

for line in D[1:]:  # skip the header line
    case=line[:-1].split("\t")
    if case[2]==str(maxp):
        coord = case[0]+","+case[1]
        AlreadyChecked.append(coord)
        Edge.append(case[:2])
    Dprime.append(coord)

You could just get rid of the coord variable and append the case[:2] length-two lists to AlreadyChecked and Dprime also. You can still perfectly well ask questions like if [3,4] not in AlreadyChecked: -- but that might be a good bit less efficient, at least until you turn AlreadyChecked into a dictionary.

Anyway, this next snippet was extra hard to read -- please have pity on other readers next time, and name a few things. You know that you just copied and pasted all that text, but everybody else has to compare it character for character to make sure:

Code: Select all

                    if str(int(Edge[cell][0])+dx)+","+str(int(Edge[cell][1])+dy) in Dprime:
                        cellq=D[Dprime.index(str(int(Edge[cell][0])+dx)+","+str(int(Edge[cell][1])+dy))]
                        if re.split("\t",cellq)[2][:len(re.split("\t",cellq)[2])-1]!="1":

The regexp version of split was overkill both places it was used; you're just splitting strings... but any time you're doing something as big as re.split("\t",cellq)[2] twice in a row, defining a temporary variable would make the code a lot more readable... but in this case a slice index of plain -1 is all you really needed anyway.

Code: Select all

                    coord = str(int(Edge[cell][0])+dx)+","+str(int(Edge[cell][1])+dy) 
                    if coord in Dprime:
                        cellq=D[Dprime.index(coord)]
                        if cellq.split("\t")[2][:-1]!="1":

But it's probably better to dig a little deeper. There are more straightforward ways of keeping track of the period of each cell. With this setup, you're building and using the Dprime list, but then it turns out you have to reach back and look something up in the original D list -- and then you have to fix the extra-newline problem again that you already fixed when you defined the case variable. How about making a dictionary instead?

Code: Select all

Pdict={}
for line in D[1:]:  # skip the header line
    case=line[:-1].split("\t")
    coord = case[0]+","+case[1]
    period = int(case[2])
    Pdict[coord]=period
    if period==maxp:
        AlreadyChecked.append(coord)
        Edge.append(case[:2])
    Dprime.append(coord)

Then just check Pdict[coord] when you want to know the period, instead of all that mysterious running around:

Code: Select all

                    coord = str(int(Edge[cell][0])+dx)+","+str(int(Edge[cell][1])+dy) 
                    if coord in Dprime:
                        if Pdict[coord]!=1:

Or something along those lines, anyway. I may have added bugs of my own -- haven't tried running any of this yet. Guess I'll re-post the whole thing if I get something running. More later, maybe...

[dvgrn]

Okay, so try this pattern --

Code: Select all

x = 40, y = 33, rule = B3/S23
b2o8b2o$b2o9bo7bo$b2o9bobo4bobo12b2o$bo11b2o5bo13b3o$obo6b2o23b2obo$ob
2o5b2o25bobo$27b2o6bo2bo$26bo2bo6b2o$b2o18b2o4b2o$b2o17bo2bo$20bo2bo$
21bobo12b2o$36b2o$b2o33b2o$o2bo32bo$obo20bo4b2o5bobo$bob2o19bo3b2o5bob
2o$2b3o13bo3b3o$3b2o12bobo$18bo17b2o$36b2o2$16bo3bo$15bobobobo$16b2ob
2o3$12b5o3b5o$12bob4ob4obo$12b2obobobobob2o11b2o$13bobobobobobo12bobo$
14b3o3b3o15bo$15bo5bo16b2o!

with this script --

Code: Select all

# trivialhunterv1.1.py
# Author: Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.

import golly as g
import re

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1
p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = []
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
triv2=0
cellcount=0
outliers=[]
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1:
    g.exit("Trivial oscillator, with a maximum cell period of %d." % maxp)
else:
    g.show("Apparent non-trivial oscillator.")
    maxp = p
File.close()
D=open("cell_periods.txt","r").readlines()
Dprime=[]
AlreadyChecked=[]
Edge=[]
Pdict={}
for line in D[1:]:  # skip the header line
    case=line[:-1].split("\t")
    coord = case[0]+","+case[1]
    period = int(case[2])
    Pdict[coord]=period
    if period==maxp:
        AlreadyChecked.append(coord)
        Edge.append(case[:2])
    Dprime.append(coord)
Edgeprime=[]
while 1:
    Edgeprime[:]=[]
    for cell in xrange(len(Edge)):
        for dx in range(3):
            for dy in range(3):
                if dx+dy:
                    coordx, coordy = int(Edge[cell][0])+dx, int(Edge[cell][1])+dy
                    coord = str(coordx)+","+str(coordy) 
                    if coord in Dprime:
                        if Pdict[coord]!=1:
                            if coord not in AlreadyChecked:
                                AlreadyChecked.append(coord)
                                # really really have make these Edge and Edgeprime things sets or dicts,
                                # and stop flipping back and forth between [x,y] and "x,y".
                                # But for now...
                                Edgeprime.append([str(coordx), str(coordy)])
    g.note("Edge length = "+str(len(Edge))+"\nEdgeprime length: " + str(len(Edgeprime)))
    Edge=Edgeprime
    if Edgeprime==[]: break
for hunt in Dprime:
    if hunt not in AlreadyChecked and Pdict[hunt]!=1:
        triv2=1
        cellcount+=1
        huntx, hunty = hunt.split(",")
        outliers+=[int(huntx),int(hunty)]  # again, let's not do this...!
if triv2==1:
  g.addlayer()
  g.putcells(outliers)
  g.show("Trivial oscillator, with a %d-cell oscillating outlier." % cellcount)
else: g.show("Non-trivial oscillator... until we optimise the script.")

It doesn't work yet. The edge-tracking cycle starts out healthily enough with 49 items in the Edge list and 6 Edgeprime, but then they both go down to zero right away.

I'm very worried about this part:

Code: Select all

        for dx in range(3):
            for dy in range(3):
                if dx+dy:

Seems like it shouldn't work for two separate reasons: one, dx and dy should vary from -1 to 1, and this just does 0 to 2; and two, once that's fixed, dx+dy will also be zero on the diagonals, not just in the middle. But maybe I just don't understand how you're doing it.

Let's get rid of the nested for loops and the skipped case here. Maybe use something like this instead:

Code: Select all

  for dx, dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]:

I'm going to leave things at this stage for another day or so. Maybe the dx, dy problem is all that's stopping the recursive search from getting back to all the other cells. But if not, my next step would probably be to rewrite this from the ground up so I can understand it better...!

(Just by the way, I can read this stuff pretty well because it looks just like what I've written an awful lot of myself. But there are definitely ways to make it easier for other people to jump in and help...!)

If we get rid of the lists of coordinate strings in Dprime and AlreadyChecked, and use a dictionary where the key is a list of two integers, that avoids a lot of unnecessary int()ing and str()ing, and then if we have to we can flatten Edge into a cell list and display it step by step to see what's going wrong. This kind of spreading search is always fun to watch, anyway.

[Rhombic]

OK, I have changed loads of stuff and unnecessary str-list changes and it finally works!! This is so motivating (after about an hour)!

The fact that with the xp208 it detects that half of the oscillator as an outlier is what we predicted initially (since it's not max period and is isolated in a gutter-symmetry fashion).

Next step:
1) Differentiate between trivial combinations of non-interacting sparky oscillators as shown here (not too hard, hopefully):

Code: Select all

x = 13, y = 15, rule = B3/S2-i34q
o2bo$obo$b3o9$10bo$9bo$10b3o$11bo!

2) Count situations like that gutter symmetry as non-trivial (hard).

Code: Select all

# trivialhunterv1.2.py
# Authors: Dave Greene, Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.

import golly as g
import re

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1
p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = []
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
triv2=0
cellcount=0
outliers=[]
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1:
    g.exit("Trivial oscillator, with a maximum cell period of %d." % maxp)
else:
    g.show("Apparent non-trivial oscillator.")
    maxp = p
File.close()
D=open("cell_periods.txt","r").readlines()
Dprime=[]
AlreadyChecked=[]
Edge=[]
Pdict={}
for line in D[1:]:  # skip the header line
    case=line[:-1].split("\t")
    period = int(case[2])
    Pdict[str(case[:2])]=period
    if period==maxp:
        AlreadyChecked.append(case[:2])
        Edge.append(case[:2])
    Dprime.append(case[:2])
Edgeprime=[]
while 1:
    Edgeprime[:]=[]
    for cell in xrange(len(Edge)):
        for dx, dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]:
            coord = [str(int(Edge[cell][0])+dx),str(int(Edge[cell][1])+dy)]
            if coord in Dprime and Pdict[str(coord)]!=1:
                    if coord not in AlreadyChecked:
                        AlreadyChecked.append(coord)
                        Edgeprime.append(coord)
    #g.note("Edge length = "+str(len(Edge))+"\nEdgeprime length = " + str(len(Edgeprime))+"\nAlreadyChecked length = "+str(len(AlreadyChecked)))
    Edge[:]=Edgeprime[:]
    if Edgeprime==[]: break
for hunt in Dprime:
    if hunt not in AlreadyChecked and Pdict[str(hunt)]!=1:
        triv2=1
        cellcount+=1
        outliers+=[int(hunt[0]),int(hunt[1])]
if triv2==1:
    g.addlayer()
    g.putcells(outliers)
    #g.note(str(outliers))
    g.show("Trivial oscillator, with a %d-cell oscillating outlier." % cellcount)
else: g.show("Non-trivial oscillator... until we optimise the script.")

----

Step 1: so as to keep the non-totalistic compatibility, I have thought of a new problem-free way to approach the gutter symmetry exception. Evolve the outliers once. Run the whole pattern for a full period and check whether the hash value of the whole pattern is the same. Are there any problems with this?

[dvgrn]

OK, I have changed loads of stuff and unnecessary str-list changes and it finally works!! This is so motivating (after about an hour)!

Ah, good -- I'm glad it was only an hour. I was hoping I hadn't introduced any subtle evil bugs that would have changed the one hour into ten -- that would probably have been much less motivating.

Step 1: so as to keep the non-totalistic compatibility, I have thought of a new way to approach the gutter symmetry exception. However, this brings other problems that are outlined later.
When a trivial section is discovered, set all those cells to 0 at the beginning, run for 2*p, check if all cells in bounding box are the same.

Yeah, definitely too many problems. Could still do it, and label the removals "super-trivial" or something, but those aren't the interesting cases. Also for something like a beacon it wouldn't be a proper test, because it effectively just changes the phase by one. On to the next --

EDIT: Perhaps this can only happen with gutter symmetry?! Any counterexamples?

Yeah, there are counterexamples. When the algorithm can figure out the triviality of something like this, then we'll be getting somewhere:

Code: Select all

x = 54, y = 26, rule = B3/S23
28b3o$28b2o$24b3ob2o18b2o$25b2o2bo3bo15bo$25b2o3b4o15bob2o$21bo3bo5b3o
14b2obo$21b4o24bobo$21b3o7b3o13b3ob2o$31b4o14bobo$16bo6b3o5bo3bo13bob
3o$3b2o10bobo4b4o9b2ob3o6b3obo$2bo12bo2bo2bo3bo9b2ob2o9bobo$o4bo2b2o
10b2o12b3ob2o8b2ob3o$4obo4bo5bobob2o17bo3bo5bobo$5bobo4bobo3bob3o17b4o
5bob2o$2b4obob4ob4o23b3o4b2obo$bo5bo43bo$2b4obob4ob2o25b3o7b2o$5bobo4b
ob2o25b4o$4obo4bo30bo3bo3b4o$o4bo2b2o35b2obo3bo$2bo42b2obobo$3b2o39b3o
$48bo2bo$49bobo$50bo!

EDIT 2:
I think I might have found a new problem-free way to do it! Evolve the outliers once. Run the whole pattern for a full period and check whether the hash value of the whole pattern is the same. Are there any problems with this?

Seems good for a start. That won't help separate the outliers into individual islands, though. If the script is just reporting trivial vs. non-trivial that almost doesn't matter, but I think a problem shows up trying to identify the trivial part of a sufficiently complex compound oscillator:

Code: Select all

x = 56, y = 40, rule = B3/S23
17b2o8b2o$17b2o9bo7bo$17b2o9bobo4bobo12b2o$17bo11b2o5bo13b3o$16bobo6b
2o23b2obo$16bob2o5b2o25bobo$43b2o6bo2bo$42bo2bo6b2o$17b2o18b2o4b2o$17b
2o17bo2bo$36bo2bo$37bobo12b2o$52b2o$17b2o33b2o$16bo2bo32bo$16bobo20bo
4b2o5bobo$17bob2o19bo3b2o5bob2o$18b3o13bo3b3o$19b2o12bobo$34bo17b2o$
52b2o$3b2o$3bo28bo3bo$2b2o2b3o22bobobobo$2bo3bob3o21b2ob2o$2b2obo4bo$
4bobo$o4bob2o11b2o6b5o3b5o$3obo3bo10b2ob2o4bob4ob4obo$2b3o2b2o5b2o4bob
2o4b2obobobobob2o11b2o$7bo6b3o4b2o6bobobobobobo12bobo$6b2o5bo2bo13b3o
3b3o15bo$13b3o15bo5bo16b2o$14bo9bo$23b3o$22bo2bo$16b2o4b3o$15b2obo4b2o
$15b2ob2o$17b2o!

Offhand I can't come up with a case where a non-trivial piece can be adjusted by one tick without breaking something, so once each island can be tested separately, that might be good enough. That doesn't mean there are no weird exceptions out there, but it seems like they would be rare... and maybe at least slightly non-trivial.

The script still runs the object for a full cycle per cell. It might speed things up by quite a bit to collect all the cell counts in one cycle, and skip the ones that are all zeroes. This will be the list of cells that are ON at some point:

Code: Select all

clist = []
for gen in xrange(p):
    clist+=g.getcells(rect)
    g.run(1)
clist = g.evolve(clist,0)

It would take a good bit of memory to store the full ON/OFF pattern for every cell in a large pattern, though not so much as it might because you don't have to check every cell in the bounding box any more. On the other hand, for patterns big enough that memory is going to be a problem, I think time is going to be a much bigger problem with the current method...!

A possible compromise would be to add a new layer, and use evolve() and putcells() to add every phase of the original object into the new layer, stacked one bounding rectangle on top of the other. Then Golly will do the storage for you fairly efficiently, and you can just calculate a location for each cell in each phase instead of re-running the oscillation cycle a bajillion times. Then g.dellayer() when you're done with it.

[BlinkerSpawn]

Offhand I can't come up with a case where a non-trivial piece can be adjusted by one tick...

The only instances I can think of are oscillators deleting junk. (e.g. a blocker sparking a block)

[Rhombic]

Test 3 has been implemented. I have added to the comments at the beginning an explanation about the tests (the higher the number, the higher the priority in its "diagnosed triviality").
Test 3 solves the problem with Rich's p16 in the xp208.

Code: Select all

# trivialhunterv1.3.py
# Authors: Dave Greene, Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.
# Possible runs: <test 1: t>; <test 1: nt><test 2: nt><test 4: t/nt>; <test 1: nt><test 2: t><test 3: t>; <test 1: nt><test 2: t><test 3: nt><test 4: t/nt>
# The last test to be run has the highest priority (i.e. it correctly characterises the triviality).

import golly as g

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1

def test4():
    return 1 #WIP

p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = [] # <test 1>
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
triv2=0
cellcount=0
outliers=[]
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1:
    g.exit("Trivial oscillator, with a maximum cell period of %d." % maxp)
else:
    g.show("Apparent non-trivial oscillator, proceeding to check non-interacting subperiodic patterns...")
    maxp = p
File.close()
D=open("cell_periods.txt","r").readlines() # <test 2>
Dprime=[]
AlreadyChecked=[]
Edge=[]
Pdict={}
for line in D[1:]:  # skip the header line
    case=line[:-1].split("\t")
    period = int(case[2])
    Pdict[str(case[:2])]=period
    if period==maxp:
        AlreadyChecked.append(case[:2])
        Edge.append(case[:2])
    Dprime.append(case[:2])
Edgeprime=[]
while 1:
    Edgeprime[:]=[]
    for cell in xrange(len(Edge)):
        for dx, dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]:
            coord = [str(int(Edge[cell][0])+dx),str(int(Edge[cell][1])+dy)]
            if coord in Dprime and Pdict[str(coord)]!=1:
                    if coord not in AlreadyChecked:
                        AlreadyChecked.append(coord)
                        Edgeprime.append(coord)
    Edge[:]=Edgeprime[:]
    if Edgeprime==[]: break
for hunt in Dprime:
    if hunt not in AlreadyChecked and Pdict[str(hunt)]!=1:
        triv2=1
        cellcount+=1
        outliers+=[int(hunt[0]),int(hunt[1])]
if triv2==0:
    g.exit("Apparent non-trivial oscillator... checking for trivial combinations of overlapping oscillators...") #CHANGE G.EXIT TO G.SHOW FOR FINAL VERSION
    test4() # <test 4>
else:
    g.show("Apparent trivial oscillator, with a %d-cell oscillating outlier... checking phase dependence..." % cellcount)
pattern=g.getcells(rect) # <test 3>: once finished, test 4 has to be run; for mistake see forums
dephase=[]
for Cell in xrange(len(outliers)/2):
    for Dx, Dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[0,0],[1,0],[-1,1],[0,1],[1,1]]:
        cx, cy = outliers[2*Cell]+Dx, outliers[2*Cell+1]+Dy
        if g.getcell(cx, cy)==1:
            dephase.append(cx)
            dephase.append(cy)
g.addlayer() # is this very slow?
g.putcells(outliers)
outrect=g.getrect()
g.select(outrect)
g.clear(0)
Dephased = g.evolve(dephase,1)
g.putcells(Dephased)
g.select(outrect)
g.clear(1)
Dephased = g.getcells(g.getrect())
g.clear(0)
g.dellayer()
g.duplicate()
for _cell in xrange(len(outliers)/2):
    cx, cy = outliers[2*_cell], outliers[2*_cell+1]
    g.setcell(cx,cy,0)
g.putcells(Dephased)
newrect = g.getrect()
init = g.hash(newrect)
g.run(p)
if g.hash(newrect)==init:
    g.select(g.getrect())
    g.clear(0)
    g.dellayer()
    g.addlayer()
    g.putcells(outliers)
    g.exit("Oscillator is confirmed to be trivial. The outlier rotor is shown in this layer.")
else:
    g.select(g.getrect())
    g.clear(0)
    g.dellayer()
    g.exit("Apparently not trivial... checking for trivial combinations of overlapping oscillators...") #CHANGE G.EXIT TO G.SHOW FOR FINAL VERSION
    test4() # <test 4>

Apart from those comments, there is something else to build on.
Given a blinker+xp208:

Code: Select all

x = 40, y = 33, rule = B3/S23
b2o8b2o$b2o9bo7bo$b2o9bobo4bobo12b2o$bo11b2o5bo13b3o$obo6b2o23b2obo$ob
2o5b2o25bobo$27b2o6bo2bo$26bo2bo6b2o$b2o18b2o4b2o$b2o17bo2bo$20bo2bo$
21bobo12b2o$36b2o$b2o33b2o$o2bo32bo$obo20bo4b2o5bobo$bob2o19bo3b2o5bob
2o$2b3o13bo3b3o$3b2o12bobo$18bo17b2o$36b2o2$16bo3bo$15bobobobo$16b2ob
2o3$2b3o7b5o3b5o$12bob4ob4obo$12b2obobobobob2o11b2o$13bobobobobobo12bo
bo$14b3o3b3o15bo$15bo5bo16b2o!

The test 3 says: OK, there's this group of cells to analyse (includes blinker and half p16). When it runs them once, due to the p16 it will all collapse. The test therefore reports "apparently non-trivial".
There should be a way to, once it proves that overall it's non-trivial, to find the non-trivial island, remove it from the outliers list and REPEAT test 3.
The outliers list will consist of the trivial bit, exclusively.

then
if len(outliers)==0: <test 4>
else: proved to be trivial!

------

I have already thought about a way to do test 4, but it seems a bit processor-intensive (and time-consuming, most importantly), so any ideas that still support non-totalistic rules are welcome.

------

EDIT: added flow chart

[dvgrn]

Apart from those comments, there is something else to build on.
Given a blinker+xp208...

An isolated blinker like this is a relatively easy case. You could pick any random cell in the outliers list, and do the same spreading-edge trick as in the original analysis until you can't add any more cells to Group 1. Group 1 cells all neighbor each other but don't affect the rest of the outliers. Pick another cell in the remaining outliers and repeat until there are no more cells in the outliers that haven't joined a group.

You could also maybe get some information about which group a cell belongs to by its period, but that's not foolproof. A few cells in a period-N oscillator might just happen to be period N/2 or N/3 or whatever -- e.g., this oscillator has a scattering of p2 and p3 cells:

Code: Select all

x = 8, y = 21, rule = B3/S23
3bo$2bobo$2bobo$4bo$3bo$3b3o$2b5o$bo3bobo$o5bo$bob2o2$3b2obo$bo5bo$obo
3bo$b5o$2b3o$4bo$3bo$3bobo$3bobo$4bo!

So probably best to not even look at the periods.

The tough cases are along the lines of the p208 chained with p16 chained with p8, second pattern in my last post. The first test pattern is p60 but has no p60 cells, so it's trivial right away... but not if we add a true p60 to it:

Code: Select all

x = 58, y = 39, rule = B3/S23
45bo$43bobo$34bo7bobo$33b2o6bo2bo11b2o$32b2o4b2o2bobo11b2o$22b2o7b3o4b
2o3bobo$22b2o8b2o4b2o5bo$33b2o$34bo5$28b3o$28b2o$24b3ob2o18b2o$25b2o2b
o3bo15bo$25b2o3b4o15bob2o$21bo3bo5b3o14b2obo$21b4o24bobo$21b3o7b3o13b
3ob2o$31b4o14bobo$16bo6b3o5bo3bo13bob3o$3b2o10bobo4b4o9b2ob3o6b3obo$2b
o12bo2bo2bo3bo9b2ob2o9bobo$o4bo2b2o10b2o12b3ob2o8b2ob3o$4obo4bo5bobob
2o17bo3bo5bobo$5bobo4bobo3bob3o17b4o5bob2o$2b4obob4ob4o23b3o4b2obo$bo
5bo43bo$2b4obob4ob4o23b3o7b2o$5bobo4bobo2bo23b4o$4obo4bo3bo26bo3bo3b4o
$o4bo2b2o4b2o29b2obo3bo$2bo42b2obobo$3b2o39b3o$48bo2bo$49bobo$50bo!

This one's ugly because you definitely can't remove just the p2 cells, or just the p4 cells, or even the p2 cells and the p4 cells together. To find the independent p4 island on the left side, you have to jump across a gutter-like line of always-OFF cells to add more cells to the island, including the p1 stator cells... but then find the right place to stop extending. Even then, you can't successfully remove the island from the rest of the compound oscillator in this version -- though you can in the original.

Or does this not really matter? Do you want this last example to be reported as trivial, or non-trivial? The lower period oscillators stuck on to the p60 part don't interact with each other, and really don't have anything to do with making the pattern period 60. None of the pieces can be removed without breaking the whole pattern, unless you do some special surgery to redraw the stator around the part you take out.

How about the original version, with a similar p60 added? You could separate the p4 part at least, if you could somehow algorithmically find the right island of p4, p2, and p1 cells to remove. Triviality doesn't really depend on the quality of the weld between non-interacting pieces, does it?

[Rhombic]

An isolated blinker like this is a relatively easy case. You could pick any random cell in the outliers list, and do the same spreading-edge trick as in the original analysis until you can't add any more cells to Group 1. Group 1 cells all neighbor each other but don't affect the rest of the outliers. Pick another cell in the remaining outliers and repeat until there are no more cells in the outliers that haven't joined a group.

You could also maybe get some information about which group a cell belongs to by its period, but that's not foolproof. A few cells in a period-N oscillator might just happen to be period N/2 or N/3 or whatever -- e.g., this oscillator has a scattering of p2 and p3 cells:

Code: Select all

x = 8, y = 21, rule = B3/S23
3bo$2bobo$2bobo$4bo$3bo$3b3o$2b5o$bo3bobo$o5bo$bob2o2$3b2obo$bo5bo$obo
3bo$b5o$2b3o$4bo$3bo$3bobo$3bobo$4bo!

So probably best to not even look at the periods.

Good idea. I'll implement it this evening.

The tough cases are along the lines of the p208 chained with p16 chained with p8, second pattern in my last post. The first test pattern is p60 but has no p60 cells, so it's trivial right away... but not if we add a true p60 to it:

Code: Select all

x = 58, y = 39, rule = B3/S23
45bo$43bobo$34bo7bobo$33b2o6bo2bo11b2o$32b2o4b2o2bobo11b2o$22b2o7b3o4b
2o3bobo$22b2o8b2o4b2o5bo$33b2o$34bo5$28b3o$28b2o$24b3ob2o18b2o$25b2o2b
o3bo15bo$25b2o3b4o15bob2o$21bo3bo5b3o14b2obo$21b4o24bobo$21b3o7b3o13b
3ob2o$31b4o14bobo$16bo6b3o5bo3bo13bob3o$3b2o10bobo4b4o9b2ob3o6b3obo$2b
o12bo2bo2bo3bo9b2ob2o9bobo$o4bo2b2o10b2o12b3ob2o8b2ob3o$4obo4bo5bobob
2o17bo3bo5bobo$5bobo4bobo3bob3o17b4o5bob2o$2b4obob4ob4o23b3o4b2obo$bo
5bo43bo$2b4obob4ob4o23b3o7b2o$5bobo4bobo2bo23b4o$4obo4bo3bo26bo3bo3b4o
$o4bo2b2o4b2o29b2obo3bo$2bo42b2obobo$3b2o39b3o$48bo2bo$49bobo$50bo!

This one's ugly because you definitely can't remove just the p2 cells, or just the p4 cells, or even the p2 cells and the p4 cells together. To find the independent p4 island on the left side, you have to jump across a gutter-like line of always-OFF cells to add more cells to the island, including the p1 stator cells... but then find the right place to stop extending. Even then, you can't successfully remove the island from the rest of the compound oscillator in this version -- though you can in the original.

Or does this not really matter? Do you want this last example to be reported as trivial, or non-trivial? The lower period oscillators stuck on to the p60 part don't interact with each other, and really don't have anything to do with making the pattern period 60. None of the pieces can be removed without breaking the whole pattern, unless you do some special surgery to redraw the stator around the part you take out.

How about the original version, with a similar p60 added? You could separate the p4 part at least, if you could somehow algorithmically find the right island of p4, p2, and p1 cells to remove. Triviality doesn't really depend on the quality of the weld between non-interacting pieces, does it?

By test 3, if you can shift the phase by one and it still works, it's trivial - I mean, you could substitute one of those segments for a still life and it still stabilises that section. Hence, the rotor is not directly stabilising the higher-period rotor. Thankfully, the script already reports this as trivial (I think, I haven't tried just yet), which is the intended behaviour.
EDIT: for some reason, test 3 is not separating it correctly. However, with the new section-by-section implementation, it should clearly distinguish each rotor region, then evolve it one tick. I attempted to do this by hand and it is stable, obviously. Why is the script not doing this?


looped Test 3 implemented:

Code: Select all

# trivialhunterv1.3.1.py
# Authors: Dave Greene, Rhombic
# For a given oscillator, returns "cell_periods.txt" with the subperiod for each individual cell.
# Shows in Golly whether the oscillator is trivial and, if so, what the maximum period is.
# Possible runs: <test 1: t>; <test 1: nt><test 2: nt><test 4: t/nt>; <test 1: nt><test 2: t><test 3: t>; <test 1: nt><test 2: t><test 3: nt><test 4: t/nt>
# The last test to be run has the highest priority (i.e. it correctly characterises the triviality).

import golly as g

def periodic(M):
    incase = 0
    for checkeach in xrange(len(M)-1):
        if M[checkeach+1]!=M[checkeach]:
            return 0
    return 1

def test3(arg1):
    pattern=g.getcells(rect) # <test 3>: once finished, test 4 has to be run
    dephase=[]
    for Cell in xrange(len(arg1)/2):
        for Dx, Dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[0,0],[1,0],[-1,1],[0,1],[1,1]]:
            cx, cy = arg1[2*Cell]+Dx, arg1[2*Cell+1]+Dy
            if g.getcell(cx, cy)==1:
                dephase.append(cx)
                dephase.append(cy)
    g.addlayer()
    g.putcells(arg1)
    outrect=g.getrect()
    g.select(outrect)
    g.clear(0)
    Dephased = g.evolve(dephase,1)
    g.putcells(Dephased)
    g.select(outrect)
    g.clear(1)
    Dephased = g.getcells(g.getrect())
    g.clear(0)
    g.dellayer()
    g.duplicate()
    for _cell in xrange(len(arg1)/2):
        cx, cy = arg1[2*_cell], arg1[2*_cell+1]
        g.setcell(cx,cy,0)
    g.putcells(Dephased)
    newrect = g.getrect()
    init = g.hash(newrect)
    g.run(p)
    if g.hash(newrect)==init: return 1
    return 0

def test4():
    return 1 #WIP

p = int(g.getstring("Period: ","1"))
rect = g.getrect()
for gen in xrange(p):
    g.run(1)
    if g.getrect()[2]>rect[2]:
        rect[0]=g.getrect()[0]
        rect[2]=g.getrect()[2]
    if g.getrect()[3]>rect[3]:
        rect[1]=g.getrect()[1]
        rect[3]=g.getrect()[3]
factors = [] # <test 1>
File = open("cell_periods.txt","w+")
File.write("x\ty\tperiod\n")
triviality=1
triv2=0
cellcount=0
outliers=[]
maxp=1
for i in xrange(p):
    if p%(i+1)==0: factors.append(i+1)
for x in xrange(rect[2]):
    for y in xrange(rect[3]):
        done = 0
        statelist=[]
        statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for j in xrange(p):
            g.run(1)
            statelist.append(g.getcell(rect[0]+x,rect[1]+y))
        for frac in xrange(len(factors)):
            psub = 1
            subperiod=statelist[:factors[frac]]
            for repetition in xrange(p/factors[frac]):
                if statelist[repetition*factors[frac]:(repetition+1)*factors[frac]]!=subperiod: psub = 0
            if psub == 1 and done == 0:
                File.write(str(rect[0]+x)+"\t"+str(rect[1]+y)+"\t"+str(factors[frac])+"\n")
                done = 1
                if factors[frac]==p: triviality=0
                else: maxp=max(maxp,factors[frac])
if triviality==1:
    g.exit("Trivial oscillator, with a maximum cell period of %d." % maxp)
else:
    g.show("Apparent non-trivial oscillator, proceeding to check non-interacting subperiodic patterns...")
    maxp = p
File.close()
D=open("cell_periods.txt","r").readlines() # <test 2>
Dprime=[]
AlreadyChecked=[]
Edge=[]
Pdict={}
for line in D[1:]:  # skip the header line
    case=line[:-1].split("\t")
    period = int(case[2])
    Pdict[str(case[:2])]=period
    if period==maxp:
        AlreadyChecked.append(case[:2])
        Edge.append(case[:2])
    Dprime.append(case[:2])
Edgeprime=[]
while 1:
    Edgeprime[:]=[]
    for cell in xrange(len(Edge)):
        for dx, dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]:
            coord = [str(int(Edge[cell][0])+dx),str(int(Edge[cell][1])+dy)]
            if coord in Dprime and Pdict[str(coord)]!=1:
                    if coord not in AlreadyChecked:
                        AlreadyChecked.append(coord)
                        Edgeprime.append(coord)
    Edge[:]=Edgeprime[:]
    if Edgeprime==[]: break
for hunt in Dprime:
    if hunt not in AlreadyChecked and Pdict[str(hunt)]!=1:
        triv2=1
        cellcount+=1
        outliers+=[int(hunt[0]),int(hunt[1])]
if triv2==0:
    g.exit("Apparent non-trivial oscillator... checking for trivial combinations of overlapping oscillators...") #CHANGE G.EXIT TO G.SHOW FOR FINAL VERSION
    test4() # <test 4>
else:
    g.show("Apparent trivial oscillator, with a %d-cell oscillating outlier... checking phase dependence..." % cellcount)
if test3(outliers)==1: # <test 3>
    g.select(g.getrect())
    g.clear(0)
    g.dellayer()
    g.addlayer()
    g.putcells(outliers)
    g.exit("Oscillator is confirmed to be trivial. The outlier rotor is shown in this layer.")
else:
    g.select(g.getrect())
    g.clear(0)
    g.dellayer()
    g.show("Apparently not trivial... checking for combinations of trivial and non-trivial oscillators...") #CHANGE G.EXIT TO G.SHOW FOR FINAL VERSION
    stilloutliers = []
    newgroup=[]
    for R in xrange(len(outliers)/2):
        stilloutliers.append([str(outliers[2*R]),str(outliers[2*R+1])])
    while len(stilloutliers)>0:
        newgroup[:]=[]
        Edge[:]=[]
        Edge.append(stilloutliers[0])
        [['-1','-2']]
        while 1:
            Edgeprime[:]=[]
            for groupcell in xrange(len(Edge)):
                for Dx, Dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]:
                    Coord = [str(int(Edge[groupcell][0])+Dx),str(int(Edge[groupcell][1])+Dy)]
                    if Coord in stilloutliers and Pdict[str(Coord)]!=1:
                        if Coord not in newgroup:
                            Edgeprime.append(Coord)
                            newgroup.append(int(Coord[0]))
                            newgroup.append(int(Coord[1]))
                            stilloutliers.pop(stilloutliers.index(Coord))
            Edge[:]=Edgeprime[:]
            if Edgeprime==[]: break
        if test3(newgroup)==1: # <test 3>
            g.select(g.getrect())
            g.clear(0)
            g.dellayer()
            g.addlayer()
            g.putcells(newgroup)
            g.exit("Oscillator is confirmed to be trivial. The outlier rotor is shown in this layer.")
        else:
            g.select(g.getrect())
            g.clear(0)
            g.dellayer()
            g.show("Still not trivial... checking for combinations of trivial and non-trivial oscillators...")
    g.show("The oscillator seems to be non-trivial... checking for trivial combinations of overlapping oscillators...")
    test4() # <test 4>

[Rhombic]

Current questions

• Why does test 3, with the iterative rotor-island identification, fail to confirm the triviality of the p60?
• What is a faster way to implement test 4? -Separating cells based on what cells allow them to be born or something
• Once test 3 and test 4 are implemented and bug-free, is there some missing situation that is not accounted for? (I think that it is unlikely - it will most likely be a mistake within a test and not a requirement for a fifth test <test 5>)

Future scope - once all the previous issues are addressed

• Optimisation of everything, while not creating additional bugs, for trivialhunter v2.0
• Expansion into spaceships
• Separating test 4 and potentially using it for apgsearch to separate very strictly non interacting oscillators (i.e. the xp160 ones that don't touch in tlife)
• Make a 2.0 C/C++ standalone version to rapidly sift through either apgcodes stores in a file or through oscillator apgcodes for a given rule in Catagolue

[praosylen]

Separating test 4 and potentially using it for apgsearch to separate very strictly non interacting oscillators (i.e. the xp160 ones that don't touch in tlife)

I actually have a working demo script for this (which I made for apgsearch v0.54+0.3i for that very reason but have not included yet). It currently works only in Life due to dependency on a custom rule, which in theory could be eliminated (but more likely what would happen is generating a version of the custom rule based on the rule of the pattern each time the script is run, just like all Python versions and variants of apgsearch already do). As a bonus, it works for spaceships too. I'll post it in a couple days when I get back from vacation.

[Rhombic]

The tough cases are along the lines of the p208 chained with p16 chained with p8, second pattern in my last post.

I had a better look at it and those kinds of patterns will be checked by test 4. It is equivalent to <test 3>-non-trivial, because the p8+p16 form a single island. Even if one interacted while the other didn't, test 3 is expected to yield non-trivial.
Test 4 should be able to assess the fact that the cells in the vicinity oscillate with the same pattern regardless of whether you separate the p8 and evolve it by itself or attached to the p208. This pattern, together with other ones, should be used to check whether test 4 is working correctly (currently not implemented).

How about the original version, with a similar p60 added? You could separate the p4 part at least, if you could somehow algorithmically find the right island of p4, p2, and p1 cells to remove. Triviality doesn't really depend on the quality of the weld between non-interacting pieces, does it?

Test 3 of the script does not look for other possible stators, so it will be able to identify that a given rotor island is trivial as long as the oscillator is stable when its subperiod is advanced by one tick (i.e. the oscillator is independent of the phase of the subperiodic section).
I'm quite worried about the fact that the third test didn't properly identify a trivial rotor for the p60 example... worrying, bearing in mind that if you select that area and advance it by one tick, the oscillator is still stable... which is exactly what the script was meant to be doing! There must be an issue somewhere.

It currently works only in Life due to dependency on a custom rule, which in theory could be eliminated (but more likely what would happen is generating a version of the custom rule based on the rule of the pattern each time the script is run, just like all Python versions and variants of apgsearch already do). As a bonus, it works for spaceships too. I'll post it in a couple days when I get back from vacation.

Good!! Hopefully, it will be able to run for all non-totalistic rules (potentially including MAP, even?). Worst case scenario, there must be a way to modify it to support them.

[dvgrn]

I'm quite worried about the fact that the third test didn't properly identify a trivial rotor for the p60 example... worrying, bearing in mind that if you select that area and advance it by one tick, the oscillator is still stable... which is exactly what the script was meant to be doing! There must be an issue somewhere.

You'll see at least part of the issue if you add a few diagnostic lines to test3():

Code: Select all

def test3(arg1):
    pattern=g.getcells(rect) # <test 3>: once finished, test 4 has to be run
    dephase=[]
    for Cell in xrange(len(arg1)/2):
        for Dx, Dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[0,0],[1,0],[-1,1],[0,1],[1,1]]:
            cx, cy = arg1[2*Cell]+Dx, arg1[2*Cell+1]+Dy
            if g.getcell(cx, cy)==1:
                dephase.append(cx)
                dephase.append(cy)
    g.addlayer()
    g.putcells(arg1)
    outrect=g.getrect()
    g.select(outrect)
    g.clear(0)
    Dephased = g.evolve(dephase,1)
    g.putcells(Dephased)
    g.select(outrect)
    g.clear(1)
    Dephased = g.getcells(g.getrect())
    g.clear(0)
    g.dellayer()
    g.duplicate()
    g.update()
    g.note("Before")
    for _cell in xrange(len(arg1)/2):
        cx, cy = arg1[2*_cell], arg1[2*_cell+1]
        g.setcell(cx,cy,0)
    g.putcells(Dephased)
    g.update()
    g.note("After")
    newrect = g.getrect()
    init = g.hash(newrect)
    g.run(p)
    if g.hash(newrect)==init: return 1
    return 0

The outliers that test3() is called on are the five apparent islands on the left side -- one p4 island and four p2 islands. Unless they're all advanced together, the test is going to fail, and there's no easy way to figure out how to group them without some difficult rule-specific analysis of what's happening across that inconvenient always-OFF column (it's not exactly a gutter).

I'm not sure why the p3 and p5 groups aren't showing up in their turn and being tested -- but they're also in multiple separate islands, so test3() might try them individually anyway and still fail to figure out that they're trivial, I'm not sure.

What would work (I think) in the p60 case, would be to run test3() on the entire outliers group. Call that test 2.5, I guess...?

I don't think most of your g.clear() statements quoted above are doing anything -- you have usually already gotten a cell list out of the bounding rectangle and are working with it directly. And anything you do to a layer immediately before a g.dellayer(), is not going to have any effect.

It would be nice if you'd get rid of the last of your str(int(x)) conversions. Just make Pdict keys be length-2 lists of ints. It's an annoying refactoring job, but possibly worthwhile for speed as well as readability reasons. You can make some other lists into dictionaries also; anywhere where you're saying "if X in Y" is likely to run a lot faster if Y is a dictionary.

Another minor readability thing: I think all the lines like newgroup[:]=[] could be just newgroup=[].

[Rhombic]

I don't think most of your g.clear() statements quoted above are doing anything -- you have usually already gotten a cell list out of the bounding rectangle and are working with it directly. And anything you do to a layer immediately before a g.dellayer(), is not going to have any effect.

It would be nice if you'd get rid of the last of your str(int(x)) conversions. Just make Pdict keys be length-2 lists of ints. It's an annoying refactoring job, but possibly worthwhile for speed as well as readability reasons. You can make some other lists into dictionaries also; anywhere where you're saying "if X in Y" is likely to run a lot faster if Y is a dictionary.

Another minor readability thing: I think all the lines like newgroup[:]=[] could be just newgroup=[].

g.clear() --> Golly keeps asking if I want to save when deleting a non-empty layer... hahaha
newgroup=[] does not delete the previous list, just assigns the variable name to a new, empty list. If I'm not mistaken, this could be a waste of computer memory.

As for the dictionaries, I'll see what I do with those soon.

----

I see what you mean by the islands. As an example, the one furthest to the left is split into two before evolving, but that causes the oscillator to break apart for obvious reasons. Since test3() is remarkably fast (compared to test 2 and almost certainly test 4), do you think a combinatorial selection of islands would work?

i.e. the outliers are divided into A, B and C. Try advancing 1 generation: A, B, C, A+B, A+C, B+C, A+B+C.
Would that work?

[dvgrn]

g.clear() --> Golly keeps asking if I want to save when deleting a non-empty layer...

Ah, that mostly explains it. I usually have that safety check turned off in Preferences > Layer. g.clear() is kind of a slow way to avoid that popup window, though, and I thought the popup wasn't supposed to appear on a layer generated entirely by a script. Will do some more checking when I get a chance -- there should be a faster workaround.

newgroup=[] does not delete the previous list, just assigns the variable name to a new, empty list. If I'm not mistaken, this could be a waste of computer memory.

This is the kind of thing I could be wrong about, but my understanding is that the previous list will be garbage collected as soon as the reference count goes to zero -- or soon after that, anyway, at Python's discretion. In which case, it's not something you're supposed to have to worry about, unlike in C/C++ where it's a lot easier to end up with annoying memory leaks. You'd only run into trouble if you had assigned another variable that was still pointing to the old list.

In my experience the good habit to get into is to write listb = lista[:], or listb = list(lista), by default, because in practice I seldom really need or want listb = lista, with two variables confusingly pointing at the same list. Plain listb = [] seems pretty safe, though -- only one variable, therefore no multiple references.

I see what you mean by the islands. As an example, the one furthest to the left is split into two before evolving, but that causes the oscillator to break apart for obvious reasons. Since test3() is remarkably fast (compared to test 2 and almost certainly test 4), do you think a combinatorial selection of islands would work?

Once you've accumulated all the islands into an islandlist variable, it's probably a good idea to check the length before attempting any combinatorial analysis. Even for the p60 sample I think there are fifteen islands in the whole outliers group, so you might have to check 2^15 = 32768 island combinations. And this isn't the hardest problem that will ever be thrown at the Triviality Tester, no doubt. Maybe report a countdown of the total number of combinations in the status bar, and allow the test to be halted by keyboard input or a reasonable timeout, if you go that route.

Of course you can stop after the first advanced-by-one combination turns out to be stable, so mostly the unworkably slow cases would be ones with a really big pile of outlier islands that all support each other:

Code: Select all

#C p60 with dozens of mutually supporting islands
x = 71, y = 74, rule = B3/S23
44b2ob2o$44b2obo$47bo2bo$47b4o2$47b4o$47bo3bob3o$49bobob2o$53b2o$48bo
2bo2bo3bo$48bobo4b4o$49bo6b3o2$56b3o$49b3o3b4o$50b2o2bo3bo$50b2ob2o$
46bo3bo2b2o$46b4o3b3o$46b3o$23b3ob3o$24b2ob2o19b3o$24b2ob2o12b3o3b4o$
20bo3bo3bo3bo9b2o2bo3bo$20b4o5b4o9b2ob2o$20b3o7b3o5bo3bo2b2o$38b4o3b3o
$20b3o5b3o7b3o$13b3o3b4o5b4o$14b2o2bo3bo5bo3bo5b3o$14b2ob2o13b2o3b4o$
10bo3bo2b2o13b2o2bo3bo$10b4o3b3o11b3ob2o$10b3o22b2o$35b3o$12b3o43bo$5b
3o3b4o41bobo$6b2o2bo3bo32bo7bobo$6b2ob2o35b2o6bo2bo11b2o$2bo3bo2b2o34b
2o4b2o2bobo11b2o$2b4o3b3o23b2o7b3o4b2o3bobo$2b3o30b2o8b2o4b2o5bo$46b2o
$3o44bo$4o$o3bo$4b2ob3o$4b2ob2o$3b3ob2o32b3o$8bo3bo28b2o$9b4o24b3ob2o
18b2o$10b3o25b2o2bo3bo15bo$38b2o3b4o14bo$8b3o23bo3bo5b3o14b2o$8b4o22b
4o24bo$8bo3bo21b3o7b3o14bo$12b2ob3o26b4o13b2o$12b2ob2o19b3o5bo3bo13bo$
11b3ob2o12b3o3b4o9b2ob3o7bo$16bo3bo9b2o2bo3bo9b2ob2o8b2o$17b4o9b2ob2o
12b3ob2o9bo$18b3o5bo3bo2b2o17bo3bo4bo3bo$26b4o3b3o17b4o5b4o$16b3o7b3o
25b3o$16b4o44b2o$16bo3bo5b3o25b3o7b2o$20b2o3b4o25b4o$20b2o2bo3bo25bo3b
o3b4o$19b3ob2o33b2obo3bo$23b2o33b2obobo$23b3o31b3o$61bo2bo$62bobo$63bo!

Ultimately it may be worth figuring out how to link these kinds of islands together in a rule-independent way, across these always-OFF gaps. (There will be always-ON gaps in some rules, too, right?) That way at worst we have a lot fewer islands to combine.

Will think about that some more when I get a chance also. The problem has probably been solved before, several times, by people much cleverer than I am...!

[praosylen]

Okay, here's the demo script for spacetime decomposition (what I call test 4):

Code: Select all

import golly as g
def nest(cl):
    rtn = []
    if len(cl) % 2:
        for i in xrange(len(cl)/3):
            rtn.append((cl[i*3],cl[i*3+1],cl[i*3+2]))
    else:
        for i in xrange(len(cl)/2):
            rtn.append((cl[i*2],cl[i*2+1]))
    return rtn
def flatten(cl):
    rtn = []
    for i in cl:
        rtn += list(i)
    if len(cl[0]) == 3 and not len(rtn) % 2:
        rtn.append(0)
    return rtn
def decompose_0(pat, period, dispx, dispy, w, alpharule, single):
    pats = []
    g.new("Decomposing")
    g.putcells(pat)
    while True:
        '''#
        g.fit()
        g.update()
        q = g.getstring("q")#'''
        g.setrule("APG_Decayer_Test")
        cls = nest(g.getcells(g.getrect()))
        i = 0
        while cls[i][2] != 1:
           i += 1
        g.setcell(cls[i][0], cls[i][1], 3)
        '''#
        g.fit()
        g.update()
        g.getstring("")#'''
        for _ in xrange(1000):#!Find better test for this
            '''#
            if q:
                g.fit()
                g.update()
                g.getstring("")#'''
            #g.step()
            t = True
            r = g.getrect()
            cls = nest(g.getcells(r))
            for i in cls:
                if i[2] > 2:
                    for j in [(x,y) for x in (-1,0,1) for y in (-1,0,1)]:
                        for k in (-1,0,1):
                            x = i[0]+j[0]+k*w
                            if x > (r[0] + r[2]):
                                x -= w*period + dispx
                                y -= dispy
                            elif x < r[0]:
                                x += w*period + dispx
                                y += dispy
                            c = g.getcell(x, i[1]+j[1])
                            if 0 < c < 3 and not ((i[2] == 4 or c == 2) and k):
                                g.setcell(x, i[1]+j[1], c+2)
                                t = False
            if t:
                break
        r = g.getrect()
        if single:
            r[2] = w
        pats.append(g.getcells(r))
        g.setrule("//9")
        g.run(4)
        g.setrule("APG_Decayer_Test")
        g.step()
        if g.getpop() == "0":
            break
    return pats
def decompose(pattern, period, dispx, dispy, alpharule):
    #'''
    g.new("Analyzing")
    g.putcells(pattern)#'''
    origrule = g.getrule()
    rect = g.getrect()
    w = rect[2] + 10#!Should test over all gens
    pat = g.getcells(rect)
    #period = int(g.getstring("Enter period of object:"))
    g.new("Preparing")
    for i in xrange(period):
        g.putcells(pat, i*w, 0)
        pat = g.evolve(pat, 1)
    pats = decompose_0(g.getcells(g.getrect()), period, dispx, dispy, w, alpharule, False)
    g.setrule("APG_Decayer_Test")
    for i in xrange(len(pats)):
        pats[i] = g.evolve(pats[i], 1)
    g.setrule("APG_TreeMaker_" + alpharule + "_Test")
    for i in pats:
        g.putcells(g.evolve(i, 1))
        '''g.fit()
        g.update()
        g.getstring("")'''
    pats = decompose_0(g.getcells(g.getrect()), period, dispx, dispy, w, alpharule, True)
    g.setrule("APG_Decayer_Test")
    g.putcells(pat)
    for i in xrange(len(pats)):
        g.putcells(g.evolve(pats[i], 1), i*w, 100)
    g.setrule(origrule)
    #return [g.evolve(i, 1) for i in pats]
decompose(g.getcells(g.getrect()), int(g.getstring("Enter period of object:")), int(g.getstring("Enter x-displacement of object:")), int(g.getstring("Enter y-displacement of object:")), g.getrule().replace("/", ""))
g.fit()

Here are the three associated rules you'll need to run it (I lied, two of them are specific to Life at the moment, but only one of them will be problematic to extend to arbitrary rules, which is what I was remembering):

Code: Select all

@RULE APG_TraverseTrees_B3S23_Test
Actually a simple 3-dimensional cellular automaton represented by this simple 2-dimensional cellular automaton and some python code. There's probably a way to significantly speed up the decomposition process by doing some partial 3d handling here.
@TABLE
n_states:5
neighborhood:Moore
symmetries:permute
var a={0,1,2,3,4}
var aa=a
var ab=a
var ac=a
var ad=a
var ae=a
var af=a
var b={3,4}
1,b,a,aa,ab,ac,ad,ae,af,3
2,b,a,aa,ab,ac,ad,ae,af,4

Code: Select all

@RULE APG_Decayer_Test
@TABLE
n_states:9
neighborhood:vonNeumann
symmetries:permute
var a={0,1,2,3,4,5,6,7,8}
var aa=a
var ab=a
var ac=a
8,a,aa,ab,ac,0
7,a,aa,ab,ac,0
6,a,aa,ab,ac,2
5,a,aa,ab,ac,1
4,a,aa,ab,ac,0
3,a,aa,ab,ac,1
2,a,aa,ab,ac,0
1,a,aa,ab,ac,0
0,a,aa,ab,ac,0

Code: Select all

@RULE APG_TreeMaker_B3S23_Test
@TABLE
n_states:3
neighborhood:Moore
symmetries:permute
var a={0,1,2}
var aa=a
var ab=a
var ac=a
var ad=a
var ae=a
var af=a
var ag=a
0,1,1,1,0,0,0,0,0,2

Test case (enter 8, 0, and 0):

Code: Select all

x = 33, y = 41, rule = B3/S23
5b2obob2o$5bob3obo2$6b2ob2o$2b2obobob2o$2b2ob2o2$2b2ob2o$bobob2o$b2o2$
b2o$b2o2$b2o$b2o3$2o$2obo$3bo$3bo3b2o$o2bo3b2o$b2o2$6b2o$6b2obo$9bo$9b
o$6bo2bo4bobo$7b2o8bo$13bo2bo12b2o$7b4obobobo$7bo2bobo2bo4bo7bo3bo$10b
o2b2o3b2obo5bo4bo$9b2o6bo8bobobo$16bobo2bo3bobobo$16bo2bo3bo4bo$17b2o
4bo3bo2$25b2o!

It also works for moving objects; just enter the displacement. The only things I've found so far that it fails for are ambiguous decompositions like the one in that test case. Multiple-copy RROs would also be problematic if they were known to exist in Life.

[Rhombic]

Okay, here's the demo script for spacetime decomposition (what I call test 4):

Code: Select all

test 4

Here are the three associated rules you'll need to run it (I lied, two of them are specific to Life at the moment, but only one of them will be problematic to extend to arbitrary rules, which is what I was remembering):

Code: Select all

rules

It also works for moving objects; just enter the displacement. The only things I've found so far that it fails for are ambiguous decompositions like the one in that test case. Multiple-copy RROs would also be problematic if they were known to exist in Life.

I'll add it this evening, and I'll read the apgsearch code to see how to automatically save the auxiliary rules (ExpungeGliders,ContagiousLife,etc.) to add something similar for this.
This is a very good step forward in the right direction; however, ideally, this should support many rules (for example, to list non-trivial rotors from certain B*3-i/S*1e2i rules after looking up the Catagolue object lists).
There probably is a way to change both of those rules you mentioned to allow other totalistic and non-totalistic rules. In fact, the worst case scenario is to find some other way to do it.

I'll add your code to the current script and see. After that, I'll first of all tackle the issue with test 3... Only once it works near-perfectly for B3/S23 can we think about other rules. For now, just "making sure we don't make wild assumptions that would only be true for CGoL" is already a decent way to save time in the future.

EDIT: I've been having to do some paperwork lately so I haven't done it yet. I'll do it in the near future.

[praosylen]

Okay, here's something problematic I found with my test 4 prototype:

Code: Select all

x = 23, y = 106, rule = B3/S23
4b2o$4b2o2$2obob3o$ob2obo2bo$6b2o39$7bo2$7bo2$7bo2$4bo2bo2bo2$5bobobo
2$7bo46$4b2o$4b2o2$5b3o11b2obo$5bo2bo10bob2o$6b2o!

[Rhombic]

Okay, here's something problematic I found with my test 4 prototype:

Code: Select all

x = 23, y = 106, rule = B3/S23
4b2o$4b2o2$2obob3o$ob2obo2bo$6b2o39$7bo2$7bo2$7bo2$4bo2bo2bo2$5bobobo
2$7bo46$4b2o$4b2o2$5b3o11b2obo$5bo2bo10bob2o$6b2o!

To account for extra non-totalistic functionality... do you think it would be possible to re-model test 4 based on a conditional evolution tester, from gaps in the generation number and active cell regions? Many of them will collapse if you remove a crucial spark, but if there is at least one way in which you can separate the oscillator into A and B, with the periods of the cells in the initial oscillator being IDENTICAL to (A+B), then it would be trivial.
NB: this allows non totalistic rules, and the only issues would surely be with the breakup of the oscillators, but this has to be possible anyway.