index

Sierpinski golfing

· 7min

I want to talk about some elegant code to visualize fractals, and, in particular, the Sierpinski Gasket, but before we can do that, we need some background information.

Geometric intuition

The typical intuition regarding the Sierpinski Gasket stems from its self-similarity. First, you take an equilateral triangle,

   #
  # #
 #   #
# # # #

Then, if you attach three of these triangles together, you form a sort of “triangle of triangles”:

       #
      # #
     #   #
    # # # #
   #       #
  # #     # #
 #   #   #   #
# # # # # # # #

Through this process, you can keep constructing larger and larger shapes that form an interesting structure.

               #
              # #
             #   #
            # # # #
           #       #
          # #     # #
         #   #   #   #
        # # # # # # # #
       #               #
      # #             # #
     #   #           #   #
    # # # #         # # # #
   #       #       #       #
  # #     # #     # #     # #
 #   #   #   #   #   #   #   #
# # # # # # # # # # # # # # # #

If you repeat this process an infinite amount of times, you arrive at the Sierpinski Gasket (or Sierpinski Triangle).

This constructive approach, reliance on infinite recursion, and focus on structural similarity follows from the abstract context where these shapes are typically studied.

Detour through the discrete world

Now, let’s leave this continuous, 2-dimensional space (R2\mathbb{R}^2) and consider the exact opposite: a discrete, 1-dimensional space.

First, let’s suppose we have an infinite row of cells, each containing either a 0 or a 1:

11010…

It would be rather boring if this list of numbers never changed, so let’s implement a rule for updating each cell. Consider the red cell:

11010…

Let’s give each cell knowledge of its neighbors (for our selected red cell, that’s the blue cells), so that we can construct a more interesting update rule.

Since there are 3 binary parameter inputs, we see there are 23=82^3 = 8 possible inputs and we need to decide what binary output we should assign to each. Thus, there is a total of 223=2562^{2^3} = 256 possible rulesets.

Suppose we pick this ruleset:

111110101100011010001000
01011010

In our red cell example, the neighborhood is 101 and therefore, in the next iteration that cell should have a value of 0, per our rules. Let’s update each cell in the row to get the next full state:

10110…

Then, we can apply the rule again:

01110…

And clearly, since we get a new row each time, we can keep applying this rules forever.

Now, the magic happens when we zoom out a bit: instead of just looking at the current state, let’s display each state before all previous states. This allows us to see how the values evolve over time, where each new line is a different step in the process.

For illustrative purposes, let’s start with a 15-cell row with all 0s, except for the center.

000000010000000

Now, let’s go through our rules a few times, appending each new row to the bottom of the previous:

000000010000000
000000101000000
000001000100000
000010101010000
000100000001000
001010000010100
010001000100010
101010010010101

This is quite hard to read, so let’s remove the table, and represent 0s with a space:

       1
      1 1
     1   1
    1 1 1 1
   1       1
  1 1     1 1
 1   1   1   1
1 1 1  1  1 1 1

And just like magic: we just constructed a slice of the Sierpinski Gasket. We defined a series of rules to update a 1-dimensional, discrete row of 0s and 1s and recovered a representation of a continuous, 2-dimensional fractal, hiding in plain sight. And this isn’t a mere coincidence- if we keep iterating on an infinite set of cells, we can approximate the Sierpinski Gasket to any depth- it’s not a look-a-like, this is the real deal.

Elementary Cellular Automata

Most of that detour was fairly motivated: if we have some object, it makes sense to define some action. If we have some action, it makes sense to do it more than once. However, I did pull one thing out of thin air: the actual rules we used.

The Sierpinski Gasket appeared using these rules:

111110101100011010001000
01011010

However, as stated before, there are 256 possible rules, corresponding to a binary option of each of these 8 possible inputs. Together, these are all the Elementary Cellular Automata since they encompass all possible automata rules with adjacent neighbors on a single dimension.

If we want to be clever and give a name to a specific rule out of the 256 possible rules, then we look no further than the rule definition. If we concatenate our outputs, we get 01011010. If we treat this as a binary string, we can convert it to decimal to obtain the number 90. And for that reason, this is called “Rule 90”, and this assignment scheme is called the Wolfram code.

There are a lot of other rules (255 in fact) and they do not all generate the Sierpinski triangle (but they do often have an overall triangular shape). Suppose we wanted to write a program that draws a little picture of each of them- like we did manually for Rule 90 to draw the Sierpinski Gasket. This is a surprisingly simple task.

Going golfing

Suppose we have some row r and we want to know how the cell at index j should update for the next state. We can do this in a single (albeit complicated) line of C:

First, we find our neighborhood

a[(j+79)%80] // left, with wrapping

a[j]         // middle (current cell)

a[(j+1)%80]  // right, with wrapping

Then, we can construct a 3-bit number by combining and carefully shifting the left, middle, and right values

(a[(j+79)%80] << 2) | (a[j] << 1) | a[(j+1)%80]

Then, we can convert our rule (in this case 90) to binary, and select based on the 3-bit number

90>>((a[(j+79)%80]<<2)|(a[j]<<1)|a[(j+1)%80])

Finally, we can use bit-arithmetic to determine our output value

r[j]=(90>>((a[(j+79)%80]<<2)|(a[j]<<1)|a[(j+1)%80]))&1

In short: the 90 encodes a rule table, the 3-bit neighborhood selects which entry in the rules to use, and the result will be the next state of the current cell.

For the case of Rule 90 in particular, we can simplify this implementation as the output is simply left XOR right:

r[j]=a[j==0?79:j-1]^a[j==79?0:j+1]

Then, in a code-golf-style format (252 characters), we can use this as the engine of our automata simulation, where 90 can be replaced with any rule number (0-255):

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

main
(j){int
*a=malloc
(80*sizeof
*a);int *r=
malloc(80*//
sizeof *r);for
(j=0;j<80;j++)a[
j]=0,r[j]=0;a[40]=
1;for(;;){for(j=0;j<
80;j++)r[j]=(90>>((a[(            // rule 90
j+79)%80]<<2)|(a[j]<<1)|
a[(j+1)%80]))&1,/********/
putchar(" #"[a[j]]);/******/
putchar('\n');int *tmp=r;r=a;
a=tmp;usleep(1e5);}}/*w1ll.fyi*/

I tried to put it in the shape of a triangle, to be thematically relevant.

Other Rules

Using this little program, we can generate an ASCII representation of any of the Elementary Cellular Automata. In fact, it can produce more cellular automata (256) than the number of characters in its source code (252).

One of my personal favorite ECA rulesets is Rule 30. Despite being exactly as deterministic as Rule 90 (which produces beautiful fractal symmetry), Rule 30 manages to produce something that looks random.

                 #
                ###
               ##  #
              ## ####
             ##  #   #
            ## #### ###
           ##  #    #  #
          ## ####  ######
         ##  #   ###     #
        ## #### ##  #   ###
       ##  #    # #### ##  #
      ## ####  ## #    # ####
     ##  #   ###  ##  ## #   #
    ## #### ##  ### ###  ## ###
   ##  #    # ###   #  ###  #  #
  ## ####  ## #  # #####  #######
 ##  #   ###  #### #    ###      #
## #### ##  ###    ##  ##  #    ###

Here is Rule 110:

                 #
                ##
               ###
              ## #
             #####
            ##   #
           ###  ##
          ## # ###
         ####### #
        ##     ###
       ###    ## #
      ## #   #####
     #####  ##   #
    ##   # ###  ##
   ###  #### # ###
  ## # ##  ##### #
 ######## ##   ###
##      ####  ## #

And Rule 73:

                                        #
#######################################   ######################################
                                      # # #
#####################################       ####################################
                                    # ##### #
###################################   #   #   ##################################
                                  # #   #   # #
#################################     #   #     ################################
                                # ###   #   ### #
###############################   # # #   # # #   ##############################
                              # #       #       # #
#############################     #####   #####     ############################
                            # ### #   # # #   # ### #
###########################   # #   #       #   # #   ##########################
                          # #     #   #####   #     # #
#########################     ###   # #   # #   ###     ########################
                        # ### # # #     #     # # # ### #
#######################   # #       ###   ###       # #   ######################

It’s remarkable that with just 252 characters, we can conjure up chaos, order, and fractals alike. In the vast universe of cellular automata, even the simplest rules can reveal deep mathematical beauty.