Cellular Automata in Bash

Stephen Wolfram eat your heart out. We don’t need no stinking Mathematica when we have Bash. I wish I could afford Mathematica, though. ;)

ca.sh Is a one-dimensional elementary cellular automaton written in Bash. This implementation uses a string of binary digits to store its world in a variable called states.

The following function reads this variable to lookup the states of a cell and its immediate neighbours:

1
2
3
4
5
6
7
8
9
# neigh <cell index> : returns neighbourhood state as integer
function neigh() {
        # cell(n - 1), wrap on edge
        state=$((4 * ${states:(${1} == 0)?${#states} - 1:${1} - 1:1}))
        # self
        state=$((state + 2 * ${states:${1}:1}))
        # cell(n + 1), wrap on edge
        echo $((state + ${states:(${1} == (${#states} - 1))?0:${1} + 1:1}))
}

Even with the comments this makes for some nice Bash code golf. I think the if-statements of the shell are plain ugly, so in this case I used the conditional operator to wrap around the begin and end of the string in states when looking up the states of the cells on the far left and right.

The value of the neighbourhood can then be fed to ca() which does return the next state for a cell based on the current rule number:

1
2
3
4
# ca <state> <rule> : returns new binary state for cell
function ca() {
        echo $(((${2}>>${1})&1));
}

Yup, that’s right, Bash has bitwise operators. :)

These two functions can then be combined like so to display succesive generations op the automaton:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# run ca algorithm
for ((;;)) {
        # display current state using ANSI colors
        display=${states//0/$'\e[0;30;44m '}
        echo ${display//1/$'\e[0;30;45m '}

        next_states=""

        # update cells
        for((c=0;c < ${#states};c++)) {
                next_states=${next_states}$(ca $(neigh ${c}) ${rule})
        }

        states=${next_states}
}

As you can see, I used a regular-expression replace to change the values in states to spaces with an ANSI escape sequence defined background color. Pretty elegant, I think. Although I don’t like the temporary variable display too much.

The full code of ca.sh is included below the break:

ca.sh (ca.sh) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#!/bin/bash
# ca.sh - 1D elementary cellular automaton
# Hessel Schut, hessel@isquared.nl, 2013-02-16

# defaults to rule 30 when no argument given
rule=${1:-30}

# cleanup terminal after the mess we've made
trap cleanup TERM EXIT INT;
function cleanup() {
  # simple reset should be enough
  echo -n $'\ec'
  exit
}

# cellular automaton: ca <state> <rule> returns new state for cell
function ca() {
  echo $(((${2}>>${1})&1));
}

# neigh <cell> : returns integer neighbourhood state
function neigh() {
  # cell(n - 1), wrap on edge
  state=$((4 * ${states:(${1} == 0)?${#states} - 1:${1} - 1:1}))
  # self
  state=$((state + 2 * ${states:${1}:1}))
  # cell(n + 1), wrap on edge
  echo $((state + ${states:(${1} == (${#states} - 1))?0:${1} + 1:1}))
}  

# combined ca() and neigh(), saves expensive function call
function ca() {
  # cell(n - 1), wrap on edge
  state=$((4 * ${states:(${1} == 0)?${#states} - 1:${1} - 1:1}))
  # self
  state=$((state + 2 * ${states:${1}:1}))
  # cell(n + 1), wrap on edge
  state=$((state + ${states:(${1} == (${#states} - 1))?0:${1} + 1:1}))
  # return new state based on rule in ${2}
  echo $(((${2}>>state)&1))
}  

# tput is for weenies, query terminal for its size
function term_size() {
  {
      read -p $'\e[18t' -s -r -d t s;
  } <> /dev/tty
  echo ${s#*;};
}

# extract columns from terminal size
cols=${COLUMNS:-$(s=$(term_size) && echo ${s/*;})}

# initialize states with single cell
states=""
for ((i = 0; i <= cols; i++)) {
  # only set one cell in the middle of the screen
  # all others will be dead initially
  states=${states}$(((i == cols/2)?1:0))
}

# run ca algorithm
for ((;;)) {
  # display current state using ANSI colors
  display=${states//0/$'\e[0;30;44m '}
  echo ${display//1/$'\e[0;30;45m '}

  next_states=""

  # update cells
  for((c = 0; c < ${#states}; c++)) {
      # next_states=${next_states}$(ca $(neigh ${c}) ${rule})
      # second ca() definition used, executes a bit faster
      next_states=${next_states}$(ca ${c} ${rule})
  }

  # synchronize states
  states=${next_states}
}

Comments