One dimension cellular automation in Python

Question

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

Janne Karila · Accepted Answer · 2014-12-01 19:18:03Z

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

Aristide · Accepted Answer · 2014-12-01 17:27:42Z

2

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.

answered Dec 1, 2014 at 17:27

Aristide

1836 bronze badges

Add a comment |

Stack Exchange Network

One dimension cellular automation in Python

2 Answers 2

You must log in to answer this question.

Hot Network Questions

One dimension cellular automation in Python

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions