# Sierpinski triangle (JavaScript)

### From LiteratePrograms

**Other implementations**: C | Erlang | Forth | Haskell |**JavaScript**| OCaml | Perl | Python | Scheme | Sed

This program will display a crude Sierpinski triangle by calculating a simple one-dimensional cellular automaton and displaying its changing state over time.

We will use an array to represent the current state of the one-dimensional universe. We allocate an extra byte at the end (**width+1**) to avoid overflow during the later generational calculation. **init_state()** clears the array and sets one cell to Full. **print_state()** writes the current state to the document, showing a space for Empty cells and '@' for full cells.

<<state>>=varwidth= 80varstatefunction init_state() {state =newArray(width+1) state[width/2] = 1}function print_state() {for(vari=0; i<width; i++)document.write(state[i] ? '@' : ' ')document.write("<br/>\n")}

The particular cellular automaton for generating a Sierpinski triangle looks at the current cell and the two neighboring cells. There are eight possible permutations of the states of these three cells (which will henceforth be called the *neighborhood*), and we will represent the automaton as a table mapping the state of the neighborhood (represented as a number from 0..7) to the next state of the current cell. The rule stated succinctly is to clear the cell if the neighborhood cells are the same (all Empty or all Full) and set the cell if the three cells differ.

<<automaton rules>>=// the index has three bits: b0,b1,b2 = next neighbor, current cell, previous neighborvartransition = [0,1,1,1,1,1,1,0]

The function **gen()** will keep the neighborhood of the current cell on the stack. It is easy to obtain the neighborhood of the current cell from the neighborhood of the previous cell. You just shift the window: shift right (**2*n**), putting the state of the next neighbor into the LSB (**| state[i+1]**) and taking away the old neighbor from the MSB by restricting the result to three bits (**& 7**).

<<current neighborhood>>=((2*n) | state[i+1]) & 7

**gen()** invokes the automaton to obtain the next generation of the state from the previous state.

<<gen>>=function gen() {varn = state[0];for(vari=0; i<width; i++){n = current neighborhood state[i] = transition[n]}}

**sierpinski()** will calculate and show *height* generations of the automaton (including the initial one), displaying a Sierpinski triangle *height* characters tall and *2*height+1* characters wide. Powers of two for *height* generate complete triangles. The entire construct is wrapped in a *pre* block for proper formatting within a web page.

<<sierpinski.js>>=state automaton rules genfunction sierpinski(height) {document.write("<"+"pre>\n") // split tag for proper wiki formatting init_state() print_state()for(vari=1; i<height; i++){gen() print_state()}document.write("<"+"/pre>\n")}sierpinski(32)

Download code |