The 1-step vanishing polyplets on Conway's game of life

Question

A $n$-polyplet is a collection of $n$ cells on a grid which are orthogonally or diagonally connected.
The number of $n$-polyplets is given by the OEIS sequence A030222: $1, 2, 5, 22, 94, 524, 3031, \dots$

See below the five $3$-polyplets:

A polyplet will be called $1$-step vanishing on Conway's game of life, if every cell dies after one step.
We observed that for $n\le 4$, a $n$-polyplet is $1$-step vanishing iff $n \le 2$.

We found $1$-step vanishing polyplets with $n=9, 12$, see below:

Question: Is there an other $1$-step vanishing $n$-polyplet with $n \le 12$?
If yes, what are they? (note that there are exactly $37963911$ $n$-polyplets with $n \le 12$).

We can build infinitely many $1$-step vanishing polyplets with such pattern, see below with $n=142$:

Bonus question: Are there $1$-step vanishing polyplets of an other kind?

Answer 1

Here are two more vanishing 12-plets similar to yours:

$$ \substack{ \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻} \cr \displaystyle{◻◻◼◼◼◼} \cr \displaystyle{◼◼◼◼◻◻} \cr \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻} } \quad \substack{ \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻} \cr \displaystyle{◻◻◼◼◼◼} \cr \displaystyle{◼◼◼◼◻◻} \cr \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◼◻◻◻} } $$

I found these using JavaLifeSearch, combined with manual filtering of the search results to skip any non-polyplet patterns. I'm pretty sure that, together with your 9- and 12-plet and the 9- and 10-plets found by Noam D. Elkies, these (and their rotations and mirror images) are the only vanishing polyplets with 5 to 12 cells in Conway's Game of Life. That said, it's always possible that I've made some kind of a mistake in my search or filtering, so independent confirmation would be nice to have.

(It's perhaps worth noting that 1-step vanishing patterns in standard GoL (rule B3/S23) are exactly the same as still lifes in the "semi-complementary" alternative rule B3/S0145678, i.e. where the birth rules are the same, but live cells survive if and only if they would not survive in standard GoL. Thus, any existing software for exhaustively enumerating still lifes — or oscillators or spaceships, of which still lifes are a special case — in Life-like cellular automata could be used for this, at least as long as it doesn't have the standard GoL rules hardcoded.)

As for your bonus question, I'm not sure what you mean by "of an other kind", but it's pretty easy to use tools like JLS to construct large vanishing polyplets with arbitrarily complex boundaries and inner structure, like this somewhat whimsical example:

$$\substack{ \displaystyle{◼◻◼◼◻◻◼◼◻◼◼◻◻◼◼◻◻◼◼◻◼◼◻◻◼◼◻◼} \cr \displaystyle{◻◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◻} \cr \displaystyle{◼◼◻◼◻◼◼◻◻◻◼◼◻◼◼◼◼◻◼◼◼◼◼◻◻◼◼◼} \cr \displaystyle{◼◼◻◼◻◼◼◻◼◼◼◼◻◼◼◼◼◻◼◼◼◼◻◼◼◻◼◼} \cr \displaystyle{◻◼◻◻◻◼◼◻◻◻◼◼◻◼◼◼◼◻◼◼◼◼◻◼◼◻◼◻} \cr \displaystyle{◼◼◻◼◻◼◼◻◼◼◼◼◻◼◼◼◼◻◼◼◼◼◻◼◼◻◼◼} \cr \displaystyle{◼◼◻◼◻◼◼◻◻◻◼◼◼◻◻◻◼◼◻◻◻◼◼◻◻◼◼◼} \cr \displaystyle{◻◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◻} \cr \displaystyle{◼◻◼◼◻◻◼◼◻◼◼◻◻◼◼◻◻◼◼◻◼◼◻◻◼◼◻◼} }$$

---

Update: I finally went and wrote a basic exhaustive search script (available on GitHub here) to find these patterns. The actual search code is currently written in (pretty awful) Python; I may (or may not) clean it up later, and maybe rewrite it in some more efficient language like C or C++. (There's also a simple Perl script to filter equivalent rotated and mirror image patterns from the output, and to sort them by live cell count.)

The search script uses a simple depth first search to fill in an $N+2$ times $N$ cell grid with live and dead cells, starting from a single live cell at the top left,¹ and backtracking if:

• the number of live cells plus the number of connected components exceeds $N+1$,²
• the number of live cells plus the actual minimum number of additional cells needed to join the components together³ exceeds $N$,
• a connected component is closed off by dead cells, so that it cannot be extended and joined with the rest of the pattern,⁴ or
• the most recently added cell or one of its neighbors cannot be part of a valid still life / one-step vanishing pattern according to the CA rule.

A lot of those checks are inefficiently implemented, and in any case Python is not a very fast language to begin with. Even so, it only took me an hour or so on my old laptop to enumerate all the one-step vanishing polyplets in GoL with up to $N = 16$ cells, and a couple of days to get up to $N = 20$.

The total number of distinct polyplets of various sizes found by my script (not counting rotated and mirror image versions separately) are:

$$ \begin{array}{r|r} \text{cells} & 1 & 2 & 9 & 10 & 12 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline \text{polyplets} & 1 & 2 & 2 & 1 & 3 & 10 & 1 & 45 & 27 & 70 & 98 & 285 \end{array} $$

Here's a picture showing all the 18-cell and smaller vanishing polyplets:

$\hspace{14px}$

As I rather expected, while some of the larger polyplets are nicely symmetric or feature obviously generalizable repetitive motifs, as the permitted number of cells gets larger more and more of the patterns look like random agglomerations of cells with no obvious structure or symmetry. While it should not be difficult to exhibit families of vanishing polyplets that can have any (sufficiently large) cell count, perimiter or enclosed area, a nontrivial classification of all vanishing polyplets in GoL seems as hopeless as attempting to classify all still lifes (or oscillators or spaceships).

---

^{1) The grid wraps around from left to right, so the pattern can in fact expand both ways from the starting cell. (It does so in a somewhat peculiar way, so that the right side of each row wraps to the left side of the next row; this effectively makes the 2-dimensional GoL lattice equivalent to a 1-dimensional CA lattice with a funny neighborhood shape.) Making the grid $N+2$ cells wide ensures that an $N$-cell pattern cannot actually reach around the whole grid, and the output code takes care to shift the grid so that the leftmost column of the pattern is actually printed on the first column of the output.}

^{2) Each additional connected component beyond the first necessarily requires at least one additional live cell to connect it to the rest of the pattern. The top-down left-to-right filling order ensures that adding a new live cell can never connect more than two components.}

^{3) This is a somewhat slower calculation, and so the cruder lower bound of one cell per component is checked first. This is also the part that took me the longest to debug, and if there are any remaining bugs in the code, my money would be on this being where they are. That said, I've checked that, at least up to $N = 14$, disabling this check does not actually change the output, so I'm fairly confident that it works.}

^{4) If this was the only connected component, then we've just completed a valid polyplet and will call the output code. Either way, the search will still backtrack the same way regardless.}

---

Ps. To answer a question posed in the comments, yes, vanishing $n$-plets (and, in fact, $n$-ominoes) exist for all $n \ge 14$. For example, the following family of vanishing 16 to 23 cell polyominoes:

$\hspace{82px}$

is easily extensible to all higher cell counts, as shown below for 24 to 32 cells:

$\hspace{82px}$

(In fact, even the 20 to 23 cell polyominoes above are just simple extensions of the 16 to 19 cell ones.) Together with the 14 and 15 cell polyominoes already found by the brute force search, these cover all the sizes from 14 cells up.

Answer 2

Yes, there are others, such as the alternative $n=9$ example

$$\substack{ \displaystyle{◻◼◻◻◻} \cr \displaystyle{◻◻◼◻◼} \cr \displaystyle{◻◼◼◼◻} \cr \displaystyle{◼◻◼◻◻} \cr \displaystyle{◻◻◻◼◻} }$$

and this orthogonally connected example with $n=10$ (i.e. a dekomino (sp?)):

$$\substack{ \displaystyle{◻◻◼◼◻◻} \cr \displaystyle{◼◼◼◼◼◼} \cr \displaystyle{◻◻◼◼◻◻} }$$

Answer 3

Since it looks like no one else has tried programmatic search I thought I'd give it a try.

I wrote the following Haskell program which generates finds vanishing polyplets.

data Polyplet = Polyplet {
 members :: [(Int,Int)],
 nonmembers :: [(Int,Int)]
} deriving Show

eq :: (Eq a) => [a] -> [a] -> Bool
eq [] [] = True
eq a []  = False
eq [] b  = False
eq (t:a) b = eq a (filter (/=t) b)

instance Eq Polyplet where
 (Polyplet a _) == (Polyplet b _) = any (eq a) [zero $ f $ g $ b|f<-[id,syma,syma.syma,syma.syma.syma],g<-[id,symb]]

syma p = [(b,-a)|(a,b)<-p] 
symb p = [(-a,b)|(a,b)<-p]

size :: Polyplet -> Int
size (Polyplet p _) = length p

zero :: [(Int,Int)] -> [(Int,Int)]
zero p = do
 let mx = minimum [x|(x,_)<-p];
 let my = minimum [y|(_,y)<-p];
 [(x-mx,y-my)|(x,y)<-p];

zeroPolyplet :: Polyplet -> Polyplet
zeroPolyplet (Polyplet p np) = do
 let mx = minimum [x|(x,_)<-p];
 let my = minimum [y|(_,y)<-p];
 Polyplet [(x-mx,y-my)|(x,y)<-p] [(x-mx,y-my)|(x,y)<-np]

rangify l = [minimum l..maximum l]

deadsAt :: Polyplet -> (Int,Int) -> [(Int,Int)]
deadsAt (Polyplet p _) x = filter(`notElem`p) $ adjacents x 

-- Maybe rename? --
allDeads :: Polyplet -> [(Int,Int)]
allDeads polyplet@(Polyplet p np) = uniquify $ filter (`notElem` np) $ p >>= deadsAt polyplet

maxLive :: Polyplet -> (Int,Int) -> Int
maxLive (Polyplet _ np) x = sum [1|u<-adjacents x,notElem u np]

minLive :: Polyplet -> (Int,Int) -> Int
minLive (Polyplet p _) x = 8 - sum [1|u<-adjacents x,notElem u p]

-- Could this be made faster? --
uniquify :: (Eq a) => [a] -> [a]
uniquify u = [a|(a,b) <- zip u [0..],notElem a $ take b u]

adjacents :: (Int,Int) -> [(Int,Int)]
adjacents (a,b) = [(a+x,b+y)|x<-[-1..1],y<-[-1..1],(x,y)/=(0,0)]

forbiddenMinor :: Polyplet -> Bool
forbiddenMinor polyplet@(Polyplet p np) = [1|lCell<-p,maxLive polyplet lCell<4,minLive polyplet lCell>1] ++ [1|dCell<-np,maxLive polyplet dCell == 3,minLive polyplet dCell == 3] == []

partitions :: (Num a,Eq a) => a -> [b] -> [([b],[b])]
partitions _ [] = [([],[])]
partitions 0 x  = [([],x)]
partitions n (x:xs) = (map (\(a,b) -> (x:a,b)) $ partitions (n-1) xs) ++ (map (\(a,b) -> (a,x:b)) $ partitions n xs)

subPolyplets :: Int -> Polyplet -> [Polyplet]
subPolyplets max polyplet@(Polyplet p np) = [Polyplet (addingLive ++ p) (addingDead ++ np)|(addingLive,addingDead) <- init $ partitions max $ allDeads polyplet]

zipCat :: [[a]] -> [[a]] -> [[a]]
zipCat [] b = b
zipCat a [] = a
zipCat (a:as) (b:bs) = (a ++ b): zipCat as bs

regroup :: [Polyplet] -> [[Polyplet]]
regroup [] = []
regroup (x:xs) = zipCat (regroup xs) $ replicate (length (members x) - 1) [] ++ [[x]]

fillPolyplets :: Int -> Int -> [[Polyplet]]
fillPolyplets 1 n = [Polyplet [(0,0)] []] : replicate (n-1) []
fillPolyplets x n = do
 let previous = fillPolyplets (x-1) n
 zipCat previous $ map (filter forbiddenMinor . uniquify . map zeroPolyplet) $ regroup $ (previous !! (x-2)) >>= subPolyplets (n-x+1)

vanishing :: Polyplet -> Bool
vanishing polyplet@(Polyplet p np) = all ((`notElem`[5,6]).length.deadsAt polyplet) p && all ((/=5).length.deadsAt polyplet) (allDeads polyplet ++ np)

getVanishingPolyplets :: Int -> [Polyplet]
getVanishingPolyplets n = fillPolyplets n n >>= (filter vanishing)

Try it online!

You can envoke it like so in ghci

mapM_ (print.members) $ getVanishingPolyplets 7

The program is not very fast but I have been able to get a complete classification for vanishing polyplets of size $n \leq 12$. Perhaps better techniques/more powerful computers can exhaust larger cases.

Here are the results of running it on $n=12$:

$$ \substack{ \displaystyle{◻◻◻} \cr \displaystyle{◻◼◻} \cr \displaystyle{◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻} \cr \displaystyle{◻◼◼◻} \cr \displaystyle{◻◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻} \cr \displaystyle{◻◻◼◻} \cr \displaystyle{◻◼◻◻} \cr \displaystyle{◻◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻} \cr \displaystyle{◻◼◼◼◼◼◻} \cr \displaystyle{◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◻◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻◻◻◻} \cr \displaystyle{◻◻◻◻◼◻◻} \cr \displaystyle{◻◼◻◼◻◻◻} \cr \displaystyle{◻◻◼◼◼◻◻} \cr \displaystyle{◻◻◻◼◻◼◻} \cr \displaystyle{◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◻◻◻◻} \cr } $$ $$ \substack{ \displaystyle{◻◻◻◻◻◻◻◻} \cr \displaystyle{◻◻◻◼◼◻◻◻} \cr \displaystyle{◻◼◼◼◼◼◼◻} \cr \displaystyle{◻◻◻◼◼◻◻◻} \cr \displaystyle{◻◻◻◻◻◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻◻◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◼◼◼◻} \cr \displaystyle{◻◼◼◼◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◻◻◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻◻◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◼◼◼◻} \cr \displaystyle{◻◼◼◼◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◻◻◻◻◻} \cr } \quad \quad \quad \substack{ \displaystyle{◻◻◻◻◻◻◻◻} \cr \displaystyle{◻◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◼◼◼◻} \cr \displaystyle{◻◼◼◼◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◼◻◻◻◻} \cr \displaystyle{◻◻◻◻◻◻◻◻} \cr } $$

All of these were previously found by others, however now we can be certain that there are no other vanishing polyplets of size less than $12$ that we are unaware of.

There also seems to be an issue that some polyplets show up in the output more times than they should. I think this is a problem with the way I handle symmetries but I can't nail it down for sure. Fixing this problem would probably make things considerably faster.

Answer 4

Theorem: The set of positive integers $n$ such that there is a $1$-step vanishing polyplet with $n$ cells is $$ \{1,2,9,10,12,14 \} \cup \mathbb{N}_{\ge 15}$$ It can be represented by $1$-step vanishing polyominoes without hole and a non-trivial symmetry group.

Proof: The finite part is given by:

For the infinite part, we will do three steps. Firstly, the family beginning as follows:

provides the integers $6a+b$ with $b \in \{ 3 , \dots , a+2 \}$. Now, $$6a + (a+2) +1 \le 6(a+1)+3$$ if and only if $a \ge 6$. But $6 \times 6+3 = 39$, so it is ok for $\mathbb{N}_{\ge 39}$.

Next, the gaps of the previous family for $14<n<39$ are given by the set $$\{17,18,19,20,24,25,26,31,32,38\}$$ and can be filled ($n=19,20$ excepted) by the family beginning as follows:

providing the integers $7a+b$ with $b \in \{ 3 , \dots , a+2 \}$.

Finally, $n=19,20$ are given by:

The result follows. $\square$

Bonus question: Can we classify (in some sense) the $1$-step vanishing polyominoes without hole?

There are $21$ such polyominoes with $n$ cells and $n \le 18$.