File:OT spaceship map.png: Difference between revisions

A map of the outer-totalistic rulespace (spanning all 512² rules), by support for spaceships.

Birth conditions are in a Gray code rightwards in the x axis (with b0 having the highest precedence, occupying the right half, b1 the central half, b2 the central halves of each half, etc.), survival ones are in one downwards in the y axis (with s0 having the highest precedence in the left half and s8 in the right half). In the bottom-right quadrant, the birth conditions' precedence is inverted again, to make it appear less fragmented.

Each one is coloured in accordance with the existence of spaceships in it. (For s8 rules, only the empty space of off cells is considered a valid background agar, except for the bottom-right quadrant, which has b0 so considers only the all-on agar, and as such duplicates all rules in the left half without S8, so may be excluded in a future version.)

Green rules have explicit examples known in the extension of David Eppstein's glider database, while the existence of spaceships in red ones is disproven. Black ones are unknown, grey rules are strobing thereof, and the white one (in a top-right corner of a green part in the top-left corner, and duplicated in the bottom-right) is Life.

The proofs regarding strobing rules come from this post by LaundryPizza03.

Generated by means of the following program (the disproofs from LaundryPizza03 enclosed in double-brackets)

import os,sys
from functools import reduce
from itertools import product,chain,starmap
ORsum=lambda l: reduce(int.__or__,l,0)
tarmap=lambda f,*l:tuple(starmap(f,*l))
tilter=lambda f,i: tuple(filter(f,i))

def niceA030101(d,n):
    b=d-1#d.bit_length()-1
    l=b.bit_length()
    o=c=(1<<(1<<l))-1
    for i in range(l):
        s=1<<l+~i #s=1<<i
        o^=o<<s #o=c//((1<<(s<<1))-1)*((1<<s)-1)
        n=(n&o)<<s|n>>s&o
    return(n>>1+(~d^~0<<d.bit_length()) if d&d-1 else n)

from PIL import Image
mask=~(~0<<9)
rules=[False]*(1<<18)
with open(os.path.join(sys.path[0],'R1-C2-NM-gliders.db.txt'),newline='') as db: #https://github.com/jedlimlx/HROT-Glider-DB/blob/master/R1-C2-NM-gliders.db.txt
    for s in db:
        for _ in range(2): s=s[s.index(':')+1:]
        minr=s[:(c:=s.index(':'))]
        s=s[c+1:]
        maxr=s[:s.index(':')]
        minr,maxr=map(lambda r: (lambda b,s: b|s<<9)(*map(lambda t: ORsum(map(lambda i: (str(i) in t)<<i,range(9))),r.split('/'))),(minr,maxr))
        diff=minr^maxr
        indexes=tilter(lambda i: diff>>i&1,range(18))
        for rule in map(ORsum,product(*map(lambda i: (0,1<<i),indexes))):
            rules[rule|minr]=True
            if minr&1 and ~minr&1<<17: #strobing
                rules[niceA030101(18,~(~0<<18)^(rule|minr))]=True #black/white reversal
spaceship=lambda b,s: rules[b|s<<9]
img=Image.frombytes('RGB',2*(1<<9,),bytes(chain.from_iterable(tarmap(lambda b,s: (lambda b,s: 3*(0xff,) if b==0b1000 and s==0b1100 else (0,0xff,0) if spaceship(b,s) else ((0xff,spaceship(b,s) and 0xff,0) if not(~b&0b1110 or s&0b11100000) or not(~b&0b111110000 or s&0b11111) or not(~b&0b011110000 or s&0b11110) or not((b^0b0010)&0b1110 or (s^0b1100000)&0b11100000) or ~b&1<<1 and s&1<<7 or b&1<<1 and ~b&1<<2 and not ~s&0b11<<6 or (((~b&0b10 or ~b&0b1100 and not s&0b1111 or not b&0b1100 and not s&1 or not s&0b11111) and (s&1<<7 or not ~b&0b111110000 or not ~b&0b111100000 and s&0b1100000 or b&1<<8 and not ~s&0b1100000) or s&1<<6 and not b&0b110 or not ~s&0b11<<6 and not b&0b100 or not ~b&0b1110 and not s&0b111<<5)) else 3*(0x33,)) if b&1 else (0xff,spaceship(b,s) and 0xff,0) if not b&0b1110 or not ~s&0b1111 or b&0b10 or not(~b&0b1100) and s&1 or not (s^0b11110)&0b11111 or ((b&0b10 or not ~b&0b1100 and s&1 or not ~s&0b1111110 or not ~b&0b11000 and not ~s&0b111110 or not ~b&0b111000 and not ~s&0b11110 or ~b&0b100 and not ~s&0b11111100 or not ~s&0b11111 or b&0b11<<2 and not ~s&0b1111)) else 3*(0,))(*((niceA030101(9,mask^s),niceA030101(9,mask^b)) if b&1 and s&1<<8 else (b,s))),starmap(lambda x,y: map(lambda n: niceA030101(9,n^n>>1),(x,y)) if x<1<<8 else (niceA030101(9,x^x>>1),y^y>>1) if y<1<<8 else ((x&~(1<<8))^(x&~(1<<8))<<1|1,y^y>>1),product(range(1<<9),repeat=2)) if True else chain(product(map(lambda n: niceA030101(9,n^n>>1),range(1<<8)),map(lambda n: niceA030101(9,n^n>>1),range(1<<9))),product(map(lambda n: niceA030101(9,n^n>>1),range(1<<8,1<<9)),map(lambda n: n^n>>1,range(1<<9)))))))).transpose(5)
img.show()