Generating rows of a rule 30 cellular automaton

Question

Rule 30 is a one dimensional cellular automaton where only the cells in the previous generation are considered by the current generation. There are two states that a cell can be in: 1 or 0. The rules for creating the next generation are represented in the row below, and depend on the cell immediately above the current cell, as well as it's immediate neighbours.

The cellular automaton is applied by the following rule (using bitwise operators):

left_cell ^ (central_cell | right_cell)

This rule forms the table below:

Now I tried to implement these rules into Python, using numpy. I defined an initial state that accepts width as a parameter and produces an initial row of zeros with 1 in the middle.

def initial_state(width):
    initial = np.zeros((1, width), dtype=int)
    if width % 2 == 0:
        initial = np.insert(initial, int(width / 2), values=0, axis=1)
        initial[0, int(width / 2)] = 1
        return initial
    else:
        initial[0, int(width / 2)] = 1
        return initial

The function below just produces the second generation given an initial row. How do I create a for loop that keeps producing new generations until the first element of the last bottom row becomes 1?

def rule30(array):
    row1 = np.pad(array,[(0,0), (1,1)], mode='constant')
    next_row = array.copy()
    for x in range(1, array.shape[0]+1):
        for y in range(1, array.shape[1]+1):
            if row1[x-1][y-1] == 1 ^ (row1[x-1][y] == 1 or row1[x-1][y+1] == 1):
                next_row[x - 1, y - 1] = 1
            else:
                next_row[x - 1, y - 1] = 0
        return np.concatenate((array, next_row))

For example, if the input is

A = [0, 0, 0, 1, 0, 0, 0]

The output should be

>>> print(rule30(A))
[[0, 0, 0, 1, 0, 0, 0],
 [0, 0, 1, 1, 1, 0, 0],
 [0, 1, 1, 0, 0, 1, 0],
 [1, 1, 0, 1, 1, 1, 1]]

Answer 1

Method 1 - Numpy

You could achieve this using the following slight modification to your current code - alter the return value of rule30 to return np.array(next_row). Then you can use the following function:

def apply_rule(n):
    rv = initial_state(n)
    while rv[-1][0] == 0:
        rv = np.append(rv, rule30(rv[-1].reshape(1,-1)), axis=0)
    return rv

Usage:

>>> apply_rule(7)
array([[0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 1, 1, 0, 0],
       [0, 1, 1, 0, 0, 1, 0],
       [1, 1, 0, 1, 1, 1, 1]])

Or plotted:

>>> plt.imshow(apply_rule(7), cmap='hot')

Method 2 - Lists

Alternatively, you could use the following solution without using numpy, which uses a few functions to apply the Rule 30 logic across each triple in each padded list, until the stop-condition is met.

Code:

def rule(t):
    return t[0] ^ (t[1] or t[2])

def initial_state(width):
    initial = [0]*width
    if width%2:
        initial[width // 2] = 1
    else:
        initial.insert(width//2, 1)
    return initial

def get_triples(l):
    return zip(l,l[1:],l[2:])       

def rule30(l):
    return [rule(t) for t in get_triples([0] + l + [0])]

def apply_rule(width):
    rv = [initial_state(width)]
    while not rv[-1][0]:
        rv.append(rule30(rv[-1]))
    return rv

Usage:

>>> apply_rule(7)
[[0, 0, 0, 1, 0, 0, 0],
 [0, 0, 1, 1, 1, 0, 0],
 [0, 1, 1, 1, 0, 1, 0],
 [1, 1, 1, 0, 0, 1, 1]]
>>> [''.join(str(y) for y in x) for x in apply_rule(7)]
['0001000',
 '0011100',
 '0111010',
 '1110011']

Matplotlib visualisation (using either method):

import matplotlib.pyplot as plt
plt.figure(figsize=(10,6))
plt.imshow(apply_rule(250), cmap='hot')

Answer 2

Here is the code based on string representations and lookup. It does use some of the ideas from the comments above. Besides I added padding for handling edge cells - the conditions were unclear about that. Also note that your proposed patterns table is not symmetric. Compare new states for '110' and '011'.

def rule30(a):
    patterns = {'111': '0', '110': '0', '101': '0', '100': '1',
                '011': '1', '010': '1', '001': '1', '000': '0', }
    a = '0' + a + '0'  # padding
    return ''.join([patterns[a[i:i+3]] for i in range(len(a)-2)])

a = '0001000'
result = [list(map (int, a))]

while a[0] != '1':
    a = rule30(a)
    result.append (list(map (int, a)))
print (result)  # list of lists 
print (np.array(result))  # np.array

list of lists:

[[0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 1, 1]]

np.array:

array([[0, 0, 0, 1, 0, 0, 0],
       [0, 0, 1, 1, 1, 0, 0],
       [0, 1, 1, 0, 0, 1, 0],
       [1, 1, 0, 1, 1, 1, 1]])