This is my attempt at writing Conway's Game of Life in a single line of Python. It's not meant to be efficient or even as short as possible, just be a single line. (An additional line is required to define the initial array, which is empty in my example, making the code even more pointless)
a = [[0 for x in range(8)] for y in range(8)]
while True: a=[[([[sum(b[y1][x1] for b in [[[((-1<x2+dx<len(a[0])) and (-1<y2+dy<len(a))) and a[y2+dy][x2+dx] or 0 for x2 in range(len(a[0]))] for y2 in range(len(a))] for (dx,dy) in [(dx,dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]]) for x1 in range(len(a[0]))] for y1 in range(len(a))][y][x]== 3 or ([[sum(c[y3][x3] for c in [[[((-1<x4+dx<len(a[0])) and (-1<y4+dy<len(a))) and a[y4+dy][x4+dx] or 0 for x4 in range(len(a[0]))] for y4 in range(len(a))] for (dx,dy) in [(dx,dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]]) for x3 in range(len(a[0]))] for y3 in range(len(a))][y][x] == 2 and a[y][x]==1)) and 1 or 0 for x in range(len(a[0]))] for y in range(len(a))]The first line sets up the initial_array, in this case an 8 by 8 array of zero. If you want to start with some live cells you can add them here. The next line is the entire Game of Life logic as a looped, nested, list comprehension. So long as you have defined a two dimensional array called a, this line will do all the work. This code doesn't output the array at any point; if you want to see what's going on then you need more lines. Sorry. You can always output the final result if you change the loop to one that terminates.
The result isn't pretty, and definitely isn't efficient, but demonstrates how good list comprehensions are at compressing code. Whether that's a good thing or a bad thing depends on how you use them. I recommend not using them like this.
Background
A friend recently sent me an article about Conway's Game of Life written in one line of a programming language I'd never heard of, called APL (Array Programming Language or A Programming Language). I was impressed that the Game of Life could be written so compactly (albeit in an obscure alphabet). I also like the algorithm used to calculate neighbours. I've also found a one-line Matlab implementation of Conway's Game of Life, though I think it's slighly cheating since because lines end with a semicolon, any number of lines can simply be concatenated.
Having recently got the hang of Python's list comprehensions, I keep finding I can write code more efficiently, but am occasionally tempted to nest them in a way that begins to make them unreadable. When I saw that the Game of Life could be written as a single line of code just using arrays, I naturally wondered how far I could get using Python.
Step-by-step explanation
Below is a description of how I went about writing such a horrible, contorted line of code. I started by writing longer, more readable code, without list comprehensions. Then I converted each stage into a list comprehension, before finally joining each of the list comprehensions into a single nested list comprehension. Once again, I want to stress that I don't think this is a good idea in general.
Step 1. Creating the initial array
The first step is to create a two dimensional array (list of lists) of zeros.
I decided to use variables for the width and height, to make things easier to test and change. They can be replaced with constants later to remove those two lines. I used different values for width and height to ensure I didn't mix up my x and y coordinates at any point. Lines 4 - 9 create a width x height array of zeros.
(width, height) = (5,4)
initial_array = []
for y in range(height):
line = []
for x in range(width):
line.append(0)
initial_array.append(line)Creating simple arrays in a perfect task for list comprehensions, so we can immediately replace those 6 lines with:
initial_array = [[0 for x in range(width)] for y in range(height)]For testing purposes, we can now add some live cells (ones) into the array.
initial_array[0][2] = 1
initial_array[1][2] = 1
initial_array[2][2] = 1We now have a horizontal line. We can view our array with the follow code:
print 'Initial array'
for line in initial_array:
print lineThe output should look something like:
[0,0,1,0,0]
[0,0,1,0,0]
[0,0,1,0,0]
[0,0,0,0,0]Step 2. Creating a shifted array
In order to calculate the number of cells neighbouring each cell, we create eight matrices, shifted one cell in every direction. Each of these matrices effectively counts whether there is a live cell in one specific surrounding cell.
To start with let's just create a single new matrix shifted one cell up and one cell left. The tricky part of this is dealing with the edges: the uppermost and leftmost edges won't be defined.
new_array = []
for y in range(height):
line = []
for x in range(width):
n = ((-1 < x+1 < width) and (-1 < y+1 < height)) and initial_array[y+1][x+1] or 0
line.append(n)
new_array.append(line)Line 13 is the key here. Rather than check whether x+1 and y+1 are within the limits of the array with an if statement and then assign the values, we use a Python trick of using and and or to combine the test and assignation (see here for details.). This will allow us to put code into a list comprehension.
If we output new_array, it should look like this:
[0,1,0,0,0]
[0,1,0,0,0]
[0,0,0,0,0]
[0,0,0,0,0]This array tells us which pixels, or values in the array, have a live neighbour (value equal to one) one cell right and one cell down. We built this array list by moving through the initial array and so this is an ideal opportunity to use another list comprehension:
new_array = [[((-1 < x+1 < width) and (-1 < y+1 < height)) and initial_array[y+1][x+1] or 0 for x in range(width)] for y in range(height)]Step 3. Creating all eight shifted arrays
We now need to calculate the other seven matrices for the other seven directions. For this we need an array/list of directions. We might as well jump right in and use a list comprehension for this now:
directions = [(dx, dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]We don't actually need to save this variable though as we can directly loop through the list of directions. As we do, we make new arrays (with a list comprehension like the one above) and sticking each in a list of arrays:
neighbour_arrays = []
for (dx, dy) in [(dx, dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]:
new_array = [[((-1<x+dx<width) and (-1<y+dy<height)) and initial_array[y+dy][x+dx] or 0 for x in range(width)] for y in range(height)]
neighbour_arrays.append(new_array)Step 4. Creating a summed array
The next step is to create an array which contain the total number of live neighbours for each cell, i.e. to sum the neighbour arrays.
sum_array = []
for y in range(height):
line = []
for x in range(width):
n = 0
for array in neighbour_arrays:
n += array[y][x]
line.append(n)
sum_array.append(line)If we output sum_array, it should look like this:
[0,2,1,2,0]
[0,3,2,3,0]
[0,2,1,2,0]
[0,1,1,1,0]Again, since are building an array by cycling through another array, we can use a list comprehension. We can also make use of Python's built-in sum function to sum each of the values for a given (x,y) coordinate, which actually quite hard to do here without a list comprehension (actually a generator expression, which means we can use fewer brackets):
sum_array = [[sum(array[y][x] for array in neighbour_arrays) for x in range(width)] for y in range(height)]Step 5. Calculating the next generation array
To create the array for the next generation, we need to test the conditions for life. The standard rules in Conway's Game of Life are that only live cells with two or three neighbours survive and any empty cell with three neighbour becomes live. Put another way, any cell with three neighbour and any live cell with two neighbour is live in the next generation. All other cells are dead. The explicit, verbose way to write this is:
new_array = []
for y in range(height):
line = []
for x in range(width):
if sum_array[y][x]==3 or (sum_array[y][x]==2 and initial_array[y][x]==1):
n = 1
else:
n = 0
line.append(n)
new_array.append(line)If we output new_array, it should look like this:
[0,0,0,0,0]
[0,1,1,1,0]
[0,0,0,0,0]
[0,0,0,0,0]Which is what should happen - the three-cell line appears to rotate 90 degrees. You know the drill: this can be converted into a single-line list comprehension. We use the same and-or trick as above to avoid the if-else statement:
new_array = [[(sum_array[y][x]==3 or (sum_array[y][x]==2 and initial_array[y][x]==1)) and 1 or 0 for x in range(width)] for y in range(height)]Step 6. Putting it all together
The code should now contain five list comprehensions a look a bit like this (give or take a few blank lines):
(width, height) = (5, 4)
initial_array = [[0 for x in range(width)] for y in range(height)]
initial_array[0][2] = 1
initial_array[1][2] = 1
initial_array[2][2] = 1
print "Initial array"
for line in initial_array:
print line
neighbour_arrays = []
for (dx, dy) in [(dx, dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]:
new_array = [[((-1 < x+dx < width) and (-1 < y+dy < height)) and initial_array[y+dy][x+dx] or 0 for x in range(width)] for y in range(height)]
neighbour_arrays.append(new_array)
sum_array = [[sum(array[y][x] for array in neighbour_arrays) for x in range(width)] for y in range(height)]
new_array = [[(sum_array[y][x]==3 or (sum_array[y][x]==2 and initial_array[y][x]==1)) and 1 or 0 for x in range(width)] for y in range(height)]
print "New array"
for line in new_array:
print lineWe still have a for loop creating the neighbour arrays, so we can convert this to a list comprehension and combine it with the directions list:
neighbour_arrays = [[[((-1 < x+dx < width) and (-1 < y+dy < height)) and initial_array[y+dy][x+dx] or 0 for x in range(width)] for y in range(height)] for (dx, dy) in [(dx, dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy != 0 or dx !=0)]]Now it's simply a matter of replacing the array variable with the code that constructs them. We also have to ensure that we don't have multiple variables called x and y.
new_array = [[([[sum(array[y1][x1] for array in [[[((-1<x2+dx<width) and (-1<y2+dy<height)) and initial_array[y2+dy][x2+dx] or 0 for x2 in range(width)] for y2 in range(height)] for (dx,dy) in [(dx,dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]]) for x1 in range(width)] for y1 in range(height)][y][x]== 3 or ([[sum(array[y3][x3] for array in [[[((-1<x4+dx<width) and (-1<y4+dy<height)) and initial_array[y4+dy][x4+dx] or 0 for x4 in range(width)] for y4 in range(height)] for (dx,dy) in [(dx,dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]]) for x3 in range(width)] for y3 in range(height)][y][x] == 2 and initial_array[y][x]==1)) and 1 or 0 for x in range(width)] for y in range(height)]Well, I never said it was readable. Now we can set the initial array to be the new array and loop however many times. Below is some code that will display the movement of a glider over 10 ticks of the clock. I warn you though: it's not quick.
(width, height) = (6, 6)
initial_array = [[0 for x in range(width)] for y in range(height)]
initial_array[0][1] = 1
initial_array[1][2] = 1
initial_array[2][0] = 1
initial_array[2][1] = 1
initial_array[2][2] = 1
for t in range(10):
initial_array=[[([[sum(array[y1][x1] for array in [[[((-1<x2+dx<width) and (-1<y2+dy<height)) and initial_array[y2+dy][x2+dx] or 0 for x2 in range(width)] for y2 in range(height)] for (dx,dy) in [(dx,dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]]) for x1 in range(width)] for y1 in range(height)][y][x]== 3 or ([[sum(array[y3][x3] for array in [[[((-1<x4+dx<width) and (-1<y4+dy<height)) and initial_array[y4+dy][x4+dx] or 0 for x4 in range(width)] for y4 in range(height)] for (dx,dy) in [(dx,dy) for dx in [-1,0,1] for dy in [-1,0,1] if (dy!=0 or dx!=0)]]) for x3 in range(width)] for y3 in range(height)][y][x] == 2 and initial_array[y][x]==1)) and 1 or 0 for x in range(width)] for y in range(height)]
print "_"*18
for line in initial_array:
print lineThis is basically the same code as at the top of his article, only with a more interesting input, an output every iteration, clearer variable names, and defined width and height variables (which you can replace by len(initial_array[0]) and len(initial_array) respectively).
Conclusions
My attempt clearly isn't as compact as with APL. This isn't surprising given that APL was designed to apply functions to matrices in an efficient and compact way, whereas Python is designed to be readable. Even so, I'm impressed that I could get as far as I did. Maybe others can improve further. Although this experiment demonstrates that list comprehensions can generate horribly unreadable and inefficient code, I hope it also demonstrates, that in moderation (i.e. the first steps of this process), they can be used to write cleaner code.
Comments (7)
Otter on 18 Nov 2010, 5:11 p.m.
Brilliant!
Shawn Driscoll on 14 May 2012, 3:30 p.m.
This might be a shorter version.
http://www.shonner.com/shawndriscoll/images/python_life.jpg
Anonymous on 23 Apr 2013, 1:35 a.m.
A little shorter with your code
while 1: a=[[([[sum(b[y1][x1] for b in [[[((-1
Mike Bell on 12 Sep 2013, 4:33 a.m.
I know I'm about 3 years late, but I saw this and wondered if I could do better.
Here's mine:
a=[[int(sum([a[x+d][y+e]if-1<x+d<len(a)and-1<y+e<len(a[0])else 0 for e in(-1,0,1)for d in(-1,0,1)])-a[x][y]in((2,3)if a[x][y]else(3,)))for y in range(len(a[0]))]for x in range(len(a))]
don't think it can get much smaller, lol
BingsF on 21 Feb 2016, 10:08 a.m.
To make it really one line:
while True: a =[[0 for x in range(8)] for y in range(8)] if 'a' in locals() else [[([[sum(b[y1][x1]
mar77i on 28 Nov 2016, 11:03 a.m.
I actually got it down in size yet again:
a = [[[int(s+(a[y][x] and s==2)==3) for s in [sum([a[(y+n//3-1)%len(a)][(x+n%3-1)%len(a[0])]for n in range(9)if n!=4])]][0]for x in range(len(a[0]))] for y in range(len(a))]
I abbreviated the whole 23/3 rule into the first int(), and the toroidal moore neighborhood in the sum(), by using only n as a counter and creating the offsets using a div/mod pair. I also avoided repetition of the neighborhood count by inserting a once-looping "for s in", and taking the first element thereof in the outer scope.
s: neighborhood sum, n: neighborhood index (0-9 with 4 excluded)
mar77i on 28 Nov 2016, 11:08 a.m.
a=[[[int(s+(a[y][x] and s==2)==3) for s in [sum([a[(y+n//3-1)%len(a)][(x+n%3-1)%len(a[0])]for n in range(9)if n!=4])]][0]for x in range(len(a[0]))] for y in range(len(a))]