Conway's Game of Life
You are encouraged to solve this task according to the task description, using any language you may know.
The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is the best-known example of a cellular automaton.
Conway's game of life is described here:
A cell C is represented by a 1 when alive or 0 when dead, in an m-by-m square array of cells. We calculate N - the sum of live cells in C's eight-location neighbourhood, then cell C is alive or dead in the next generation based on the following table:
C N new C 1 0,1 -> 0 # Lonely 1 4,5,6,7,8 -> 0 # Overcrowded 1 2,3 -> 1 # Lives 0 3 -> 1 # It takes three to give birth! 0 0,1,2,4,5,6,7,8 -> 0 # Barren
Assume cells beyond the boundary are always dead.
The "game" is actually a zero-player game, meaning that its evolution is determined by its initial state, needing no input from human players. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.
Although you should test your implementation on more complex examples such as the glider in a larger universe, show the action of the blinker (three adjoining cells in a row all alive), over three generations, in a 3 by 3 grid.
6502 Assembly
<lang 6502asm>randfill: stx $01 ;$200 for indirect
ldx #$02 ;addressing
stx $02
randloop: lda $fe ;generate random
and #$01 ;pixels on the
sta ($01),Y ;screen
jsr inc0103
cmp #$00
bne randloop
lda $02
cmp #$06
bne randloop
clearmem: lda #$df ;set $07df-$0a20
sta $01 ;to $#00
lda #$07
sta $02
clearbyte: lda #$00
sta ($01),Y
jsr inc0103
cmp #$20
bne clearbyte
lda $02
cmp #$0a
bne clearbyte
starttick:
copyscreen: lda #$00 ;set up source
sta $01 ;pointer at
sta $03 ;$01/$02 and
lda #$02 ;dest pointer
sta $02 ;at $03/$04
lda #$08
sta $04
ldy #$00
copybyte: lda ($01),Y ;copy pixel to
sta ($03),Y ;back buffer
jsr inc0103 ;increment pointers
cmp #$00 ;check to see
bne copybyte ;if we're at $600
lda $02 ;if so, we've
cmp #$06 ;copied the
bne copybyte ;entire screen
conway: lda #$df ;apply conway rules
sta $01 ;reset the pointer
sta $03 ;to $#01df/$#07df
lda #$01 ;($200 - $21)
sta $02 ;($800 - $21)
lda #$07
sta $04
onecell: lda #$00 ;process one cell
ldy #$01 ;upper cell
clc
adc ($03),Y
ldy #$41 ;lower cell
clc
adc ($03),Y
chkleft: tax ;check to see
lda $01 ;if we're at the
and #$1f ;left edge
tay
txa
cpy #$1f
beq rightcells
leftcells: ldy #$00 ;upper-left cell
clc
adc ($03),Y
ldy #$20 ;left cell
clc
adc ($03),Y
ldy #$40 ;lower-left cell
clc
adc ($03),Y
chkright: tax ;check to see
lda $01 ;if we're at the
and #$1f ;right edge
tay
txa
cpy #$1e
beq evaluate
rightcells: ldy #$02 ;upper-right cell
clc
adc ($03),Y
ldy #$22 ;right cell
clc
adc ($03),Y
ldy #$42 ;lower-right cell
clc
adc ($03),Y
evaluate: ldx #$01 ;evaluate total
ldy #$21 ;for current cell
cmp #$03 ;3 = alive
beq storex
ldx #$00
cmp #$02 ;2 = alive if
bne storex ;c = alive
lda ($03),Y
and #$01
tax
storex: txa ;store to screen
sta ($01),Y
jsr inc0103 ;move to next cell
conwayloop: cmp #$e0 ;if not last cell,
bne onecell ;process next cell
lda $02
cmp #$05
bne onecell
jmp starttick ;run next tick
inc0103: lda $01 ;increment $01
cmp #$ff ;and $03 as 16-bit
bne onlyinc01 ;pointers
inc $02
inc $04
onlyinc01: inc $01
lda $01
sta $03
rts</lang>
ACL2
<lang Lisp>(defun print-row (row)
(if (endp row)
nil
(prog2$ (if (first row)
(cw "[]")
(cw " "))
(print-row (rest row)))))
(defun print-grid-r (grid)
(if (endp grid)
nil
(progn$ (cw "|")
(print-row (first grid))
(cw "|~%")
(print-grid-r (rest grid)))))
(defun print-line (l)
(if (zp l)
nil
(prog2$ (cw "-")
(print-line (1- l)))))
(defun print-grid (grid)
(progn$ (cw "+")
(print-line (* 2 (len (first grid))))
(cw "+~%")
(print-grid-r grid)
(cw "+")
(print-line (* 2 (len (first grid))))
(cw "+~%")))
(defun neighbors-row-r (row)
(if (endp (rest (rest row)))
(list (if (first row) 1 0))
(cons (+ (if (first row) 1 0)
(if (third row) 1 0))
(neighbors-row-r (rest row)))))
(defun neighbors-row (row)
(cons (if (second row) 1 0)
(neighbors-row-r row)))
(defun zip+ (xs ys)
(if (or (endp xs) (endp ys))
(append xs ys)
(cons (+ (first xs) (first ys))
(zip+ (rest xs) (rest ys)))))
(defun counts-row (row)
(if (endp row)
nil
(cons (if (first row) 1 0)
(counts-row (rest row)))))
(defun neighbors-r (grid prev-counts curr-counts next-counts
prev-neighbors curr-neighbors
next-neighbors)
(if (endp (rest grid))
(list (zip+ (zip+ prev-counts
prev-neighbors)
(neighbors-row (first grid))))
(cons (zip+ (zip+ (zip+ prev-counts next-counts)
(zip+ prev-neighbors next-neighbors))
curr-neighbors)
(neighbors-r (rest grid)
curr-counts
next-counts
(counts-row (third grid))
curr-neighbors
next-neighbors
(neighbors-row (third grid))))))
(defun neighbors (grid)
(neighbors-r grid
nil
(counts-row (first grid))
(counts-row (second grid))
nil
(neighbors-row (first grid))
(neighbors-row (second grid))))
(defun life-rules-row (life neighbors)
(if (or (endp life) (endp neighbors))
nil
(cons (or (and (first life)
(or (= (first neighbors) 2)
(= (first neighbors) 3)))
(and (not (first life))
(= (first neighbors) 3)))
(life-rules-row (rest life) (rest neighbors)))))
(defun life-rules-r (grid neighbors)
(if (or (endp grid) (endp neighbors))
nil
(cons (life-rules-row (first grid) (first neighbors))
(life-rules-r (rest grid) (rest neighbors)))))
(defun conway-step (grid)
(life-rules-r grid (neighbors grid)))
(defun conway (grid steps)
(if (zp steps)
nil
(progn$ (print-grid grid)
(conway (conway-step grid) (1- steps)))))</lang>
Output:
+------+ | [] | | [] | | [] | +------+ +------+ | | |[][][]| | | +------+ +------+ | [] | | [] | | [] | +------+
Ada
<lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Life is
type Cell is (O, X); -- Two states of a cell
-- Computation of neighborhood
function "+" (L, R : Cell) return Integer is
begin
case L is
when O =>
case R is
when O => return 0;
when X => return 1;
end case;
when X =>
case R is
when O => return 1;
when X => return 2;
end case;
end case;
end "+";
function "+" (L : Integer; R : Cell) return Integer is
begin
case R is
when O => return L;
when X => return L + 1;
end case;
end "+";
-- A colony of cells. The borders are dire and unhabited
type Petri_Dish is array (Positive range <>, Positive range <>) of Cell;
procedure Step (Culture : in out Petri_Dish) is
Above : array (Culture'Range (2)) of Cell := (others => O);
Left : Cell;
This : Cell;
begin
for I in Culture'First (1) + 1 .. Culture'Last (1) - 1 loop
Left := O;
for J in Culture'First (2) + 1 .. Culture'Last (2) - 1 loop
case Above (J-1) + Above (J) + Above (J+1) +
Left + Culture (I, J+1) +
Culture (I+1, J-1) + Culture (I+1, J) + Culture (I+1, J+1) is
when 2 => -- Survives if alive
This := Culture (I, J);
when 3 => -- Survives or else multiplies
This := X;
when others => -- Dies
This := O;
end case;
Above (J-1) := Left;
Left := Culture (I, J);
Culture (I, J) := This;
end loop;
Above (Above'Last - 1) := Left;
end loop;
end Step;
procedure Put (Culture : Petri_Dish) is
begin
for I in Culture'Range loop
for J in Culture'Range loop
case Culture (I, J) is
when O => Put (' ');
when X => Put ('#');
end case;
end loop;
New_Line;
end loop;
end Put;
Blinker : Petri_Dish := (2..4 =>(O,O,X,O,O), 1|5 =>(O,O,O,O,O));
Glider : Petri_Dish :=
( (O,O,O,O,O,O,O,O,O,O,O),
(O,O,X,O,O,O,O,O,O,O,O),
(O,O,O,X,O,O,O,O,O,O,O),
(O,X,X,X,O,O,O,O,O,O,O),
(O,O,O,O,O,O,O,O,O,O,O),
(O,O,O,O,O,O,O,O,O,O,O)
);
begin
for Generation in 1..3 loop
Put_Line ("Blinker" & Integer'Image (Generation));
Put (Blinker);
Step (Blinker);
end loop;
for Generation in 1..5 loop
Put_Line ("Glider" & Integer'Image (Generation));
Put (Glider);
Step (Glider);
end loop;
end Life;</lang> The solution uses one cell thick border around square Petri dish as uninhabited dire land. This simplifies computations of neighborhood. Sample output contains 3 generations of the blinker and 5 of the glider:
Sample output:
Blinker 1
#
#
#
Blinker 2
###
Blinker 3
#
#
#
Glider 1
#
#
###
Glider 2
# #
##
#
Glider 3
#
# #
##
Glider 4
#
##
##
Glider 5
#
#
###
ALGOL 68
See Conway's Game of Life/ALGOL 68
APL
AutoHotkey
ahk discussion <lang autohotkey>rows := cols := 10 ; set grid dimensions i = -1,0,1, -1,1, -1,0,1 ; neighbors' x-offsets j = -1,-1,-1, 0,0, 1,1,1 ; neighbors' y-offsets StringSplit i, i, `, ; make arrays StringSplit j, j, `,
Loop % rows { ; setup grid of checkboxes
r := A_Index, y := r*17-8 ; looks good in VISTA
Loop % cols {
c := A_Index, x := c*17-5
Gui Add, CheckBox, x%x% y%y% w17 h17 vv%c%_%r% gCheck
}
} Gui Add, Button, % "x12 w" x+2, step ; button to step to next generation Gui Show Return
Check:
GuiControlGet %A_GuiControl% ; manual set of cells
Return
ButtonStep: ; move to next generation
Loop % rows {
r := A_Index
Loop % cols {
c := A_Index, n := 0
Loop 8 ; w[x,y] <- new states
x := c+i%A_Index%, y := r+j%A_Index%, n += 1=v%x%_%y%
GuiControl,,v%c%_%r%,% w%c%_%r% := v%c%_%r% ? n=2 || n=3 : n=3
}
}
Loop % rows { ; update v[x,y] = states
r := A_Index
Loop % cols
v%A_Index%_%r% := w%A_Index%_%r%
}
Return
GuiClose: ; exit when GUI is closed ExitApp</lang>
AWK
<lang AWK> BEGIN { c=220; d=619; i=10000; printf("\033[2J");
while(i--) m[i]=0;
while(d--) m[int(rand()*1000)]=1;
while(c--){
for(i=52; i<=949; i++){
d=m[i-1]+m[i+1]+m[i-51]+m[i-50]+m[i-49]+m[i+49]+m[i+50]+m[i+51];
n[i]=m[i];
if(m[i]==0 && d==3) n[i]=1;
else if(m[i]==1 && d<2) n[i]=0;
else if(m[i]==1 && d>3) n[i]=0;
}
printf("\033[1;1H");
for(i=1;i<=1000;i++)
{
if(n[i]) printf("O"); else printf(".");
m[i]=n[i];
if(!(i%50)) printf("\n");
}
printf("%3d\n",c); x=30000; while(x--) ;
}
} </lang>
BASIC256
Saving to PNG files function is omited. You can find it in the Galton box animation example.
<lang basic256>X = 59 : Y = 35 : H = 4
fastgraphics graphsize X*H,Y*H
dim c(X,Y) : dim cn(X,Y) : dim cl(X,Y) c[X/2-1,Y/3+1] = 1 : c[X/2,Y/3+1] = 1 : c[X/2+1,Y/3+1] = 1 # Thunderbird methuselah c[X/2,Y/3+3] = 1 : c[X/2,Y/3+4] = 1 : c[X/2,Y/3+5] = 1
s = 0 do color black rect 0,0,graphwidth,graphheight alive = 0 : stable = 1 s = s + 1 for y = 0 to Y-1 for x = 0 to X-1 xm1 = (x-1+X)%X : xp1 = (x+1+X)%X ym1 = (y-1+Y)%Y : yp1 = (y+1+Y)%Y cn[x,y] = c[xm1,y] + c[xp1,y] cn[x,y] = c[xm1,ym1] + c[x,ym1] + c[xp1,ym1] + cn[x,y] cn[x,y] = c[xm1,yp1] + c[x,yp1] + c[xp1,yp1] + cn[x,y] if c[x,y] = 1 then if cn[x,y] < 2 or cn[x,y] > 3 then cn[x,y] = 0 else cn[x,y] = 1 alive = alive + 1 end if else if cn[x,y] = 3 then cn[x,y] = 1 alive = alive + 1 else cn[x,y] = 0 end if end if if c[x,y] then if cn[x,y] then if cl[x,y] then color purple # adult if not cl[x,y] then color green # newborn else if cl[x,y] then color red # old if not cl[x,y] then color yellow # shortlived end if rect x*H,y*H,H,H end if next x next y refresh pause 0.06 # Copy arrays for i = 0 to X-1 for j = 0 to Y-1 if cl[i,j]<>cn[i,j] then stable = 0 cl[i,j] = c[i,j] c[i,j] = cn[i,j] next j next i until not alive or stable
if not alive then print "Died in "+s+" iterations" color black rect 0,0,graphwidth,graphheight refresh else print "Stabilized in "+(s-2)+" iterations" end if</lang> Text output:
Stabilized in 243 iterations
BBC BASIC
<lang bbcbasic> dx% = 64
dy% = 64
DIM old&(dx%+1,dy%+1), new&(dx%+1,dy%+1)
VDU 23,22,dx%*4;dy%*4;16,16,16,0
OFF
REM Set blinker:
old&(50,50) = 1 : old&(50,51) = 1 : old&(50,52) = 1
REM Set glider:
old&(5,7) = 1 : old&(6,7) = 1 : old&(7,7) = 1 : old&(7,6) = 1 : old&(6,5) = 1
REM Draw initial grid:
FOR X% = 1 TO dx%
FOR Y% = 1 TO dy%
IF old&(X%,Y%) GCOL 11 ELSE GCOL 4
PLOT 69, X%*8-6, Y%*8-4
NEXT
NEXT X%
REM Run:
GCOL 4,0
REPEAT
FOR X% = 1 TO dx%
FOR Y% = 1 TO dy%
S% = old&(X%-1,Y%) + old&(X%,Y%-1) + old&(X%-1,Y%-1) + old&(X%+1,Y%-1) + \
\ old&(X%+1,Y%) + old&(X%,Y%+1) + old&(X%-1,Y%+1) + old&(X%+1,Y%+1)
O% = old&(X%,Y%)
N% = -(S%=3 OR (O%=1 AND S%=2))
new&(X%,Y%) = N%
IF N%<>O% PLOT X%*8-6, Y%*8-4
NEXT
NEXT X%
SWAP old&(), new&()
WAIT 30
UNTIL FALSE</lang>
Output:
C
Play game of life on your console: gcc -std=c99 -Wall game.c; ./a.out [width] [height]
<lang C>#include <stdio.h>
- include <stdlib.h>
- include <unistd.h>
- define for_x for (int x = 0; x < w; x++)
- define for_y for (int y = 0; y < h; y++)
- define for_xy for_x for_y
void show(void *u, int w, int h) { int (*univ)[w] = u; printf("\033[H"); for_y { for_x printf(univ[y][x] ? "\033[07m \033[m" : " "); printf("\033[E"); } fflush(stdout); }
void evolve(void *u, int w, int h) { unsigned (*univ)[w] = u; unsigned new[h][w];
for_y for_x { int n = 0; for (int y1 = y - 1; y1 <= y + 1; y1++) for (int x1 = x - 1; x1 <= x + 1; x1++) if (univ[(y1 + h) % h][(x1 + w) % w]) n++;
if (univ[y][x]) n--; new[y][x] = (n == 3 || (n == 2 && univ[y][x])); } for_y for_x univ[y][x] = new[y][x]; }
void game(int w, int h) { unsigned univ[h][w]; for_xy univ[y][x] = rand() < RAND_MAX / 10 ? 1 : 0; while (1) { show(univ, w, h); evolve(univ, w, h); usleep(200000); } }
int main(int c, char **v) { int w = 0, h = 0; if (c > 1) w = atoi(v[1]); if (c > 2) h = atoi(v[2]); if (w <= 0) w = 30; if (h <= 0) h = 30; game(w, h); }</lang> Also see Conway's Game of Life/C
C++
Considering that the simplest implementation in C++ would lack any use of the object-oriented paradigm, this code was specifically written to demonstrate the various object-oriented features of C++. Thus, while it is somewhat verbose, it fully simulates Conway's Game of Life and is relatively simple to expand to feature different starting shapes. <lang c>#include <iostream>
- define HEIGHT 4
- define WIDTH 4
struct Shape { public:
char xCoord; char yCoord; char height; char width; char **figure;
};
struct Glider : public Shape {
static const char GLIDER_SIZE = 3; Glider( char x , char y ); ~Glider();
};
struct Blinker : public Shape {
static const char BLINKER_HEIGHT = 3; static const char BLINKER_WIDTH = 1; Blinker( char x , char y ); ~Blinker();
};
class GameOfLife { public:
GameOfLife( Shape sh ); void print(); void update(); char getState( char state , char xCoord , char yCoord , bool toggle); void iterate(unsigned int iterations);
private:
char world[HEIGHT][WIDTH]; char otherWorld[HEIGHT][WIDTH]; bool toggle; Shape shape;
};
GameOfLife::GameOfLife( Shape sh ) :
shape(sh) , toggle(true)
{
for ( char i = 0; i < HEIGHT; i++ ) {
for ( char j = 0; j < WIDTH; j++ ) {
world[i][j] = '.';
}
}
for ( char i = shape.yCoord; i - shape.yCoord < shape.height; i++ ) {
for ( char j = shape.xCoord; j - shape.xCoord < shape.width; j++ ) {
if ( i < HEIGHT && j < WIDTH ) {
world[i][j] =
shape.figure[ i - shape.yCoord ][j - shape.xCoord ];
}
}
}
}
void GameOfLife::print() {
if ( toggle ) {
for ( char i = 0; i < HEIGHT; i++ ) {
for ( char j = 0; j < WIDTH; j++ ) {
std::cout << world[i][j];
}
std::cout << std::endl;
}
} else {
for ( char i = 0; i < HEIGHT; i++ ) {
for ( char j = 0; j < WIDTH; j++ ) {
std::cout << otherWorld[i][j];
}
std::cout << std::endl;
}
}
for ( char i = 0; i < WIDTH; i++ ) {
std::cout << '=';
}
std::cout << std::endl;
}
void GameOfLife::update() {
if (toggle) {
for ( char i = 0; i < HEIGHT; i++ ) {
for ( char j = 0; j < WIDTH; j++ ) {
otherWorld[i][j] =
GameOfLife::getState(world[i][j] , i , j , toggle);
}
}
toggle = !toggle;
} else {
for ( char i = 0; i < HEIGHT; i++ ) {
for ( char j = 0; j < WIDTH; j++ ) {
world[i][j] =
GameOfLife::getState(otherWorld[i][j] , i , j , toggle);
}
}
toggle = !toggle;
}
}
char GameOfLife::getState( char state, char yCoord, char xCoord, bool toggle ) {
char neighbors = 0;
if ( toggle ) {
for ( char i = yCoord - 1; i <= yCoord + 1; i++ ) {
for ( char j = xCoord - 1; j <= xCoord + 1; j++ ) {
if ( i == yCoord && j == xCoord ) {
continue;
}
if ( i > -1 && i < HEIGHT && j > -1 && j < WIDTH ) {
if ( world[i][j] == 'X' ) {
neighbors++;
}
}
}
}
} else {
for ( char i = yCoord - 1; i <= yCoord + 1; i++ ) {
for ( char j = xCoord - 1; j <= xCoord + 1; j++ ) {
if ( i == yCoord && j == xCoord ) {
continue;
}
if ( i > -1 && i < HEIGHT && j > -1 && j < WIDTH ) {
if ( otherWorld[i][j] == 'X' ) {
neighbors++;
}
}
}
}
}
if (state == 'X') {
return ( neighbors > 1 && neighbors < 4 ) ? 'X' : '.';
}
else {
return ( neighbors == 3 ) ? 'X' : '.';
}
}
void GameOfLife::iterate( unsigned int iterations ) {
for ( int i = 0; i < iterations; i++ ) {
print();
update();
}
}
Glider::Glider( char x , char y ) {
xCoord = x;
yCoord = y;
height = GLIDER_SIZE;
width = GLIDER_SIZE;
figure = new char*[GLIDER_SIZE];
for ( char i = 0; i < GLIDER_SIZE; i++ ) {
figure[i] = new char[GLIDER_SIZE];
}
for ( char i = 0; i < GLIDER_SIZE; i++ ) {
for ( char j = 0; j < GLIDER_SIZE; j++ ) {
figure[i][j] = '.';
}
}
figure[0][1] = 'X';
figure[1][2] = 'X';
figure[2][0] = 'X';
figure[2][1] = 'X';
figure[2][2] = 'X';
}
Glider::~Glider() {
for ( char i = 0; i < GLIDER_SIZE; i++ ) {
delete[] figure[i];
}
delete[] figure;
}
Blinker::Blinker( char x , char y ) {
xCoord = x;
yCoord = y;
height = BLINKER_HEIGHT;
width = BLINKER_WIDTH;
figure = new char*[BLINKER_HEIGHT];
for ( char i = 0; i < BLINKER_HEIGHT; i++ ) {
figure[i] = new char[BLINKER_WIDTH];
}
for ( char i = 0; i < BLINKER_HEIGHT; i++ ) {
for ( char j = 0; j < BLINKER_WIDTH; j++ ) {
figure[i][j] = 'X';
}
}
}
Blinker::~Blinker() {
for ( char i = 0; i < BLINKER_HEIGHT; i++ ) {
delete[] figure[i];
}
delete[] figure;
}
int main() {
Glider glider(0,0); GameOfLife gol(glider); gol.iterate(5); Blinker blinker(1,0); GameOfLife gol2(blinker); gol2.iterate(4);
} </lang> Which outputs first a glider, then a blinker, over a few iterations. The following output is reformatted for convenience.
.X.. .... .... .... .... ..X. X.X. ..X. .X.. ..X. XXX. .XX. X.X. ..XX ...X .... .X.. .XX. .XX. .XXX ==== ==== ==== ==== ==== .X.. .... .X.. .X.. XXX. .X.. .X.. .... .X.. .... .... .... ==== ==== ====
C#
<lang c sharp>using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq;
namespace Game_of_Life {
internal static class Program
{
private static void Main()
{
var blinker = new Blinker();
for (int i = 0; i < 3; i++)
{
blinker.Print(new Cell(-1, -2), new Cell(4, 4));
blinker.Step();
}
var glider = new Glider();
for (int i = 0; i < 3; i++)
{
var top = glider.Top;
var left = glider.Left;
var bottom = glider.Bottom;
var right = glider.Right;
glider.Print(new Cell(left - 1, top - 1), new Cell(right - left + 2, bottom - top + 2));
glider.Step();
}
}
private static void Print(this CellCollection state, Cell topLeft, Cell size)
{
const char alive = '#';
const char dead = ' ';
Console.WriteLine("Generation {0} [({1}, {2}), ({3}, {4})] ({5} live cells)",
state.Generation,
topLeft.X, topLeft.Y,
topLeft.X + size.X, topLeft.Y + size.Y,
state.Count);
for (int i = topLeft.Y; i <= topLeft.Y + size.Y; i++)
{
for (int o = topLeft.X; o <= topLeft.X + size.X; o++)
{
Console.Write(state.Contains(o, i) ? alive : dead);
}
Console.WriteLine();
}
Console.WriteLine("Generated in {0} ms.", state.MillisecondsToGenerate);
}
private class Blinker : CellCollection
{
public Blinker()
{
Add(0, 0);
Add(1, 0);
Add(2, 0);
}
}
private class Glider : CellCollection
{
public Glider()
{
Add(1, 0);
Add(2, 1);
Add(0, 2);
Add(1, 2);
Add(2, 2);
}
}
private class CellCollection : List<Cell>
{
public CellCollection(IEnumerable<Cell> cells)
: this()
{
foreach (var cell in cells)
Add(cell);
}
public CellCollection()
{
Generation = 0;
_stopwatch = new Stopwatch();
}
// Returns the amount of neighboring cells that are alive.
private byte GetAliveNeighborsCount(int x, int y)
{
byte neighbors = 0;
for (int i = -1; i <= 1; i++)
{
for (int o = -1; o <= 1; o++)
{
if (i == 0 && o == 0)
continue;
if (Contains(x + i, y + o))
neighbors++;
}
}
return neighbors;
}
// Returns all neighboring cells.
private IEnumerable<Cell> GetNeighbors(int x, int y)
{
for (int i = -1; i <= 1; i++)
{
for (int o = -1; o <= 1; o++)
{
if (i == 0 && o == 0)
continue;
yield return new Cell(x + o, y + i);
}
}
}
// Steps forward the specified amount of generations.
public void Step(uint steps = 1)
{
_stopwatch.Restart();
for (uint step = 0; step < steps; step++)
{
Generation++;
// Variable to act as a snapshot of the current state while we make changes.
var oldState = new CellCollection(this);
// Variable to hold the cells that we will check.
var checkCells = new List<Cell>(oldState);
// Adds all dead cells neighboring alive cells to the cells that we will check.
checkCells.AddRange(
from cell in oldState
from neighbor in GetNeighbors(cell.X, cell.Y)
where !checkCells.Contains(neighbor)
select neighbor);
foreach (var cell in checkCells)
{
byte neighbors = oldState.GetAliveNeighborsCount(cell.X, cell.Y);
/*
* Checks if the current cell is alive or not.
*
* If so, if the cell has less than 2, or more than 3 alive neighbors,
* the cell will be killed.
*
* If not, if the cell has 3 alive neighbors, the cell will be brought to life.
*/
if (oldState.Contains(cell.X, cell.Y))
{
if (neighbors < 2 || neighbors > 3)
Remove(cell);
}
else
{
if (neighbors == 3)
Add(cell);
}
}
}
_stopwatch.Stop();
}
public void Add(int x, int y)
{
Add(new Cell(x, y));
}
public bool Contains(int x, int y)
{
return Contains(new Cell(x, y));
}
public int Top
{
get { return (from cell in this orderby cell.Y ascending select cell.Y).First(); }
}
public int Bottom
{
get { return (from cell in this orderby cell.Y descending select cell.Y).First(); }
}
public int Left
{
get { return (from cell in this orderby cell.X ascending select cell.X).First(); }
}
public int Right
{
get { return (from cell in this orderby cell.X descending select cell.X).First(); }
}
public uint Generation { get; private set; }
public long MillisecondsToGenerate { get { return _stopwatch.ElapsedMilliseconds; } }
private readonly Stopwatch _stopwatch;
}
private struct Cell : IEquatable<Cell>
{
public Cell(int x, int y)
{
_x = x;
_y = y;
}
private readonly int _x;
public int X
{
get { return _x; }
}
private readonly int _y;
public int Y
{
get { return _y; }
}
public bool Equals(Cell other)
{
return (X == other.X && Y == other.Y);
}
}
}
}</lang>
Sample Output
Blinker Generation 0 [(-1, -2), (3, 2)] (3 live cells) ### Generated in 0 ms. Generation 1 [(-1, -2), (3, 2)] (3 live cells) # # # Generated in 13 ms. Generation 2 [(-1, -2), (3, 2)] (3 live cells) ### Generated in 0 ms. Glider Generation 0 [(-1, -1), (3, 3)] (5 live cells) # # ### Generated in 0 ms. Generation 1 [(-1, 0), (3, 4)] (5 live cells) # # ## # Generated in 0 ms. Generation 2 [(-1, 0), (3, 4)] (5 live cells) # # # ## Generated in 0 ms.
Clojure
Based on the implementation by Christophe Grand here: http://clj-me.cgrand.net/2011/08/19/conways-game-of-life/ This implementation models the live cells as a set of coordinates. <lang lisp>(defn neighbours x y
(for [dx [-1 0 1] dy [-1 0 1]
:when (not (and (zero? dx) (zero? dy)))]
[(+ x dx) (+ y dy)]))
(defn next-step [cells]
(set (for [[cell n] (frequencies (mapcat neighbours cells))
:when (or (= n 3) (and (= n 2) (cells cell)))]
cell)))</lang>
Common Lisp
<lang lisp>(defun next-life (array &optional results)
(let* ((dimensions (array-dimensions array))
(results (or results (make-array dimensions :element-type 'bit))))
(destructuring-bind (rows columns) dimensions
(labels ((entry (row col)
"Return array(row,col) for valid (row,col) else 0."
(if (or (not (< -1 row rows))
(not (< -1 col columns)))
0
(aref array row col)))
(neighbor-count (row col &aux (count 0))
"Return the sum of the neighbors of (row,col)."
(dolist (r (list (1- row) row (1+ row)) count)
(dolist (c (list (1- col) col (1+ col)))
(unless (and (eql r row) (eql c col))
(incf count (entry r c))))))
(live-or-die? (current-state neighbor-count)
(if (or (and (eql current-state 1)
(<= 2 neighbor-count 3))
(and (eql current-state 0)
(eql neighbor-count 3)))
1
0)))
(dotimes (row rows results)
(dotimes (column columns)
(setf (aref results row column)
(live-or-die? (aref array row column)
(neighbor-count row column)))))))))
(defun print-grid (grid &optional (out *standard-output*))
(destructuring-bind (rows columns) (array-dimensions grid)
(dotimes (r rows grid)
(dotimes (c columns (terpri out))
(write-char (if (zerop (aref grid r c)) #\+ #\#) out)))))
(defun run-life (&optional world (iterations 10) (out *standard-output*))
(let* ((world (or world (make-array '(10 10) :element-type 'bit)))
(result (make-array (array-dimensions world) :element-type 'bit)))
(do ((i 0 (1+ i))) ((eql i iterations) world)
(terpri out) (print-grid world out)
(psetq world (next-life world result)
result world))))</lang>
<lang lisp>(run-life (make-array '(3 3)
:element-type 'bit
:initial-contents '((0 0 0)
(1 1 1)
(0 0 0)))
3)</lang>
produces
+++ ### +++ +#+ +#+ +#+ +++ ### +++
D
<lang d>import std.stdio,std.string,std.algorithm,std.typetuple,std.array;
struct GameOfLife {
enum Cell : char { dead = ' ', alive = '#' }
Cell[][] grid, newGrid;
this(in int x, in int y) pure nothrow {
grid = new typeof(grid)(y + 2, x + 2);
newGrid = new typeof(grid)(y + 2, x + 2);
}
void opIndexAssign(in string[] v, in size_t y, in size_t x)
pure nothrow {
foreach (nr, row; v)
foreach (nc, state; row) {
//grid[y + nr][x + nc] = to!Cell(state);
assert(state == Cell.dead || state == Cell.alive);
grid[y + nr][x + nc] = cast(Cell)state;
}
}
void iteration() pure nothrow {
newGrid[0][] = Cell.dead;
newGrid[$ - 1][] = Cell.dead;
foreach (row; newGrid)
row[0] = row[$ - 1] = Cell.dead;
foreach (r; 1 .. grid.length - 1)
foreach (c; 1 .. grid[0].length - 1) {
int count = 0;
foreach (i; -1 .. 2)
foreach (j; -1 .. 2)
if (i != 0 || j != 0)
count += grid[r + i][c + j] == Cell.alive;
auto a = count == 3 ||
(count == 2 && grid[r][c] == Cell.alive);
newGrid[r][c] = a ? Cell.alive : Cell.dead;
}
swap(grid, newGrid); }
string toString() const pure nothrow {
string ret = "-".replicate(grid[0].length - 1) ~ "\n";
foreach (row; grid[1 .. $ - 1])
ret ~= "|" ~ cast(char[])row[1 .. $-1] ~ "|\n";
return ret ~ "-".replicate(grid[0].length - 1);
}
} void main() {
immutable glider1 = [" #", "# #", " ##"]; immutable glider2 = ["# ", "# #", "## "];
auto uni = GameOfLife(60, 20); uni[3, 2] = glider1; uni[3, 15] = glider2; uni[3, 19] = glider1; uni[3, 32] = glider2; uni[5, 50] = [" # #", "# ", "# #", "#### "]; writeln(uni);
foreach (i; 0 .. 20) {
uni.iteration();
writeln(uni);
}
}</lang> Output, first iteration:
------------------------------------------------------------- | | | | | # # # # | | # # # # # # # # | | ## ## ## ## # # | | # | | # # | | #### | | | | | | | | | | | | | | | | | | | | | | | | | -------------------------------------------------------------
Faster Version
Same output. <lang d>import std.stdio,std.string,std.algorithm,std.typetuple,std.array;
template Iota(int start, int stop) {
static if (stop <= start)
alias TypeTuple!() Iota;
else
alias TypeTuple!(Iota!(start, stop-1), stop-1) Iota;
}
struct GameOfLife {
enum Cell : char { dead = ' ', alive = '#' }
Cell[] grid, newGrid;
immutable size_t nCols;
this(int nx, int ny) pure nothrow {
nCols = nx + 2;
grid = new typeof(grid)(nCols * (ny + 2));
newGrid = new typeof(grid)(grid.length);
}
void opIndexAssign(in string[] v, in size_t y, in size_t x)
pure nothrow {
foreach (nr, row; v)
foreach (nc, state; row) {
//grid[(y + nr) * nCols + x + nc] = to!Cell(state);
assert(state == Cell.dead || state == Cell.alive);
grid[(y + nr) * nCols + x + nc] = cast(Cell)state;
}
}
void iteration() {
newGrid[0 .. nCols] = Cell.dead;
newGrid[$ - nCols .. $] = Cell.dead;
foreach (nr; 1 .. (newGrid.length / nCols) - 1) {
newGrid[nr * nCols + 0] = Cell.dead;
newGrid[nr * nCols + nCols - 1] = Cell.dead;
}
foreach (nr; 1 .. (grid.length / nCols) - 1) {
size_t nr_nCols = nr * nCols;
foreach (nc; 1 .. nCols - 1) {
uint count = 0;
/*static*/ foreach (i; Iota!(-1, 2))
/*static*/ foreach (j; Iota!(-1, 2))
static if (i != 0 || j != 0)
count +=
(grid[nr_nCols + i * nCols + nc + j] == Cell.alive);
const a = count == 3 ||
(count == 2 && grid[nr_nCols + nc] == Cell.alive);
newGrid[nr_nCols + nc] = a ? Cell.alive : Cell.dead;
}
}
swap(grid, newGrid); }
string toString() const pure nothrow {
string ret = "-".replicate(nCols - 1) ~ "\n";
foreach (nr; 1 .. (grid.length / nCols) - 1)
ret ~= "|" ~
cast(char[])grid[nr * nCols + 1 .. nr * nCols + nCols - 1]
~ "|\n";
return ret ~ "-".replicate(nCols - 1);
}
}
void main() {
immutable glider1 = [" #", "# #", " ##"]; immutable glider2 = ["# ", "# #", "## "];
auto uni = GameOfLife(60, 20); uni[3, 2] = glider1; uni[3, 15] = glider2; uni[3, 19] = glider1; uni[3, 32] = glider2; uni[5, 50] = [" # #", "# ", "# #", "#### "]; writeln(uni);
foreach (i; 0 .. 20) {
uni.iteration();
writeln(uni);
}
}</lang>
Dart
<lang dart>/**
- States of a cell. A cell is either [ALIVE] or [DEAD].
- The state contains its [symbol] for printing.
- /
class State {
const State(this.symbol);
static final ALIVE = const State('#');
static final DEAD = const State(' ');
final String symbol;
}
/**
- The "business rule" of the game. Depending on the count of neighbours,
- the [cellState] changes.
- /
class Rule {
Rule(this.cellState);
reactToNeighbours(int neighbours) {
if (neighbours == 3) {
cellState = State.ALIVE;
} else if (neighbours != 2) {
cellState = State.DEAD;
}
}
var cellState;
}
/**
- A coordinate on the [Grid].
- /
class Point {
const Point(this.x, this.y);
operator +(other) => new Point(x + other.x, y + other.y);
final int x; final int y;
}
/**
- List of the relative indices of the 8 cells around a cell.
- /
class Neighbourhood {
List<Point> points() {
return [
new Point(LEFT, UP), new Point(MIDDLE, UP), new Point(RIGHT, UP),
new Point(LEFT, SAME), new Point(RIGHT, SAME),
new Point(LEFT, DOWN), new Point(MIDDLE, DOWN), new Point(RIGHT, DOWN)
];
}
static final LEFT = -1; static final MIDDLE = 0; static final RIGHT = 1; static final UP = -1; static final SAME = 0; static final DOWN = 1;
}
/**
- The grid is an endless, two-dimensional [field] of cell [State]s.
- /
class Grid {
Grid(this.xCount, this.yCount) {
_field = new Map();
_neighbours = new Neighbourhood().points();
}
set(point, state) {
_field[_pos(point)] = state;
}
State get(point) {
var state = _field[_pos(point)];
return state != null ? state : State.DEAD;
}
int countLiveNeighbours(point) => _neighbours.filter((offset) => get(point + offset) == State.ALIVE).length;
_pos(point) => '${(point.x + xCount) % xCount}:${(point.y + yCount) % yCount}';
print() {
var sb = new StringBuffer();
iterate((point) { sb.add(get(point).symbol); }, (x) { sb.add("\n"); });
return sb.toString();
}
iterate(eachCell, [finishedRow]) {
for (var x = 0; x < xCount; x++) {
for (var y = 0; y < yCount; y++) {
eachCell(new Point(x, y));
}
if(finishedRow != null) {
finishedRow(x);
}
}
}
final xCount, yCount; List<Point> _neighbours; Map<String, State> _field;
}
/**
- The game updates the [grid] in each step using the [Rule].
- /
class Game {
Game(this.grid);
tick() {
var newGrid = createNewGrid();
grid.iterate((point) {
var rule = new Rule(grid.get(point));
rule.reactToNeighbours(grid.countLiveNeighbours(point));
newGrid.set(point, rule.cellState);
});
grid = newGrid; }
createNewGrid() => new Grid(grid.xCount, grid.yCount);
printGrid() => print(grid.print());
Grid grid;
}
main() {
// Run the GoL with a blinker. runBlinker();
}
runBlinker() {
var game = new Game(createBlinkerGrid());
for(int i = 0; i < 3; i++) {
game.printGrid();
game.tick();
}
game.printGrid();
}
createBlinkerGrid() {
var grid = new Grid(4, 4); loadBlinker(grid); return grid;
}
loadBlinker(grid) => blinkerPoints().forEach((point) => grid.set(point, State.ALIVE));
blinkerPoints() => [new Point(0, 1), new Point(1, 1), new Point(2, 1)];</lang>
Test cases driving the design of this code: <lang dart>#import('<path to sdk>/lib/unittest/unittest.dart');
main() {
group('rules', () {
test('should let living but lonely cell die', () {
var rule = new Rule(State.ALIVE);
rule.reactToNeighbours(1);
expect(rule.cellState, State.DEAD);
});
test('should let proper cell live on', () {
var rule = new Rule(State.ALIVE);
rule.reactToNeighbours(2);
expect(rule.cellState, State.ALIVE);
});
test('should let dead cell with three neighbours be reborn', () {
var rule = new Rule(State.DEAD);
rule.reactToNeighbours(3);
expect(rule.cellState, State.ALIVE);
});
test('should let living cell with too many neighbours die', () {
var rule = new Rule(State.ALIVE);
rule.reactToNeighbours(4);
expect(rule.cellState, State.DEAD);
});
});
group('grid', () {
var origin = new Point(0, 0);
test('should have state', () {
var grid = new Grid(1, 1);
expect(grid.get(origin), State.DEAD);
grid.set(origin, State.ALIVE);
expect(grid.get(origin), State.ALIVE);
});
test('should have dimension', () {
var grid = new Grid(2, 3);
expect(grid.get(origin), State.DEAD);
grid.set(origin, State.ALIVE);
expect(grid.get(origin), State.ALIVE);
expect(grid.get(new Point(1, 2)), State.DEAD);
grid.set(new Point(1, 2), State.ALIVE);
expect(grid.get(new Point(1, 2)), State.ALIVE);
});
test('should be endless', () {
var grid = new Grid(2, 4);
grid.set(new Point(2, 4), State.ALIVE);
expect(grid.get(origin), State.ALIVE);
grid.set(new Point(-1, -1), State.ALIVE);
expect(grid.get(new Point(1, 3)), State.ALIVE);
});
test('should print itself', () {
var grid = new Grid(1, 2);
grid.set(new Point(0, 1), State.ALIVE);
expect(grid.print(), " #\n");
});
});
group('game', () {
test('should exists', () {
var game = new Game(null);
expect(game, isNotNull);
});
test('should create a new grid when ticked', () {
var grid = new Grid(1, 1);
var game = new Game(grid);
game.tick();
expect(game.grid !== grid);
});
test('should have a grid with the same dimension after tick', (){
var game = new Game(new Grid(2, 3));
game.tick();
expect(game.grid.xCount, 2);
expect(game.grid.yCount, 3);
});
test('should apply rules to middle cell', (){
var grid = new Grid(3, 3);
grid.set(new Point(1, 1), State.ALIVE);
var game = new Game(grid);
game.tick();
expect(game.grid.get(new Point(1, 1)), State.DEAD);
grid.set(new Point(0, 0), State.ALIVE);
grid.set(new Point(1, 0), State.ALIVE);
game = new Game(grid);
game.tick();
expect(game.grid.get(new Point(1, 1)), State.ALIVE);
});
test('should apply rules to all cells', (){
var grid = new Grid(3, 3);
grid.set(new Point(0, 1), State.ALIVE);
grid.set(new Point(1, 0), State.ALIVE);
grid.set(new Point(1, 1), State.ALIVE);
var game = new Game(grid);
game.tick();
expect(game.grid.get(new Point(0, 0)), State.ALIVE);
});
});
}</lang> Output:
# # # ### # # # ###
E
Just does three generations of a blinker in a dead-boundary grid, as specified. (User:Kevin Reid has graphical and wrapping versions.)
<lang e>def gridWidth := 3 def gridHeight := 3 def X := 0..!gridWidth def Y := 0..!gridHeight
def makeFlexList := <elib:tables.makeFlexList> def makeGrid() {
def storage := makeFlexList.fromType(<type:java.lang.Boolean>, gridWidth * gridHeight) storage.setSize(gridWidth * gridHeight)
def grid {
to __printOn(out) {
for y in Y {
out.print("[")
for x in X {
out.print(grid[x, y].pick("#", " "))
}
out.println("]")
}
}
to get(xb :int, yb :int) {
return if (xb =~ x :X && yb =~ y :Y) {
storage[y * gridWidth + x]
} else {
false
}
}
to put(x :X, y :Y, c :boolean) {
storage[y * gridWidth + x] := c
}
}
return grid
}
def mooreNeighborhood := [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]] def computeNextLife(prevGrid, nextGrid) {
for y in Y {
for x in X {
var neighbors := 0
for [nx, ny] ? (prevGrid[x+nx, y+ny]) in mooreNeighborhood {
neighbors += 1
}
def self := prevGrid[x, y]
nextGrid[x, y] := (self && neighbors == 2 || neighbors == 3)
}
}
}
var currentFrame := makeGrid() var nextFrame := makeGrid() currentFrame[1, 0] := true currentFrame[1, 1] := true currentFrame[1, 2] := true
for _ in 1..3 {
def frame := nextFrame computeNextLife(currentFrame, frame) nextFrame := currentFrame currentFrame := frame println(currentFrame)
}</lang>
Erlang
<lang Erlang>
-module(life).
-export([bang/1]).
-define(CHAR_DEAD, 32). % " "
-define(CHAR_ALIVE, 111). % "o"
-define(CHAR_BAR, 45). % "-"
-define(GEN_INTERVAL, 100).
-record(state, {x :: non_neg_integer()
,y :: non_neg_integer()
,n :: pos_integer()
,bar :: nonempty_string()
,board :: array()
,gen_count :: pos_integer()
,gen_duration :: non_neg_integer()
,print_time :: non_neg_integer()
}).
%% ============================================================================
%% API
%% ============================================================================
bang(Args) ->
[X, Y] = [atom_to_integer(A) || A <- Args],
{Time, Board} = timer:tc(fun() -> init_board(X, Y) end),
State = #state{x = X
,y = Y
,n = X * Y
,bar = [?CHAR_BAR || _ <- lists:seq(1, X)]
,board = Board
,gen_count = 1 % Consider inital state to be generation 1
,gen_duration = Time
,print_time = 0 % There was no print time yet
},
life_loop(State).
%% ============================================================================
%% Internal
%% ============================================================================
life_loop(
#state{x = X
,y = Y
,n = N
,bar = Bar
,board = Board
,gen_count = GenCount
,gen_duration = Time
,print_time = LastPrintTime
}=State) ->
{PrintTime, ok} = timer:tc(
fun() ->
do_print_screen(Board, Bar, X, Y, N, GenCount, Time, LastPrintTime)
end
),
{NewTime, NewBoard} = timer:tc(
fun() ->
next_generation(X, Y, Board)
end
),
NewState = State#state{board = NewBoard
,gen_count = GenCount + 1
,gen_duration = NewTime
,print_time = PrintTime
},
NewTimeMil = NewTime / 1000, NextGenDelay = at_least_zero(round(?GEN_INTERVAL - NewTimeMil)), timer:sleep(NextGenDelay),
life_loop(NewState).
at_least_zero(Integer) when Integer >= 0 -> Integer;
at_least_zero(_) -> 0.
do_print_screen(Board, Bar, X, Y, N, GenCount, Time, PrintTime) ->
ok = do_print_status(Bar, X, Y, N, GenCount, Time, PrintTime), ok = do_print_board(Board).
do_print_status(Bar, X, Y, N, GenCount, TimeMic, PrintTimeMic) ->
TimeSec = TimeMic / 1000000,
PrintTimeSec = PrintTimeMic / 1000000,
ok = io:format("~s~n", [Bar]),
ok = io:format(
"X: ~b Y: ~b CELLS: ~b GENERATION: ~b DURATION: ~f PRINT TIME: ~f~n",
[X, Y, N, GenCount, TimeSec, PrintTimeSec]
),
ok = io:format("~s~n", [Bar]).
do_print_board(Board) ->
% It seems that just doing a fold should be faster than map + to_list
% combo, but, after measuring several times, map + to_list has been
% consistently (nearly twice) faster than either foldl or foldr.
RowStrings = array:to_list(
array:map(
fun(_, Row) ->
array:to_list(
array:map(
fun(_, State) ->
state_to_char(State)
end,
Row
)
)
end,
Board
)
),
ok = lists:foreach(
fun(RowString) ->
ok = io:format("~s~n", [RowString])
end,
RowStrings
).
state_to_char(0) -> ?CHAR_DEAD;
state_to_char(1) -> ?CHAR_ALIVE.
next_generation(W, H, Board) ->
array:map(
fun(Y, Row) ->
array:map(
fun(X, State) ->
Neighbors = filter_offsides(H, W, neighbors(X, Y)),
States = neighbor_states(Board, Neighbors),
LiveNeighbors = lists:sum(States),
new_state(State, LiveNeighbors)
end,
Row
)
end,
Board
).
new_state(1, LiveNeighbors) when LiveNeighbors < 2 -> 0;
new_state(1, LiveNeighbors) when LiveNeighbors < 4 -> 1;
new_state(1, LiveNeighbors) when LiveNeighbors > 3 -> 0;
new_state(0, LiveNeighbors) when LiveNeighbors =:= 3 -> 1;
new_state(State, _LiveNeighbors) -> State.
neighbor_states(Board, Neighbors) ->
[array:get(X, array:get(Y, Board)) || {X, Y} <- Neighbors].
filter_offsides(H, W, Coordinates) ->
[{X, Y} || {X, Y} <- Coordinates, is_onside(X, Y, H, W)].
is_onside(X, Y, H, W) when (X >= 0) and (Y >= 0) and (X < W) and (Y < H) -> true;
is_onside(_, _, _, _) -> false.
neighbors(X, Y) ->
[{X + OffX, Y + OffY} || {OffX, OffY} <- offsets()].
offsets() ->
[offset(D) || D <- directions()].
offset('N') -> { 0, -1};
offset('NE') -> { 1, -1};
offset('E') -> { 1, 0};
offset('SE') -> { 1, 1};
offset('S') -> { 0, 1};
offset('SW') -> {-1, 1};
offset('W') -> {-1, 0};
offset('NW') -> {-1, -1}.
directions() ->
['N', 'NE', 'E', 'SE', 'S', 'SW', 'W', 'NW'].
init_board(X, Y) ->
array:map(fun(_, _) -> init_row(X) end, array:new(Y)).
init_row(X) ->
array:map(fun(_, _) -> init_cell_state() end, array:new(X)).
init_cell_state() ->
crypto:rand_uniform(0, 2).
atom_to_integer(Atom) ->
list_to_integer(atom_to_list(Atom)).
</lang>
F#
The following F# implementation uses
for visualization and is easily compiled into a standalone executable:
<lang fsharp>let count (a: _ [,]) x y =
let m, n = a.GetLength 0, a.GetLength 1
let mutable c = 0
for x in x-1..x+1 do
for y in y-1..y+1 do
if x>=0 && x<m && y>=0 && y<n && a.[x, y] then
c <- c + 1
if a.[x, y] then c-1 else c
let rule (a: _ [,]) x y =
match a.[x, y], count a x y with | true, (2 | 3) | false, 3 -> true | _ -> false
open System.Windows open System.Windows.Media.Imaging
[<System.STAThread>] do
let rand = System.Random()
let n = 256
let game = Array2D.init n n (fun _ _ -> rand.Next 2 = 0) |> ref
let image = Controls.Image(Stretch=Media.Stretch.Uniform)
let format = Media.PixelFormats.Gray8
let pixel = Array.create (n*n) 0uy
let update _ =
game := rule !game |> Array2D.init n n
for x in 0..n-1 do
for y in 0..n-1 do
pixel.[x+y*n] <- if (!game).[x, y] then 255uy else 0uy
image.Source <-
BitmapSource.Create(n, n, 1.0, 1.0, format, null, pixel, n)
Media.CompositionTarget.Rendering.Add update
Window(Content=image, Title="Game of Life")
|> (Application()).Run |> ignore</lang>
Forth
gencell uses an optimization for the core Game of Life rules: new state = (old state | neighbors == 3).
<lang forth> \ The fast wrapping requires dimensions that are powers of 2.
1 6 lshift constant w \ 64 1 4 lshift constant h \ 16 : rows w * 2* ; 1 rows constant row h rows constant size create world size allot world value old old w + value new variable gens : clear world size erase 0 gens ! ; : age new old to new to old 1 gens +! ; : col+ 1+ ; : col- 1- dup w and + ; \ avoid borrow into row : row+ row + ; : row- row - ; : wrap ( i -- i ) [ size w - 1- ] literal and ; : w@ ( i -- 0/1 ) wrap old + c@ ; : w! ( 0/1 i -- ) wrap old + c! ; : foreachrow ( xt -- ) size 0 do I over execute row +loop drop ; : showrow ( i -- ) cr old + w over + swap do I c@ if [char] * else bl then emit loop ; : show ['] showrow foreachrow cr ." Generation " gens @ . ; : sum-neighbors ( i -- i n ) dup col- row- w@ over row- w@ + over col+ row- w@ + over col- w@ + over col+ w@ + over col- row+ w@ + over row+ w@ + over col+ row+ w@ + ; : gencell ( i -- ) sum-neighbors over old + c@ or 3 = 1 and swap new + c! ; : genrow ( i -- ) w over + swap do I gencell loop ; : gen ['] genrow foreachrow age ; : life begin gen 0 0 at-xy show key? until ;
\ patterns
char | constant '|'
: pat ( i addr len -- )
rot dup 2swap over + swap do
I c@ '|' = if drop row+ dup else
I c@ bl = 1+ over w! col+ then
loop 2drop ;
: blinker s" ***" pat ;
: toad s" ***| ***" pat ;
: pentomino s" **| **| *" pat ;
: pi s" **| **|**" pat ;
: glider s" *| *|***" pat ;
: pulsar s" *****|* *" pat ;
: ship s" ****|* *| *| *" pat ;
: pentadecathalon s" **********" pat ;
: clock s" *| **|**| *" pat ;
clear 0 glider show * * *** Generation 0 ok gen show * * ** * Generation 1 ok</lang>
Fortran
<lang fortran> PROGRAM LIFE_2D
IMPLICIT NONE
INTEGER, PARAMETER :: gridsize = 10
LOGICAL :: cells(0:gridsize+1,0:gridsize+1) = .FALSE.
INTEGER :: i, j, generation=0
REAL :: rnums(gridsize,gridsize)
! Start patterns
! **************
! cells(2,1:3) = .TRUE. ! Blinker
! cells(3,4:6) = .TRUE. ; cells(4,3:5) = .TRUE. ! Toad
! cells(1,2) = .TRUE. ; cells(2,3) = .TRUE. ; cells(3,1:3) = .TRUE. ! Glider
cells(3:5,3:5) = .TRUE. ; cells(6:8,6:8) = .TRUE. ! Figure of Eight
! CALL RANDOM_SEED
! CALL RANDOM_NUMBER(rnums)
! WHERE (rnums>0.6) cells(1:gridsize,1:gridsize) = .TRUE. ! Random universe
CALL Drawgen(cells(1:gridsize, 1:gridsize), generation)
DO generation = 1, 8
CALL Nextgen(cells)
CALL Drawgen(cells(1:gridsize, 1:gridsize), generation)
END DO
CONTAINS
SUBROUTINE Drawgen(cells, gen)
LOGICAL, INTENT(IN OUT) :: cells(:,:)
INTEGER, INTENT(IN) :: gen
WRITE(*, "(A,I0)") "Generation ", gen
DO i = 1, SIZE(cells,1)
DO j = 1, SIZE(cells,2)
IF (cells(i,j)) THEN
WRITE(*, "(A)", ADVANCE = "NO") "#"
ELSE
WRITE(*, "(A)", ADVANCE = "NO") " "
END IF
END DO
WRITE(*,*)
END DO
WRITE(*,*)
END SUBROUTINE Drawgen
SUBROUTINE Nextgen(cells)
LOGICAL, INTENT(IN OUT) :: cells(0:,0:)
LOGICAL :: buffer(0:SIZE(cells, 1)-1, 0:SIZE(cells, 2)-1)
INTEGER :: neighbours, i, j
buffer = cells ! Store current status
DO i = 1, SIZE(cells, 1)-2
DO j = 1, SIZE(cells, 2)-2
if(buffer(i, j)) then
neighbours = sum(count(buffer(i-1:i+1, j-1:j+1), 1)) - 1
else
neighbours = sum(count(buffer(i-1:i+1, j-1:j+1), 1))
end if
SELECT CASE(neighbours)
CASE (0:1, 4:8)
cells(i,j) = .FALSE.
CASE (2)
! No change
CASE (3)
cells(i,j) = .TRUE.
END SELECT
END DO
END DO
END SUBROUTINE Nextgen
END PROGRAM LIFE_2D</lang>
Sample output:
Blinker
Generation 0
###
Generation 1
#
#
#
Generation 2
###
Figure of Eight (a period eight oscillator)
Generation 0
###
###
###
###
###
###
Generation 1
#
# #
# #
# #
# #
# #
# #
#
Generation 2
#
###
### #
# #
# #
# ###
###
#
Generation 3
###
#
# #
# # #
# # #
# #
#
###
Generation 4
#
##
# ##
### #
# # #
# # #
# ###
## #
##
#
Generation 5
##
# #
# #
# # #
# # #
# #
# #
##
Generation 6
#
# ###
## #
# ##
### #
#
Generation 7
##
## #
#
#
# ##
##
Generation 8
###
###
###
###
###
###
Go
<lang go>package main
import "fmt"
const (
rows = 3 cols = 3 empty = '·' // middle dot alive = '*' start = "···***···" sz = (rows + 2) * (cols + 2)
)
var (
cs = make([]rune, sz) ns = make([]int, sz) nb [8]int
)
func main() {
// initialize empty (really we just need the border)
for i := range cs {
cs[i] = empty
}
// initialize start
si := []rune(start)
for row := 1; row <= rows; row++ {
for col := 1; col <= cols; col++ {
cs[row*(cols+2)+col] = si[(row-1)*cols+col-1]
}
}
// initialize neighbor offsets
for i := 0; i < 3; i++ {
nb[i] = i - cols - 3
nb[i+3] = i + cols + 1
}
nb[6] = -1
nb[7] = 1
// run
printU()
for g := 0; g < 3; g++ {
genU()
printU()
}
}
func genU() {
// compute n
for row := 1; row <= rows; row++ {
for col := 1; col <= cols; col++ {
cx := row*(cols+2) + col
n := 0
for _, d := range nb {
if cs[cx+d] == '*' {
n++
}
}
ns[cx] = n
}
}
// update c
for row := 1; row <= rows; row++ {
for col := 1; col <= cols; col++ {
cx := row*(cols+2) + col
if cs[cx] == '*' {
switch ns[cx] {
case 0, 1, 4, 5, 6, 7, 8:
cs[cx] = '·'
}
} else if ns[cx] == 3 {
cs[cx] = '*'
}
}
}
}
func printU() {
fmt.Println("")
for row := 1; row <= rows; row++ {
cx := row*(cols+2) + 1
fmt.Println(string(cs[cx : cx+cols]))
}
}</lang> Output:
··· *** ··· ·*· ·*· ·*· ··· *** ··· ·*· ·*· ·*·
Haskell
<lang haskell>import Data.Array
type Grid = Array Int Bool
-- The grid is flattened into one dimension for simplicity.
life :: Int -> Int -> Grid -> Grid {- Returns the given Grid advanced by one generation. -} life w h old =
listArray (bounds old) (map f coords) where coords = [(x, y) | y <- [0 .. h - 1], x <- [0 .. w - 1]]
f (x, y) | c && (n == 2 || n == 3) = True
| not c && n == 3 = True
| otherwise = False
where c = get x y
n = count [get (x + x') (y + y') |
x' <- [-1, 0, 1], y' <- [-1, 0, 1],
not (x' == 0 && y' == 0)]
get x y | x < 0 || x == w = False
| y < 0 || y == h = False
| otherwise = old ! (x + y*w)
count :: [Bool] -> Int count [] = 0 count (False : l) = count l count (True : l) = 1 + count l</lang>
Example of use:
<lang haskell>grid :: [String] -> (Int, Int, Grid) grid l = (width, height, a)
where (width, height) = (length $ head l, length l)
a = listArray (0, width * height - 1) $ concatMap f l
f = map g
g '.' = False
g _ = True
printGrid :: Int -> Grid -> IO () printGrid width = mapM_ f . split width . elems
where f = putStrLn . map g
g False = '.'
g _ = '#'
split :: Int -> [a] -> a split _ [] = [] split n l = a : split n b
where (a, b) = splitAt n l
blinker = grid
[".#.", ".#.", ".#."]
glider = grid
["............", "............", "............", ".......###..", ".......#....", "........#...", "............"]
printLife :: Int -> (Int, Int, Grid) -> IO () printLife n (w, h, g) = mapM_ f $ take n $ iterate (life w h) g
where f g = do
putStrLn "------------------------------"
printGrid w g
main = printLife 10 glider</lang>
Icon and Unicon
<lang icon>global limit
procedure main(args)
n := args[1] | 50 # default is a 50x50 grid
limit := args[2] | &null # optional limit to number of generations
write("Enter the starting pattern, end with EOF")
grid := getInitialGrid(n)
play(grid)
end
- This procedure reads in the initial pattern, inserting it
- into an nXn grid of cells. The nXn grid also gets a
- new border of empty cells, which just makes the test simpler
- for determining what do with a cell on each generation.
- It would be better to let the user move the cursor and click
- on cells to create/delete living cells, but this version
- assumes a simple ASCII terminal.
procedure getInitialGrid(n)
static notBlank, allStars
initial {
notBlank := ~' '
allStars := repl("*",*notBlank)
}
g := [] # store as an array of strings
put(g,repl(" ",n))
while r := read() do { # read in rows of grid
r := left(r,n) # force each to length n
put(g," "||map(r,notBlank,allStars)||" ") # and making any life a '*'
}
while *g ~= (n+2) do
put(g,repl(" ",n))
return g
end
- Simple-minded procedure to 'play' Life from a starting grid.
procedure play(grid)
while not allDone(grid) do {
display(grid)
grid := onePlay(grid)
}
end
- Display the grid
procedure display(g)
write(repl("-",*g[1]))
every write(!g)
write(repl("-",*g[1]))
end
- Compute one generation of Life from the current one.
procedure onePlay(g)
ng := []
every put(ng, !g) # new generation starts as copy of old
every ng[r := 2 to *g-1][c := 2 to *g-1] := case sum(g,r,c) of {
3: "*" # cell lives (or is born)
2: g[r][c] # cell unchanged
default: " " # cell dead
}
return ng
end
- Return the number of living cells surrounding the current cell.
procedure sum(g,r,c)
cnt := 0
every (i := -1 to 1, j := -1 to 1) do
if ((i ~= 0) | (j ~= 0)) & (g[r+i][c+j] == "*") then cnt +:= 1
return cnt
end
- Check to see if all the cells have died or we've exceeded the
- number of allowed generations.
procedure allDone(g)
static count initial count := 0 return ((count +:= 1) > \limit) | (trim(!g) == " ")
end</lang>
A sample run:
->life 3 3
Enter the starting pattern, end with EOF
***
---
***
---
---
*
*
*
---
---
***
---
->
J
Solution: <lang j>pad=: 0,0,~0,.0,.~] life=: (_3 _3 (+/ e. 3+0,4&{)@,;._3 ])@pad</lang>
In other words, given a life instance, the next generation can be found by:
- . adding extra empty cells, surrounding the life instance,
- . tessellating the result, finding every overlapping 3 by 3 subinstance,
- . totaling the number of live cells in each subinstance,
- . treating a subinstance as a live cell iff that total is a member of the sequence 3,x where x is 3 if the center cell was previously dead, and 4 if the center cell was previously alive.
Example (showing generations 0, 1 and 2 of a blinker): <lang j> life^:0 1 2 #:0 7 0 0 0 0 1 1 1 0 0 0
0 1 0 0 1 0 0 1 0
0 0 0 1 1 1 0 0 0</lang>
JAMES II/Rule-based Cellular Automata
<lang j2carules>@caversion 1;
dimensions 2;
//using Moore neighborhood neighborhood moore;
//available states state DEAD, ALIVE;
/*
if current state is ALIVE and the neighborhood does not contain 2 or 3 ALIVE states the cell changes to DEAD
- /
rule{ALIVE}:!ALIVE{2,3}->DEAD;
/*
if current state is DEAD and there are exactly 3 ALIVE cells in the neighborhood the cell changes to ALIVE
- /
rule{DEAD}:ALIVE{3}->ALIVE;</lang> Animated output for the blinker example:
Java
<lang java>public class GameOfLife{ public static void main(String[] args){ String[] dish= { "_#_", "_#_", "_#_",}; int gens= 3; for(int i= 0;i < gens;i++){ System.out.println("Generation " + i + ":"); print(dish); dish= life(dish); } }
public static String[] life(String[] dish){ String[] newGen= new String[dish.length]; for(int row= 0;row < dish.length;row++){//each row newGen[row]= ""; for(int i= 0;i < dish[row].length();i++){//each char in the row String above= "";//neighbors above String same= "";//neighbors in the same row String below= "";//neighbors below if(i == 0){//all the way on the left //no one above if on the top row //otherwise grab the neighbors from above above= (row == 0) ? null : dish[row - 1].substring(i, i + 2); same= dish[row].substring(i + 1, i + 2); //no one below if on the bottom row //otherwise grab the neighbors from below below= (row == dish.length - 1) ? null : dish[row + 1] .substring(i, i + 2); }else if(i == dish[row].length() - 1){//right //no one above if on the top row //otherwise grab the neighbors from above above= (row == 0) ? null : dish[row - 1].substring(i - 1, i + 1); same= dish[row].substring(i - 1, i); //no one below if on the bottom row //otherwise grab the neighbors from below below= (row == dish.length - 1) ? null : dish[row + 1] .substring(i - 1, i + 1); }else{//anywhere else //no one above if on the top row //otherwise grab the neighbors from above above= (row == 0) ? null : dish[row - 1].substring(i - 1, i + 2); same= dish[row].substring(i - 1, i) + dish[row].substring(i + 1, i + 2); //no one below if on the bottom row //otherwise grab the neighbors from below below= (row == dish.length - 1) ? null : dish[row + 1] .substring(i - 1, i + 2); } int neighbors= getNeighbors(above, same, below); if(neighbors < 2 || neighbors > 3){ newGen[row]+= "_";//<2 or >3 neighbors -> die }else if(neighbors == 3){ newGen[row]+= "#";//3 neighbors -> spawn/live }else{ newGen[row]+= dish[row].charAt(i);//2 neighbors -> stay } } } return newGen; }
public static int getNeighbors(String above, String same, String below){ int ans= 0; if(above != null){//no one above for(char x: above.toCharArray()){//each neighbor from above if(x == '#') ans++;//count it if someone is here } } for(char x: same.toCharArray()){//two on either side if(x == '#') ans++;//count it if someone is here } if(below != null){//no one below for(char x: below.toCharArray()){//each neighbor below if(x == '#') ans++;//count it if someone is here } } return ans; }
public static void print(String[] dish){ for(String s: dish){ System.out.println(s); } } }</lang> Output:
Generation 0: _#_ _#_ _#_ Generation 1: ___ ### ___ Generation 2: _#_ _#_ _#_
JavaScript
<lang javascript>function GameOfLife () {
this.init = function (turns,width,height) { this.board = new Array(height); for (var x = 0; x < height; x++) { this.board[x] = new Array(width); for (var y = 0; y < width; y++) { this.board[x][y] = Math.round(Math.random()); } } this.turns = turns; }
this.nextGen = function() { this.boardNext = new Array(this.board.length); for (var i = 0; i < this.board.length; i++) { this.boardNext[i] = new Array(this.board[i].length); } for (var x = 0; x < this.board.length; x++) { for (var y = 0; y < this.board[x].length; y++) { var n = 0; for (var dx = -1; dx <= 1; dx++) { for (var dy = -1; dy <= 1; dy++) { if ( dx == 0 && dy == 0){} else if (typeof this.board[x+dx] !== 'undefined' && typeof this.board[x+dx][y+dy] !== 'undefined' && this.board[x+dx][y+dy]) { n++; } } } var c = this.board[x][y]; switch (n) { case 0: case 1: c = 0; break; case 2: break; case 3: c = 1; break; default: c = 0; } this.boardNext[x][y] = c; } } this.board = this.boardNext.slice(); }
this.print = function() { for (var x = 0; x < this.board.length; x++) { var l = ""; for (var y = 0; y < this.board[x].length; y++) { if (this.board[x][y]) l += "X"; else l += " "; } print(l); } }
this.start = function() { for (var t = 0; t < this.turns; t++) { print("---\nTurn "+(t+1)); this.print(); this.nextGen() } }
}
var game = new GameOfLife();
print("---\n3x3 Blinker over three turns."); game.init(3); game.board = [ [0,0,0], [1,1,1], [0,0,0]]; game.start();
print("---\n10x6 Glider over five turns."); game.init(5); game.board = [ [0,0,0,0,0,0,0,0,0,0], [0,0,1,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,0,0,0], [0,1,1,1,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0]]; game.start();
print("---\nRandom 5x10"); game.init(5,5,10); game.start();</lang> Output:
---
3x3 Blinker over three turns.
---
Turn 1
XXX
---
Turn 2
X
X
X
---
Turn 3
XXX
---
10x6 Glider over five turns.
---
Turn 1
X
X
XXX
---
Turn 2
X X
XX
X
---
Turn 3
X
X X
XX
---
Turn 4
X
XX
XX
---
Turn 5
X
X
XXX
---
Random 5x10
---
Turn 1
XXXX
XX
X
XX X
XX
X X
X
X X
X
X XX
---
Turn 2
XXXX
X XX
XX X
XX
X X
X X
XX
XX
XX XX
---
Turn 3
XX X
X
X X
XX X
XXX
---
Turn 4
X
X X
X
X
X
---
Turn 5
XXX
Essentially the same as the above straight JavaScript but displayed in an HTML5 Canvas. <lang javascript> <html> <head> <title></title> <script type="text/javascript">
function GameOfLife () {
this.init = function (turns,width,height) { this.board = new Array(height); for (var x = 0; x < height; x++) { this.board[x] = new Array(width); for (var y = 0; y < width; y++) { this.board[x][y] = Math.round(Math.random()); } } this.turns = turns; }
this.nextGen = function() { this.boardNext = new Array(this.board.length); for (var i = 0; i < this.board.length; i++) { this.boardNext[i] = new Array(this.board[i].length); } for (var x = 0; x < this.board.length; x++) { for (var y = 0; y < this.board[x].length; y++) { var n = 0; for (var dx = -1; dx <= 1; dx++) { for (var dy = -1; dy <= 1; dy++) { if ( dx == 0 && dy == 0){} else if (typeof this.board[x+dx] !== 'undefined' && typeof this.board[x+dx][y+dy] !== 'undefined' && this.board[x+dx][y+dy]) { n++; } } } var c = this.board[x][y]; switch (n) { case 0: case 1: c = 0; break; case 2: break; case 3: c = 1; break; default: c = 0; } this.boardNext[x][y] = c; } } this.board = this.boardNext.slice(); }
this.print = function(ctx,w,h) { if (!w) w = 8; if (!h) h = 8; for (var x = 0; x < this.board.length; x++) { var l = ""; for (var y = 0; y < this.board[x].length; y++) { if (this.board[x][y]) // x and y reversed to draw matrix like it looks in source // rather than the "actual" positions ctx.fillStyle = "orange"; else ctx.fillStyle = "black"; ctx.fillRect(y*h,x*w,h,w); } } }
this.start = function(ctx,w,h) { for (var t = 0; t < this.turns; t++) { this.print(ctx,w,h); this.nextGen() } }
}
function init() { // Change document title and text under canvas document.title = "Conway's Game of Life";
// Setup game boards for Conway's Game of Life var blinker = new GameOfLife(); blinker.board = [ [0,1,0], [0,1,0], [0,1,0]];
var glider = new GameOfLife(); glider.board = [ [0,0,0,0,0,0], [0,0,1,0,0,0], [0,0,0,1,0,0], [0,1,1,1,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0]];
var random = new GameOfLife(); random.init(null,8,8);
// Get canvas contexts or return 1 blinker.canvas = document.getElementById('blinker'); glider.canvas = document.getElementById('glider'); random.canvas = document.getElementById('random'); if (blinker.canvas.getContext && glider.canvas.getContext && random.canvas.getContext) { blinker.ctx = blinker.canvas.getContext('2d'); glider.ctx = glider.canvas.getContext('2d'); random.ctx = random.canvas.getContext('2d'); } else { return 1; }
// Run main() at set interval
setInterval(function(){run(glider,glider.ctx,25,25)},250);
setInterval(function(){run(blinker,blinker.ctx,25,25)},250);
setInterval(function(){run(random,random.ctx,25,25)},250);
return 0;
}
function run(game,ctx,w,h) { game.print(ctx,w,h); game.nextGen()
return 0; }
</script>
</head>
<body onLoad="init();">
3x3 Blinker
<canvas id="blinker" width="75" height="75">
No canvas support found!
</canvas>
6x6 Glider
<canvas id="glider" width="150" height="150">
No canvas support found!
</canvas>
8x8 Random
<canvas id="random" width="200" height="200">
No canvas support found!
</canvas>
</body>
</html></lang>
Output for 3x3 Blinker:
Liberty BASIC
It will run slow for grids above say 25! <lang lb>
nomainwin
gridX = 20
gridY = gridX
mult =500 /gridX
pointSize =360 /gridX
dim old( gridX +1, gridY +1), new( gridX +1, gridY +1)
'Set blinker:
old( 16, 16) =1: old( 16, 17) =1 : old( 16, 18) =1
'Set glider:
old( 5, 7) =1: old( 6, 7) =1: old( 7, 7) =1
old( 7, 6) =1: old( 6, 5) =1
WindowWidth =570
WindowHeight =600
open "Conway's 'Game of Life'." for graphics_nsb_nf as #w
#w "trapclose [quit]"
#w "down ; size "; pointSize
#w "fill black"
'Draw initial grid
for x = 1 to gridX
for y = 1 to gridY
'#w "color "; int( old( x, y) *256); " 0 255"
if old( x, y) <>0 then #w "color red" else #w "color darkgray"
#w "set "; x *mult +20; " "; y *mult +20
next y
next x
' ______________________________________________________________________________ 'Run
do
for x =1 to gridX
for y =1 to gridY
'find number of live Moore neighbours
neighbours =old( x -1, y -1) +old( x, y -1) +old( x +1, y -1)+_
old( x -1, y) +old( x +1, y )+_
old( x -1, y +1) +old( x, y +1) +old( x +1, y +1)
was =old( x, y)
if was =0 then
if neighbours =3 then N =1 else N =0
else
if neighbours =3 or neighbours =2 then N =1 else N =0
end if
new( x, y) = N
'#w "color "; int( N /8 *256); " 0 255"
if N <>0 then #w "color red" else #w "color darkgray"
#w "set "; x *mult +20; " "; y *mult +20
next y
next x
scan
'swap
for x =1 to gridX
for y =1 to gridY
old( x, y) =new( x, y)
next y
next x
'Re-run until interrupted...
loop until FALSE
'User shutdown received
[quit] close #w end
</lang>
Lua
<lang lua>function Evolve( cell )
local m = #cell
local cell2 = {}
for i = 1, m do
cell2[i] = {}
for j = 1, m do
cell2[i][j] = cell[i][j]
end
end
for i = 1, m do
for j = 1, m do
local count
if cell2[i][j] == 0 then count = 0 else count = -1 end
for x = -1, 1 do
for y = -1, 1 do
if i+x >= 1 and i+x <= m and j+y >= 1 and j+y <= m and cell2[i+x][j+y] == 1 then count = count + 1 end
end
end
if count < 2 or count > 3 then cell[i][j] = 0 end
if count == 3 then cell[i][j] = 1 end
end
end
return cell
end
m = 3 -- number rows / colums
num_iterations = 10
cell = {} for i = 1, m do
cell[i] = {}
for j = 1, m do
cell[i][j] = 0
end
end
cell[2][2], cell[2][1], cell[2][3] = 1, 1, 1
for l = 1, num_iterations do
for i = 1, m do
for j = 1, m do
if cell[i][j] == 1 then io.write( "#" ) else io.write( " " ) end
end
io.write( "\n" )
end
cell = Evolve( cell )
end </lang>
MATLAB
MATLAB has a builtin Game of Life GUI. Type <lang matlab>life</lang> to run it. To view the code, type
<lang matlab>open(fullfile(matlabroot, 'toolbox', 'matlab', 'demos', 'life.m'))</lang>
Here is an example code, more simple (runs the game of life for N generations in a square of side S) :
<lang matlab>function GoL(S, N) %
colormap copper; whitebg('black');
G= round(rand(S));
A = [S 1:S-1]; B = [2:S 1];
for k=1:N
Sum = G(A,:)+G(B,:)+G(:,B)+G(:,A)+G(A,B)+G(A,A)+G(B,B)+G(B,A);
G = double((G & (Sum == 2)) | (Sum == 3));
surf(G); view([0 90]); pause(0.001)
end
end</lang>
Mathematica
Mathematica has cellular automaton functionality built in, so implementing Conway's Game of Life is a one-liner: <lang Mathematica>CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}}, startconfiguration, steps];</lang> Example of a glyder progressing 8 steps and showing the 9 frames afterwards as grids of hashes and dots: <lang Mathematica>results=CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},{{{0,1,0},{0,0,1},{1,1,1}},0},8];
Do[Print[i-1];Print[Grid[resultsi/.{1->"#",0->"."}]];,{i,1,Length[results]}]</lang>
gives back:
0 .#... ..#.. ###.. ..... ..... 1 ..... #.#.. .##.. .#... ..... 2 ..... ..#.. #.#.. .##.. ..... 3 ..... .#... ..##. .##.. ..... 4 ..... ..#.. ...#. .###. ..... 5 ..... ..... .#.#. ..##. ..#.. 6 ..... ..... ...#. .#.#. ..##. 7 ..... ..... ..#.. ...## ..##. 8 ..... ..... ...#. ....# ..###
Maxima
<lang maxima>life(A) := block(
[p, q, B: zerofor(A), s],
[p, q]: matrix_size(A),
for i thru p do (
for j thru q do (
s: 0,
if j > 1 then s: s + A[i, j - 1],
if j < q then s: s + A[i, j + 1],
if i > 1 then (
s: s + A[i - 1, j],
if j > 1 then s: s + A[i - 1, j - 1],
if j < q then s: s + A[i - 1, j + 1]
),
if i < p then (
s: s + A[i + 1, j],
if j > 1 then s: s + A[i + 1, j - 1],
if j < q then s: s + A[i + 1, j + 1]
),
B[i, j]: charfun(s = 3 or (s = 2 and A[i, j] = 1))
)
),
B
)$
/* a glider */
L: matrix([0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])$
gen(A, n) := block(thru n do A: life(A), A)$
gen(L, 4); matrix([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])</lang>
OCaml
<lang ocaml>let get g x y =
try g.(x).(y) with _ -> 0
let neighbourhood g x y =
(get g (x-1) (y-1)) + (get g (x-1) (y )) + (get g (x-1) (y+1)) + (get g (x ) (y-1)) + (get g (x ) (y+1)) + (get g (x+1) (y-1)) + (get g (x+1) (y )) + (get g (x+1) (y+1))
let next_cell g x y =
let n = neighbourhood g x y in match g.(x).(y), n with | 1, 0 | 1, 1 -> 0 (* lonely *) | 1, 4 | 1, 5 | 1, 6 | 1, 7 | 1, 8 -> 0 (* overcrowded *) | 1, 2 | 1, 3 -> 1 (* lives *) | 0, 3 -> 1 (* get birth *) | _ (* 0, (0|1|2|4|5|6|7|8) *) -> 0 (* barren *)
let copy g = Array.map Array.copy g
let next g =
let width = Array.length g
and height = Array.length g.(0)
and new_g = copy g in
for x = 0 to pred width do
for y = 0 to pred height do
new_g.(x).(y) <- (next_cell g x y)
done
done;
(new_g)
let print g =
let width = Array.length g
and height = Array.length g.(0) in
for x = 0 to pred width do
for y = 0 to pred height do
if g.(x).(y) = 0
then print_char '.'
else print_char 'o'
done;
print_newline()
done</lang>
put the code above in a file named "life.ml", and then use it in the ocaml toplevel like this:
# #use "life.ml";;
val get : int array array -> int -> int -> int = <fun>
val neighbourhood : int array array -> int -> int -> int = <fun>
val next_cell : int array array -> int -> int -> int = <fun>
val copy : 'a array array -> 'a array array = <fun>
val next : int array array -> int array array = <fun>
val print : int array array -> unit = <fun>
# let g = [|
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 1; 1; 1; 0; 0; 0; |];
[| 0; 0; 0; 1; 1; 1; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
|] ;;
val g : int array array =
[|[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 1; 1; 1; 0; 0; 0|];
[|0; 0; 0; 1; 1; 1; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]|]
# print g;;
..........
..........
..........
..........
....ooo...
...ooo....
..........
..........
..........
..........
- : unit = ()
# print (next g) ;;
..........
..........
..........
.....o....
...o..o...
...o..o...
....o.....
..........
..........
..........
- : unit = ()
A graphical version
This implementation has 6 starting patterns (most get quite large) and a random option, and you can set the grid size. <lang OCaml>let alive = 0 let dead = 0xFFFFFF
let iteration ib ob m n =
let rule = function 3,_ | 2,true -> alive | _ -> dead in
let f x y =
if x >= 0 && x < m && y >= 0 && y < n && ib.(x).(y) = alive
then 1 else 0 in
let count b q =
let a, c, p, r = b-1, b+1, q-1, q+1 in
f a p + f a q + f a r + f b p + f b r + f c p + f c q + f c r in
for i = 0 to m-1 do
for j = 0 to n-1 do
ob.(i).(j) <- rule (count i j, ib.(i).(j) = alive)
done
done
let make_random w h bd =
Random.self_init ();
for i = 0 to w-1 do
for j = 0 to h-1 do
bd.(i).(j) <- if Random.bool () then alive else dead
done
done
let set_cells a b cells w h bd =
let w', h' = w/2 - a, h/2 - b in List.iter (fun (i,j) -> bd.(i+w').(j+h') <- alive) cells
let make_blinker = set_cells 1 1 [(1,0); (1,1); (1,2)]
let make_acorn =
set_cells 1 3 [(0,1); (1,3); (2,0); (2,1); (2,4); (2,5); (2,6)]
let make_growth =
set_cells 2 3 [(0,6); (1,4); (1,6); (1,7); (2,4); (2,6); (3,4); (4,2); (5,0); (5,2)]
let make_rabbits =
set_cells 1 3 [(0,0); (0,4); (0,5); (0,6); (1,0); (1,1); (1,2); (1,5); (2,1)]
let make_engine =
set_cells (-100) (-100) [(0,1); (0,3); (1,0); (2,1); (2,4); (3,3); (3,4); (3,5); (4,26); (4,27); (5,26); (5,27)]
let make_line w h bd =
let w', h', l = w/2, h/2, w/3 in for i = -l to l do bd.(i+w').(h') <- alive done
let () =
let argc = Array.length Sys.argv in
let init =
let default () = (print_endline "Using random start"; make_random) in
if argc < 2 then default () else
match Sys.argv.(1) with
| "acorn" -> make_acorn
| "blinker" -> make_blinker
| "growth" -> make_growth
| "engine" -> make_engine
| "line" -> make_line
| "rabbits" -> make_rabbits
| "random" -> make_random
| "-h" -> Printf.printf
"Usage: %s [acorn|growth|blinker|engine|line|rabbits|random] width height\n" Sys.argv.(0);
exit 0
| _ -> default () in
let width = if argc > 2 then int_of_string Sys.argv.(2) else 300 in
let height = if argc > 3 then int_of_string Sys.argv.(3) else 300 in
let bd1 = Array.make_matrix width height dead in
let bd2 = Array.make_matrix width height dead in
let border = 5 in
let disp m = Graphics.draw_image (Graphics.make_image m) border border in
init width height bd1;
Graphics.open_graph (Printf.sprintf " %dx%d" (height+2*border) (width+2*border));
while true do
disp bd1;
iteration bd1 bd2 width height;
disp bd2;
iteration bd2 bd1 width height
done</lang>
Compile with:
ocamlopt -o life graphics.cmxa life.ml
and run with
./life acorn 250 250
If you run the blinker it will probably blink too fast to see unless you choose a large grid size.
Oz
<lang oz>declare
Rules = [rule(c:1 n:[0 1] new:0) %% Lonely
rule(c:1 n:[4 5 6 7 8] new:0) %% Overcrowded
rule(c:1 n:[2 3] new:1) %% Lives
rule(c:0 n:[3] new:1) %% It takes three to give birth!
rule(c:0 n:[0 1 2 4 5 6 7 8] new:0) %% Barren
]
Blinker = ["..."
"###"
"..."]
Toad = ["...."
".###"
"###."
"...."]
Glider = [".#.........."
"..#........."
"###........."
"............"
"............"
"............"
"............"
"............"
"............"
"............"
"............"]
Init = Blinker MaxGen = 2
%% G(i) -> G(i+1)
fun {Evolve Gi}
fun {Get X#Y}
Row = {CondSelect Gi Y unit}
in
{CondSelect Row X 0} %% cells beyond boundaries are dead (0)
end
fun {GetNeighbors X Y}
{Map [X-1#Y-1 X#Y-1 X+1#Y-1
X-1#Y X+1#Y
X-1#Y+1 X#Y+1 X+1#Y+1]
Get}
end
in
{Record.mapInd Gi
fun {$ Y Row}
{Record.mapInd Row
fun {$ X C}
N = {Sum {GetNeighbors X Y}}
in
for Rule in Rules return:Return do
if C == Rule.c andthen {Member N Rule.n} then
{Return Rule.new}
end
end
end}
end}
end
%% For example: [".#"
%% "#."] -> grid(1:row(1:0 2:1) 2:row(1:1 2:0))
fun {ReadG LinesList}
{List.toTuple grid
{Map LinesList
fun {$ Line}
{List.toTuple row
{Map Line
fun {$ C}
if C == &. then 0
elseif C == &# then 1
end
end}}
end}}
end
%% Inverse to ReadG
fun {ShowG G}
{Map {Record.toList G}
fun {$ Row}
{Map {Record.toList Row}
fun {$ C}
if C == 0 then &.
elseif C == 1 then &#
end
end}
end}
end
%% Helpers
fun {Sum Xs} {FoldL Xs Number.'+' 0} end
fun lazy {Iterate F V} V|{Iterate F {F V}} end
G0 = {ReadG Init}
Gn = {Iterate Evolve G0}
in
for
Gi in Gn
I in 0..MaxGen
do
{System.showInfo "\nGen. "#I}
{ForAll {ShowG Gi} System.showInfo}
end</lang>
PARI/GP
Basic implementation; prints a matrix representing the state of the game directly. Supports large games but this example uses only the required 3 X 3 blinker. <lang parigp>step(M)={
my(N=M,W=matsize(M)[1],L=#M,t); for(l=1,W,for(w=1,L, t=sum(i=l-1,l+1,sum(j=w-1,w+1,if(i<1||j<1||i>W||j>L,0,M[i,j]))); N[l,w]=(t==3||(M[l,w]&&t==4)) )); N
}; M=[0,1,0;0,1,0;0,1,0]; for(i=1,3,print(M);M=step(M))</lang>
Perl
This a perl example the simulates Conway's life starting with a random grid of the given size for the given number of steps. Example:
life.pl numrows numcols numiterations life.pl 5 10 15
would do 15 iterations over 5 rows and 10 columns.
<lang perl>my ($width, $height, $generations) = @ARGV;
my $printed;
sub generate {
(map
{[ (map { rand () < 0.5 } 1 .. $width), 0 ]}
1 .. $height),
[(0) x ($width + 1)];
}
sub nexgen {
my @prev = map {[@$_]} @_;
my @new = map {[ (0) x ($width + 1) ]} 0 .. $height;
foreach my $row ( 0 .. $height - 1 ) {
foreach my $col ( 0 .. $width - 1 ) {
my $val =
$prev[ $row - 1 ][ $col - 1 ] +
$prev[ $row - 1 ][ $col ] +
$prev[ $row - 1 ][ $col + 1 ] +
$prev[ $row ][ $col - 1 ] +
$prev[ $row ][ $col + 1 ] +
$prev[ $row + 1 ][ $col - 1 ] +
$prev[ $row + 1 ][ $col ] +
$prev[ $row + 1 ][ $col + 1 ];
$new[$row][$col] =
( $prev[$row][$col] && $val == 2 || $val == 3 );
}
}
return @new;
}
sub printlife {
my @life = @_;
if ($printed) {
# Move the cursor up to print over prior generation. print "\e[1A" x $height;
}
$printed = 1;
foreach my $row ( 0 .. $height - 1 ) {
foreach my $col ( 0 .. $width - 1 ) {
print($life[$row][$col]
? "\e[33;45;1m \e[0m"
: "\e[1;34;1m \e[0m");
}
print "\n";
}
}
my @life = generate; print "Start\n"; printlife @life; foreach my $stage ( 1 .. $generations ) {
sleep 1; print "Generation $stage\n\e[1A"; @life = nexgen @life; printlife @life;
} print "\n";</lang>
Another version, takes up the whole area of your terminal. Using warping edges.<lang Perl>my $w = `tput cols` - 1; my $h = `tput lines` - 1; my $r = "\033[H";
my @universe = map([ map(rand(1) < .1, 1 .. $w) ], 1 .. $h); sub iterate { my @new = map([ map(0, 1 .. $w) ], 1 .. $h); for my $i (0 .. $h - 1) { for my $j (0 .. $w - 1) { my $neighbor = 0; for ( [-1, -1], [-1, 0], [-1, 1], [ 0, -1], [ 0, 1], [ 1, -1], [ 1, 0], [ 1, 1] ) { my $y = $_->[0] + $i; my $x = $_->[1] + $j; $neighbor += $universe[$y % $h][$x % $w]; last if $neighbor > 3; }
$new[$i][$j] = $universe[$i][$j] ? ($neighbor == 2 or $neighbor == 3) : $neighbor == 3; }} @universe = @new; }
while(1) { print $r; print map((map($_ ? "#" : " ", @$_), "\n"), @universe); iterate; }</lang>
Perl 6
<lang perl6>class Grid {
has Int $.width; has Int $.height; has @!a;
multi method new (@a) {
# Makes a new grid with @!a equal to @a.
Grid.bless(*,
width => @a[0].elems, height => @a.elems,
a => @a)
}
multi method new (Str $s) {
# Interprets the string as a grid.
Grid.new(map
{ [map { $^c eq '#' ?? True !! False }, split , $^l] },
grep /\N/, split "\n", $s)
}
method clone { Grid.new(map { [$^x.clone] }, @!a) }
method Str {
[~] map
{ [~] map({ $^c ?? '#' !! '.' }, |$^row), "\n" },
@!a
}
method alive (Int $row, Int $col --> Bool) {
0 <= $row < $.height and 0 <= $col < $.width
and @!a[$row][$col];
}
method nextgen {
my $prev = self.clone;
for ^$.height -> $row {
for ^$.width -> $col {
my $v = [+]
map({ $prev.alive($^r, $^c) },
($col - 1, $col, $col + 1 X
$row - 1, $row, $row + 1)),
-$prev.alive($row, $col);
@!a[$row][$col] =
$prev.alive($row, $col) && $v == 2 || $v == 3;
}
}
}
}</lang>
An example of use:
<lang perl6>my Grid $glider .= new ' ............ ............ ............ .......###.. .......#.... ........#... ............';
loop {
say $glider; sleep 1; $glider.nextgen;
}</lang>
PicoLisp
This example uses 'grid' and 'disp' from "lib/simul.l". These functions maintain an array of multiply linked objects, and are also used in the chess program and other games in the distribution. <lang PicoLisp>(load "@lib/simul.l")
(de life (DX DY . Init)
(let Grid (grid DX DY)
(for This Init
(=: life T) )
(loop
(disp Grid NIL
'((This) (if (: life) "X " " ")) )
(wait 1000)
(for Col Grid
(for This Col
(let N # Count neighbors
(cnt
'((Dir) (get (Dir This) 'life))
(quote
west east south north
((X) (south (west X)))
((X) (north (west X)))
((X) (south (east X)))
((X) (north (east X))) ) )
(=: next # Next generation
(if (: life)
(>= 3 N 2)
(= N 3) ) ) ) ) )
(for Col Grid # Update
(for This Col
(=: life (: next)) ) ) ) ) )
(life 5 5 b3 c3 d3)</lang> Output:
5 4 3 X X X 2 1 a b c d e 5 4 X 3 X 2 X 1 a b c d e 5 4 3 X X X 2 1 a b c d e
PostScript
<lang PostScript>%!PS-Adobe-3.0 %%BoundingBox: 0 0 400 400
/size 400 def
realtime srand /rand1 { rand 2147483647 div } def
/m { moveto } bind def /l { rlineto} bind def /drawboard {
0 1 n 1 sub { /y exch def
0 1 n 1 sub { /x exch def
board x get y get 1 eq {
x c mul y c mul m
c 0 l 0 c l c neg 0 l
closepath fill
} if
} for } for
} def
/r1n { dup 0 lt { n add } if dup n ge { n sub } if } def /neighbors { /y exch def /x exch def 0
y 1 sub 1 y 1 add { r1n /y1 exch def
x 1 sub 1 x 1 add { r1n /x1 exch def
board x1 get y1 get add
} for } for
board x get y get sub
} def
/iter {
/board
[0 1 n 1 sub { /x exch def
[0 1 n 1 sub { /y exch def
x y neighbors
board x get y get
0 eq { 3 eq {1}{0} ifelse }
{ dup 2 eq exch 3 eq or {1}{0} ifelse } ifelse
} for ]
} for ] def
} def
/n 200 def /initprob .15 def /c size n div def /board [ n {[ n { rand1 initprob le {1}{0} ifelse } repeat]} repeat ] def
1000 { drawboard showpage iter } repeat %%EOF</lang>
Prolog
<lang Prolog> %----------------------------------------------------------------------% % GAME OF LIFE % % % % Adapt the prediacte grid_size according to the grid size of the % % start pic. % % Modify the number of generations. % % Run PROLOG and type '[gol].' to compile the source file. % % Create a subfolder <subfolder> where your gol.pl resides and place % % your initial PBM '<filename>0.0000.pbm' inside <subfolder>. % % You need to adjust the number of zeros after <filename>. The % % sequence of zeros after '0.' must be as long as the number of % % generations. This is important to obtain a propper animation. % % (Maybe someone knows a better solution for this) % % Start PROLOG and run % % % % cellular('./<subloder>/<filename>'). % % % % Inside <subfolder> run the following shell command % % % % convert -delay 25 -loop 0 <filename>* <filename>.gif % % % %----------------------------------------------------------------------%
%----------------------------------------------------------------------% % Special thanks to René Thiemann improving the runtime performance. % %----------------------------------------------------------------------%
% Size of the 2D grid grid_size(300). % Number of generations generations(1000).
%----------------------------------------------------------------------% % Main procedure: generate n generations of life and store each file. % % cellular( +File path ) % %----------------------------------------------------------------------% cellular(I) :- grid_size(GS), string_concat(I,'0.0000.pbm',I1), read_pbm(I1,GS,M), cellular_(I,M,GS,1), !.
cellular_(I,M,GS,N) :- N1 is N+1, format(atom(N0),'~4d',N), string_concat(I,N0,I1), string_concat(I1,'.pbm',I2), step(M,M1), write_pbm(M1,GS,I2), !, cellular_(I,M1,GS,N1). cellular_(_,_,_,GE) :- generations(GE),!.
%----------------------------------------------------------------------% % Apply the Game Of Life rule set to every cell. % % step( +OldMatrix, +NewMatrix ) % % % % ss | s | ... | s ss ... step_ss % % ----+---+-----+--- s ... step_s % % ii | i | ... | i ii ... step_ii % % ----+---+-----+--- i ... step_i % % : | : | : | : ee ... step_ee % % ----+---+-----+--- e ... step_e % % ii | i | ... | i % % ----+---+-----+--- % % ee | e | ... | e % % % %----------------------------------------------------------------------% step([R1,R2|M],[H|T]) :- step_ss(R1,R2,H), !, step_([R1,R2|M],T).
step_([R1,R2,R3|M],[H|T]) :- step_ii(R1,R2,R3,H), step_([R2,R3|M],T), !. step_([R1,R2],[H]) :- step_ee(R1,R2,H).
% Start case step_ss([A1,A2|R1],[B1,B2|R2],[H|T]) :- rule([0,0,0],[0,A1,A2],[0,B1,B2],H), step_s([A1,A2|R1],[B1,B2|R2],T). step_s([A1,A2,A3|R1],[B1,B2,B3|R2],[H|T]) :- rule([0,0,0],[A1,A2,A3],[B1,B2,B3],H), step_s([A2,A3|R1],[B2,B3|R2],T). step_s([A1,A2],[B1,B2],[H]) :- rule([0,0,0],[A1,A2,0],[B1,B2,0],H).
% Immediate case step_ii([A1,A2|R1],[B1,B2|R2],[C1,C2|R3],[H|T]) :- rule([0,A1,A2],[0,B1,B2],[0,C1,C2],H), step_i([A1,A2|R1],[B1,B2|R2],[C1,C2|R3],T). step_i([A1,A2,A3|R1],[B1,B2,B3|R2],[C1,C2,C3|R3],[H|T]) :- rule([A1,A2,A3],[B1,B2,B3],[C1,C2,C3],H), step_i([A2,A3|R1],[B2,B3|R2],[C2,C3|R3],T). step_i([A1,A2],[B1,B2],[C1,C2],[H]) :- rule([A1,A2,0],[B1,B2,0],[C1,C2,0],H).
% End case step_ee([A1,A2|R1],[B1,B2|R2],[H|T]) :- rule([0,A1,A2],[0,B1,B2],[0,0,0],H), step_e([A1,A2|R1],[B1,B2|R2],T). step_e([A1,A2,A3|R1],[B1,B2,B3|R2],[H|T]) :- rule([A1,A2,A3],[B1,B2,B3],[0,0,0],H), step_e([A2,A3|R1],[B2,B3|R2],T). step_e([A1,A2],[B1,B2],[H]) :- rule([A1,A2,0],[B1,B2,0],[0,0,0],H).
%----------------------------------------------------------------------% % o Any dead cell with exactly three live neighbours becomes a live % % cell, as if by reproduction. % % o Any other dead cell remains dead. % % o Any live cell with fewer than two live neighbours dies, as if % % caused by under-population. % % o Any live cell with two or three live neighbours lives on to the % % next generation. % % o Any live cell with more than three live neighbours dies, as if by % % overcrowding. % % % % [Source: Wikipedia] % %----------------------------------------------------------------------% rule([A,B,C],[D,0,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 3. rule([_,_,_],[_,0,_],[_,_,_],0). rule([A,B,C],[D,1,F],[G,H,I],0) :- A+B+C+D+F+G+H+I < 2. rule([A,B,C],[D,1,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 2. rule([A,B,C],[D,1,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 3. rule([A,B,C],[D,1,F],[G,H,I],0) :- A+B+C+D+F+G+H+I > 3.
%----------------------------------------------------------------------% % Read a 2bit Protable Bitmap into a GS x GS 2-dimensional list. % % read_pbm( +File path, +Grid size, -List 2D ) % %----------------------------------------------------------------------% read_pbm(F,GS,M) :- open(F,read,S), skip(S,10), skip(S,10), get(S,C), read_file(S,C,L), nest(L,GS,M), close(S).
read_file(S,C,[CHR|T]) :- CHR is C-48, get(S,NC), read_file(S,NC,T). read_file(_,-1,[]) :- !.
%----------------------------------------------------------------------% % Morph simple list into a 2-dimensional one with size GS x GS % % nest( ?List simple, ?Grid size, ?2D list ) % %----------------------------------------------------------------------% nest(L,GS,[H|T]) :- length(H,GS), append(H,S,L), nest(S,GS,T). nest(L,GS,[L]) :- length(L,S), S =< GS, !.
%----------------------------------------------------------------------% % Write a GS x GS 2-dimensional list into a 2bit Protable Bitmap. % % write_pbm( +List 2D, +Grid size, +File path ) % %----------------------------------------------------------------------% write_pbm(L,GS,F) :- open(F,write,S), write(S,'P1'), nl(S), write(S,GS), put(S,' '), write(S,GS), nl(S), write_file(S,L), close(S).
write_file(S,[H|T]) :- write_line(S,H), nl(S), write_file(S,T). write_file(_,[]) :- !.
write_line(S,[H|T]) :- write(S,H), put(S,' '), write_line(S,T). write_line(_,[]) :- !. </lang>
Sample output:
PureBasic
<lang PureBasic>EnableExplicit Define.i x, y ,Xmax ,Ymax ,N Xmax = 13 : Ymax = 20 Dim world.i(Xmax+1,Ymax+1) Dim Nextworld.i(Xmax+1,Ymax+1)
- Glider test
- ------------------------------------------
world(1,1)=1 : world(1,2)=0 : world(1,3)=0 world(2,1)=0 : world(2,2)=1 : world(2,3)=1 world(3,1)=1 : world(3,2)=1 : world(3,3)=0
- ------------------------------------------
OpenConsole() EnableGraphicalConsole(1) ClearConsole() Print("Press any key to interrupt") Repeat
ConsoleLocate(0,2)
PrintN(LSet("", Xmax+2, "-"))
;---------- endless world ---------
For y = 1 To Ymax
world(0,y)=world(Xmax,y)
world(Xmax+1,y)=world(1,y)
Next
For x = 1 To Xmax
world(x,0)=world(x,Ymax)
world(x,Ymax+1)=world(x,1)
Next
world(0 ,0 )=world(Xmax,Ymax)
world(Xmax+1,Ymax+1)=world(1 ,1 )
world(Xmax+1,0 )=world(1 ,Ymax)
world( 0,Ymax+1)=world(Xmax,1 )
;---------- endless world ---------
For y = 1 To Ymax
Print("|")
For x = 1 To Xmax
Print(Chr(32+world(x,y)*3))
N = world(x-1,y-1)+world(x-1,y)+world(x-1,y+1)+world(x,y-1)
N + world(x,y+1)+world(x+1,y-1)+world(x+1,y)+world(x+1,y+1)
If (world(x,y) And (N = 2 Or N = 3))Or (world(x,y)=0 And N = 3)
Nextworld(x,y)=1
Else
Nextworld(x,y)=0
EndIf
Next
PrintN("|")
Next
PrintN(LSet("", Xmax+2, "-"))
Delay(100)
;Swap world() , Nextworld() ;PB <4.50
CopyArray(Nextworld(), world());PB =>4.50
Dim Nextworld.i(Xmax+1,Ymax+1)
Until Inkey() <> ""
PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""</lang>
Sample output:
Python
This implementation uses defaultdict(int) to create dictionaries that return the result of calling int(), i.e. zero for any key not in the dictionary. This 'trick allows celltable to be initialized to just those keys with a value of 1.
Python allows many types other than strings and ints to be keys in a dictionary. The example uses a dictionary with keys that are a two entry tuple to represent the universe, which also returns a default value of zero. This simplifies the calculation N as out-of-bounds indexing of universe returns zero.
<lang python>import random from collections import defaultdict
printdead, printlive = '-#' maxgenerations = 3 cellcount = 3,3 celltable = defaultdict(int, {
(1, 2): 1, (1, 3): 1, (0, 3): 1, } ) # Only need to populate with the keys leading to life
- Start States
- blinker
u = universe = defaultdict(int) u[(1,0)], u[(1,1)], u[(1,2)] = 1,1,1
- toad
- u = universe = defaultdict(int)
- u[(5,5)], u[(5,6)], u[(5,7)] = 1,1,1
- u[(6,6)], u[(6,7)], u[(6,8)] = 1,1,1
- glider
- u = universe = defaultdict(int)
- maxgenerations = 16
- u[(5,5)], u[(5,6)], u[(5,7)] = 1,1,1
- u[(6,5)] = 1
- u[(7,6)] = 1
- random start
- universe = defaultdict(int,
- # array of random start values
- ( ((row, col), random.choice((0,1)))
- for col in range(cellcount[0])
- for row in range(cellcount[1])
- ) ) # returns 0 for out of bounds
for i in range(maxgenerations):
print "\nGeneration %3i:" % ( i, )
for row in range(cellcount[1]):
print " ", .join(str(universe[(row,col)])
for col in range(cellcount[0])).replace(
'0', printdead).replace('1', printlive)
nextgeneration = defaultdict(int)
for row in range(cellcount[1]):
for col in range(cellcount[0]):
nextgeneration[(row,col)] = celltable[
( universe[(row,col)],
-universe[(row,col)] + sum(universe[(r,c)]
for r in range(row-1,row+2)
for c in range(col-1, col+2) )
) ]
universe = nextgeneration</lang>
Sample output:
Generation 0: --- ### --- Generation 1: -#- -#- -#- Generation 2: --- ### ---
R
<lang r># Generates a new board - either a random one, sample blinker or gliders, or user specified. gen.board <- function(type="random", nrow=3, ncol=3, seeds=NULL) {
if(type=="random")
{
return(matrix(runif(nrow*ncol) > 0.5, nrow=nrow, ncol=ncol))
} else if(type=="blinker")
{
seeds <- list(c(2,1),c(2,2),c(2,3))
} else if(type=="glider")
{
seeds <- list(c(1,2),c(2,3),c(3,1), c(3,2), c(3,3))
}
board <- matrix(FALSE, nrow=nrow, ncol=ncol)
for(k in seq_along(seeds))
{
board[seedsk[1],seedsk[2]] <- TRUE
}
board
}
- Returns the number of living neighbours to a location
count.neighbours <- function(x,i,j) {
sum(x[max(1,i-1):min(nrow(x),i+1),max(1,j-1):min(ncol(x),j+1)]) - x[i,j]
}
- Implements the rulebase
determine.new.state <- function(board, i, j) {
N <- count.neighbours(board,i,j) (N == 3 || (N ==2 && board[i,j]))
}
- Generates the next interation of the board from the existing one
evolve <- function(board) {
newboard <- board
for(i in seq_len(nrow(board)))
{
for(j in seq_len(ncol(board)))
{
newboard[i,j] <- determine.new.state(board,i,j)
}
}
newboard
}
- Plays the game. By default, the board is shown in a plot window, though output to the console if possible.
game.of.life <- function(board, nsteps=50, timebetweensteps=0.25, graphicaloutput=TRUE) {
if(!require(lattice)) stop("lattice package could not be loaded")
nr <- nrow(board)
for(i in seq_len(nsteps))
{
if(graphicaloutput)
{
print(levelplot(t(board[nr:1,]), colorkey=FALSE))
} else print(board)
Sys.sleep(timebetweensteps)
newboard <- evolve(board)
if(all(newboard==board))
{
message("board is static")
break
} else if(sum(newboard) < 1)
{
message("everything is dead")
break
} else board <- newboard
}
invisible(board)
}
- Example usage
game.of.life(gen.board("blinker")) game.of.life(gen.board("glider", 18, 20)) game.of.life(gen.board(, 50, 50))</lang>
Retro
<lang Retro> create world
20 20 * allot
create next
20 20 * allot
create initial ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ) ( 0 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 1 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , ( 2 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , ( 3 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , ( 4 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 5 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 6 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 7 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 8 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 9 ) 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 10 ) 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 11 ) 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 12 ) 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 13 ) 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 14 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , ( 15 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , ( 16 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , ( 17 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , ( 18 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , ( 19 ) 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
( Assumes anything outside the bounds is "dead" ) {{
variable surrounding : get ( rc- ) 2over [ 0 19 within ] bi@ and [ world + [ 20 * ] dip + @ ] [ 2drop 0 ] if ; : neighbor? ( rc- ) get +surrounding ; : NW ( rc-rc ) 2over [ 1- ] bi@ neighbor? ; : NN ( rc-rc ) 2over [ 1- ] dip neighbor? ; : NE ( rc-rc ) 2over [ 1- ] dip 1+ neighbor? ; : WW ( rc-rc ) 2over 1- neighbor? ; : EE ( rc-rc ) 2over 1+ neighbor? ; : SW ( rc-rc ) 2over [ 1+ ] dip 1- neighbor? ; : SS ( rc-rc ) 2over [ 1+ ] dip neighbor? ; : SE ( rc-rc ) 2over [ 1+ ] bi@ neighbor? ; : count ( rc-rcn ) 0 !surrounding NW NN NE WW EE SW SS SE @surrounding ; : alive ( rc-n ) count [ 0 1 within ] [ drop 0 ] when [ 4 8 within ] [ drop 0 ] when [ 2 3 within ] [ drop 1 ] when ; : dead ( rc-n ) count [ 3 = ] [ drop 1 ] when [ 0 2 within ] [ drop 0 ] when [ 4 8 within ] [ drop 0 ] when ; : newState ( rc-n ) 2over get 1 = [ alive ] [ dead ] if ; : set ( nrc- ) next + [ 20 * ] dip + ! ; : cols ( r- ) 20 [ over swap newState 2rot set ] iter drop ; : output ( n- ) [ 'o ] [ '. ] if putc space ;
---reveal---
: display ( - ) cr world 20 [ 20 [ @+ output ] times cr ] times drop ; : start ( - ) initial world 20 20 * copy display ; : gen ( - ) 20 [ cols ] iter next world 20 20 * copy ; : delay ( - ) time 1+ [ time over <= ] while drop ; : run ( n- ) [ delay clear gen display ] times ;
}}
start 20 run</lang>
REXX
This version has been elided, otherwise the size of the program (with all it's options and optional formatting) would probably be on the big side for general viewing, and maybe a wee bit complex to demonstrate how to program for this task. <lang rexx>/*REXX program displays Conway's game of life.
┌───────────────────────────elided version─────────────────────────┐ ├─── full version has many more options and enhanced displays. ────┤ └──────────────────────────────────────────────────────────────────┘ */
signal on syntax; signal on novalue /*handle REXX program errors. */ signal on halt /*handle cell growth interruptus.*/ parse arg peeps '(' generations rows cols bare! life! clearscreen every repeats @abc='abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU
blank = 'BLANK'
generations = p(generations 100)
rows = p(rows 3)
cols = p(cols 3)
bare! = pickchar(bare! blank)
clearscreen = p(clearscreen 0)
every = p(every 999999999)
life! = pickchar(life! '☼')
repeats = p(repeats 2)
fents=max(79,cols) /*fence width shown after display*/
- repeats=0; $.=bare! /*the universe is new, and barren*/
gens=abs(generations) /*use this for convenience. */ x=space(peeps) /*remove superfluous spaces. */ if x== then x='2,1 2,2 2,3'
do while x \==
parse var x p x; parse var p r ',' c .; $.r=overlay(life!,$.r,c+1)
end
life=0; !.=0; call showCells /*show initial state of the cells*/ /*─────────────────────────────────────watch cell colony grow/live/die. */
do life=1 for gens
do r=1 for rows; rank=bare!
do c=2 for cols; ?=substr($.r,c,1); ??=?; n=neighbors()
select /*select da quickest choice first*/
when ?==bare! then if n==3 then ??=life!
otherwise if n<2 | n>3 then ??=bare!
end /*select*/
rank=rank || ??
end /*c*/
@.r=rank
end /*c*/
do r=1 for rows; $.r=@.r; end /*assign alternate cells ──► real*/ if life//every==0 | generations>0 | life==gens then call showCells end /*life*/
/*─────────────────────────────────────stop watching the universe (life)*/ halt: cycles=life-1; if cycles\==gens then say 'REXX program interrupted.' exit /*stick a fork in it, we're done.*/ /*───────────────────────────────SHOWCELLS subroutine─-─────────────────*/ showCells: if clearscreen then 'CLS' /* ◄─── change this for your OS.*/ _=; do r=rows by -1 for rows /*show the forest in proper order*/
z=strip(substr($.r,2),'T') /*pick off the meat of the row. */
say z; _=_ || z /*be neat about trailing blanks. */
end /*r*/
say right(copies('═',fents)life,fents) /*show&tell for a stand of trees.*/ if _== then exit /*if no life, then stop the run. */ if !._ then #repeats=#repeats+1 /*we detected a repeated pattern.*/ !._=1 /*assign a state & compare later.*/ if repeats\==0 & #repeats<=repeats then return /*so far, so good. */ say '"Life" repeated itself' repeats "times, program is stopping." exit /*stick a fork in it, we're done.*/ /*───────────────────────────────NEIGHBORS subroutine───────────────────*/ neighbors: rp=r+1; cp=c+1; rm=r-1; cm=c-1 /*count 8 neighbors of a cell*/ return (substr($.rm,cm,1)==life!) + (substr($.rm,c ,1)==life!) + ,
(substr($.rm,cp,1)==life!) + (substr($.r ,cm,1)==life!) + ,
(substr($.r ,cp,1)==life!) + (substr($.rp,cm,1)==life!) + ,
(substr($.rp,c ,1)==life!) + (substr($.rp,cp,1)==life!)
/*───────────────────────────────1-liner subroutines────────────────────*/ err: say;say;say center(' error! ',max(40,linesize()%2),"*");say;do j=1 for arg();say arg(j);say;end;say;exit 13 novalue: syntax: call err 'REXX program' condition('C') "error",condition('D'),'REXX source statement (line' sigl"):",sourceline(sigl) pickchar: _=p(arg(1));if translate(_)==blank then _=' ';if length(_) ==3 then _=d2c(_);if length(_) ==2 then _=x2c(_);return _ p: return word(arg(1),1)</lang> output when using the default input
☼☼☼ ══════════════════════════════════════════════════════════════════════════════0 ☼ ☼ ☼ ══════════════════════════════════════════════════════════════════════════════1 ☼☼☼ ══════════════════════════════════════════════════════════════════════════════2 ☼ ☼ ☼ ══════════════════════════════════════════════════════════════════════════════3 ☼☼☼ ══════════════════════════════════════════════════════════════════════════════4 "Life" repeated itself 2 times, program is stopping.
Ruby
<lang ruby>def game_of_life(name, size, generations, initial_life=nil)
board = new_board size seed board, size, initial_life print_board board, 0, name reason = generations.times do |gen| new = evolve board, size print_board new, gen+1, name break :all_dead if barren? new, size break :static if board == new board = new end if reason == :all_dead then puts "no more life." elsif reason == :static then puts "no movement" else puts "specified lifetime ended" end
end
def new_board(n)
Array.new(n) {Array.new(n, 0)}
end
def seed(board, n, points=nil)
if points.nil?
# randomly seed board
srand
indices = []
n.times {|x| n.times {|y| indices << [x,y] }}
indices.shuffle[0,10].each {|x,y| board[y][x] = 1}
else
points.each {|x, y| board[y][x] = 1}
end
end
def evolve(board, n)
new = new_board n
n.times {|i| n.times {|j| new[i][j] = fate board, i, j, n}}
new
end
def fate(board, i, j, n)
i1 = [0, i-1].max; i2 = [i+1, n-1].min
j1 = [0, j-1].max; j2 = [j+1, n-1].min
sum = 0
for ii in (i1..i2)
for jj in (j1..j2)
sum += board[ii][jj] if not (ii == i and jj == j)
end
end
(sum == 3 or (sum == 2 and board[i][j] == 1)) ? 1 : 0
end
def barren?(board, n)
n.times {|i| n.times {|j| return false if board[i][j] == 1}}
true
end
def print_board(m, generation, name)
puts "#{name}: generation #{generation}"
m.each {|row| row.each {|val| print "#{val == 1 ? '#' : '.'} "}; puts}
puts
end
game_of_life "blinker", 3, 2, [[1,0],[1,1],[1,2]]
- game_of_life "glider", 4, 4, [[1,0],[2,1],[0,2],[1,2],[2,2]]
- game_of_life "random", 5, 10</lang>
The above implementation uses only methods. Below is one that is object-oriented and feels perhaps a bit more Ruby-ish.
<lang ruby>class Game
def initialize(name, size, generations, initial_life=nil)
@board = GameBoard.new size, initial_life
@board.display 0, name
reason = generations.times do |gen|
new_board = evolve
new_board.display gen+1, name
break :all_dead if new_board.barren?
break :static if @board == new_board
@board = new_board
end
if reason == :all_dead then puts "No more life."
elsif reason == :static then puts "No movement."
else puts "Specified lifetime ended."
end
end
def evolve
new_board = GameBoard.new @board.size, @board.life
@board.size.times do |i|
@board.size.times do |j|
if cell_fate i, j
new_board[i,j].live
else
new_board[i,j].die
end
end
end
new_board
end
def cell_fate(i, j)
left = [0, i-1].max; right = [i+1, @board.size-1].min
top = [0, j-1].max; bottom = [j+1, @board.size-1].min
sum = 0
for x in (left..right)
for y in (top..bottom)
sum += @board[x,y].value if (x != i or y != j)
end
end
(sum == 3 or (sum == 2 and @board[i,j].alive?))
end
end
class GameBoard
attr_reader :size
def initialize(size, initial_life=nil)
@size = size
@board = Array.new(size) {Array.new(size) {Cell.new false}}
self.seed_board initial_life
end
def seed_board(life)
if life.nil?
# randomly seed board
srand # seed the random number generator
indices = []
@size.times {|x| @size.times {|y| indices << [x,y] }}
indices.shuffle[0,10].each {|x,y| @board[y][x].live}
else
life.each {|x, y| @board[y][x].live}
end
end
def [](x, y)
@board[y][x]
end
def ==(board)
self.life == board.life
end
def barren?
@size.times do |i|
@size.times do |j|
return false if @board[i][j].alive?
end
end
true
end
def life
indices = []
@size.times do |x|
@size.times do |y|
if @board[y][x].alive?
indices << [x,y]
end
end
end
indices
end
def display(generation, name)
puts "#{name}: generation #{generation}"
@board.each do |row|
row.each do |cell|
print "#{cell.alive? ? '#' : '.'} "
end
puts
end
puts
end
def apocalypse
# utility function to entirely clear the game board
@board.each do |row|
row.each do |cell|
if cell.alive?
cell.die
end
end
end
end
end
class Cell
def initialize is_alive
@is_alive = is_alive
end
def alive?
@is_alive
end
def value
if self.alive?
return 1
else
return 0
end
end
def live
@is_alive = true
end
def die
@is_alive = false
end
end
game_of_life = Game.new "blinker", 3, 2, [[1,0],[1,1],[1,2]] game_of_life = Game.new "glider", 4, 4, [[1,0],[2,1],[0,2],[1,2],[2,2]] game_of_life = Game.new "random", 5, 10</lang>
Scala
See Conway's Game of Life/Scala
Scheme
<lang Scheme>
- An R6RS Scheme implementation of Conway's Game of Life --- assumes
- all cells outside the defined grid are dead
- if n is outside bounds of list, return 0 else value at n
(define (nth n lst)
(cond ((> n (length lst)) 0)
((< n 1) 0)
((= n 1) (car lst))
(else (nth (- n 1) (cdr lst)))))
- return the next state of the supplied universe
(define (next-universe universe)
;value at (x, y)
(define (cell x y)
(if (list? (nth y universe))
(nth x (nth y universe))
0))
;sum of the values of the cells surrounding (x, y)
(define (neighbor-sum x y)
(+ (cell (- x 1) (- y 1))
(cell (- x 1) y)
(cell (- x 1) (+ y 1))
(cell x (- y 1))
(cell x (+ y 1))
(cell (+ x 1) (- y 1))
(cell (+ x 1) y)
(cell (+ x 1) (+ y 1))))
;next state of the cell at (x, y)
(define (next-cell x y)
(let ((cur (cell x y))
(ns (neighbor-sum x y)))
(cond ((and (= cur 1)
(or (< ns 2) (> ns 3)))
0)
((and (= cur 0) (= ns 3))
1)
(else cur))))
;next state of row n
(define (row n out)
(let ((w (length (car universe))))
(if (= (length out) w)
out
(row n
(cons (next-cell (- w (length out)) n)
out)))))
;a range of ints from bot to top
(define (int-range bot top)
(if (> bot top) '()
(cons bot (int-range (+ bot 1) top))))
(map (lambda (n)
(row n '()))
(int-range 1 (length universe))))
- represent the universe as a string
(define (universe->string universe)
(define (prettify row)
(apply string-append
(map (lambda (b)
(if (= b 1) "#" "-"))
row)))
(if (null? universe)
""
(string-append (prettify (car universe))
"\n"
(universe->string (cdr universe)))))
- starting with seed, show reps states of the universe
(define (conway seed reps)
(when (> reps 0) (display (universe->string seed)) (newline) (conway (next-universe seed) (- reps 1))))
- --- Example Universes --- ;;
- blinker in a 3x3 universe
(conway '((0 1 0)
(0 1 0)
(0 1 0)) 5)
- glider in an 8x8 universe
(conway '((0 0 1 0 0 0 0 0)
(0 0 0 1 0 0 0 0)
(0 1 1 1 0 0 0 0)
(0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0)) 30)</lang>
Sample output:
-#- -#- -#- --- ### --- -#- -#- -#- --- ### --- -#- -#- -#- --#----- ---#---- -###---- -------- -------- -------- -------- -------- -------- -#-#---- --##---- --#----- -------- -------- -------- -------- -------- ---#---- -#-#---- --##---- -------- -------- -------- -------- -------- --#----- ---##--- --##---- -------- -------- -------- -------- -------- ---#---- ----#--- --###--- -------- -------- -------- -------- -------- -------- --#-#--- ---##--- ---#---- -------- -------- -------- -------- -------- ----#--- --#-#--- ---##--- -------- -------- -------- -------- -------- ---#---- ----##-- ---##--- -------- -------- -------- -------- -------- ----#--- -----#-- ---###-- -------- -------- -------- -------- -------- -------- ---#-#-- ----##-- ----#--- -------- -------- -------- -------- -------- -----#-- ---#-#-- ----##-- -------- -------- -------- -------- -------- ----#--- -----##- ----##-- -------- -------- -------- -------- -------- -----#-- ------#- ----###- -------- -------- -------- -------- -------- -------- ----#-#- -----##- -----#-- -------- -------- -------- -------- -------- ------#- ----#-#- -----##- -------- -------- -------- -------- -------- -----#-- ------## -----##- -------- -------- -------- -------- -------- ------#- -------# -----### -------- -------- -------- -------- -------- -------- -----#-# ------## ------#- -------- -------- -------- -------- -------- -------# -----#-# ------## -------- -------- -------- -------- -------- ------#- -------# ------## -------- -------- -------- -------- -------- -------- -------# ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------## -------- -------- -------- -------- -------- -------- ------## ------##
SETL
Compiler: GNU SETL
This version uses a live cell set representation (set of coordinate pairs.) This example first appeared here. <lang setl>program life;
const
initialMatrix =
[".....",
"..#..",
"...#.",
".###.",
"....."];
loop init
s := initialLiveSet();
do
output(s);
nm := {[[x+dx, y+dy], [x, y]]: [x, y] in s, dx in {-1..1}, dy in {-1..1}};
s := {c: t = nm{c} | 3 in {#t, #(t less c)}};
end;
proc output(s);
system("clear");
(for y in [0..24])
(for x in [0..78])
nprint(if [x, y] in s then "#" else " " end);
end;
print();
end;
select([], 250);
end proc;
proc initialLiveSet();
return {[x,y]: row = initialMatrix(y), c = row(x) | c = '#'};
end proc;
end program;</lang>
SystemVerilog
Note using non-blocking assignments, so that the code behaves as if every cell is updated in parallel on each clock edge. (I didn't need to use a clock here, but doing so looks more like standard verilog coding that is familiar to hardware designers). <lang SystemVerilog>module gol;
parameter NUM_ROWS = 20; parameter NUM_COLS = 32;
bit [NUM_COLS:1] cell[1:NUM_ROWS]; bit clk;
initial begin cell[10][10:8] = 3'b111; cell[11][10:8] = 3'b100; cell[12][10:8] = 3'b010; repeat(8) #5 clk = ~clk; end
always @(posedge clk) begin
foreach (cell[y,x]) begin
automatic int count = $countones({ cell[y-1][x-1+:3], cell[y][x-1], cell[y][x+1], cell[y+1][x-1+:3] });
if (count == 3) cell[y][x] <= 1'b1;
else if (count != 2) cell[y][x] <= 1'b0;
end
end
always @(negedge clk) begin
$display("--");
foreach (cell[y]) $display( " %b", cell[y] );
end
endmodule</lang>
Tcl
<lang tcl>package require Tcl 8.5
proc main {} {
evolve 3 blinker [initialize_tableau {3 3} {{0 1} {1 1} {2 1}}]
evolve 5 glider [initialize_tableau {4 4} {{0 1} {1 2} {2 0} {2 1} {2 2}}]
}
proc evolve {generations name tableau} {
for {set gen 1} {$gen <= $generations} {incr gen} {
puts "$name generation $gen:"
print $tableau
set tableau [next_generation $tableau]
}
puts ""
}
proc initialize_tableau {size initial_life} {
lassign $size ::max_x ::max_y
set tableau [blank_tableau]
foreach point $initial_life {
lset tableau {*}$point 1
}
return $tableau
}
proc blank_tableau {} {
return [lrepeat $::max_x [lrepeat $::max_y 0]]
}
proc print {tableau} {
foreach row $tableau {puts [string map {0 . 1 #} [join $row]]}
}
proc next_generation {tableau} {
set new [blank_tableau]
for {set x 0} {$x < $::max_x} {incr x} {
for {set y 0} {$y < $::max_y} {incr y} {
lset new $x $y [fate [list $x $y] $tableau]
}
}
return $new
}
proc fate {point tableau} {
set current [value $point $tableau]
set neighbours [sum_neighbours $point $tableau]
return [expr {($neighbours == 3) || ($neighbours == 2 && $current == 1)}]
}
proc value {point tableau} {
return [lindex $tableau {*}$point]
}
proc sum_neighbours {point tableau} {
set sum 0
foreach neighbour [get_neighbours $point] {
incr sum [value $neighbour $tableau]
}
return $sum
}
proc get_neighbours {point} {
lassign $point x y
set results [list]
foreach x_off {-1 0 1} {
foreach y_off {-1 0 1} {
if { ! ($x_off == 0 && $y_off == 0)} {
set i [expr {$x + $x_off}]
set j [expr {$y + $y_off}]
if {(0 <= $i && $i < $::max_x) && (0 <= $j && $j < $::max_y)} {
lappend results [list $i $j]
}
}
}
}
return $results
}
main</lang>
blinker generation 1: . # . . # . . # . blinker generation 2: . . . # # # . . . blinker generation 3: . # . . # . . # . glider generation 1: . # . . . . # . # # # . . . . . glider generation 2: . . . . # . # . . # # . . # . . glider generation 3: . . . . . . # . # . # . . # # . glider generation 4: . . . . . # . . . . # # . # # . glider generation 5: . . . . . . # . . . . # . # # #
TI-83 BASIC
This implementation is loosely based on the Processing Version. It uses the home screen and draws cells as "X"s. It is extremely slow, and limited to a bounding box of 16 by 8. In order for it to work, you need to initialize arrays [A] and [B] to be 18x10. <lang ti83b> PROGRAM:CONWAY
- While 1
- For(X,2,9,1)
- For(Y,2,17,1)
- If [A](Y,X)
- Then
- Output(X-1,Y-1,"X")
- Else
- Output(X-1,Y-1," ")
- End
- [A](Y-1,X-1)+[A](Y,X-1)+[A](Y+1,X-1)+[A](Y-1,X)+[A](Y+1,X)+[A](Y-1,X+1)+[A](Y,X+1)+[A](Y+1,X+1)→N
- If ([A](Y,X) and (N=2 or N=3)) or (not([A](Y,X)) and N=3)
- Then
- 1→[B](Y,X)
- Else
- 0→[B](Y,X)
- End
- End
- End
- [B]→[A]
- End
</lang> Here is an additional, very simple program to input the top corner of the GRAPH screen into the starting array. Make sure to draw on pixels in the rectangle (1,1) to (8,16). <lang ti83b>PROGRAM:PIC2LIFE
- For(I,0,17,1)
- For(J,0,9,1)
- pxl-Test(J,I)→[A](I+1,J+1)
- End
- End
</lang>
TI-89 BASIC
This program draws its cells as 2x2 blocks on the graph screen. In order to avoid needing external storage for the previous generation, it uses the upper-left corner of each block to mark the next generation's state in all cells, then updates each cell to match its corner pixel.
A further improvement would be to have an option to start with the existing picture rather than clearing, and stop at a point where the picture has clean 2x2 blocks.
<lang ti89b>Define life(pattern) = Prgm
Local x,y,nt,count,save,xl,yl,xh,yh
Define nt(y,x) = when(pxlTest(y,x), 1, 0)
{}→save
setGraph("Axes", "Off")→save[1]
setGraph("Grid", "Off")→save[2]
setGraph("Labels", "Off")→save[3]
FnOff
PlotOff
ClrDraw
If pattern = "blinker" Then 36→yl 40→yh 78→xl 82→xh PxlOn 36,80 PxlOn 38,80 PxlOn 40,80 ElseIf pattern = "glider" Then 30→yl 40→yh 76→xl 88→xh PxlOn 38,76 PxlOn 36,78 PxlOn 36,80 PxlOn 38,80 PxlOn 40,80 ElseIf pattern = "r" Then 38-5*2→yl 38+5*2→yh 80-5*2→xl 80+5*2→xh PxlOn 38,78 PxlOn 36,82 PxlOn 36,80 PxlOn 38,80 PxlOn 40,80 EndIf
While getKey() = 0
© Expand upper-left corner to whole cell
For y,yl,yh,2
For x,xl,xh,2
If pxlTest(y,x) Then
PxlOn y+1,x
PxlOn y+1,x+1
PxlOn y, x+1
Else
PxlOff y+1,x
PxlOff y+1,x+1
PxlOff y, x+1
EndIf
EndFor
EndFor
© Compute next generation
For y,yl,yh,2
For x,xl,xh,2
nt(y-1,x-1) + nt(y-1,x) + nt(y-1,x+2) + nt(y,x-1) + nt(y+1,x+2) + nt(y+2,x-1) + nt(y+2,x+1) + nt(y+2,x+2) → count
If count = 3 Then
PxlOn y,x
ElseIf count ≠ 2 Then
PxlOff y,x
EndIf
EndFor
EndFor
EndWhile
© Restore changed options
setGraph("Axes", save[1])
setGraph("Grid", save[2])
setGraph("Labels", save[3])
EndPrgm</lang>
Ursala
Three functions are defined: rule takes a pair (c,<n..>) representing a cell and its list of neighboring cells to the new cell, neighborhoods takes board of cells <<c..>..> to a structure <<(c,<n..>)..>..> explicitly pairing each cell with its neighborhood, and evolve(n) takes a board <<c..>..> to a sequence of n boards evolving from it.
<lang Ursala>#import std
- import nat
rule = -: ^(~&,~&l?(~&r-={2,3},~&r-={3})^|/~& length@F)* pad0 iota512
neighborhoods = ~&thth3hthhttPCPthPTPTX**K7S+ swin3**+ swin3@hNSPiCihNCT+ --<0>*+ 0-*
evolve "n" = next"n" rule**+ neighborhoods</lang> test program: <lang Ursala>blinker =
(==`O)**t -[ +++ OOO +++]-
glider =
(==`O)**t -[ +O++++ ++O+++ OOO+++ ++++++ ++++++]-
- show+
examples = mat0 ~&?(`O!,`+!)*** evolve3(blinker)-- evolve5(glider)</lang> output:
+++ OOO +++ +O+ +O+ +O+ +++ OOO +++ +O++++ ++O+++ OOO+++ ++++++ ++++++ ++++++ O+O+++ +OO+++ +O++++ ++++++ ++++++ ++O+++ O+O+++ +OO+++ ++++++ ++++++ +O++++ ++OO++ +OO+++ ++++++ ++++++ ++O+++ +++O++ +OOO++ ++++++
Vedit macro language
This implementation uses an edit buffer for data storage and to show results. For purpose of this task, the macro writes the initial pattern in the buffer. However, easier way to enter patterns would be by editing them directly in the edit buffer before starting the macro (in which case the Ins_Text commands would be omitted).
The macro calculates one generation and then waits for a key press before calculating the next generation.
The algorithm used is kind of reverse to the one normally used in Life implementations. Instead of counting cells around each location, this implementation finds each living cell and then increments the values of the 8 surrounding cells. After going through all the living cells, each location of the grid contains an unique ascii value depending on the original value (dead or alive) and the number of living cells in surrounding positions. Two Replace commands are then used to change characters into '.' or 'O' to represent dead and living cells in the new generation.
<lang vedit>IT("Generation 0 ") IN IT(".O.") IN IT(".O.") IN IT(".O.")
- 9 = 2 // number of generations to calculate
- 10 = Cur_Line
- 11 = Cur_Col-1
for (#2 = 1; #2 <= #9; #2++) {
Update()
Get_Key("Next gen...", STATLINE)
Call("calculate")
itoa(#2, 20, LEFT)
GL(1) GC(12) Reg_Ins(20, OVERWRITE)
} EOF Return
// Calculate one generation
- calculate:
Goto_Line(2) While (At_EOF == 0) {
Search("|A",ERRBREAK) // find next living cell
#3 = Cur_Line
#4 = #7 = #8 = Cur_Col
if (#4 > 1) { // increment cell at left
#7 = #4-1
Goto_Col(#7)
Ins_Char(Cur_Char+1,OVERWRITE)
}
if (#4 < #11) { // increment cell at right
#8 = #4+1
Goto_Col(#8)
Ins_Char(Cur_Char+1,OVERWRITE)
}
if (#3 > 2) { // increment 3 cells above
Goto_Line(#3-1)
Call("inc_3")
}
if (#3 < #10) { // increment 3 cells below
Goto_Line(#3+1)
Call("inc_3")
}
Goto_Line(#3)
Goto_Col(#4+1)
}
Replace("[1QR]", "O", REGEXP+BEGIN+ALL) // these cells alive Replace("[/-7P-X]", ".", REGEXP+BEGIN+ALL) // these cells dead Return
// increment values of 3 characters in a row
- inc_3:
for (#1 = #7; #1 <= #8; #1++) {
Goto_Col(#1) Ins_Char(Cur_Char+1,OVERWRITE)
} Return</lang>
Output: <lang vedit>Generation 0 .O. .O. .O.
Generation 1 ... OOO ...
Generation 2 .O. .O. .O.</lang>
XPL0
<lang XPL0>def M=3; \array size char NowGen(M+2, M+2), \size with surrounding borders
NewGen(M+2, M+2);
int X, Y, I, J, N, Gen; code ChOut=8, CrLf=9;
[for Y:= 0 to M+1 do \set up initial state
for X:= 0 to M+1 do
[NowGen(X,Y):= ^ ; NewGen(X,Y):= ^ ];
NowGen(1,2):= ^#; NowGen(2,2):= ^#; NowGen(3,2):= ^#;
for Gen:= 1 to 3 do
[for Y:= 1 to M do \show current generation
[for X:= 1 to M do [ChOut(0, NowGen(X,Y)); ChOut(0,^ )];
CrLf(0);
];
CrLf(0);
for Y:= 1 to M do \determine next generation
for X:= 1 to M do
[N:= 0; \count adjacent live (#) cells
for J:= Y-1 to Y+1 do
for I:= X-1 to X+1 do
if NowGen(I,J) = ^# then N:= N+1;
if NowGen(X,Y) = ^# then N:= N-1; \don't count center
NewGen(X,Y):= ^ ; \assume death
if N=2 then NewGen(X,Y):= NowGen(X,Y) \actually no change
else if N=3 then NewGen(X,Y):= ^#; \actually birth
];
I:= NowGen; NowGen:= NewGen; NewGen:= I; \swap arrays
];
]</lang>
Output:
# # #
#
#
#
# # #
ZPL
<lang ZPL>program Life;
config var
n : integer = 100;
region
BigR = [0 .. n+1, 0 .. n+1];
R = [1 .. n, 1 .. n ];
direction
nw = [-1, -1]; north = [-1, 0]; ne = [-1, 1];
west = [ 0, -1]; east = [ 0, 1];
sw = [ 1, -1]; south = [ 1, 0]; se = [ 1, 1];
var
TW : [BigR] boolean; -- The World
NN : [R] integer; -- Number of Neighbours
procedure Life(); begin
-- Initialize world
[R] repeat
NN := TW@nw + TW@north + TW@ne +
TW@west + TW@east +
TW@sw + TW@south + TW@se;
TW := (TW & NN = 2) | ( NN = 3);
until !(|<< TW);
end;</lang>
- Programming Tasks
- Games
- Cellular automata
- 6502 Assembly
- ACL2
- Ada
- ALGOL 68
- APL
- AutoHotkey
- AWK
- BASIC256
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- Dart
- E
- Erlang
- F Sharp
- Windows Presentation Foundation
- Forth
- Fortran
- Go
- Haskell
- Icon
- Unicon
- J
- JAMES II/Rule-based Cellular Automata
- JAMES II
- Java
- JavaScript
- HTML5
- Liberty BASIC
- Lua
- MATLAB
- Mathematica
- Maxima
- OCaml
- Oz
- PARI/GP
- Perl
- Perl 6
- PicoLisp
- PostScript
- Prolog
- PureBasic
- Python
- R
- Retro
- REXX
- Ruby
- Scala
- Scheme
- SETL
- SystemVerilog
- Tcl
- TI-83 BASIC
- TI-89 BASIC
- Ursala
- Vedit macro language
- XPL0
- ZPL