John Horton Conway’s Game Of Life

April 20, 2012

We steal the screen-handling code from a prior exercise:

(define esc (integer->char 27)) (define (cls) (display esc) (display #\[) (display #\2) (display #\J)) (define (hide-cursor) (display esc) (display #\[) (display #\?) (display #\2) (display #\5) (display #\l)) (define (show-cursor) (display esc) (display #\[) (display #\?) (display #\2) (display #\5) (display #\h)) (define (goto r c) (display esc) (display #\[) (display r) (display #\;) (display c) (display #\H)) (define max-r 24) (define max-c 39)

(define (show grid) (for (r 0 max-r) (for (c 0 max-c) (when (matrix-ref grid r c) (goto r (+ c c 1)) (display #\*)))))

The neighbors function counts the number of occupied cells that adjoin the given cell, wrapping around at the edges:

(define (neighbors grid r c) (define (cell rc) (if (matrix-ref grid (modulo (+ r (car rc)) max-r) (modulo (+ c (cadr rc)) max-c)) 1 0)) (apply + (map cell '((-1 -1) (-1 0) (-1 1) (0 -1) (0 1) (1 -1) (1 0) (1 1)))))

The Game of Life is implemented using two grids, so that all the assignments happen simultaneously; the input grid, init, is read at each step as the output grid, next is built one cell at a time, then the output grid replaces the input grid at the recursive call of the function. The Scheme idiom for <= allows us to use three operands to implement a between operator:

(define (life init) (cls) (hide-cursor) (show init) (let ((next (make-matrix max-r max-c))) (for (r 0 max-r) (for (c 0 max-c) (matrix-set! next r c (or (and (matrix-ref init r c) (<= 2 (neighbors init r c) 3)) (and (not (matrix-ref init r c)) (= (neighbors init r c) 3)))))) (life next)))

A function to generate a random initial population is shown below. Some populations quickly die, others churn for a long time, all eventually become stable. You can watch what happens to a random population by saying (life (rand-init)):

(define (rand-init) (let ((grid (make-matrix max-r max-c #f))) (for (r 0 max-r) (for (c 0 max-c) (if (< (rand) 1/2) (matrix-set! grid r c #t)))) grid))

One of the most famous Life patterns is the glider, which keeps moving endlessly along the infinite grid:

(define glider (let ((grid (make-matrix max-r max-c #f))) (matrix-set! grid 0 1 #t) (matrix-set! grid 1 2 #t) (matrix-set! grid 2 0 #t) (matrix-set! grid 2 1 #t) (matrix-set! grid 2 2 #t) grid))

We used the matrix functions, the for macro, and the random number generator from the Standard Prelude. You can see the complete program at http://programmingpraxis.codepad.org/l6ExmA3j.

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