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

\$\endgroup\$
1
  • \$\begingroup\$ Nice work - I started thinking of ways to get rid of enumerate, but it was late. \$\endgroup\$ May 9 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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte \$\endgroup\$
    – att
    May 9 at 1:04
2
\$\begingroup\$

Charcoal, 50 bytes

IE²Φ⁹⊙θ∧ξ⊙ν⊙⌕A§§θ⊖ξρι∧§πς⁼⁺ιλΣE✂§θ⊖ξ⊖ρ⁺²ρ¹Σ✂τ⊖ς⁺²ς

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✂§θ⊖ξ⊖ρ⁺²ρ¹Σ✂τ⊖ς⁺²ς

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.

IE²Φ⁹

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.

\$\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!

\$\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\$
    – Neil
    May 7 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.

\$\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))
  } 
}
\$\endgroup\$

Your Answer

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

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