John Horton Conway’s Game Of Life

April 20, 2012

We studied one-dimensional cellular automata in a previous exercise. In today’s exercise, we will implement the famous two-dimensional cellular automaton by the British mathematician John Horton Conway, the Game of Life. Life was introduced by Martin Gardner in the October 1970 issue of Scientific American; I can remember coming home from the library and tracing a glider as it moved across my checkerboard.

The automaton exists on an infinite two-dimensional grid of cells, each either alive or dead. Each cell has a neighborhood of the eight cells horizontally, vertically or diagonally adjacent to it. A cell that is alive in one generation dies if it has less than two live neighbors or more than three live neighbors, otherwise is survives to the next generation; a cell that is dead becomes alive at the next generation if it has exactly three living neighbors. All births and deaths occur simultaneously from one generation to the next.

Mathematicians have shown that these simple rules evoke immense variety, and have built general-purpose computing structures from particular configurations of living cells. Forty-two years on, there are articles in scholarly journals, doctoral dissertations, and jillions of web sites that serve Life enthusiasts.

Your task is to write a program that computes and displays the history of a Life population. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Posted by programmingpraxis

Filed in Exercises

6 Comments »

6 Responses to “John Horton Conway’s Game Of Life”

ardnew said

April 20, 2012 at 4:13 PM

Pulled a lot of code from the Voters exercise.. This isn’t really implemented as an infinite two-dimensional grid, as the generations just wrap around the edges and persist in the same finite space, but here’s a solution in perl:

use strict;
use warnings;

our $NROWS = 20;
our $NCOLS = 20;
our $DELAY = 0.1; # seconds

sub gen_grid
{
  my ($r, $c, $d, @g) = @_;
 
  push @g, [map {int(rand($d + 1))} (1 .. $c)] for (1 .. $r);
  return @g;
}

sub print_grid
{
  print "\033[2J";
  print +(join '', @$_).$/ foreach @_;
  select undef, undef, undef, $DELAY;
}
 
sub neighbors
{
  my ($y, $m, $x, $n, $g) = @_;
  
  return grep 
    { 
      $$g[($y + $$_[0]) % $m][($x + $$_[1]) % $n] 
    }
    ([-1,-1],[-1, 0],[-1, 1],[ 0,-1],
     [ 0, 1],[ 1,-1],[ 1, 0],[ 1, 1])
}

sub main
{
  my ($rows, $cols) = @_;
  my @grid = gen_grid($rows, $cols, 1);

  while (1)
  {
    my @next = gen_grid($rows, $cols, 0);    
    print_grid(@grid);
    
    foreach my $r (0 .. $rows - 1)
    {
      foreach my $c (0 .. $cols - 1)
      {
        my $n = neighbors($r, $rows, $c, $cols, \@grid);
        $next[$r][$c] = $grid[$r][$c] & ($n == 2) | ($n == 3);
      }
    }        
    @grid = @next;
  }
}

main($NROWS, $NCOLS);

stungeye said
April 21, 2012 at 5:08 PM
Here’s a test-driven game of life I wrote in Ruby last year:

Tests (Minitest Specs): http://stungeye.github.com/tdd_game_of_life/test_life.html
Game of Life Code: http://stungeye.github.com/tdd_game_of_life/
Simple GUI: http://stungeye.github.com/tdd_game_of_life/shoes_life.html
Kwiatki said
April 23, 2012 at 7:35 PM
I came across the Game of Life in One Hundred Computer Programming Problems by Newey. I got hooked, spent a lot of time with a pencil and an eraser, used the Go board too. But I think I only learned about the glider when I saw one as a screensaver on a Sun workstation years later.
When Cellular Automata Come to Life – Wired Cosmos said
April 24, 2012 at 8:44 AM
[…] John Horton Conway’s Game Of Life « Programming Praxis […]
Jamison White said
April 25, 2012 at 9:45 PM
Reblogged this on Jamison White's Blog and commented:
I completed a rough text only version of it. I tried to limit myself to declarative Python statements (no for loops).
Dennis Smith said
August 28, 2012 at 2:27 PM
The September 1985 issue of Nibble magazine published my “One-Liner” version of John Conway’s Game Of Life. The rules for the contest were simple; no more than 256 characters could be used and all had to be on one line. The program allows for the entry of the starting live cells and will run until CtrlC is pressed. Because of the program size restriction the board is limited to 9 x 9 (to allow 10 or above would have made the program one character too long.

Programming Praxis