TL;DR

Letâ€™s add a little improvement to the implementation of Conwayâ€™s Game of Life.

In the Game of Life, the rules are pretty simple. The next state of a cell depends in the previous state like this:

• if the cell is alive, then it will survive if and only if it is surrounded by 2 or 3 alive cells;
• if the cell is empty, it will spawn new life if it has exactly 3 alive cells around, otherwise it will stay empty.

Soâ€¦ counting the number of cells around the target one is pretty important.

In the first implementation, itâ€™s only about counting all values around the target cells:

`````` 1 sub alive_around (\$field, \$y, \$x) {
2    my \$n = 0;
3    for my \$dy (-1 .. 1) {
4       for my \$dx (-1 .. 1) {
5          ++\$n if \$field->[\$y + \$dy][\$x + \$dx] eq '#';
6       }
7    }
8    --\$n if \$field->[\$y][\$x] eq '#';
9    return \$n;
10 } ## end sub alive_around
``````

Each cellâ€™s contents will be counted overâ€¦ and overâ€¦ and over. About least 9 times, as a matter of fact. Can we do better?

The new implementation keeps track of the surrounding cells horizontally, on three lines. This allows calculating the value at a target cell by simply adding up these values, possibly removing one for the specific target cell (line 19, where it only makes sense).

`````` 1 sub life_tick (\$field) {
2    my @retval;
3    my \$nx     = \$field->[0]->@*;
4    my @previous = my @current = (0) x \$nx;
5    for my \$y (0 .. \$#\$field - 1) {
6       my (\$irow, \$nrow) = \$field->@[\$y, \$y + 1];
7       my @next = (0) x \$nx;
8       \$next[-1] = \$nrow->[-2] eq '#' ? 1 : 0;
9       my @row  = (' ') x \$nx;
10       push @retval, \@row;
11       for my \$x (0 .. \$nx - 1) {
12          \$next[\$x] = \$next[\$x - 1] - (\$nrow->[\$x - 2] eq '#' ? 1 : 0)
13             + (\$nrow->[(\$x + 1) % \$nx] eq '#' ? 1 : 0);
14          my \$around = \$previous[\$x] + \$current[\$x] + \$next[\$x];
15          if (\$irow->[\$x] eq ' ') {
16             \$row[\$x] = '#' if \$around == 3;
17          }
18          elsif (\$irow->[\$x] eq '#') {
19             \$around--; # the item itself must not be counted
20             \$row[\$x] = '#' if \$around == 2 || \$around == 3;
21          }
22          else {
23             \$row[\$x] = \$irow->[\$x];
24          }
25       } ## end for my \$x (0 .. \$nx - 1)
26       @previous = @current;
27       @current = @next;
28    } ## end for my \$y (1 .. \$#\$field...)
29    push @retval, \$field->[-1];
30    return \@retval;
31 } ## end sub life_tick (\$field)
``````

The three arrays `@previous`, `@current` and `@next` keep track of these horizontal values. When a row is complete (i.e. after line 25), these array are shifted to prepare for the next loop.

After doing this, I realize that I donâ€™t want to benchmark the improvements, if anyâ€¦ Iâ€™m too scared!!!

Comments? Octodon, , GitHub, Reddit, or drop me a line!