One dimension cellular automation in Python

Here is my implementation for one dimensional cellular automation in Python. Any suggestions for more efficiency - other strategies?

ncells = ['111','110','101','100','011','010','001','000']

def next_state (state, rule):
newstate = ''
binrule = bin(rule)[2:]
binrule = (8-len(binrule))*'0' + binrule
for i in range(len(state)):
cells = state[i-1] + state[i] + state[(i+1)%len(state)]
newstate += binrule[ncells.index(cells)]
return newstate

def wolfram (init_state, generations, rule):
state = init_state
for i in range(generations):
yield state
state = next_state(state, rule)

for i in wolfram('000000000010000000000', 30, 30):
print i


binrule = bin(rule)[2:]
binrule = (8-len(binrule))*'0' + binrule


you can use string formatting:

binrule = '{:08b}'.format(rule)

• Let the caller compute binrule so this only gets done once.

• Better yet, precompute a transition table: a dictionary that maps cell triplets directly to the new values.

transitions = dict(zip(ncells, binrule))

• Slightly more convenient than this

for i in range(len(state)):
cells = state[i-1] + state[i] + state[(i+1)%len(state)]


is this:

padded_state = state[-1] + state + state[0]
for i in range(len(state)):


Putting it all together:

NCELLS = ['111','110','101','100','011','010','001','000']

def next_state(state, transition_table):
padded_state = state[-1] + state + state[0]
triplets = [padded_state[i:i+3] for i in range(len(state))]
newstate = ''.join(transition_table[cells] for cells in triplets)
return newstate

def wolfram(init_state, generations, rule):
state = init_state
binrule = '{:08b}'.format(rule)
transitions = dict(zip(NCELLS, binrule))
for i in range(generations):
yield state
state = next_state(state, transitions)

for i in wolfram('000000000010000000000', 30, 30):
print i


ncells.index(cells) is linear. You could treat cells as a binary number and use it as an index in a code array. Not sure whether the access in constant time compensates the cost of the conversion with an 8-rule though.