21
$\begingroup$

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:
enter image description here
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:
enter image description here
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$:
enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ Has anyone considered running nauty on this? You are essentially counting connected subgraphs of a not very large graph which avoid certain degree counts. Gerhard "Use Hammer To Make Tool" Paseman, 2018.01.03. $\endgroup$ – Gerhard Paseman Jan 4 '18 at 0:40
30
$\begingroup$

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,1 and backtracking if:

  • the number of live cells plus the number of connected components exceeds $N+1$,2
  • the number of live cells plus the actual minimum number of additional cells needed to join the components together3 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,4 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}$All 1-step vanishing polyplets with up to 18 cells in Conway's Game of Life

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}$Extensible family of vanishing polyominoes in Conway's Game of Life

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

$\hspace{82px}$Family of vanishing polyominoes in Conway's Game of Life, extended by 8 cells

(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.

$\endgroup$
  • 1
    $\begingroup$ Yes, your last polyplet gives a new boundary pattern able to produce infinitely many 1-step vanishing polyplets. It is a kind of generalization of the second polyplet given by Noam D. Elkies. It can also be mixed with the boundary pattern I proposed. I wonder whether the boundary patterns can be classified in some sense. The inner structure can be seen as an independent problem. $\endgroup$ – Sebastien Palcoux Jan 4 '18 at 0:29
21
$\begingroup$

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{◻◻◼◼◻◻} }$$

$\endgroup$
  • $\begingroup$ Do they complete the classification for $n \le 12$? $\endgroup$ – Sebastien Palcoux Jan 3 '18 at 9:47
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I tried a computation online, it works up to $n=6$, but then the computation stops after 60s. How long did you need for $n=7$? How long a usual laptop should need for $n=8$? for $n=9$? According to oeis.org/A030222, the $n$-polyplets has been computed by Matthew Cook (et al.) up to $n=17$, so perhaps the list exists somewhere. $\endgroup$ – Sebastien Palcoux Jan 3 '18 at 23:51
  • 1
    $\begingroup$ Also note that 1-step vanishing patterns in standard GoL (rule B3/S23) are exactly the same as still life patterns in the "semi-complementary" rule B3/S0145678, so any existing software for exhaustively enumerating still lifes (or oscillators or spaceships) in Life-like cellular automata could be directly repurposed as long as they don't have the GoL rules hardcoded. $\endgroup$ – Ilmari Karonen Jan 4 '18 at 6:19
  • 1
    $\begingroup$ It should be pretty efficient, if you make sure to prune the search space as early as possible. For an even more efficient search, you could use something like David Eppstein's de Bruijn graph based spaceship search algorithm (which is actually directly applicable: just search for "spaceships" with speed 0 and period 1 in rule B3/S0145678) with extra pruning rules to reject patterns that are disconnected or too large. $\endgroup$ – Ilmari Karonen Jan 4 '18 at 15:55
  • 1
    $\begingroup$ @SebastienPalcoux After a rewrite and some more computation time I have completed the classification of $n \leq 12$. $\endgroup$ – W W Jan 8 '18 at 23:04
  • 1
    $\begingroup$ @SebastienPalcoux: True, connectedness is a global property. But if you're generating the pattern e.g. row by row, it should be possible to keep track of the connected components of each partial pattern and to prune any extension that either a) closes off a component so that it cannot be connected to the rest of the pattern, or b) has two separate components so far apart that connecting them would require exceeding the $n$ cell limit. I'd expect the time savings from restricting the search space to be worthwhile, even with the extra cost of tracking the connected components. $\endgroup$ – Ilmari Karonen Jan 8 '18 at 23:10
5
$\begingroup$

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:
enter image description here
For the infinite part, we will do three steps. Firstly, the family beginning as follows:

enter image description here

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:

enter image description here

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

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

enter image description here

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$.

$\endgroup$
  • 1
    $\begingroup$ Nice. I added another extensible family of vanishing polyominoes to my own answer. In fact, there seem to be plenty of such families. $\endgroup$ – Ilmari Karonen Jan 19 '18 at 22:39
  • $\begingroup$ @IlmariKaronen: The quality of your representation is that it is unified for $n≥16$. The quality of my representation is that the symmetry group of any representative is non-trivial. $\endgroup$ – Sebastien Palcoux Jan 19 '18 at 23:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.