Find the rule of a cellular automaton

There are already many challenges where you are given a cellular automaton rule and an initial state and you have to find the state after a certain number of steps. This challenge is the opposite: you are given the states of a pattern in several consecutive steps, and you need to find the rule of the cellular automaton.

Rules

In this challenge, we will only consider life-like cellular automata. A rule of a life-like cellular automaton is defined by two sets of integers in the range 0 to 8, which we will call the B set and the S set. The cellular automaton is played on a 2D grid of cells, where each cell can be either alive or dead. In each generation, the state of each cell is determined by the following rules:

• A dead cell becomes alive in the next generation if the number of its living neighbors is in the B set.
• A living cell stays alive in the next generation if the number of its living neighbors is in the S set.
• Otherwise, the cell dies or remains dead.

For example, when B = {3} and S = {2,3}, we have the famous Conway's Game of Life.

For simplicity, we assume that the B set does not contain 0. (If it did, the dead cells in the background would become alive in the next generation, so the pattern would be unbounded.)

Example

Let's take the famous Glider pattern as an example. Here are the states of the Glider in the first 3 generations, where 0 represents a dead cell and 1 represents a living cell:

Step 0:
[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]

Step 1:
[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]

Step 2:
[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]


One possible rule for this pattern is B = {3} and S = {2,3}. But there are other rules that the pattern satisfies. For example, B = {3, 6, 7, 8} and S = {0, 2, 3, 5, 6, 7, 8} is another possible rule. In fact, the glider satisfies all rules where the B set contains 3 but does not contain 0, 1, 2, 4, 5, and the S set contains 2, 3 but does not contain 1, 4.

In this challenge, you may output any rule that the pattern satisfies.

Input

The input is a list of binary matrices, each representing the state of the pattern in a generation.

The matrices are guaranteed to have the same dimensions and contain only 0s and 1s. They are padded with two layers of 0s on all sides, so that you don't need to worry about the edges of the grid.

Output

You can output the rule in any reasonable format. For example, Conway's Game of Life can be represented as:

• A string, like "B3/S23".
• A list of two lists, like [[3], [2, 3]].
• A list of two integers interpreted as bitsets, like [8, 12], where 8 = 2^3 and 12 = 2^2 + 2^3.

When there are multiple possible rules, you can output any of them.

This is , so the shortest code in bytes wins.

Testcases

Since there are multiple possible outputs, in the following testcases I will give a minimal rule and a maximal rule that the pattern satisfies. Your output's B and S sets should be a subset of the sets in the maximal rule and a superset of the sets in the minimal rule.

[[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]]
=> [[3], [2, 3]] - [[3, 6, 7, 8], [0, 2, 3, 5, 6, 7, 8]]

[[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]]]
=> [[3], [2]] - [[3, 4, 5, 6, 7, 8], [0, 2, 3, 4, 5, 6, 7, 8]]

[[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]]]
=> [[], [2, 3]] - [[3, 4, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8]]

[[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]]
=> [[2], []] - [[2, 4, 5, 6, 7, 8], [0, 3, 4, 5, 6, 7, 8]]


Python 3, 142 bytes

lambda x:[{sum(c,-i)for a,b in zip(x,x[1:])for*c,d in zip(*[sum(a[j//3:],[0])[j%3:]for j in range(9)],sum(b[1:],[]))if c[4]^i<d}for i in(0,1)]


Try it online!

Output two sets [B, S].

(Ab)uses the guaranteed two layers of 0-padding. Stole the condition from Jonathan Allan's Python 3 solution.

• Nice work - I started thinking of ways to get rid of enumerate, but it was late. Commented May 9 at 19:12

Python 3, 150 bytes

...or 149 in Python 2 by changing // to /.

-1 Thanks to att - subtract d when considering the cell itself to avoid needing to ignore it.)

lambda p,e=enumerate:[{sum(b[i+n%3-1][j+n//3-1]for n in range(9))-d for b,a in zip(p,p[1:])for i,r in e(b)for j,s in e(r)if s^d<a[i][j]}for d in(0,1)]


An unnamed function that accepts the pattern, p, and returns the minimal B and S as a list of two sets.

Try it online!

The deltas to neighbours are calculated from n in range(9) as:

$$n$$ $$\delta x=n \pmod 3 - 1$$ $$\delta y=\lfloor \frac{n}{3} \rfloor - 1$$ comment
0 -1 -1
1 0 -1
2 1 -1
3 -1 0
4 0 0 ignored (-d)
5 1 0
6 -1 1
7 0 1
8 1 1
• -1 byte
– att
Commented May 9 at 1:04

Charcoal, 50 bytes

ＩＥ²Φ⁹⊙θ∧ξ⊙ν⊙⌕Ａ§§θ⊖ξρι∧§πς⁼⁺ιλΣＥ✂§θ⊖ξ⊖ρ⁺²ρ¹Σ✂τ⊖ς⁺²ς


Attempt This Online! Link is to verbose version of code. Sadly doesn't work on TIO due to having six nestings of loops. Finds the minimal rule. Explanation:

ΣＥ✂§θ⊖ξ⊖ρ⁺²ρ¹Σ✂τ⊖ς⁺²ς


Calculate the sum of a 3x3 area around the old cell.

⁼⁺ιλ


Compare that to the target value, but exclude the old cell itself.

∧§πς


Check that the new cell is in fact live.

⊙θ∧ξ⊙ν⊙⌕Ａ§§θ⊖ξρι


Check all the new cells where the old cell has the old state.

ＩＥ²Φ⁹


Map over both cell states, finding all necessary neighbour counts and output the results for dead and live cells with a blank line in between.

Python3, 235 bytes

E=enumerate
def f(b):
B,S=[],[]
for i in range(len(b)-1):
for x,r in E(b[i]):
for y,v in E(r):
if b[i+1][x][y]:[B,S][v]+=[sum(b[i][x+X][y+Y]for X,Y in[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(-1,-1),(1,-1)])]
return{*B},{*S}


Try it online!

• if b[i+1][x][y]:[B,S][v]+=[sum(b[i][x+X][y+Y]for X,Y in[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(-1,-1),(1,-1)])] saves 85 bytes.
– Neil
Commented May 7 at 15:48

APL(Dyalog Unicode), 56 bytes SBCS

Assume ⎕io←0

A tacit train that takes a three-dimensional array where time is the leading axis and outputs B and S in a nested array.

(⊂1 3)⌷((⍳4),∘,2⊥¨2,⌿⊢){⊂∪⍵~9}⌸(4⌿9),∘,¯1↓{+/,⍵}⌺1 3 3-⊢


Try it on APLgolf!

(⊂1 3)⌷((⍳4),∘,2⊥¨2,⌿⊢){⊂∪⍵~9}⌸(4⌿9),∘,¯1↓{+/,⍵}⌺1 3 3-⊢
,¯1↓{+/,⍵}⌺1 3 3-⊢  1. ravelled adjacent counts, with the last iteration removed
(4⌿9),∘                    2. prepend 1. with 9 9 9 9
(      ,2⊥¨2,⌿⊢)                                   3. ravelled encoded state transitions, with 0->0 as 0, 0->1 as 1, and so on.
((⍳4),∘        )                                   4. prepend 3. with 0 1 2 3
{⊂∪⍵~9}⌸                           5. group 2. by 4. and discard 9
(⊂1 3)⌷                                                   6. take the 2nd and the 4th items in 5


We do 2. and 4. to sort the output of 5. and to deal with potential empty B and S.

Scala 3, 336 bytes

Golfed version. Attempt This Online!

g=>{var b,s=Set.empty[Int];for(i<-0to g.size-2){for(x<-g(i).indices){for(y<-g(i)(x).indices){if(g(i+1)(x)(y)==1){val n=Seq((1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(-1,-1),(1,-1)).map{case(j,k)=>(x+j,y+k)}.filter{case(r,t)=>r>=0&&t>=0&&t<g(i).size&&t<g(i)(x).size}.map{case(r,t)=>g(i)(r)(t)}.sum;if(g(i)(x)(y)==1)s+=n else b+=n}}}};(b,s)}


Ungolfed version. Attempt This Online!

object Main {
def computeNeighbors(grids: Array[Array[Array[Int]]]): (Set[Int], Set[Int]) = {
var birth = Set.empty[Int]
var survival = Set.empty[Int]

for (i <- 0 until grids.length - 1) {
for (x <- grids(i).indices) {
for (y <- grids(i)(x).indices) {
if (grids(i + 1)(x)(y) == 1) {
val neighbors = List((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1))
.map { case (dx, dy) => (x + dx, y + dy) }
.filter { case (nx, ny) => nx >= 0 && ny >= 0 && nx < grids(i).length && ny < grids(i)(x).length }
.map { case (nx, ny) => grids(i)(nx)(ny) }
.sum

if (grids(i)(x)(y) == 1) survival += neighbors
else birth += neighbors
}
}
}
}

(birth, survival)
}

def main(args: Array[String]): Unit = {
val grids1 = Array(
Array(
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 1, 0, 1, 0, 0, 0),
Array(0, 0, 0, 1, 1, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0)
),
Array(
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 1, 0, 0, 0, 0),
Array(0, 0, 0, 0, 1, 1, 0, 0),
Array(0, 0, 0, 1, 1, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0)
),
Array(
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 0, 0, 0, 1, 0, 0),
Array(0, 0, 0, 1, 1, 1, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0)
)
)
println(computeNeighbors(grids1))

val grids2 = Array(
Array(
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 1, 1, 1, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0)
),
Array(
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0)
)
)
println(computeNeighbors(grids2))

val grids3 = Array(
Array(
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 1, 0, 1, 0, 0),
Array(0, 0, 1, 1, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0)
),
Array(
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 1, 0, 0, 0),
Array(0, 0, 1, 0, 1, 0, 0),
Array(0, 0, 1, 1, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0)
)
)
println(computeNeighbors(grids3))

val grids4 = Array(
Array(
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 1, 1, 0, 0, 0),
Array(0, 0, 1, 0, 0, 1, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0)
),
Array(
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 1, 1, 0, 0, 0),
Array(0, 0, 1, 0, 0, 1, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0),
Array(0, 0, 0, 0, 0, 0, 0, 0)
)
)
println(computeNeighbors(grids4))
}
}