index

I recently rediscovered the classic donut.c by a1k0n and was inspired to make my own C golf animation.

“code-golf is a competition to solve a problem in the fewest bytes of source code.” - Code Golf StackExchange

I also have an interest in automata, so I decided to build Conway’s Game of Life, given its concise instruction set.

To begin, I started with a basic, unobfuscated C implementation of Conway’s Game of Life. To keep things minimal, I used a 2080-cell array to represent the board with 0 and 1 as the expected character set.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

int main(void) {
  int N = 2080;                   // number of cells
  int *b = malloc(N * sizeof *b); // current board
  int *a = malloc(N * sizeof *a); // update board (to avoid corrupting state)

  for (int i = 0; i < N; i++) {   // random board values of 0, 1
    b[i] = rand() % 2;
  }

  while(1) {
    // move terminal cursor to top left
    printf("\x1b[H");

    // for each cell
    for (int j=0; j<N; j++) {
      // number of neighbors
      int n = b[j-81] + b[j-80] + b[j-79] + b[j-1] + b[j+1] + b[j+79] + b[j+80] + b[j+81];

      // set corresponding cell value in update board by Life rules
      a[j] = (b[j]==1 && n >= 2 && n <= 3) || (b[j]==0 && n == 3) ? 1 : 0;

      // output character, including wrap
      if (j % 80 == 79) {
        putchar('\n');
      } else if (a[j] == 0) {
        putchar('.');
      } else if (a[j] == 1) {
        putchar('#');
      }
    }

    // update pointer to set update board -> current board
    int *tmp=b;
    b = a;
    a = tmp;

    // animation loop timer
    usleep(1000000);
  }
  return 0;
}

As an example, a frame from its output looks like this:

.###.........#........#...##...##.....#....####.##.####.###...#.#..............
#..##.......#.#.#....#...##...........#.#.###.#.#.##.#.#......##.........######
#...#......###..#...###.##.#####..............#.#.##.......##.###..##....###...
#..#####.#....#.##..##.#.#..#..##.......#...###...##.....................##....
...#...##.....###...##.##..##.#.......##......###......#.#####........#......##
.##.#...#.............##....##........####......#.......#.........#..##..##...#
.#..####.....................#.##.....####......##................##.#...##...#
##............................##.##........####.#####.##..........##.#........#
###..#..........................####.###.........#..#.##.....#.##.#...........#
..#..#..............#..............##.......#...##....##....#.###.....#........
.#..#..............#.##...........###...............##.#...##.#.#....#......##.
.###.....#.#.....#.....#......#...##..#.##...#..#.#..##.....#..##..............
...#.....#..#....##.#...#....#.#..##........#...#.#...#......#.................
###......#.##.##..#..#..#.....#.###..............##.....##.......##............
###...........#.###....##.......##..............##......##......#.............#
.##.............#...........................#...##.##..#..#.#..............#...
..#........##..................#.##.......##.#.#.#.#...#.##.#...#.....#.####.#.
..###......###...............#.....#......#..#.....#..##..##.#.##...###....##..
#.######.................##....##.................#....######.#.....###.....##.
.#######..................####.#...#...##..####.........#.#.#......##.#.#.#.###
#.#.##..#..................##...##..#.......#....#......#..........##.##.#..#..
#..#.###...........##.........#......##..##.#.#..#....#........#.........#....#
...#...#.......###...#........#.....####.#.##.#.##...#...#.....#........#...#.#
...##.#....#..#.##..##..............###...##....##...#.........#............#..
....#.#....#..##.###..........#.....#...#.............#.......##..#.....##.###.
#....#.#....##................#.....##..#.#....#.....#.....#.#..........###..#.

When minified, this naive approach uses a total of 420 characters, which serves as our baseline:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

int main(void){int N=2080;int *b=malloc(N*sizeof *b);int *a =malloc(N*sizeof *a);for(int i=0;i<N;i++){b[i]=rand()%2;}while(1){printf("\x1b[H");for(int j=0;j<N;j++){int n=b[j-81]+b[j-80]+b[j-79]+b[j-1]+b[j+1]+b[j+79]+b[j+80]+b[j+81];a[j]=(b[j]==1&&n>=2&&n<=3)||(b[j]==0&&n==3)?1:0;if(j%80==79){putchar('\n');}else if(a[j]==0){putchar('.');}else if(a[j]==1){putchar('#');}}int *tmp=b;b=a;a=tmp;usleep(1000000);}return 0;}

Now, we can get into the interesting part: elegant ways to shorten our code. There are some relatively minor changes elsewhere in the code, but these four tweaks are the most conceptually interesting.

1. Random board initialization

old:

for (int i = 0; i < N; i++) {
  b[i] = rand() % 2;
}

new:

for(j=0; j<N; ) b[j++] = rand() & 1;

2. Neighbor counting

old:

int n = b[j-81] + b[j-80] + b[j-79] + b[j-1] + b[j+2] + b[j+79] + b[j+80] + b[j+81];

new:

int n = b[j-1] + b[j+1];
for (k=79; k<82; k++) n+= b[j-k] + b[j+k];

3. Game of Life ruleset

old:

a[j] = (b[j] == 1 && n >= 2 && n<=3) || (b[j] == 0 && n==3) ? 1 : 0;

new:

a[j] = n==3 || b[j] && n==2;

The Game of Life has four instructions for a given cell:

• If the cell is alive and has less than 2 neighbors, it dies
• If the cell is alive and has more than 3 neighbors, it dies
• If the cell is alive and has 2 or 3 neighbors, it stays alive
• If the cell is dead and has exactly 3 neighbors, then it becomes alive

However, if n is the number of neighbors for a given cell j with state b[j], then its value at the next iteration is simply n==3 || b[j] && n == 2, since the cell will be alive under any environment where it has 3 neighbors; or if it is already alive with 2 neighbors.

4. Character display

old:

if (j % 80 == 79) {
  putchar('\n');
} else if (a[j] == 0) {
  putchar('.');
} else if (a[j] == 1) {
  putchar('#');
}

new:

putchar((j % 80) == 79 ? '\n' : ".#"[a[j]]);

This uses a common code golfing trick. We can construct a string of possible characters to output. For example, "abcde" if we wanted 5 possible characters at indices 0, 1, 2, 3, 4. Then, we can select a character from this string at index i with "abcde"[i]. Since the character to select is completely dependent on the value of the cell, we can set i=b[j].

---

Putting it all together (with a couple technical tweaks), we get this code:

note: compile with “gcc -std=gnu89”

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

main(j,k){int N=2080;int *b=malloc(N*sizeof *b), *a=malloc(N*sizeof *a);for(j=0;j<N;)b[j++]=rand()&1;for(;;){printf("\x1b[H");for(j=0;j<N;j++){int n=b[j-1]+b[j+1];for(k=79;k<82;k++)n+=b[j-k]+b[j+k];a[j]=n==3||b[j]&&n==2,putchar((j%80)==79?'\n':".#"[a[j]]);}int *tmp=b;b=a;a=tmp;usleep(1e6);}}

This final version is 292 characters, which is 30.4% smaller than the original, minimized code, while remaining functionally identical.

I can’t imagine a better symbol of Conway’s Game of Life than the ubiquitous glider:

Half of the beauty of the donut.c example is that the source code forms the shape of its output so I tried to do the same:

                                main(j,k){int/**/
                                N=2080;int *b/**/
                                =malloc(N*sizeof
*b), *a=malloc(N                *sizeof *a);for(
j=0;j<N;)b[j++]=                rand()&1;for(;;){
printf("\x1b[H");               for(j=0;j<N;j++){
int n=b[j-1]+/**/               b[j+1];for(k=79;k<
                82;k++)n+=b[j-k]+b[j+k];a[j]=n==3
                ||b[j]&&n==2, putchar((j%80)==79
                ?'\n':".#"[a[j]]);}int *tmp=b;b=a;
                a=tmp;usleep(1e6);}} /*w1ll.fyi*/