Conway's Game of Life: Difference between revisions
m (→{{header|F#}}: use libheader template) |
(→{{works with|Scala|2.8}}: template should not be a header) |
||
| Line 1,975: | Line 1,975: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
{{works with|Scala|2.8}} |
|||
A Conway "board" has infinite dimensions -- in fact, Conway's Game of Life is Turing complete -- so |
A Conway "board" has infinite dimensions -- in fact, Conway's Game of Life is Turing complete -- so |
||
the algorithm below avoids using fixed-size structures such as arrays. Instead, each generation is |
the algorithm below avoids using fixed-size structures such as arrays. Instead, each generation is |
||
Revision as of 15:27, 8 January 2010
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.
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
The first Life program was written for the PDP-7 by M. J. T. Guy and S. R. Bourne in 1970. It was written in ALGOL 68. c.f. Scientific American 223 (October 1970): 120-123 <lang algol68>MODE UNIVERSE = [upb OF class universe, upb OF class universe]BOOL;
STRUCT(
INT upb, BOOL lifeless, alive, PROC(REF UNIVERSE)VOID init, PROC(REF UNIVERSE)STRING repr, PROC(REF UNIVERSE, INT, INT)VOID insert glider, PROC(REF UNIVERSE)VOID next
) class universe = (
- upb = # 50,
- lifeless = # FALSE,
- alive = # TRUE,
- PROC init = # (REF UNIVERSE self)VOID:
FOR row index FROM LWB self TO UPB self DO
init row(self[row index, ])
OD,
- PROC repr = # (REF UNIVERSE self)STRING:(
FORMAT cell = $b("[]", " ")$,
horizon = $"+"n(UPB self)("--")"+"l$;
FILE outf; STRING out; associate(outf, out); putf(outf, (horizon, $"|"n(UPB self)(f(cell))"|"l$, self, horizon)); close(outf); out ),
- PROC insert glider = # (REF UNIVERSE self, INT row, col)VOID:(
self[row-2, col+1] := TRUE; self[row-1, col+2] := TRUE; self[row, col:col+2] := (TRUE, TRUE, TRUE ) ),
- PROC next = # (REF UNIVERSE self)VOID:(
[0:2, LWB self-1:UPB self+1]BOOL window; # Create a 3 row window into the previous generation #
# Set the universe horizon to be lifeless cells #
init row(window[LWB window, ]);
window[LWB self, 2 LWB window] :=
window[LWB self, 2 UPB window] :=
window[UPB window, 2 LWB window] :=
window[UPB window, 2 UPB window] := lifeless OF class universe;
# Initialise the first row # window[LWB self, LWB self:UPB self] := self[LWB self, ];
FOR row FROM LWB self TO UPB self DO
REF []BOOL next row = window[(row+1) MOD 3, ];
IF row NE UPB self THEN
next row[LWB self:UPB self] := self[row+1, ]
ELSE
init row(next row)
FI;
FOR col FROM LWB self TO UPB self DO
INT live := 0;
# Scan for life forms in 3x3 block #
FOR row FROM row-1 TO row+1 DO
REF[]BOOL window row = window[row MOD 3, ];
FOR col FROM col-1 TO col+1 DO
IF window row[col] THEN live +:= 1 FI
OD
OD;
self[row, col] :=
IF window[row MOD 3, col] THEN #
1. Any live cell with fewer than two live neighbours dies, as if by loneliness. 2. Any live cell with more than three live neighbours dies, as if by overcrowding. 3. Any live cell with two or three live neighbours lives, unchanged, to the next generation. #
live -:= 1; # don't count life in current cell #
live = 3 OR live = 2
ELSE #
4. Any lifeless cell with exactly three live neighbours comes to life. #
live = 3
FI
OD
OD
)
);
- Shared static procedure #
PROC init row = (REF [] BOOL xrow)VOID:
FOR col FROM LWB xrow TO UPB xrow DO xrow[col] := lifeless OF class universe OD;
PROC insert gosper gun = (REF [, ] BOOL universe)VOID:(
[, ]CHAR template = (
("________________________X___________"),
("______________________X X___________"),
("____________XX______XX____________XX"),
("___________X___X____XX____________XX"),
("XX________X_____X___XX______________"),
("XX________X___X_XX____X_X___________"),
("__________X_____X_______X___________"),
("___________X___X____________________"),
("____________XX______________________")
);
FOR row TO 1 UPB template DO
FOR col TO 2 UPB template DO
universe[row, col] := template[row, col]="X"
OD
OD
);
UNIVERSE conways universe; (init OF class universe)(conways universe);
- Insert a squadron of gliders #
FOR i FROM UPB conways universe OVER 2 BY 5 TO UPB conways universe DO
(insert glider OF class universe)(conways universe, i, ENTIER (UPB conways universe*1.2 - i*0.9))
OD;
- Insert a gosper (repeating) gun #
insert gosper gun(conways universe[5:, :]);
STRING home = REPR 27 +"[H"; TO 564 DO
print((home)); print((repr OF class universe)(conways universe)); (next OF class universe)(conways universe)
OD</lang> Output after 564 iterations:
+----------------------------------------------------------------------------------------------------+ | | | | | | | | | [][] | | [] [] | | [] [][][] [][] [][][] | | [][][][] [][][] [] [][][][] | |[][] [][][][] [][][] [][] | |[][] [] [] [] [] | | [] [][][][] [][] | | [] [][][][] [] | | [] [] | | [][][] | | | | | | | | | | | | [] | | [] [] | | [][] | | | | | | | | [][] | | [] [] [] | | [] [] | | [][][] | | | | | | | | | | | | | | [][] | | [][] | | [] | | [] | | [] | | | | [][][] [][][] | | | | [] | | [] | | [] | | [] | | [] [] | | [] [] | | [][] | +----------------------------------------------------------------------------------------------------+
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>
C
I wrote functions that can be used in a rather general way.
<lang c>#define CELL(I,J) (field[size*(I)+(J)])
- define ALIVE(I,J) t[size*(I)+(J)] = 1
- define DEAD(I,J) t[size*(I)+(J)] = 0
int count_alive(const char *field, int i, int j, int size) {
int x, y, a=0;
for(x=i-1; x <= (i+1) ; x++)
{
for(y=j-1; y <= (j+1) ; y++)
{
if ( (x==i) && (y==j) ) continue;
if ( (y<size) && (x<size) &&
(x>=0) && (y>=0) )
{
a += CELL(x,y);
}
}
}
return a;
}
void evolve(const char *field, char *t, int size) {
int i, j, alive, cs;
for(i=0; i < size; i++)
{
for(j=0; j < size; j++)
{
alive = count_alive(field, i, j, size);
cs = CELL(i,j);
if ( cs )
{
if ( (alive > 3) || ( alive < 2 ) )
DEAD(i,j);
else
ALIVE(i,j);
} else {
if ( alive == 3 )
ALIVE(i,j);
else
DEAD(i,j);
}
}
}
}</lang>
The function evolve needs a buffer where to store the result, and this buffer must be provided by the user calling the function. An example of usage to test the blinker and the glider is the following.
<lang c>#include <stdio.h>
/* some additional header needed to use the function evolve provided
previously, or just copy/paste the given code here */
- define BLINKER_SIZE 3
- define BLINKER_GEN 3
char small_blinker[] = {
0,0,0,
1,1,1,
0,0,0
}; char temp_blinker[BLINKER_SIZE*BLINKER_SIZE];
- define FIELD_SIZE 45
- define FIELD_GEN 175
char field[FIELD_SIZE * FIELD_SIZE]; char temp_field[FIELD_SIZE*FIELD_SIZE];
/* set the cell i,j as alive */
- define SCELL(I,J) field[FIELD_SIZE*(I)+(J)] = 1
void dump_field(const char *f, int size) {
int i;
for (i=0; i < (size*size); i++)
{
if ( (i % size) == 0 ) printf("\n");
printf("%c", f[i] ? 'X' : '.');
}
printf("\n");
}
int main(int argc, char **argv)
{
int i;
char *fa, *fb, *tt, op;
/* fast and dirty selection option */
if ( argc > 1 )
{
op = *argv[1];
} else {
op = 'b';
}
switch ( op )
{
case 'B':
case 'b':
/* blinker test */
fa = small_blinker;
fb = temp_blinker;
for(i=0; i< BLINKER_GEN; i++)
{
dump_field(fa, BLINKER_SIZE);
evolve(fa, fb, BLINKER_SIZE);
tt = fb; fb = fa; fa = tt;
}
return 0;
case 'G':
case 'g':
for(i=0; i < (FIELD_SIZE*FIELD_SIZE) ; i++) field[i]=0;
/* prepare the glider */
SCELL(0, 1);
SCELL(1, 2);
SCELL(2, 0); SCELL(2, 1); SCELL(2, 2);
/* evolve */
fa = field;
fb = temp_field;
for (i=0; i < FIELD_GEN; i++)
{
dump_field(fa, FIELD_SIZE);
evolve(fa, fb, FIELD_SIZE);
tt = fb; fb = fa; fa = tt;
}
return 0;
default:
fprintf(stderr, "no CA for this\n");
break;
}
return 1;
}</lang>
The blinker output (reformatted) is simply:
... .X. ... XXX .X. XXX ... .X. ...
Clojure
In keeping with idiomatic Clojure, the solution is implemented as discrete, composable functions and datastructures rather than one big blob of code. <lang lisp>(defstruct grid :w :h :cells)
(defn get-cell
"Returns the value at x,y. The grid is treated as a torus, such that both x and
y coordinates will wrap around if greater than width and height respectively."
[grid x y]
(let [x (mod x (:w grid))
y (mod y (:h grid))]
(-> grid :cells (nth y) (nth x))))
(defn neighbors
"Returns a lazy sequence of all neighbors of the specified cell."
[grid x y]
(for [j [(dec y) y (inc y)]
i [(dec x) x (inc x)]
:when (not (and (= i x) (= j y)))]
(get-cell grid i j)))
(defn evolve-cell
"Returns the new state of the specifed cell."
[grid x y]
(let [c (get-cell grid x y)
n (reduce + (neighbors grid x y))]
(if (or (and (zero? c) (= 3 n))
(and (= 1 c) (or (= 2 n) (= 3 n))))
1 0)))
(defn evolve-grid
"Returns a new grid whose cells have all been evolved."
[grid]
(assoc grid :cells
(vec (for [y (range (:h grid))]
(vec (for [x (range (:w grid))]
(evolve-cell grid x y)))))))
(defn generations [grid]
"Returns a lazy sequence of the grid, and all subsequent generations." (iterate evolve-grid grid))</lang>
The above does the work of creating subsequent generations of an initial grid. Now we add in some functions to create and display the grids: <lang lisp>(defn make-grid [w h & row-patterns]
(let [cells (vec (for [rp row-patterns]
(vec (mapcat #(take %1 (repeat %2)) rp (cycle [0 1])))))]
(if (and (= h (count cells))
(every? #(= w (count %)) cells))
(struct grid w h cells)
(throw (IllegalArgumentException. "Resulting cells do not match expected width/height.")))))
(defn display-row [row]
(do (dorun (map print (map #(if (zero? %) " . " "[X]") row))) (println)))
(defn display-grid [grid]
(dorun (map display-row (:cells grid))))
(defn display-grids [grids]
(dorun
(interleave
(repeatedly println)
(map display-grid grids))))</lang>
Thus, running: <lang lisp>(def blinker (make-grid 5 5 [5] [5] [1 3 1] [5] [5])) (display-grids (take 3 (generations blinker)))</lang> Outputs:
. . . . . . . . . . . [X][X][X] . . . . . . . . . . . . . . . . . . [X] . . . . [X] . . . . [X] . . . . . . . . . . . . . . . . . . [X][X][X] . . . . . . . . . . .
Similarly we can simply jump to a particular generation: <lang lisp>(def figure-eight (make-grid 10 10 [10] [10] [2 3 5] [2 3 5] [2 3 5] [5 3 2] [5 3 2] [5 3 2] [10] [10])) (display-grid figure-eight) (display-grid (nth (generations figure-eight) 7))</lang> Outputs:
. . . . . . . . . . . . . . . . . . . . . . [X][X][X] . . . . . . . [X][X][X] . . . . . . . [X][X][X] . . . . . . . . . . [X][X][X] . . . . . . . [X][X][X] . . . . . . . [X][X][X] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . [X][X] . . . . . . . . [X][X] . [X] . . . . . . . . . . [X] . . . . . . [X] . . . . . . . . . . [X] . [X][X] . . . . . . . . [X][X] . . . . . . . . . . . . . . . . . . . . . .
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
The implementation keeps universe in ubyte array, alive state is kept as 0x10 bit value, lower 4 bits are used for calculations of number of neighbors.
Output is generated every time it's printed, this probably isn't the best idea.
<lang D>import tango.io.Stdout; import tango.core.Thread; import tango.text.convert.Integer;
class GameOfLife {
private:
static const int ClearNeighboursCountMask = 0xf0;
static const int NeighboursCountMask = 0xf;
static const int AliveMask = 0x10;
ubyte[][] universe2d;
public:
this(int x = 60, int y = 20)
{
assert (x > 0 && y > 0, "oh noez, universe collapsed!");
universe2d = new ubyte[][](y + 2, x + 2);
}
void opIndexAssign(int v, size_t y, size_t x)
{
if (!v || v == ' ') universe2d[y][x] = 0;
else universe2d[y][x] = AliveMask;
}
void opIndexAssign(char[][] v, size_t y, size_t x)
{
foreach (rowIdx, row; v)
foreach (cellIdx, cell; row)
this[y + rowIdx, x + cellIdx] = cell;
}
//
char[] toString()
{
char[] ret;
ret.length = 2*(universe2d[0].length + 1);
ret[] = '=';
ret ~= "\n";
foreach (row; universe2d[1 .. $-1]) {
ret ~= "|";
foreach (ref cell; row)
if (cell & AliveMask) ret ~= "[]";
else ret ~= " ";
ret ~= "|\n";
}
ret ~= ret[0 .. 2*(universe2d[0].length + 1)];
return ret;
}
}
int main(char[][] args) {
auto uni = new GameOfLife(80, 20); char[][] glider1 = [ " #", "# #", " ##" ]; char[][] glider2 = [ "$ ", "$ $", "$$ " ]; char[][] lwss = [ " X X", "X ", "X X", "XXXX " ]; uni.iteration;
uni[3, 2] = glider1; uni[3,15] = glider2; uni[3,19] = glider1; uni[3,32] = glider2;
uni[5,50] = lwss;
// clear screen :> for (int j = 0; j < 100; j++) Stdout.newline;
for (int i = 0; i < 300; i++)
{
Stdout (uni).newline;
uni.iteration;
Thread.sleep(0.1);
}
return 0;
}</lang>
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>
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).
\ 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
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
neighbours = Getneighbours(buffer(i-1:i+1, j-1:j+1))
SELECT CASE(neighbours)
CASE (0:1)
cells(i,j) = .FALSE.
CASE (2)
! No change
CASE (3)
cells(i,j) = .TRUE.
CASE (4:8)
cells(i,j) = .FALSE.
END SELECT
END DO
END DO
END SUBROUTINE Nextgen
FUNCTION Getneighbours(neighbourhood)
INTEGER :: Getneighbours
LOGICAL, INTENT(IN) :: neighbourhood(:,:)
INTEGER :: k
Getneighbours = 0
DO k = 1, 3
IF (neighbourhood(1,k)) Getneighbours = Getneighbours + 1
END DO
DO k = 1, 3, 2
IF (neighbourhood(2,k)) Getneighbours = Getneighbours + 1
END DO
DO k = 1, 3
IF (neighbourhood(3,k)) Getneighbours = Getneighbours + 1
END DO
END FUNCTION Getneighbours
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
###
###
###
###
###
###
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>
J
Solution: <lang j>pad=: 0,0,~0,.0,.~] life=: (_3 _3 (+/ e. 3+0,4&{)@,;._3 ])@pad</lang>
Example: <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>
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: _#_ _#_ _#_
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 ..... ..... ...#. ....# ..###
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 = ()
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>
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>
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>
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>
Scala
A Conway "board" has infinite dimensions -- in fact, Conway's Game of Life is Turing complete -- so the algorithm below avoids using fixed-size structures such as arrays. Instead, each generation is represented by a set of the coordinates which are "alive".
The solution will be presented in four sections: coordinates, generations, sample patterns and tester. The first two implement everything that is needed for Conway's Game of Life. The sample patterns includes four classes of patterns that are tested. The tester checks some specific characteristic of each pattern, and then shows the three generations of blinker, as requested.
Coordinates
The coordinates to any cell in the board is represented as an immutable tuple of integers. To speed up computation speed, each coordinate keeps a list of all its neighbors. This is computed on demand, as some coordinates may never become alive and, thus, never require it.
All coordinates are memoized (cached), so that the list of neighbors will never need to be recomputed for any coordinate. This can lead to memory starvation, however.
No coordinate will be accepted at the limits of the representation (Int). If any such coordinate is created, an exception will be thrown to indicate the board can no longer be correctly represented.
<lang scala>class Coord private (val x: Int, val y: Int) {
private val offsets = List(-1, 0, 1)
private def offsetsOf(n: Int) = offsets map (_ + n)
/**
* A memoized list of all neighbors of a coordinate
*/
lazy val neighbors = for {
xn <- offsetsOf(x) if Coord.legal(xn)
yn <- offsetsOf(y) if Coord.legal(yn) && (x, y) != (xn, yn)
} yield Coord(xn, yn)
// Coordinates can be used as offsets def +(c: Coord) = Coord(x + c.x, y + c.y) def -(c: Coord) = Coord(x - c.x, y - c.y)
override def equals(other: Any) = other match {
case that: Coord => this.x == that.x && this.y == that.y
case _ => false
}
override def hashCode = ((x * 41) + y) * 41 + 41
override def toString = "Coord(%d, %d)" format (x, y)
}
object Coord {
// A Conway board is infinite in size; throw an exception if our hard limits are reached
private def legal(n: Int) = {
n.ensuring(Int.MinValue < _, "Coord too low").ensuring(_ < Int.MaxValue, "Coord too high")
true
}
private val cache = new scala.collection.mutable.HashMap[(Int,Int), Coord]
/**
* Factory for coordinates. All coordinates are memoized.
*/
def apply(x: Int, y: Int) = {
require(legal(x) && legal(y))
cache getOrElseUpdate ((x,y), new Coord(x, y))
}
/**
* Coordinate extractor
*/
def unapply(c: Coord) = Some((c.x, c.y))
/**
* An Ordering for coordinates which sorts by the X coordinate
*/
val xOrdering = Ordering.fromLessThan((_: Coord).x < (_: Coord).x)
/** * An Ordering for coordinates which sorts by the Y coordinate */ val yOrdering = Ordering.fromLessThan((_: Coord).y < (_: Coord).y)
/** * Any Tuple2[Int, Int] can be used as a Coordinate through this implict * conversion. */ implicit def coordFromTuple(t: (Int, Int)) = apply(t._1, t._2)
}</lang>
Generation
Generations are represented as immutable sets of coordinates for the cells which are alive at that generation. They extend Scala's immutable Set, but adds a few methods. They can return the next generation, of course, and also have a few methods to help with that. When converted to string, it will return a representation of the smallest board that fully contains the pattern. It can also return representation for fixed-coordinates windows. Last, it can return a new generation with the pattern recentered.
<lang scala>class Generation(val alive: Set[Coord]) extends Set[Coord] {
import Generation._
// Abstract methods that need to be defined as a Set def contains(elem: Coord): Boolean = alive contains elem def iterator: Iterator[Coord] = alive.iterator def +(elem: Coord): Generation = if (alive contains elem) this else Generation(alive + elem) def -(elem: Coord): Generation = if (alive contains elem) Generation(alive - elem) else this // Helper methods to be able to pass tuples of Int instead of Coord def apply(x: Int, y: Int): Boolean = apply(Coord(x, y)) def +(x: Int, y: Int): Generation = this.+(Coord(x, y)) def -(x: Int, y: Int): Generation = this.-(Coord(x, y)) def ++(coords: Iterator[(Int,Int)]): Generation = Generation(alive ++ (coords map (c => c: Coord))) def ++(coords: Traversable[(Int,Int)]): Generation = Generation(alive ++ (coords map (c => c: Coord)))
/**
* A list containing all coordinates that are neighbors of a cell which is alive, together
* with the number of alive cells it is neighbor of.
*/
lazy val neighbors = alive.toList flatMap (_ neighbors) groupBy identity map { case (c, l) => (c, l.size) }
// Filter all neighbors for desired characteristics def neighborhood(filter: Filter) = for (filter(coord) <- neighbors) yield coord def babies = neighborhood(Fecund) def adults = alive & neighborhood(Stable).toSet /** * The next generation is composed of babies from fecund neighborhoods and adults on stable * neighborhoods. */ def nextGeneration = Generation(adults ++ babies)
/**
* Return a string with the representation of this generation on a window
* defined by its upper-left and lower-right coordinates.
*/
def windowToString(upperLeft: Coord, lowerRight: Coord) = {
def toChar(c: Coord) = if (alive contains c) 'X' else ' '
def toRow(y: Int) = for (x <- upperLeft.x to lowerRight.x) yield toChar(Coord(x, y))
def toMatrix = for (y <- upperLeft.y to lowerRight.y by -1) yield toRow(y).mkString
toMatrix mkString "\n"
}
/**
* This generation's upper left corner
*/
lazy val upperLeft = {
val x = alive min Coord.xOrdering x;
val y = alive max Coord.yOrdering y;
Coord(x, y)
}
/**
* This generation's lower right corner
*/
lazy val lowerRight = {
val x = alive max Coord.xOrdering x;
val y = alive min Coord.yOrdering y;
Coord(x, y)
}
/**
* Recenter the pattern without altering its disposition
*/
def recenter = {
val offset = Coord(
upperLeft.x + (lowerRight.x - upperLeft.x) / 2,
lowerRight.y + (upperLeft.y - lowerRight.y) / 2
)
Generation(alive map (_ - offset))
}
override def equals(other: Any) = other match {
case that: Generation => this.alive == that.alive
case _ => false
}
override def hashCode = alive.hashCode
override def toString = windowToString(upperLeft, lowerRight)
}
object Generation {
def apply(coords: Iterator[Coord]): Generation = apply(coords.toSeq)
def apply(coords: Traversable[Coord]): Generation = apply(coords.toSet)
def apply(alive: Set[Coord]) = new Generation(alive)
def apply() = new Generation(Set.empty[Coord])
// Helper class to filter neighbors for desired qualities
class Filter(f: ((Coord, Int)) => Option[Coord]) {
def unapply(t: (Coord, Int)): Option[Coord] = f(t)
}
object Filter {
def apply(f: ((Coord, Int)) => Option[Coord]) = new Filter(f)
}
// A fecund filter will return all coordinates with three neighbors alive
val Fecund = Filter {
case (c, 3) => Some(c)
case _ => None
}
// A stable filter will return all coordinates with two or three neighbors alive
val Stable = Filter {
case (c, 2) => Some(c)
case (c, 3) => Some(c)
case _ => None
}
}</lang>
Conway's Game of Life Patterns
A number of patterns are provided, which are used to test the program. They are divided into still lives, oscillators, spaceships and methuselahs. Still lives are immutable patterns. Oscillators are patterns that follow a fixed length cycle, after which they repeat themselves. Spaceships are patterns that move across the board -- they also have a fixed length cycle, after which they repeat themselves at some offset from their original position. Methuselahs are patterns that take a long time to stabilize. When stabilized, they consist of still lives, oscillators and gliders, but have a fixed population size.
A few helper methods are provided to get these patterns into use.
<lang scala>object ConwayPatterns {
// Lists for all patterns available def stillLives = List(block, beehive, loaf, boat) map ((_, 1)) def oscillators = oscillators2.map((_, 2)) ::: oscillators3.map((_, 3)) def oscillators2 = List(blinker, toad, beacon) def oscillators3 = List(pulsar) def spaceships = List(glider, LWSS) map ((_, 4)) def methuselahs = List((diehard, 130), (acorn, 5206), (rPentomino, 1103))
// Still Lives patterns
val block = """|
| XX
| XX
|"""
val beehive = """|
| XX
| X X
| XX
|"""
val loaf = """|
| XX
| X X
| X X
| X
|"""
val boat = """|
| XX
| X X
| X
|"""
// Oscillators patterns
val blinker = """|
|
| XXX
|
|"""
val toad = """|
|
| XXX
| XXX
|
|"""
val beacon = """|
| XX
| XX
| XX
| XX
|"""
val pulsar = """|
|
| XXX XXX
|
| X X X X
| X X X X
| X X X X
| XXX XXX
|
| XXX XXX
| X X X X
| X X X X
| X X X X
|
| XXX XXX
|
|"""
// Spaceship patterns
val glider = """|
| X
| X X
| XX
|"""
val LWSS = """|
|
| XXXX
| X X
| X
| X X
|"""
// Methuselah patterns
val diehard = """|
| X
| XX
| X XXX
|"""
val acorn = """|
| X
| X
| XX XXX
|"""
val rPentomino = """|
| XX
| XX
| X
|"""
// Helper methods
// Enable constructing sets of coordinates from string patterns.
implicit def coordsFromPattern(pattern: String) = for {
(xs, y) <- pattern.stripMargin.split('\n').map(_.zipWithIndex).zipWithIndex.iterator
(c, x) <- xs.iterator
if c != ' '
} yield Coord(x, y)
// Move a set of coordinates to a point
def moveTo(pattern: String, to: Coord) = (pattern: Iterator[Coord]) map (_ + to)
def moveTo(coords: Iterator[Coord], to: Coord) = coords map (_ + to)
def moveTo(coords: Traversable[Coord], to: Coord) = coords map (_ + to)
}</lang>
Tester
We test still lives, oscillators and spaceships for their cycle length -- where still lives are considered to have a cycle length of 1 -- it repeats itself every generation. Methuselahs are tested for the number of generations until the population stabilizes. The test for stabilization is not fully accurate, as it just checks that the population is the same after a number of generations.
It also prints three generations of a blinker, as requested.
<lang scala>object ConwayTester {
import ConwayPatterns._
val MaxGenerations = 5500 // Give up at MaxGenerations to avoid spending too much time on errors
val WindowSize = 10 // To check for stable populations, use a window this big
import Coord.{xOrdering, yOrdering}
/**
* Return an iterator for the generations of a starting pattern
*/
def conwayIterator(first: Generation) = Iterator.iterate(first)(_.nextGeneration)
/**
* Return the period (number of different generations) for oscillators
*/
def getPeriod(first: Generation) = {
val it = conwayIterator(first)
it.next // drop first generation
(it take MaxGenerations takeWhile (_ != first) length) + 1
}
/**
* Return the period (number of different generations, ignoring offset) for
* spaceships.
*/
def getSpaceshipPeriod(first: Generation) = {
val it = conwayIterator(first) map (_.recenter)
it.next // drop first generation
(it take MaxGenerations takeWhile (_ != first) length) + 1
}
/**
* Return the number of generations until the population of a pattern
* stabilizes. This test only checks a window of generations for
* population size, as the test for spaceships won't work when multiple
* spaceships are present.
*/
def getUnstableGenerations(first: Generation) = (
conwayIterator(first)
take MaxGenerations
map (_.size)
sliding WindowSize
map (_.removeDuplicates.length)
takeWhile (_ > 1)
length
)
/**
* Return the first generation, properly centered, for a given pattern
* as represented by a string.
*/
def initPattern(pattern: String) =
Generation(pattern: Iterator[Coord]).recenter
/**
* For each pattern passed, apply a function which will measure some characteristic
* of the generations of that pattern, and assert it is equal to expected value.
*/
def testHarness(patterns: Traversable[(String, Int)], test: Generation => Int, msg: String) =
assert(patterns forall { case (pattern, period) => test(initPattern(pattern)) == period }, msg)
// Available tests
def testStillLives = testHarness(stillLives, getPeriod _, "Failure in still lives")
def testOscillators = testHarness(oscillators, getPeriod _, "Failure in oscillators")
def testSpaceships = testHarness(spaceships, getSpaceshipPeriod _, "Failure in spaceships")
def testMethuselahs = testHarness(methuselahs, getUnstableGenerations _, "Failure in methuselahs")
/**
* Do all available tests
*/
def testAll {
testStillLives
testOscillators
testSpaceships
testMethuselahs
}
/**
* Do all available tests, and print three generations of a blinker on a 3x3 window.
*/
def main(args: Array[String]) {
val upperLeft = Coord(-1, 1)
val lowerRight = Coord(1, -1)
testAll
println("Passed all tests. Printing three generations of blinker:")
conwayIterator(initPattern(blinker)).zipWithIndex.take(3).toList zip List("st", "nd", "rd") foreach {
case ((generation, nth), suffix) =>
println((nth + 1) + suffix + " generation: \n"+generation.windowToString(upperLeft, lowerRight)+"\n")
}
}
}</lang>
Output:
Passed all tests. Printing three generations of blinker: 1st generation: XXX 2nd generation: X X X 3rd generation: XXX
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>
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 {5 5} {{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-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 neighborhood to the new cell, neighborhoods takes board of cells <<c..>..> to a board <<(c,<n..>)..>..> with neighborhoods, and evolve(n) takes a board <<c..>..> to a sequence of n boards evolving from it.
<lang Ursala>#import std
- import nat
rule = -: (^/~& ^|(~&,length@F); ~&l?/~&r-={2,3} ~&r-={3})*T ~&brlD@G\(0,&) ~&rSS zipp0*ziD iota256
neighborhoods = ~&thth3hthhttPCPthPTPTX**K7S+ swin3**+ swin3@hNSPiCihNCT+ --<0>*+ 0-*
evolve "n" = @iNC ~&x+ rep"n" ^C\~& rule**+ neighborhoods@h</lang> test program: <lang Ursala>blinker =
(==`O)**t -[ +++ OOO +++]-
glider =
(==`O)**t -[ +O++++ ++O+++ OOO+++ ++++++ ++++++]-
- show+
examples = mat0 ~&?(`O!,`+!)*** evolve2(blinker)-- evolve4(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>