Welcome, guest | Sign In | My Account | Store | Cart

This is a little script that uses Python to generate the cellular automata that Wolfram discusses in his book "A New Kind of Science". The script uses the Python Imaging Library to render the output, but you could replace this with text or any other method of visualization.

Python, 65 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#!/usr/bin/env python
"""
 CellularAutomata.py: Wolfram-style cellular automata in Python

 Options:
 -h #  Use a screen of height # for the simulation
 -w #  Use a screen of width # for the simulation
 -r      Use a random initial row (rather than the standard single 1 in the middle)
 -R #  Use rule # for the simulation

"""

import getopt,sys
from random import randint

def ca_data(height,width,dorandom,rulenum):
    # Create the first row, either randomly, or with a single 1
    if dorandom:
        first_row = [randint(0,1) for i in range(width)]
    else:
        first_row = [0]*width
        first_row[width/2] = 1
    results = [first_row]

    # Convert the rule number to a list of outcomes. 
    rule = [(rulenum/pow(2,i)) % 2 for i in range(8)]

    for i in range(height-1):
        data = results[-1]
        # Determine the new row based on the old data. We first make an
        #  integer out of the value of the old row and its two neighbors
        #  and then use that value to get the outcome from the table we
        #  computed earlier
        new = [rule[4*data[(j-1)%width]+2*data[j]+data[(j+1)%width]]
               for j in range(width)]
        results.append(new)
    return results

def pil_render(data,height,width,fname="bs.png"):
    import Image, ImageDraw
    img = Image.new("RGB",(width,height),(255,255,255))
    draw = ImageDraw.Draw(img)

    for y in range(height):
        for x in range(width):
            if data[y][x]: draw.point((x,y),(0,0,0))
    img.save(fname,"PNG")
    return

def main():
    opts,args = getopt.getopt(sys.argv[1:],'h:w:rR:')
    height = 500
    width = 500
    dorandom = 0
    rule = 22
    for key,val in opts:
        if key == '-h': height = int(val)
        if key == '-w': width = int(val)
        if key == '-r': dorandom = 1
        if key == '-R': rule = int(val)
    data = ca_data(height,width,dorandom,rule)
    pil_render(data,height,width)
    return

if __name__ == '__main__': main()

Stephen Wolfram's book "A New Kind of Science" is a fun read, and the pictures that his 1-d cellular automata generate are quite compelling. This is a simple little script that uses Python to generate these images. I use the Python Imaging Library to generate images from the data, but you could substitute any number of other methods. Much of the original work on cellular automata (Conway's game of life) was done using text output, and you could easily image "+" and " " (space) for the 1/0's here.

This script uses lists of integers to hold the rules; there's probably a way to speed the code up by using bit arithmatic, and I would welcome someone enlightening me about how this would be done.

6 comments

LJ Janowski 19 years, 5 months ago  # | flag

Bitwise Versions. First, thanks for the recipe, Rick. While I have not read A New Kind of Science, I had the chance to see Wolfram lecture in support of the book and found myself amused and intrigued. I am eager to sit down and see what I can do with your code. That being said, here are bitwise arithmetic versions of the ca_data and pil_render functions.

<pre width="80"> def ca_data_bwa(height,width,dorandom,rulenum):

# Ensure that we are working with long integers, otherwise bitwise
# operations will not work properly for widths greater than 31 on most
# python implementations.
height = long(height)
width = long(width)
rulenum = long(rulenum)

# Create the first row, either randomly, or with a single 1
if dorandom:
    first_row = randint(0, (1 &#60;&#60; width) - 1)
else:
    first_row = 1L &#60;&#60; width/2L
results = [first_row]

rule = rulenum

for i in range(height-1L):
    data = results[-1]

    # Determine the new row based on the old data. We create appropriate
    # bitmasks to allow us to read/write to a particular bit and then use
    # bitwise operations to do the actual reading/writing.
    new = 0L
    for j in range(width):

        # Create a bitmask and then access the 'upper left' bit
        ul_bitmask = 1L &#60;&#60; ((j - 1L) % width)
        ul_bit = (data &#38; ul_bitmask) / ul_bitmask

        # Create a bitmask and then access the 'above' bit
        above_bitmask = 1L &#60;&#60; j
        above_bit = (data &#38; above_bitmask) / above_bitmask

        # Create a bitmask and then access the 'upper right' bit
        ur_bitmask = 1L &#60;&#60; ((j + 1L) % width)
        ur_bit = (data &#38; ur_bitmask) / ur_bitmask

        # Create a bitmask and then access the rule
        rule_bitmask = 1L &#60;&#60; ((ul_bit &#60;&#60; 2L) + (above_bit &#60;&#60; 1L) + ur_bit)
        new_bit = (rule &#38; rule_bitmask) / rule_bitmask

        # Create a bitmask and then adjust the value of new at j
        new_bitmask = new_bit &#60;&#60; j
        new = new | new_bitmask

    results.append(new)
return results

def pil_render_bwa(data,height,width,fname="bs_bwa.png"): import Image, ImageDraw img = Image.new("RGB",(width,height),(255,255,255)) draw = ImageDraw.Draw(img)

for y in range(height):
    for x in range(width):
        if (data[y] &#38; (1L &#60;&#60; x)) / (1L &#60;&#60; x): draw.point((x,y),(0,0,0))
img.save(fname,"PNG")
return

</pre>

(comment continued...)

LJ Janowski 19 years, 5 months ago  # | flag

(...continued from previous comment)

Unfortunately, bitwise ops are rather slow under Python, so the bitwise versions take roughly 6 times as long to run on my machine. So, no speed optimization for me, though your mileage may vary. I tried to optimize with various different approaches to bit shifting, but found that the << (left shift) operator was almost universally faster than pow and a number of other approaches.

On another dimension, these routines may provide an optimization. While I have not yet investigated the matter thoroughly, I suspect that the bitwise versions probably perform better than the originals with regard to memory consumption. While I am ignorant of the actual memory representation of Python long integers, it seems that, unless they are grossly inefficient, a list of arbitrarily long Python long integers must take up less space than an equivalent representation using a list of lists of 32-bit integers. Of course, the phrase "it seems reasonable that" often has very little to do with actual performance, so it would be nice if someone would check this out.

Regardless of their efficiency, these alternate versions should serve as basic examples of bit arithmetic in Python. With the exception of the randomization function (where using long integers opened up obvious optimizations too good to pass up) I have attempted to keep the flow of the functions as similar as possible. The comments are a bit sparse, so, should anyone be really puzzled, I can clarify further.

Enjoy,

LJ

David Brown 19 years, 5 months ago  # | flag

profiled and speedy. I got fascinated by Wolfram's 1d automata experimentation as well. I went back to the math he presented in one of his papers, and came up with this implementation, which I profiled and tweaked until I got it as fast as I could make it without dropping into C:

import Image
import ImageOps
import random

def step(a, rule, k=2, r=1):
    nbrs = [a[c:] + a[:c] for c in range(-r, r+1, 1)]
    l = []
    for t in apply(zip, nbrs):
        result = 0
        for i in t:
            result = (result * k) + i
        l.append(result)
    return [((rule / (k ** v)) % k) for v in l]

def basicRun(rule, steps, stepper, seed=[1], k=2, r=1):
    seed = ([0] * steps) + seed + ([0] * steps)
    result = seed[:]
    for i in range(steps):
        seed = stepper(seed, rule, k=k, r=r)
        result += seed[:]
    return result, (len(seed), steps + 1)

def showResult(result, dims, k=2):
    i = Image.new("L", dims)
    i.putdata(result, (255 / (k - 1)))
    i = i.crop(i.getbbox())
    i = ImageOps.invert(i)
    i.load()
    i.show()

def runTest():
    lines = 400
    result, dims = basicRun(110, lines, step)
    showResult(result, dims)

if __name__ == "__main__":
    runTest()

step() is where all the real action occurs. That's where most of the tweaking happened. And while bitwise manipulation is slow, basic math seems to be fast.

LJ Janowski 19 years, 5 months ago  # | flag

Nice. Thanks, Dan. Go list comprehensions.

LJ Janowski 19 years, 5 months ago  # | flag

Er, Dave, sorry.

Nicolas Seriot 6 years, 11 months ago  # | flag

I came up with this shorter and faster implementation.

Time to compute Rule 110, 2500x2500:

1.9 s vs 8 s for David's solution (including image write)

0.9 s vs 6.8 s for David solution (without image write)

import png

def next_row(row, rule_bits):
    r = row[-1:] + row + row[:1]
    return [rule_bits[r[i]*4 + b*2 + r[i+2]] for (i, b) in enumerate(row)]

def save_png_data(rows, filename):
    ll = [[255 - b * 255 for b in row] for row in rows]
    png.from_array(ll, 'L').save(filename)

def run():

    rule = 110 # or 0b01101110

    (WIDTH, HEIGHT) = (2500, 2500)

    row = [0] * (WIDTH-1) + [1]

    s = bin(rule)[2:].zfill(8)
    rule_bits = [int(x) for x in s[::-1]]

    png_data = [row]

    for i in range(HEIGHT):
        row = next_row(row, rule_bits)
        png_data.append(row)

    save_png_data(png_data, "rule_%d_%d_%s.png" % (rule, WIDTH, HEIGHT))

if __name__ == "__main__":
    run()