69
\$\begingroup\$

Conway's Game of Life is the classic example of cellular automation. The cells form a square grid and each has two states: alive or dead. On each turn, each cell simultaneously updates according to its state and those of its eight neighbours:

  • A live cell remains alive if it has exactly two or three live neighbours
  • A dead cell becomes alive if it has exactly three live neighbours

Your mission, should you choose to accept it, is to code the shortest Game of Life implementation in your favourite language.

The rules:

  • The grid must be at least 20x20
  • The grid must wrap around (so the grid is like the surface of a Torus)
  • Your implementation must allow the user to input their own starting patterns
  • GoL is a bit pointless if you can't see what is happening, so there must be visual output of the automaton running, with each turn's result being shown for long enough to be seen!
\$\endgroup\$
14
  • 9
    \$\begingroup\$ Previously on Stack Overflow: Code Golf: Conway's Game of Life, and be sure to look at the APL implementation link in the comments. \$\endgroup\$ – dmckee --- ex-moderator kitten Aug 14 '11 at 3:07
  • 1
    \$\begingroup\$ Ah, I did not see that. But this is slightly different no (save me deleting the work putting the challenge together? \$\endgroup\$ – Griffin Aug 14 '11 at 3:15
  • 7
    \$\begingroup\$ It's not a problem. Many puzzles already run on Stack Overflow have been done here too, but people will tell you that I am obsessive about linking to similar challenges. \$\endgroup\$ – dmckee --- ex-moderator kitten Aug 14 '11 at 3:17
  • \$\begingroup\$ @Griffin: You can remove all those ; before }s. Also vars can be eliminated at times (if it doesn't break your code). And for one-line fors, ifs etc, you can eliminate the { } completely: for(...) for(...) dosomething(). \$\endgroup\$ – pimvdb Aug 14 '11 at 14:21
  • \$\begingroup\$ @pimvdb, cheers, I haven't fully golfed it yet, haven't had the time. just wanted to show that I had a go too, rather than idly setting a challenge. Will golf it to the max soon. \$\endgroup\$ – Griffin Aug 14 '11 at 17:53

37 Answers 37

1
2
1
\$\begingroup\$

Octave (153)

the same as Matlab by DenDenDo at Shortest Game of Life , but had to change imshow to imagesc:

b=uint8(rand(20)<0.2)
s=@(m)imfilter(m,[1 1 1;1 0 1;1 1 1],'circular')
p=@(m,n)uint8((n==3)|(m&(n==2)))
while 1
imagesc(b)
drawnow
b=p(b,s(b))
end
\$\endgroup\$
1
\$\begingroup\$

Python 2: 334 Bytes

Only 6 years late.

import time
s='';s=map(list,iter(raw_input,s));k=len(s);l=(-1,0,1);n=int;z=range
while 1:
 r=[[0]*k for i in z(k)]
 for i in z(k*k):
  a,b=i//k,i%k
  m,g=sum([n(s[(a+c)%k][(b+d)%k])for c in l for d in l if c|d]),n(s[a][b])
  r[a][b]=n((m==2)&g or m==3)
  print'*'if r[a][b]else' ',
  if b-k+1==0:print
 s=r;time.sleep(.2);print"\033c"

You can run it like:

python gol.py
0000000
0001000
0000100
0011100
0000000
0000000
0000000

Where the 0s and 1s represent dead and live cells, an extra newline at the end begins execution.

Grids must be square.

It's easier to run than the shortest python one, supports any sized grids, and looks pretty when run.

It's also 100 bytes more, so there's that.

\$\endgroup\$
1
\$\begingroup\$

HTML and Javascript, 248 characters

<script>b=[];setInterval(()=>x.innerHTML=(b=b.map((r,y)=>r.map((c,x)=>+(([0,1,2,4,6,8,9,10].reduce((s,n)=>s+((b[y-1+(n>>2)]||[])[x+n%4-1]||0),0)|c)==3)))).map(r=>`<tr>${r.map(v=>`<td>${'⬜⬛'[v]}`).join('')}`).join(''),999)</script><table id='x'>

Run it by opening the web developer console and setting the global variable b (for "board") to a 2D-array of 0 (dead) and 1 (alive) values, for example:

b=new Array(32).fill(0).map(() => new Array(32).fill(0).map(() => Math.floor(Math.random() * 2)))

The core of this is the following:

Javascript, 114 characters

l=b=>b.map((r,y)=>r.map((c,x)=>+(([0,1,2,4,6,8,9,10].reduce((s,n)=>s+((b[y-1+(n>>2)]||[])[x+n%4-1]||0),0)|c)==3)))

Annotated as follows:

l=       // l="Life"
  b=>    // Function that takes a board (2D array of ints that are 1 or 0)
  b.map( // map each row 
    (
      r, // the row (array of 1s and 0s)
      y  // index is the y position of the row
    )=>
    r.map( //map each cell
      (
        c, // the cell value (0, or 1)
        x  // index is the x position
      )=>(+( //this whole thing will return true or false, convert to 1 or 0
        // these magic numbers represent the eight neighbors of a cell
        // they map to x, y offsets (used below):
        // value  x     y
        //      n%4-1 (n>>2)-1
        [
          0, //  -1    -1
          1, //   0    -1
          2, //   1    -1
          4, //  -1     0
          6, //   1     0
          8, //   1    -1
          9, //   1     0
          10 //   1     1
        ]
        .reduce( //get the number of neighbors that are alive (===1)
          (
            s, // the accumulator (sum of alive neighbors so far)
            n  // the number from the list of magic numbers above
          )=>
          s+(  // add to the accumulator
            (
              b[            // find the row containing the neighbor
                y-1+(n>>2)  // A shorter way of expressing y+Math.floor(n/4)-1
              ]||[]         // if index is -1 or b.length, empty array
            )[              // within the row, find the value
              x+n%4-1       // offset x value (see table above)
            ]||0            // coalesce undefined(x is -1 or r.length) to 0
          ),0               // initial value for neighborCount accumulator
        )|c                 // | bitwise or with the value of the cell, 1 or zero
                            // if the cell is dead (0), this has no effect
                            // if the cell is alive (1), this changes 2 to 3
      )==3)                 // 3 means either:
                            // 3 neighbors or
                            // 2 neighbors and an alive cell (the rules for life)
    )
)

More info here: https://github.com/noops-challenge/golfbot/blob/master/challenges/conways-life/entries/davidmfoley

\$\endgroup\$
1
\$\begingroup\$

QBasic, 276 271 bytes

-5 bytes thanks to Dominic van Essen

DIM a(20,20)
DO
FOR y=0TO 19
FOR x=0TO 19
IF j THEN c=a(x,y)\2ELSE c=INPUT$(1)>"0
a(x,y)=c
NEXT x,y
CLS
FOR y=0TO 19
?
FOR x=0TO 19
?a(x,y);
n=0
FOR j=19TO 21
FOR i=19TO 21
n=n-a((x+i)MOD 20,(y+j)MOD 20)MOD 2
NEXT i,j
a(x,y)=2*(n=3)+(1-2*(n=4))*a(x,y)
NEXT x,y
SLEEP
LOOP

Ways to run QBasic

Disclaimer: This golfed version is extremely user-unfriendly. See below for details and a somewhat friendlier version.

Algorithm

We store the grid in the 2D array a. A value of 0 is a dead cell; a value of -1 (QBasic's default truthy value) is a living cell.

The whole program is wrapped in an infinite DO ... LOOP. On the first iteration, j is 0, and so the first nested FOR loop initializes the array from user input (c=INPUT$(1)>"0). We then clear the screen with CLS and proceed to the next set of nested loops. Before each row y, we print a newline (?). Then for each cell at column x:

  • We print the cell's value, suppressing the trailing newline (?a(x,y);).
  • We loop over the 3x3 neighborhood around the cell. The loop indices j and i are essentially going from -1 to 1, but in QBasic, (-1) MOD num is -1 rather than num - 1, so to avoid any negative numbers we loop from 19 to 21 instead.
  • For each living cell in the neighborhood, we add 1 to n.
  • After the loop, we subtract 2 from the cell's value if it will be alive at the next step. A more straightforward but less golfy way to write the expression is a(x,y) = a(x,y) - 2 * ((n=3) - (n=4)*a(x,y)): subtract 2 if n=3 or if n=4 and a(x,y) is true (-1).

After the FOR loops, SLEEP pauses until the user presses a key. We then return to the top. At this point, the elements in array a can have any of four values:

  • 0 is a cell that was dead last step and will remain dead.
  • -1 is a cell that was alive last step but will die.
  • -2 is a cell that was dead last step but will come alive.
  • -3 is a cell that was alive last step and will remain alive.

When we reach the first nested FOR loop again, j is now truthy (having been used as a loop index), so we integer-divide each element by 2 (c=a(x,y)\2). Values of 0 and -1 become 0 (dead), and values of -2 and -3 become -1 (alive).

I/O format and caveats; or: Don't Run This Code

The input format for this code is just awful. The user is expected to press a key 400 times to initialize the 400 cells. (Any key with an ASCII value of 48 ("0") or less is a dead cell; any key with a greater ASCII value is a living cell.) The worst part: none of this input is echoed to the screen. You just have to keep count in your head and hope you didn't double-press a key. In practice? Something always goes wrong.

Once all the input has been received, the raw array values are output. Because of the way QBasic formats numeric output, they do line up in a grid, like this--

 0 -1  0 
 0  0 -1
-1 -1 -1

--but it's still not the nicest output format.

Rather than an animation per se, the code waits for a user keypress between iterations. I think this fits the spec (it shows each step long enough to be seen), and it's the golfiest way to pause in QBasic. SLEEP 1 would wait one second between each iteration for +2 bytes.

A couple more caveats:

  • The code runs as an infinite loop, so you'll have to kill the program to make it exit.
  • The sequence 2ELSE on line 5 is correctly parsed as 2 ELSE by actual QBasic, but the QB64 emulator has trouble with it, expecting the 2E sequence to be the start of a number in scientific notation. You'll have to add in the space if you're using QB64.

All that to say: I don't recommend you run this code as-is. Either change the array size to 5x5 (which makes the input manageable and still allows for a glider) or use the nicer version.

Nicer version, 319 bytes

It's still not what I'd call user-friendly, but here's a version I'm actually willing to run:

DIM a(20,20)
1CLS
FOR y=0TO 19
IF j=0THEN INPUT r$
FOR x=0TO 19
IF j THEN c=a(x,y)\2 ELSE c=MID$(r$,x+1,1)>"0
a(x,y)=c
NEXT x,y
CLS
FOR y=0TO 19
?
FOR x=0TO 19
?CHR$(34-a(x,y));
n=0
FOR j=19TO 21
FOR i=19TO 21
n=n-a((x+i)MOD 20,(y+j)MOD 20)MOD 2
NEXT i,j
a(x,y)=2*(n=3)+(1-2*(n=4))*a(x,y)
NEXT x,y
IF"!">INPUT$(1)GOTO 1

Differences:

  • This version takes input line by line. There is a prompt, and characters are echoed as they're typed; you can even backspace if you make a mistake. The same range of ASCII values represents dead vs. living, with the caveat that this form of input doesn't play well with space, double quote, or comma. I recommend . for dead cells and a letter for living ones. You can also give it lines shorter than 20 characters, and it will pad them out with dead cells--super convenient.
  • Output is a grid of characters: " for dead cells, # for living ones.
  • Press space or enter to go to the next step; any other printable ASCII character ends the program.
\$\endgroup\$
5
  • \$\begingroup\$ Is there a good online emulator for Qbasic that you could link so we can see it running? \$\endgroup\$ – Dominic van Essen Jul 19 '20 at 7:41
  • \$\begingroup\$ You can recycle j instead of z to save 4 bytes by removing z=1. \$\endgroup\$ – Dominic van Essen Jul 19 '20 at 8:01
  • \$\begingroup\$ And save another 1 byte by changing FOR FOR NEXT ? NEXT into FOR ? FOR NEXT x,y \$\endgroup\$ – Dominic van Essen Jul 19 '20 at 8:10
  • \$\begingroup\$ Ah, nice, thanks! QBasic is runnable online at Archive.org; I've added a link to the answer. \$\endgroup\$ – DLosc Jul 19 '20 at 18:30
  • \$\begingroup\$ Thanks for the link! QB64 was actually quite painless to install on my computer, so super-useful to know the caveats... \$\endgroup\$ – Dominic van Essen Jul 19 '20 at 19:34
1
\$\begingroup\$

Python with numpy and matplotlib

765 characters

This script is quite optimized, since it uses no loops: only numpy functions or animations loops (that are like recursion). So even if its quite long, I think that it was interesting to put it here (and it could be really shorter, but I just took my classic program, and simplified it).

import matplotlib.pyplot as P;import numpy as N;from matplotlib.animation import FuncAnimation;neighbours=lambda G:N.sum([N.roll(N.roll(G,y,1),x,0)for x in(-1,0,1)for y in(-1,0,1)if x+y],axis=0);A=N.array
class G:
    o=1
    def __init__(Z,e,r):Z.g=N.random.rand(e,r)<.3;Z.r=lambda a,v:N.logical_or(N.any(A([v==3]),axis=0),N.logical_and(a,N.any(A([N.logical_or(v==2,v==3)]),axis=0)))
    def S(Z):Z.g=(Z.r(Z.g,neighbours(Z.g)),Z.g)[Z.o];return Z.g
    def P(Z,x):Z.o^=1
    def G(Z,n):
        for _ in[0]*n:Z.S()
        return Z.g
    def R(Z,skip=0,t=0):l=P.figure();im=P.imshow(Z.g,cmap="Greys");l.canvas.mpl_connect('button_press_event',Z.P);FuncAnimation(l,lambda I:(im.set_array(Z.G(skip+1)),[im])[-1],interval=1,blit=1);P.show()
life=G(100,100);life.R(t=1)

If you want to change the grid, you can simply replace the statement:

life.fill()

That fills randomly the center part of the grid, by:

life.g=matrix

Where matrix is your grid, a numpy booleans array.

This code comes from a more complex code, this one :

import matplotlib.pyplot as plt
import numpy as np
from matplotlib.animation import FuncAnimation

out = __import__('sys').stdout.write

neighbours = lambda grid: np.sum([
    np.roll(np.roll(grid, y, 1), x, 0)
    for x in (-1, 0, 1) for y in (-1, 0, 1)
    if x or y
], axis=0)
neighbours.__doc__ = """# function that returns sum of neighbours of all the
cells for a given grid"""


class GOL:
    """Object to run a game of life - type Cellular Automaton"""
    on = True  # variable: bool; is the simulation runing ?
    i = 0  # generation number

    def __init__(self, dim_x=800, dim_y=400, R=None, show_gen=False):
        """dim_x and dim_y are the batch size

        R is the rule, specified as here: B___/S___
        example: B3/S23 for the classic game of life.
        default value: B3/S23"""
        if R is None:
            self.B, self.S = ([3], [2, 3])
        else:
            self.B, self.S = [list(map(int, p)) for p in R.split("/")]
        self.shape = (dim_y, dim_x)  # variable:tuple(int, int); grid shape
        self.g = np.zeros(self.shape) == 1  # variable:np.array()
        self.showGen = show_gen  # variable:bool; print the gen number ?

        if R is None:  # default rule: a bit speedier (no loops)
            # function to compute next generation for the conway's game of life
            self.rule = lambda actuel, voisins: \
                np.logical_or(
                    np.any(
                        np.array([voisins == 3]),
                        axis=0
                    ),
                    np.logical_and(
                        actuel,
                        np.any(
                            np.array([
                                np.logical_or(
                                    voisins == 2,
                                    voisins == 3
                                )
                            ]),
                            axis=0)
                    ))
        else:  # other rules
            # function to compute the next generation for any given rule
            self.rule = lambda actuel, voisins: \
                np.logical_or(
                    np.any(
                        np.array([voisins == b for b in self.B]),
                        axis=0
                    ),
                    np.logical_and(
                        actuel,
                        np.any(
                            np.array([voisins == s for s in self.S]),
                            axis=0)
                    ))

    def __str__(self):
        """how to print the automata (info : rule and rule number)"""
        return "I'm a life-like automata" \
               '\nmy rule : B' + ''.join(map(str, self.B)) +\
               '/S' + ''.join(map(str, self.S)) \
               + "\nmy hexa-code :  " + str(self.rule_number())

    def fill(self, mode, d=.3, n=10):
        """Random filling of the grid
        mode : {'rNoise', 'cloud', 'parse'}
        rNoise:
            fill all the grid with the density d
        cloud:
            fill a third of the grid with the density d
        parse:
            fill n cells exactly in the grid (no overlappings)
        """
        self.g &= False
        s0, s1 = self.shape
        if mode == "rNoise":
            self.g = np.random.rand(*self.g.shape) < d

        elif mode == "cloud":

            self.g[s0 // 3: s0 // 3 * 2, s1 // 3: s1 // 3 * 2] = (
                np.random.rand(s0 // 3, s1 // 3) < d)

        elif mode == "parse":
            for _ in range(n):
                x, y = np.random.randint(s1), np.random.randint(s0)
                while self.g[y, x]:
                    x, y = np.random.randint(s1), np.random.randint(s0)
                self.g[y, x] = True  # it's a boolean list !!!

    def step(self):
        """Compute the next generation and refresh the grid"""
        if self.on:
            self.i += 1
            # if self.showGen and not self.i % 10:
            #     out("generation " + str(self.i))
            self.g = self.rule(self.g, neighbours(self.g))
        return self.g

    def pause(self, x):
        """Action for the animation : swich the value of self.on"""
        self.on ^= True

    def gen(self, n):
        """Generate n generations """
        for _ in [0] * n:
            self.step()
        return self.g

    def run(self, skip=0, t=0, showGen=False):
        """Run the CA with a matplotlib animation graphics"""
        self.showGen = showGen
        fig = plt.figure()
        im = plt.imshow(self.g, cmap="Greys")
        fig.canvas.mpl_connect('button_press_event', self.pause)

        FuncAnimation(fig,
                      lambda i: (im.set_array(self.gen(skip + 1)), [im])[-1],
                      interval=t,
                      blit=True)
        plt.show()

    def rule_number(self):
        return sum(2 ** (np.hstack((np.array(self.B), np.array(self.S) + 9))))


new_rule = lambda: (
    np.arange(8)[np.random.rand(8) > .5],
    np.arange(8)[np.random.rand(8) > .5]
)

new_rule.__doc__ == """returns a random rule"""


life = GOL(600, 600, R="3/23")
life.fill("cloud")
print(life)
life.run(t=1, showGen=True)

This long version allows you to chose any life-like rule, and to fill the grid with different random modes.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to the site! There are a couple of obvious golfs here (GOL -> G, True -> 1, False -> 0), but otherwise, this is an impressive first answer. Be sure to check out our Tips for golfing in Python page for less obvious ways to save bytes! \$\endgroup\$ – caird coinheringaahing Oct 6 '20 at 22:02
0
\$\begingroup\$

PHP, 201 bytes (not tested)

for($s=file(f);print"\n";$s=$t)foreach($s as$y=>$r)for($x=-print"
";"
"<$c=$s[$y][++$x];print$t[$y][$x]=" X"[$n<4&$n>2-$a])for($n=-$a=$c>A,$i=$x-!!$x-1;$i++<=$x;)for($k=$y-2;$k++<=$y;)$n+=$s[$k][$i]>A;

Run with -nr.

breakdown

for($s=file(f);                         # import input from file "f"
    print"\n";                              # infinite loop: 1. print newline
    $s=$t)                                  # 3. copy target to source, next iteration
    foreach($s as$y=>$r)                    # 2. loop through lines
        for($x=-print"\n";"\n"<$c=$s[$y][++$x]; # print newline, loop $x/$c through line characters (before line break)
            print                                   # 5. print new cell
                $t[$y][$x]=" X"[$n>2-$a&$n<4])      # 4. new cell is alive if neighbour count<4 and >2 (>1 if alive)
            for($n=-                                # 2. init neighbour count: exclude self
                $a=$c>A,                            # 1. $a=cell is alife
                $i=$x-!!$x-1;$i++<=$x;)             # 3. loop $i from one left to one right of current position
                for($k=$y-2;$k++<=$y;)                  # loop $k from one above to one below current position
                    $n+=$s[$k][$i]>A;                       # increase neighbor count if neighbour is alife
\$\endgroup\$
0
\$\begingroup\$

VBA (Excel), 546* Bytes

Sub t()
f=[a1:t20]
For Each c In f.Cells
c.Value=""
r=c.Row
l=c.Column
If g(r,0,0,l,-1,0)Then h=h+1
If g(r,0,0,l,1,21)Then h=h+1
If g(r,-1,0,l,0,0)Then h=h+1
If g(r,1,21,l,0,0)Then h=h+1
If g(r,1,21,l,-1,0)Then h=h+1
If g(r,-1,0,l,1,21)Then h=h+1
If g(r,-1,0,l,-1,0)Then h=h+1
If g(r,1,21,l,1,21)Then h=h+1
If h=3Or(h=2And c.Interior.Color=0)Then c.Value="A"
Next
f.Interior.ColorIndex=0
For Each c In f
If c.Value="A"Then c.Interior.Color=0
Next
End Sub
Function g(r,e,f,c,q,z)
g=(Cells(IIf(r+e=f,Abs(f-20),r+e),IIf(c+q=z,Abs(z-20),c+q)).Interior.Color=0)
End Function

Create the living cells by highlighting cells in A1:T20 and coloring them black.

*When t is run, it executes a single tick. I added a button on mine to click repeatedly. If this doesn't satisfy the requirements, I'll add a do-->while[counta(f)]>0 and a DoEvents for +34 bytes.

[I'll edit this with a link when I upload a copy of my macro-enabled Excel doc]

\$\endgroup\$
1
  • \$\begingroup\$ This answer appears to be non-functional for a couple of reasons, namely the declaration of f should include a set clause as otherwise f.cells will invoke an object required error as f will be instanciated as a 20 x 20 Array. Secondly, when this is corrected the given solution does not implement the rules of conways game of life properly. I suggest using a simple blinker oscillator as a future test case \$\endgroup\$ – Taylor Scott Feb 15 '19 at 19:11
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.