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>
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>
C
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>
Icon and Unicon
Icon
<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 *** --- *** --- --- * * * --- --- *** --- ->
Unicon
The Icon solution also works in Unicon.
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>
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: _#_ _#_ _#_
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>
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 = ()
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>
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>
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
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>
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
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>
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-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>
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
- 6502 Assembly
- Ada
- ALGOL 68
- APL
- AutoHotkey
- C
- Clojure
- Common Lisp
- D
- E
- F Sharp
- Windows Presentation Foundation
- Forth
- Fortran
- Haskell
- Icon
- Unicon
- J
- JAMES II/Rule-based Cellular Automata
- JAMES II
- Java
- MATLAB
- Mathematica
- OCaml
- Oz
- Perl
- Perl 6
- PicoLisp
- PureBasic
- Python
- R
- Ruby
- Scala
- Scheme
- SETL
- Tcl
- TI-89 BASIC
- Ursala
- Vedit macro language
- ZPL