Here is my implementation of John Conway's Game of Life in Python:
from copy import deepcopy
def countSurrounding(board, row, cell):
SURROUNDING = ((row - 1, cell - 1),
(row - 1, cell ),
(row - 1, cell + 1),
(row , cell - 1),
(row , cell + 1),
(row + 1, cell - 1),
(row + 1, cell ),
(row + 1, cell + 1))
count = 0
for row, cell in SURROUNDING:
if isInRange(board, row, cell) and board[row][cell] == True:
count += 1
return count
def isInRange(board, row, cell):
return 0 <= row < len(board) and 0 <= cell < len(board[0])
def nextGeneration(board):
nextBoard = deepcopy(board)
for row in range(len(board)):
for cell in range(len(board[0])):
if board[row][cell] == True and countSurrounding(board, row, cell) not in (2, 3):
nextBoard[row][cell] = False
elif board[row][cell] == False and countSurrounding(board, row, cell) == 3:
nextBoard[row][cell] = True
return nextBoard
def printBoard(board):
for row in board:
for cell in row:
if cell == True:
print("#", end = "")
else:
print(".", end = "")
print()
print()
def main():
board = [[False, False, False, False, False, False, False, False, False],
[False, False, False, True , False, False, False, False, False],
[False, True , False, True , False, False, False, False, False],
[False, False, True , True , False, False, False, False, False],
[False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False]]
for i in range(10):
printBoard(board)
board = nextGeneration(board)
main()
Can anyone suggest any improvements to optimize my code?
Thanks
2 Answers 2
1. Comments on your code
You have no guard on the call to
main(). This makes it harder to debug the program using the interactive interpreter: as soon as the module is imported, it callmain()and starts running. Better to put a guard in place:if __name__ == '__main__': main()This program consists of persistent state (the board) together with a set of operations on that state. It is therefore crying out to be implemented in the form of a class. See section 3 for how you might do this.
It's horribly tedious to watch the progress of the cellular automaton coming out on the terminal. This is the kind of program that really requires the use of a graphics toolkit like PyGame to draw and animate it. See section 4 for how you might do this.
It's almost never necessary to compare values explicitly against
TrueorFalse. Instead of:if cell == True:you can write:
if cell:and instead of:
if board[row][cell] == False:you can write:
if not board[row][cell]:Giant blocks of values like this are hard to input and hard to check.
board = [[False, False, False, False, False, False, False, False, False], [False, False, False, True , False, False, False, False, False], [False, True , False, True , False, False, False, False, False], [False, False, True , True , False, False, False, False, False], [False, False, False, False, False, False, False, False, False], [False, False, False, False, False, False, False, False, False], [False, False, False, False, False, False, False, False, False], [False, False, False, False, False, False, False, False, False], [False, False, False, False, False, False, False, False, False]]It would be better to draw a "picture" and write a bit of code to decode it into the values you want:
glider = '''..o o.o .oo'''See the
pastemethod in section 3 below for how to decode this kind of picture.
2. Suggestions
When you have a program like this that operates on a two-dimensional array of cells, it often simplifies matters if you represent the two-dimensional array as a one-dimensional list. Then a cell can be represented by a single number instead of a pair; lookups are of the form
array[cell]instead ofarray[x][y], and adjacent cells may be found by simple arithmetic operations.It's a feature of the game of Life that, most of the time, very few cells are changing. You can take advantage of this fact to speed up the update operation. Instead of examining all cells to see if they need updating, maintain a set of cells that need to be looked at. Whenever you change a cell from live to dead or vice versa, add it, and all its neighbours, to the set. In the update operation, look only at those cells that were added to the set in the course of the previous update operation.
This means that you don't have to copy out the whole world each update: you only need a copy of the information (liveness and neighbour count) relating to the cells in the set.
Similarly, rather than count the number of live neighbours each time you update a cell, you could maintain an array containing these neighbour counts and update the array whenever a cell changes.
3. Revised code
from itertools import product
class Life(object):
def __init__(self, width, height):
self.width = width
self.height = height
cells = (width + 2) * (height + 2)
self.live = [False] * cells
self.in_bounds = [True] * cells
self.neighbours = [0] * cells
for i in range(width + 2):
self.in_bounds[i] = self.in_bounds[-i] = False
for j in range(height):
k = (j + 1) * (width + 2)
self.in_bounds[k - 1] = self.in_bounds[k] = False
self.neighbourhood = [y * (width + 2) + x
for x, y in product((-1, 0, 1), repeat=2)
if x or y]
self.needs_update = set()
def cell(self, x, y):
"""Return the cell number corresponding to the coordinates (x, y)."""
return (self.width + 2) * (y + 1) + x + 1
def set(self, p, value):
"""Set cell number 'p' to 'value' (True=live, False=dead)."""
if value != self.live[p] and self.in_bounds[p]:
self.live[p] = value
self.needs_update.add(p)
adjust = 1 if value else -1
for n in self.neighbourhood:
n += p
if self.in_bounds[n]:
self.neighbours[n] += adjust
self.needs_update.add(n)
def update(self, steps=1):
"""Update the world by 'steps' generations (default: 1)."""
for _ in range(steps):
u = [(p, self.live[p], self.neighbours[p]) for p in self.needs_update]
self.needs_update = set()
for p, live, neighbours in u:
if live and not 2 <= neighbours <= 3:
self.set(p, False)
elif not live and neighbours == 3:
self.set(p, True)
def paste(self, s, x, y):
"""Decode 's' as a life pattern (o = live, any other character = dead)
and paste it with top left corner at (x, y).
"""
for j, line in enumerate(s.strip().splitlines()):
for i, char in enumerate(line.strip()):
self.set(self.cell(x + i, y + j), char == 'o')
Note:
- It would be possible to combine the
live,in_boundsandneighboursarrays into one, perhaps using bit twiddling to combine the values (the neighbour count fits into 4 bits and the other two arrays are one bit each). I've left it as three separate arrays for simplicity here.
4. Animation
Here's a quick implementation in Pygame:
import pygame
from pygame.constants import KEYUP, MOUSEBUTTONDOWN, MOUSEMOTION, QUIT, \
K_p, K_q, K_s, K_ESCAPE, K_SPACE
class PygameLife(Life):
def __init__(self, width, height,
background=pygame.Color(240, 240, 255),
foreground=pygame.Color('black'),
cell_size=4):
super(PygameLife, self).__init__(width, height)
self.background = background
self.foreground = foreground
self.cell_size = cell_size
def draw(self):
screen = pygame.display.get_surface()
screen.fill(self.background)
c = self.cell_size
for x in range(self.width):
for y in range(self.height):
if self.live[self.cell(x, y)]:
screen.fill(self.foreground, pygame.Rect(x * c, y * c, c, c))
pygame.display.flip()
def screen_cell(self, pos):
"""Return the cell number corresponding to screen position 'pos', or
None if the position is out of bounds.
"""
x, y = pos
x //= self.cell_size
y //= self.cell_size
if 0 <= x < self.width and 0 <= y < self.height:
return self.cell(x, y)
return None
def run(self):
pygame.init()
pygame.display.set_mode((self.width * self.cell_size,
self.height * self.cell_size))
paused = False
drawing = False
running = True
while running:
for event in pygame.event.get():
t = event.type
if t == QUIT or t == KEYUP and event.key in (K_q, K_ESCAPE):
running = False
elif t == KEYUP and event.key in (K_p, K_SPACE):
paused = not paused
elif t == KEYUP and event.key in (K_s,):
self.update()
elif t == MOUSEBUTTONDOWN and event.button == 1:
paused = True
p = self.screen_cell(event.pos)
drawing = not self.live[p]
self.set(p, drawing)
elif t == MOUSEMOTION and event.buttons[0]:
paused = True
self.set(self.screen_cell(event.pos), drawing)
if paused:
pygame.display.set_caption('Paused (press SPACE to run)')
else:
pygame.display.set_caption('Life')
self.update()
self.draw()
pygame.quit()
And here's Bill Gosper's glider gun in action:
>>> glider_gun = '''
........................o...........
......................o.o...........
............oo......oo............oo
...........o...o....oo............oo
oo........o.....o...oo..............
oo........o...o.oo....o.o...........
..........o.....o.......o...........
...........o...o....................
............oo......................'''
>>> p = PygameLife(100, 60)
>>> p.paste(glider_gun, 8, 1)
>>> p.run()
Glider gun
5. Advanced topic
Typical Life patterns contain many repeated objects. For example, the output of a glider gun contains many gliders, all of which behave identically. It would be nice to be able to exploit this repetition so that the evolution of a glider (or any other repeated pattern) could be computed just once, with the result appearing at all the necessary places in the world.
Making this idea precise and turning it into an algorithm leads to Bill Gosper's Hashlife.
Firstly read http://www.python.org/dev/peps/pep-0008/ and be Pythonic. You will be amazed how your code will get improve, write the new one as a new file and compare them.
This is a huge brick of False bools on your board list. You can easily and cleanly populate this list by using list comprehensions