Sierpinski triangle (Perl)
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 Perl.
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 internally represent the Empty and Full states as 0 and 1 respectively. The state transformation rule can be expressed as a dictionary keyed on tuples of state values. For clarity, we'll write out the complete ruleset.
<<rules>>= $rules = { '000' => 0, '001' => 1, '010' => 1, '011' => 1, '100' => 1, '101' => 1, '110' => 1, '111' => 0, };
We represent the state of the cellular automaton in a given generation as a list of cell states of size AUTOMATA_SIZE. The initial automaton state is set to Empty, with the exception of the middle cell in the list, which is Full.
<<initial state>>= # Constants. use constant AUTOMATA_SIZE => 80; # Global variables. use vars qw($init_states $rules); # Default values. $init_states = [(0) x (AUTOMATA_SIZE/2 - 1), (1), (0) x (AUTOMATA_SIZE/2)];
To transform the automaton from one generation to the next we apply the rules to each cell in the automaton in turn. Rule application consists of performing a dictionary lookup on the tuple of states corresponding to cell to which the rule is being applied, along with it's neighbors to the left and right.
<<apply rules>>= sub apply_rules($) { my $states = shift; my $width = scalar @{$states}; my $new_states = []; end states foreach my $i (1 .. $width - 2) { $new_states->[$i] = $rules->{$states->[$i - 1]. $states->[$i].$states->[$i + 1]}; } return $new_states; }
We assume that the states at either end of the automaton space have neighbors that are always empty:
<<end states>>= $new_states->[0] = $rules->{'0'.$states->[0].$states->[1]}; $new_states->[$width - 1] = $rules->{$states->[$width - 2].$states->[$width - 1].'0'};
To run the automaton we provide a simple function that takes as an argument the number of generations to create, and prints successive generations to the screen. For display purposes, we represent Empty cells as a space, and Full cells as a @ character (although these choices can easily be changed by modifying the state_to_char function).
<<sierpinski.pl>>= # Pragmas. use strict; use warnings; initial state rules apply rules sub state_to_char($) { my $state = shift; if ($state == 0) { return ' '; } else { return '@'; } } sub states_to_string($) { my $states = shift; return join('', map { state_to_char($_) } @{$states}); } sub run_and_display($) { my $n_gens = shift; my $states = $init_states; foreach (1 .. $n_gens) { print states_to_string($states)."\n"; $states = apply_rules($states); } } # Main. run_and_display(32);
| Download code |