Conway's Game of Life

Game of life is a cellular simulation; not really a game that is played, but more a sequence that is observed. In today’s article, I’ll walk through the rules and a simple C implementation.

How to play

There are some simple rules that the game must abide by.

The universe that it is played within is an orthogonal cartesian grid of squares that define if a cell is dead or if it’s alive. The lifespan of the cells is determined by the following rules:

• Any cell that’s alive with fewer than two live neighbours dies (underpopulation)
• Any cell that’s alive with two or three live neighbours lives on to the next generation
• Any cell that’s alive with more than three live neighbours dies (overpopulation)
• Any dead cell that has three live neighbours becomes alive (reproduction)

And, that’s it.

Implementation

The pitch where the game is played would be a pretty simple buffer of 1’s and 0’s. 1 would define “alive”, and 0 would define “dead”:

#define UV_WIDTH 64
#define UV_HEIGHT 32

unsigned char *universe;


universe = (unsigned char *) malloc(UV_HEIGHT * UV_WIDTH * sizeof(unsigned char));

So, a buffer of memory for a defined width and height will do the job.

The remainder of the process could be split into the following:

• Seed the universe
• Permute the universe
• Render the universe

Seed

Chicken or the egg isn’t asked here. We just use srand and rand to play god for us:

void universe_seed(unsigned char *u, int width, int height) {
  int i;

  for (i = 0; i < (width * height); i ++) {
    u[i] = rand() % 9 == 0;
  }
}

For every cell, we’ll get a random number from rand. If that number is divisible by 9, we’ll mark the cell as alive.

There are much more clever ways to seed the universe, in such a way that the rules of the game keep the generations running for ever with very clever patterns.

Permute

Actually making the universe kick along between frames, is simply applying the rules to a buffer of states. This buffer of states needs to be considered all in the same move; so we can’t mutate the original buffer sequentially.

void universe_permute(unsigned char *u, int width, int height) {
  int x, y, n, l;
  unsigned char *r = (unsigned char *)malloc(width * height);

  memcpy(r, u, width * height);

  for (y = 0; y < height; y ++) {
    for (x = 0; x < width; x ++) {
      l = u[x + (y * width)];
      n = count_live_neighbours(u, width, height, x, y);

      if (l & ((n < 2) || (n > 3))) {
        r[x + (y * width)] = 0;
      } else if (!l & (n == 3)) {
        r[x + (y * width)] = 1;
      }
    }
  }

  memcpy(u, r, width * height);
  free(r);
}

A copy of the game buffer is made, first up. This is what we’ll actually write the next buffer states to; leaving the current buffer intact.

Following the rules of the game:

  if (l & ((n < 2) || (n > 3))) {
    r[x + (y * width)] = 0;
  } else if (!l & (n == 3)) {
    r[x + (y * width)] = 1;
  }

Here, we see the overpopulation, underpopulation, and reproduction rules in action.

The number of neighbours, is counted with a difference:

int count_live_neighbours(unsigned char *u, int width, int height, int x, int y) {
  /* clip the bounds */
  int x1 = (x - 1) % width;
  int x2 = (x + 1) % width;
  int y1 = (y - 1) % height;
  int y2 = (y + 1) % height;

  return u[x1 + (y1 * width)] +
         u[x1 + (y2 * width)] +
         u[x2 + (y1 * width)] +
         u[x2 + (y2 * width)] +
         u[x  + (y1 * width)] +
         u[x  + (y2 * width)] +
         u[x1 + (y  * width)] +
         u[x2 + (y  * width)];
}

The x and y values are clipped to the width and height values. This means that if you fall off the right-hand side of the universe, you’ll magically appear back on the left-hand side. In the same way - top to bottom, etc.

A neighbour check must look at all 8 cells that surround the cell in question. If a cell is alive, it’s value will be 1; this gives us a really simple hack of adding all of these values together. This now tells us the number of neighbours to this cell.

Rendering

To the terminal.

Always, to the terminal.

You can render anywhere you want. For my example implementation, I’ve used the console.

void universe_render(unsigned char *u, int width, int height) {
  int x, y;

  erase();

  for (y = 0; y < height; y ++) {
    for (x = 0; x < width; x ++) {
      if (u[x + (y * width)]) {
        mvprintw(y + 1, x, "*");
      } else {
        mvprintw(y + 1, x, ".");
      }
    }
  }
}

Finishing up

Here’s a grab of the console.

Alive: 81    Dead: 1967
........................*.......................................
.......................*.*.............***......................
.......................*.*...........*.***......................
........................*...........*...........................
...................................**...........................
..........***.......................**.........**...............
.....................................*.........**...............
........*.....*.................................................
........*.....*.......................................*.........
........*.....*.......................................*.........
.***..................................................*.........
..........***...................................................
................**..............................................
...............*..*.............................................
................**..............................................
................................................................
................................................................
................................................................
................................................................
................................................................
................................................................
................................................................
..........................*.....................................
.........................***....................................
........................***.*...................................
.......................*....**..................................
......................**....*...................................
.......................*.**.*...................................
*...........................*..................................*
.*.......................***.........................**........*
*.........................*.........................*..*........
.....................................................**.........

The full code for this article can be found here.

Create tables from queries with Redshift

As a convenience to the developer, AWS Redshift offers CTAS for those times where you need to materialise a physical table from the result of a query.

Syntax

CREATE [ [LOCAL ] { TEMPORARY | TEMP } ]
TABLE table_name
[ ( column_name [, ... ] ) ]
[ BACKUP { YES | NO } ]
[ table_attributes ]
AS query

where table_attributes are:
[ DISTSTYLE { EVEN | ALL | KEY } ]
[ DISTKEY ( distkey_identifier ) ]
[ [ { COMPOUND | INTERLEAVED } ] SORTKEY ( column_name [, ...] ) ]

Re-produced from the documentation.

As you can see, this is basically a CREATE TABLE statement, with a SELECT query at the end of it.

The new table is loaded with data defined by the query in the command. The table columns have names and data types associated with the output columns of the query. The CREATE TABLE AS (CTAS) command creates a new table and evaluates the query to load the new table.

More Window Functions

This article is an extension of the window function, to follow up on each of the window functions.

MAX

The MAX function will retrieve the maximum value that it sees within the window.

MEDIAN

The MEDIAN function will calculate the median value for the range seen, within the window.

MIN

The MIN function will retrieve the minimum value that it sees within the window.

NTH_VALUE

Where the LAG and LEAD values are relative to the row in question, NTH_VALUE will retain the value at the literal offset specified.

NTILE

NTILE ranks rows into equally proportioned groups within the window seen by the expression.

PERCENT_RANK

Calculates the percent rank on rows seen by the window. The formula calculation is defined as:

(x - 1) / (the number of rows in the window or partition - 1)

PERCENTILE_CONT

PERCENTIL_CONT will calculate the linear interpolation between ordered values.

PERCENTILE_DISC

Returns the value with the smallest cumulative distribution value.

RATIO_TO_REPORT

Calculates a percentage where the row’s value is the divisor, and the total amount for the window is the dividend.

In this example, we’ll use RATIO_TO_REPORT to show us the percentage each sale makes over the period of a single day.

SELECT sale_date, salesperson, quantity::decimal * unit_cost,
  RATIO_TO_REPORT(quantity::decimal * unit_cost) OVER (PARTITION BY sale_date)
FROM public.sales
ORDER BY sale_date, sale_id;

RATIO_TO_REPORT(quantity::decimal * unit_cost) is what gives us the value that we’re working with in terms of ratio; the PARTITION BY sale_date then gives us the window; these ratios need to be calculated for the day.

ROW_NUMBER

ROW_NUMBER is a utility function that simply gives the row an ordinal value, counting up from 1; over the window.

We count the sales for the day, by applying ROW_NUMBER over the sale_date.

SELECT sale_date, salesperson, quantity::decimal * unit_cost,
  ROW_NUMBER() OVER (PARTITION BY sale_date)
FROM public.sales
ORDER BY sale_date, sale_id;

STDDEV_SAMP and STDDEV_POP

STDDEV_SAMP and STDDEV_POP will find the sample and population standard deviation of the values seen in a window.

SUM

The SUM function will retrieve the accumulated sum of an expression over the defined window.

VAR_SAMP and VAR_POP

VAR_SAMP and VAR_POP will find the sample and population variance of the values seen in a window.

Window Function LISTAGG

This article is an extension of the window function, to follow up on each of the window functions.

The LISTAGG function will aggregate values that are collected within the window defined by the partition expression.

In this example, we’ll list each sale in the database; adding a column at the end which will list all of the salespeople who made a sale on that particular day.

SELECT sale_date,
  LISTAGG(salesperson, ', ') OVER (PARTITION BY sale_date)
FROM public.sales
ORDER BY sale_date, sale_id;

This emits a dataset as follows:

Window Function LEAD

This article is an extension of the window function, to follow up on each of the window functions.

The LEAD function returns values in an offset row. The offset is given by the second argument to the function itself. The offset pushes the index below (or after) the selected row.

To demonstrate the effect of this function, we’ll take the sales_id value, and then we’ll also take a led sales_id. By adjusting the offset value, you’ll see how the leaded value ascends up the rows.

SELECT sale_id,
  LEAD(sale_id, 1) OVER (ORDER BY sale_id)
FROM public.sales
ORDER BY sale_date, sale_id
LIMIT 5;

Adjusting the index so that it’s now 2; the lead row is now offset by 2.