Sierpinski triangle (C)
From LiteratePrograms
- Other implementations: C | Erlang | Forth | Haskell | JavaScript | OCaml | Perl | Python | Scheme | Sed
The following is an implementation of the one-dimensional cellular automata, and the Sierpinski cellular automaton in particular, in C.
A one-dimensional cellular automaton is a linear space of cells, each of which has a state. The automaton changes in discrete time steps called generations. In each generation the state of each cell is decided according to a set of rules that is based on the states of neighboring cells. In the case of one-dimensional cellular automaton each cell has its state decided by considering three cells, itself and its left and right neighboring cells. Neighbouring the first and last cells of the space, we will assume virtual cells that are always in a default state.
The Sierpinski cellular automaton has two states, Empty and Full. The only rule states that a cell will be set to Full if and only if of the three states considered exactly one or two are Full.
When run output similar to the following will be produced.
@
@@@
@@ @@
@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Implementation
We use two arrays of char to represent the cellular automaton in the current and next generation. The value for each cell is either Empty (0) or Full (1). The initial automaton state is set to Empty, with the exception of the middle cell in the list, which is Full.
<<initial_state>>= char statelist1[WIDTH]; char statelist2[WIDTH]; char *statelist, *new_statelist; int i; memset(statelist1, 0, WIDTH); statelist1[WIDTH/2]=1; statelist=statelist1; new_statelist=statelist2;
The rules are represented by this C expression:
<<rules>>= new_sl[i]=!((sl[i-1] && sl[i] && sl[i+1]) || (!sl[i-1] && !sl[i] && !sl[i+1]));
We assume that the states at either end of the automaton space have neighbors that are always Empty:
<<start_end_rules>>= new_sl[0]=(sl[0] || sl[1]); new_sl[width-1]=(sl[width-2] || sl[width-1]);
The rules for the next generation are applied to the new_sl array.
<<apply_rules>>= char *apply_rules(char *new_sl, const char *sl, size_t width) { int i; start_end_rules for(i=1; i<width-1; ++i) { rules } return new_sl; }
This function prints all cells of a generation, using '@' for Full and ' ' (space) for empty.
<<print_statelist>>= void print_statelist(const char *sl, size_t width) { int i; for(i=0; i<width; ++i) putchar(sl[i]?'@':' '); putchar('\n'); }
<<sierpinski.c>>= #include<stdio.h> #include<string.h> apply_rules print_statelist #define WIDTH 80 void run_and_display(size_t niters) { initial_state for(i=0; i<niters; ++i) { print_statelist(statelist, WIDTH); if((statelist=apply_rules(new_statelist, statelist, WIDTH))==statelist1) new_statelist=statelist2; else new_statelist=statelist1; } } main
main
To produce the example output, we create and print 32 generations.
<<main>>= int main() { run_and_display(32); return 0; }
| Download code |