# Conway's Game of Life - Optimization of Python Program

Hey Guys,

Recently, someone shared a few problems about Conway's Game of Life, which I tried to simulate in Python. I'm still relatively new to Python and have no clue how I could optimize the program.

If you have tried simulating this, could you also post your code?

Thanks a lot!

Code:

#---------------------------------------------------------------------------
# Name:        Conway's Game of Life - A Simulation
# Author:      G Raj Magesh
# Created:     29-01-2014
# Copyright:   (c) G Raj Magesh 2014
#
# m = rows
# n = columns
# l = list of 1s and 0s from left to right
# c = counter
#---------------------------------------------------------------------------
def ReturnList(m, n, l):
newlist = []
for x in range(0, m*n):
c = 0
if x > n-1:
if l[x - n] == 1:
c += 1
if x < m*n-n:
if l[x + n] == 1:
c += 1
if x%n != 0:
if l[x-1] == 1:
c += 1
if (x + 1) % n != 0:
if l[x + 1] == 1:
c += 1
if x > n - 1 and x%n != 0:
if l[x - n - 1] == 1:
c += 1
if x > n - 1 and (x + 1) % n != 0:
if l[x - n + 1] == 1:
c += 1
if x < m*n - n and x%n != 0:
if l[x + n - 1] == 1:
c += 1
if x < m*n - n and (x + 1) % n != 0:
if l[x + n + 1] == 1:
c += 1
if l[x] == 1:
if c == 2 or c == 3:
newlist.append(1)
else:
newlist.append(0)
else:
if c == 3:
newlist.append(1)
else:
newlist.append(0)
return newlist

def PrintBoard(m, n, l):
c = 0
for x in l:
if c%n == 0:
print "[" + str(x),
elif (c+1)%n == 0:
print str(x) + "]"
else:
print str(x),
c += 1

def IterateXTimes(m, n, l, X):
c = 0
while c <= X:
print "------- Iteration " + str(c) + " -------"
PrintBoard(m, n, l)
l = ReturnList(m, n, l)
c += 1

IterateXTimes(4, 3, [1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0], 5)


Output:

------- Iteration 0 -------
[1 0 0]
[0 0 1]
[0 1 0]
[0 1 0]
------- Iteration 1 -------
[0 0 0]
[0 1 0]
[0 1 1]
[0 0 0]
------- Iteration 2 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 3 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 4 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 5 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]


Note by Raj Magesh
5 years, 8 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I've been hoping someone else would step in and help out, but I guess I can get it started since I spend a decent amount of time optimizing stuff here at Brilliant.

The first rule of optimization is to be able to measure the impact of changes that you make.

If you are on a linux or mac machine you should be able to use the time command from the shell when running the program to get a rough estimate of the amount of time your program will take to run overall:

time python ./game_of_life.py
------- Iteration 0 -------
[1 0 0]
[0 0 1]
[0 1 0]
[0 1 0]
------- Iteration 1 -------
[0 0 0]
[0 1 0]
[0 1 1]
[0 0 0]
------- Iteration 2 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 3 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 4 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 5 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]

real    0m0.023s
user    0m0.012s
sys 0m0.008s


After you have the overall number, it's usually good to start digging down to see what exact parts take the most time (especially when the number is relatively small such as in this case, where you'd get different numbers depending on what else your computer is doing in the background, etc).

Modifying the code in these ways will give a tiny bit more insight:

import time
import pprint
from collections import defaultdict


replace IterateXTimes:

def IterateXTimes(m, n, l, X):
timers = defaultdict(float)
c = 0
timers['last'] = time.time()
while c <= X:
timers['last'] = time.time()

print "------- Iteration " + str(c) + " -------"
timers['iteration_print'] += time.time() - timers['last']
timers['last'] = time.time()

PrintBoard(m, n, l)
timers['print_board'] += time.time() - timers['last']
timers['last'] = time.time()

l = ReturnList(m, n, l)
timers['return_list'] += time.time() - timers['last']
timers['last'] = time.time()

c += 1
pprint.pprint(dict(timers))


Which then will add this to the output:

{'iteration_print': 8.058547973632812e-05,
'print_board': 0.00019812583923339844,
'return_list': 0.00012993812561035156}


So already, we notice that surprisingly, printing the board takes longer that computing the next level.

We can get a pretty good speedup on that function by converting the list to a 2d array and then just printing it out directly to reduce the amount of int-> string conversions as well as separate print functions:

def PrintBoard(m, n, l):
board = [l[x*n:x*n+n] # slice the board up into a matrix
for x
in xrange(m)]
print board

{'iteration_print': 9.393692016601562e-05,
'print_board': 9.703636169433594e-05,
'return_list': 0.0001289844512939453}


As with most things, I'm pretty confident that if it's worth it for you to do (optimization for the sake of optimization isn't usually a good idea, it should be because you will be able to work more efficiently or use the program in a different and better way), there are more optimizations that could be had, but I'll let you try to take it from here. One suggestion would be to see if you can figure out how to get your algorithm to work with a matrix so that you can eliminate the conversion at print time (and it may or may not also allow you to speed up the ReturnList function).

Another thing to note is that it is sorta hard to see "real" timings when you deal with small data-sets, to be more scientific, you should probably increase the board size to something closer to what you'll actually run it on and then also increase the number of iterations (in the main loop and perhaps also perform several runs of the entire program and average times across the different runs (or at least ignore the really high or really low results)).

And finally: if you are going to be running this with a main loop iteration of thousands, printing the board over and over again to the standard output could get costly and it may be better to skip printing all of them unless you need to inspect each and every one of them afterwards, or append to a file (either straight from python or by telling the command line to send the output to a file: python ./game_of_life.py > ./game_of_life_results.txt)

Staff - 5 years, 8 months ago