8
\$\begingroup\$

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]]
asked May 7, 2024 at 3:36
\$\endgroup\$

6 Answers 6

3
\$\begingroup\$

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.

answered May 9, 2024 at 8:27
\$\endgroup\$
1
  • \$\begingroup\$ Nice work - I started thinking of ways to get rid of enumerate, but it was late. \$\endgroup\$ Commented May 9, 2024 at 19:12
3
\$\begingroup\$

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
answered May 7, 2024 at 22:39
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte \$\endgroup\$ Commented May 9, 2024 at 1:04
2
\$\begingroup\$

Charcoal, 50 bytes

IE2Φ9⊙θ∧ξ⊙ν⊙⌕A§§θ⊖ξρι∧§πς=+ιλΣE✂§θ⊖ξ⊖ρ+2ρ1Σ✂τ⊖ς+2ς

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:

ΣE✂§θ⊖ξ⊖ρ+2ρ1Σ✂τ⊖ς+2ς

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.

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

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

IE2Φ9

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.

answered May 7, 2024 at 7:47
\$\endgroup\$
2
\$\begingroup\$

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!

answered May 7, 2024 at 13:42
\$\endgroup\$
1
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ Commented May 7, 2024 at 15:48
1
\$\begingroup\$

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.

answered May 10, 2024 at 5:18
\$\endgroup\$
1
\$\begingroup\$

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))
 } 
}
answered May 13, 2024 at 13:40
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.