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.

Pages: 1 2

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

  1. ardnew said

    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);
    
  2. stungeye said

    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

  3. Kwiatki said

    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.

  4. [...] John Horton Conway’s Game Of Life « Programming Praxis [...]

  5. 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).

  6. Dennis Smith said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: