One dimensional cellular automata code in Python..

July 9, 2015 | Computer Science, Math, Python | By: Mark VandeWettering

Inspired by the KnitYak Kickstarter, I thought I would code up a simple Python program that could generate the same sort of patterns that are used in the scarves in the video. If you want to learn more about the mathematical theory of these cellular automata, google for keywords like “1D” “cellular automata” and “steve wolfram”. Without much further explanation, here is the code:

[sourcecode lang=”python”]
#!/usr/bin/env python

# __
# ___ __ __ _ _ _ / _|
# (_-</ _/ _` | ‘_| _|
# /__/\__\__,_|_| |_|
#
# Inspired by the KnitYak Kickstarter, which offers
# mathematical scarves whose patterns are algorithmically
# generated, I thought it would be good to dust off my old
# knowledge and generate the same sort of patterns using
# Python. The patterns are simply printed using ASCII,
# but the code could be adapted to output in other forms
# easily.
#
# Written by Mark VandeWettering
#

import sys
import random

WIDTH=79 # How wide is the pattern?

w = WIDTH * [0] # create the current generation
nw = WIDTH * [0] # and the next generation
w[WIDTH/2] = 1 # populate with a single one

# or alternatively, you can populate it with a random
# initial configuration. If you want to start with
# just a single one, comment the next two lines out.

#for i in range(WIDTH):
# w[i] = random.randint(0, 1)

# How wide is the neighborhood of cells that are
# examined? The traditional Wolfram 1D cellular
# automata uses a neighborhood of 3…

NEIGHBORHOOD=3

# rtab is space for the rule table. It maps all
# numbers from [0, 2**NEIGHBORHOOD) to either a 0 or 1.
rtab = (2**NEIGHBORHOOD) * [0]

# The "rule" is a number which is used to populate
# rtab. The number is in the range [0, 2**(2**NEIGHBORHOOD))
# Many rules generate uninteresting patterns, but some
# like 30 generate interesting, aperiodic patterns.
rule = 30

# This fills in the table…
for i in range(2**NEIGHBORHOOD):
if ((2**i) & rule) != 0:
rtab[i] = 1

def dump(r):
for x in r:
if x == 1:
sys.stdout.write(‘X’)
else:
sys.stdout.write(‘ ‘)
sys.stdout.write(‘\n’)

# and generates 100 lines…

for y in range(100):
dump(w)
for x in range(WIDTH):
sum = 0
for d in range(NEIGHBORHOOD):
sum = sum + (2**d) * w[(x+d+WIDTH – NEIGHBORHOOD/2) % WIDTH]
nw[x] = rtab[sum]
w, nw = nw, w
[/sourcecode]

The pattern this generates with these settings follows. Try adjusting rule to other numbers up to 255 to generate other patterns. Lots will be boring, but some will be pretty interesting.

                                                                               
                                       X                                       
                                      XXX                                      
                                     X  XX                                     
                                    XXXX XX                                    
                                   X   X  XX                                   
                                  XXX XXXX XX                                  
                                 X  X    X  XX                                 
                                XXXXXX  XXXX XX                                
                               X     XXX   X  XX                               
                              XXX   X  XX XXXX XX                              
                             X  XX XXXX X    X  XX                             
                            XXXX X    X XX  XXXX XX                            
                           X   X XX  XX  XXX   X  XX                           
                          XXX XX  XXX XXX  XX XXXX XX                          
                         X  X  XXX  X   XXX X    X  XX                         
                        XXXXXXX  XXXXX X  X XX  XXXX XX                        
                       X      XXX    X XXXX  XXX   X  XX                       
                      XXX    X  XX  XX    XXX  XX XXXX XX                      
                     X  XX  XXXX XXX XX  X  XXX X    X  XX                     
                    XXXX XXX   X   X  XXXXXX  X XX  XXXX XX                    
                   X   X   XX XXX XXXX     XXXX  XXX   X  XX                   
                  XXX XXX X X   X    XX   X   XXX  XX XXXX XX                  
                 X  X   X X XX XXX  X XX XXX X  XXX X    X  XX                 
                XXXXXX XX X  X   XXXX  X   X XXX  X XX  XXXX XX                
               X     X  X XXXXX X   XXXXX XX   XXXX  XXX   X  XX               
              XXX   XXXXX     X XX X    X  XX X   XXX  XX XXXX XX              
             X  XX X    XX   XX  X XX  XXXX X XX X  XXX X    X  XX             
            XXXX X XX  X XX X XXXX  XXX   X X  X XXX  X XX  XXXX XX            
           X   X X  XXXX  X X    XXX  XX XX XXXX   XXXX  XXX   X  XX           
          XXX XX XXX   XXXX XX  X  XXX X  X    XX X   XXX  XX XXXX XX          
         X  X  X   XX X   X  XXXXXX  X XXXXX  X X XX X  XXX X    X  XX         
        XXXXXXXXX X X XX XXXX     XXXX     XXXX X  X XXX  X XX  XXXX XX        
       X        X X X  X    XX   X   XX   X   X XXXX   XXXX  XXX   X  XX       
      XXX      XX X XXXXX  X XX XXX X XX XXX XX    XX X   XXX  XX XXXX XX      
     X  XX    X X X     XXXX  X   X X  X   X  XX  X X XX X  XXX X    X  XX     
    XXXX XX  XX X XX   X   XXXXX XX XXXXX XXXX XXXX X  X XXX  X XX  XXXX XX    
   X   X  XXX X X  XX XXX X    X  X     X    X    X XXXX   XXXX  XXX   X  XX   
  XXX XXXX  X X XXX X   X XX  XXXXXX   XXX  XXX  XX    XX X   XXX  XX XXXX XX  
 X  X    XXXX X   X XX XX  XXX     XX X  XXX  XXX XX  X X XX X  XXX X    X  XX 
XXXXXX  X   X XX XX  X  XXX  XX   X X XXX  XXX  X  XXXX X  X XXX  X XX  XXXX XX
     XXXXX XX  X  XXXXXX  XXX XX XX X   XXX  XXXXXX   X XXXX   XXXX  XXX   X   
    X    X  XXXXXX     XXX  X  X  X XX X  XXX     XX XX    XX X   XXX  XX XXX  
   XXX  XXXX     XX   X  XXXXXXXXXX  X XXX  XX   X X  XX  X X XX X  XXX X   XX 
  X  XXX   XX   X XX XXXX         XXXX   XXX XX XX XXX XXXX X  X XXX  X XX X XX
XXXXX  XX X XX XX  X    XX       X   XX X  X  X  X   X    X XXXX   XXXX  X X  X
    XXX X X  X  XXXXX  X XX     XXX X X XXXXXXXXXXX XXX  XX    XX X   XXXX XXX 
   X  X X XXXXXX    XXXX  XX   X  X X X           X   XXX XX  X X XX X   X   XX
X XXXXX X      XX  X   XXX XX XXXXX X XX         XXX X  X  XXXX X  X XX XXX X X
X     X XX    X XXXXX X  X  X     X X  XX       X  X XXXXXX   X XXXX  X   X X  
XX   XX  XX  XX     X XXXXXXXX   XX XXX XX     XXXXX      XX XX    XXXXX XX XXX
 XX X XXX XXX XX   XX        XX X X   X  XX   X    XX    X X  XX  X    X  X    
X X X   X   X  XX X XX      X X X XX XXXX XX XXX  X XX  XX XXX XXXXX  XXXXXX   
X X XX XXX XXXX X X  XX    XX X X  X    X  X   XXXX  XXX X   X     XXX     XX X
X X  X   X    X X XXX XX  X X X XXXXX  XXXXXX X   XXX  X XX XXX   X  XX   X X  
X XXXXX XXX  XX X   X  XXXX X X     XXX     X XX X  XXXX  X   XX XXXX XX XX XXX
X     X   XXX X XX XXXX   X X XX   X  XX   XX  X XXX   XXXXX X X    X  X  X    
XX   XXX X  X X  X    XX XX X  XX XXXX XX X XXXX   XX X    X X XX  XXXXXXXXX  X
 XX X  X XXXX XXXXX  X X  X XXX X    X  X X    XX X X XX  XX X  XXX        XXX 
X X XXXX    X     XXXX XXXX   X XX  XXXXX XX  X X X X  XXX X XXX  XX      X  XX
X X    XX  XXX   X   X    XX XX  XXX    X  XXXX X X XXX  X X   XXX XX    XXXX  
X XX  X XXX  XX XXX XXX  X X  XXX  XX  XXXX   X X X   XXXX XX X  X  XX  X   XXX
X  XXXX   XXX X   X   XXXX XXX  XXX XXX   XX XX X XX X   X  X XXXXXX XXXXX X   
XXX   XX X  X XX XXX X   X   XXX  X   XX X X  X X  X XX XXXXX      X     X XX X
  XX X X XXXX  X   X XX XXX X  XXXXX X X X XXXX XXXX  X     XX    XXX   XX  X  
 X X X X    XXXXX XX  X   X XXX    X X X X    X    XXXXX   X XX  X  XX X XXXXX 
XX X X XX  X    X  XXXXX XX   XX  XX X X XX  XXX  X    XX XX  XXXXXX X X     XX
 X X X  XXXXX  XXXX    X  XX X XXX X X X  XXX  XXXXX  X X  XXX     X X XX   X  
XX X XXX    XXX   XX  XXXX X X   X X X XXX  XXX    XXXX XXX  XX   XX X  XX XXX 
 X X   XX  X  XX X XXX   X X XX XX X X   XXX  XX  X   X   XXX XX X X XXX X   X 
XX XX X XXXXXX X X   XX XX X  X  X X XX X  XXX XXXXX XXX X  X  X X X   X XX XXX
 X  X X      X X XX X X  X XXXXXXX X  X XXX  X     X   X XXXXXXX X XX XX  X    
XXXXX XX    XX X  X X XXXX       X XXXX   XXXXX   XXX XX       X X  X  XXXXX   
    X  XX  X X XXXX X    XX     XX    XX X    XX X  X  XX     XX XXXXXX    XX X
X  XXXX XXXX X    X XX  X XX   X XX  X X XX  X X XXXXXX XX   X X      XX  X X X
XXX   X    X XX  XX  XXXX  XX XX  XXXX X  XXXX X      X  XX XX XX    X XXXX X  
  XX XXX  XX  XXX XXX   XXX X  XXX   X XXX   X XX    XXXX X  X  XX  XX    X XXX
XX X   XXX XXX  X   XX X  X XXX  XX XX   XX XX  XX  X   X XXXXXX XXX XX  XX   X
 X XX X  X   XXXXX X X XXXX   XXX X  XX X X  XXX XXXXX XX      X   X  XXX XX X 
XX  X XXXXX X    X X X    XX X  X XXX X X XXX  X     X  XX    XXX XXXX  X  X XX
 XXXX     X XX  XX X XX  X X XXXX   X X X   XXXXX   XXXX XX  X  X    XXXXXXX   
X   XX   XX  XXX X X  XXXX X    XX XX X XX X    XX X   X  XXXXXXXX  X      XX  
XX X XX X XXX  X X XXX   X XX  X X  X X  X XX  X X XX XXXX       XXXXX    X XXX
 X X  X X   XXXX X   XX XX  XXXX XXXX XXXX  XXXX X  X    XX     X    XX  XX    
XX XXXX XX X   X XX X X  XXX   X    X    XXX   X XXXXX  X XX   XXX  X XXX XX   
 X    X  X XX XX  X X XXX  XX XXX  XXX  X  XX XX     XXXX  XX X  XXXX   X  XX X
 XX  XXXXX  X  XXXX X   XXX X   XXX  XXXXXX X  XX   X   XXX X XXX   XX XXXX X X
  XXX    XXXXXX   X XX X  X XX X  XXX     X XXX XX XXX X  X X   XX X X    X X X
XX  XX  X     XX XX  X XXXX  X XXX  XX   XX   X  X   X XXXX XX X X X XX  XX X X
 XXX XXXXX   X X  XXXX    XXXX   XXX XX X XX XXXXXX XX    X  X X X X  XXX X X  
X  X     XX XX XXX   XX  X   XX X  X  X X  X      X  XX  XXXXX X X XXX  X X XX 
XXXXX   X X  X   XX X XXXXX X X XXXXXXX XXXXX    XXXX XXX    X X X   XXXX X  X 
    XX XX XXXXX X X X     X X X       X     XX  X   X   XX  XX X XX X   X XXXX 
   X X  X     X X X XX   XX X XX     XXX   X XXXXX XXX X XXX X X  X XX XX    XX
X XX XXXXX   XX X X  XX X X X  XX   X  XX XX     X   X X   X X XXXX  X  XX  X X
X  X     XX X X X XXX X X X XXX XX XXXX X  XX   XXX XX XX XX X    XXXXXX XXXX  
XXXXX   X X X X X   X X X X   X  X    X XXX XX X  X  X  X  X XX  X     X    XXX
    XX XX X X X XX XX X X XX XXXXXX  XX   X  X XXXXXXXXXXXXX  XXXXX   XXX  X   
   X X  X X X X  X  X X X  X      XXX XX XXXXX             XXX    XX X  XXXXX  
  XX XXXX X X XXXXXXX X XXXXX    X  X  X     XX           X  XX  X X XXX    XX

I will experiment with larger rules: the space of possible behaviors with a neighborhood of 5 is quite a bit larger (there are 2**32 possible rules instead of just 256).

Comments

Comment from Randy A MacDonald
Time 8/3/2015 at 7:42 am

1 line of APL, 6 if you document:
fBW?{i w n?? ? ‘ X'{?[1+?]}?(n?{({(,?)/,???}?(8/2)??)?{(2??)??}¨3,/0{?,?,?}?}){i x?? ? i=0:? ? x{(??),?}?(i-1)(?? x)}i(w?(-1+2×w)?1)}

Comment from Randy A MacDonald
Time 8/3/2015 at 7:44 am

fBW←{i w n←⍵ ⋄ ‘ X'{⍺[1+⍵]}↑(n∘{({(,⍵)/,⍳⍴⍵}⌽(8/2)⊤⍺)∘{(2⊥⍵)∊⍺}¨3,/0{⍺,⍵,⍺}⍵}){i x←⍵ ⋄ i=0:⍬ ⋄ x{(⊂⍺),⍵}∇(i-1)(⍺⍺ x)}i(w⌽(-1+2×w)↑1)}