Elementary cellular automaton
An elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors. Those three values can be encoded with three bits.
The rules of evolution are then encoded with eight bits indicating the outcome of each of the eight possibilities 111, 110, 101, 100, 011, 010, 001 and 000 in this order. Thus for instance the rule 13 means that a state is updated to 1 only in the cases 011, 010 and 000, since 13 in binary is 0b00001101.
The purpose of this task is to create a subroutine, program or function that allows to create and visualize the evolution of any of the 256 possible elementary cellular automata of arbitrary space length and for any given initial state. You can demonstrate your solution with any automaton of your choice.
You can either produce an ASCII rendering of the state evolution or a PBM image.
You can deal with the limit conditions (what happens on the borders of the space) in any way you please.
This task is basically a generalization of one-dimensional cellular automaton.
Go
<lang go>package main
import (
"fmt" "math/big" "math/rand" "strings"
)
func main() {
const cells = 20
const generations = 9
fmt.Println("Single 1, rule 90:")
a := big.NewInt(1)
a.Lsh(a, cells/2)
elem(90, cells, generations, a)
fmt.Println("Random intial state, rule 30:")
a = big.NewInt(1)
a.Rand(rand.New(rand.NewSource(3)), a.Lsh(a, cells))
elem(30, cells, generations, a)
}
func elem(rule uint, cells, generations int, a *big.Int) {
output := func() {
fmt.Println(strings.Replace(strings.Replace(
fmt.Sprintf("%0*b", cells, a), "0", " ", -1), "1", "#", -1))
}
output()
a1 := new(big.Int)
set := func(cell int, k uint) {
a1.SetBit(a1, cell, rule>>k&1)
}
last := cells - 1
for r := 0; r < generations; r++ {
k := a.Bit(last) | a.Bit(0)<<1 | a.Bit(1)<<2
set(0, k)
for c := 1; c < last; c++ {
k = k>>1 | a.Bit(c+1)<<2
set(c, k)
}
set(last, k>>1|a.Bit(0)<<2)
a, a1 = a1, a
output()
}
}</lang>
- Output:
Single 1, rule 90:
#
# #
# #
# # # #
# #
# # # #
# # # #
# # # # # # # #
# #
# # # #
Random intial state, rule 30:
# # # #### #
## ## #### # ##
# # # # ### ##
######### ## # # #
# ## ## #
# ##### # #
# ## ######
## ## # ##
## # ## #### #
# #### ### ## #
Perl
<lang perl>use strict; use warnings;
package Automaton {
sub new {
my $class = shift; my $rule = [ reverse split //, sprintf "%08b", shift ]; return bless { rule => $rule, cells => [ @_ ] }, $class;
}
sub next {
my $this = shift; my @previous = @{$this->{cells}}; $this->{cells} = [ @{$this->{rule}}[ map { 4*$previous[($_ - 1) % @previous] + 2*$previous[$_] + $previous[($_ + 1) % @previous] } 0 .. @previous - 1 ] ]; return $this;
}
use overload
q{""} => sub {
my $this = shift; join , map { $_ ? '#' : ' ' } @{$this->{cells}}
};
}
my @a = map 0, 1 .. 91; $a[45] = 1; my $a = Automaton->new(90, @a);
for (1..40) {
print "|$a|\n"; $a->next;
}</lang>
- Output:
| # | | # # | | # # | | # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # |
Perl 6
<lang perl6>class Automaton {
has ($.rule, @.cells);
method gist { <| |>.join: @!cells.map({$_ ?? '#' !! ' '}).join }
method code { $!rule.fmt("%08b").flip.comb }
method succ {
self.new: :$!rule, :cells(
self.code[
(4 X* @!cells.rotate(-1))
Z+ (2 X* @!cells)
Z+ @!cells.rotate(1)
]
)
}
}
my $size = 10; my Automaton $a .= new:
:rule(30), :cells( 0 xx $size, 1, 0 xx $size );
say $a++ for ^$size;</lang>
- Output:
| # | | ### | | ## # | | ## #### | | ## # # | | ## #### ### | | ## # # # | | ## #### ###### | | ## # ### # | | ## #### ## # ### |
Python
<lang python>def eca(cells, rule):
lencells = len(cells)
c = "0" + cells + "0" # Zero pad the ends
rulebits = '{0:08b}'.format(rule)
neighbours2next = {'{0:03b}'.format(n):rulebits[::-1][n] for n in range(8)}
yield c[1:-1]
while True:
c = .join(['0',
.join(neighbours2next[c[i-1:i+2]]
for i in range(1,lencells+1)),
'0'])
yield c[1:-1]
for rule in (90, 30, 122):
print('\nRule: %i' % rule)
for i, c in zip(range(16), eca('0000000001000000000', rule)):
print('%2i: %s' % (i, c.replace('0', '.').replace('1', '#')))</lang>
- Output:
Rule: 90 0: .........#......... 1: ........#.#........ 2: .......#...#....... 3: ......#.#.#.#...... 4: .....#.......#..... 5: ....#.#.....#.#.... 6: ...#...#...#...#... 7: ..#.#.#.#.#.#.#.#.. 8: .#...............#. 9: #.#.............#.# 10: ...#...........#... 11: ..#.#.........#.#.. 12: .#...#.......#...#. 13: #.#.#.#.....#.#.#.# 14: .......#...#....... 15: ......#.#.#.#...... Rule: 30 0: .........#......... 1: ........###........ 2: .......##..#....... 3: ......##.####...... 4: .....##..#...#..... 5: ....##.####.###.... 6: ...##..#....#..#... 7: ..##.####..######.. 8: .##..#...###.....#. 9: ##.####.##..#...### 10: #..#....#.####.##.. 11: #####..##.#....#.#. 12: #....###..##..##.## 13: ##..##..###.###..#. 14: #.###.###...#..#### 15: #.#...#..#.#####... Rule: 122 0: .........#......... 1: ........#.#........ 2: .......#.#.#....... 3: ......#.#.#.#...... 4: .....#.#.#.#.#..... 5: ....#.#.#.#.#.#.... 6: ...#.#.#.#.#.#.#... 7: ..#.#.#.#.#.#.#.#.. 8: .#.#.#.#.#.#.#.#.#. 9: #.#.#.#.#.#.#.#.#.# 10: .#.#.#.#.#.#.#.#.#. 11: #.#.#.#.#.#.#.#.#.# 12: .#.#.#.#.#.#.#.#.#. 13: #.#.#.#.#.#.#.#.#.# 14: .#.#.#.#.#.#.#.#.#. 15: #.#.#.#.#.#.#.#.#.#