2
\$\begingroup\$

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

2 Answers 2

1
\$\begingroup\$
  • Instead of

    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)):
        cells = padded_state[i:i+3]
    

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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