# Simulation to find max population of R-pentominos in Game of Life

I'm brand new to Python and I feel my code is really like what coded in Java.

I try to practice python by small problem and that is to find the maximum population of R-pentomino. Wiki says:

During this early research, Conway discovered that the R-pentomino failed to stabilize in a small number of generations. In fact, it takes 1103 generations to stabilize, by which time it has a population of 116 and has fired six escaping gliders (these were the first gliders ever discovered).

So I write this code:

from sets import Set

__author__ = 'Sayakiss'

dx = [0, 0, 1, -1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, -1, 1, 1, -1]

def is_ng_alive(x, y, original_set):
cnt = 0;
for i in range(len(dx)):
nx = x + dx[i]
ny = y + dy[i]
if (nx, ny) in original_set:
cnt += 1
if (x, y) in original_set:
if cnt in [2, 3]:
return True
else:
if cnt == 3:
return True
return False

def sim(original_set):
new_set = Set()
for (x, y) in original_set:
for i in range(len(dx)):
nx = x + dx[i]
ny = y + dy[i]
if is_ng_alive(nx, ny, original_set):
if is_ng_alive(x, y, original_set):
return new_set

def print_cell_set(cell_set, x_size=10, y_size=10):
for x in range(-x_size, x_size):
for y in range(-y_size, y_size):
if (x, y) in cell_set:
print '*',
else:
print '.',
print ''

cell_set = Set([(0, 1), (0, 2), (1, 0), (1, 1), (2, 1)])
max_size = 0
max_gen = 0
for i in range(1500):
cell_set = sim(cell_set)
gen_size = len(cell_set)
if gen_size > max_size:
max_size = gen_size
max_gen = i + 1
print str(i + 1) + " generation population: " + str(gen_size)

print str(max_gen) + "-" + str(max_size)


Output of my code should be 821-319. It means the maximum population is 319 and occurs in 821-th generation. I'm quite sure it's correct because my friend's code gives the same answer.

Could anyone give me some suggestions about my code?

# Global

• Python has deprecated sets, instead use the __builtins__.set. This allows us to add some nice sugar to your code, for creating the set.

cell_set = {(0, 1), (0, 2), (1, 0), (1, 1), (2, 1)}

• Your names are good, but a few 'let you down', as I don't know what sim means, I assume simulate.

• You may want to use str.format to format strings for print. This is as it will be simpler to add strings and numbers.

print str(i + 1) + " generation population: " + str(gen_size)
print "{} generation population: {}".format(i + 1, gen_size)

• You can use Python's max to find the maximum.

max([1, 2, 3]) # 3
max([(1, 3), (2, 2), (3, 1)]) # (3, 1)


As you mutate cell_set you will have to use a full-fledged generator, rather than a generator comprehension. Where you yield (gen_size, i).

def generate_cells(cell_set, generations=1500):
for i in range(1, generations + 1):
cell_set = sim(cell_set)
print "{} generation population: {}".format(i, len(cell_set))
yield len(cell_set), i

max_size, max_gen = max(generate_cells(cell_set))


In my opinion that is much easier to understand.

• Python has a dedicated style guide called PEP8, it states that constants, dx and dy, should be upper-snake case. So DX and DY.

# is_ng_alive

• You should use zip, to loop through both dx and dy.

for ax, ay in zip(dx, dy):
if (x + ax, y + ay) in original_set:
cnt += 1

• You can use sum and a generator comprehension to not have to add up cnt manually.

cnt = sum((x + ax, y + ay) in original_set for ax, ay in zip(dx, dy))

• You can simplify your logic, as if cnt is 3 it will return true. Then you can just return the boolean from the new truth statement.

if cnt == 3:
return True

return (x, y) in original_set and cnt == 2

• I mistakenly thought that zip(dx, dy) would be a line. Instead you may want the algorithm to be 'more square', which would be:

for ax in dx:
for ay in dy:
(x + ax, y + ay)


# sim

Using the changes from above you can change the for loop with ease. However to make things easier to read you may want to make (x + ax, y + ay) for ax, ay in zip(dx, dy) a function.

def new_coords(x, y):
return ((x + ax, y + ay) for ax, ay in zip(dx, dy))

for item in ((nx, ny) for (nx, ny) in new_coords(x, y)
if is_ng_alive(nx, ny, original_set)):


# print_cell_set

This is very bad on performance, instead you would want to build a string, and then limit prints. You can do this with another list comprehension, a turnery and str.join.

for x in range(-x_size, x_size):
print ''.join('*' if (x, y) in cell_set else '.' for y in range(-y_size, y_size))


Overall you have nice code, you just missed a few things to improve clarity.

And I got:

__author__ = 'Sayakiss'

DX = [0, 0, 1, -1, 1, -1, 1, -1]
DY = [1, -1, 0, 0, -1, 1, 1, -1]

def new_coords(x, y):
return ((x + ax, y + ay) for ax, ay in zip(DX, DY))

def is_ng_alive(x, y, original_set):
cnt = sum((nx, ny) in original_set for nx, ny in new_coords(x, y))
if cnt == 3:
return True

return (x, y) in original_set and cnt == 2

def sim(original_set):
new_set = set()
for (x, y) in original_set:
for item in ((nx, ny) for (nx, ny) in new_coords(x, y)
if is_ng_alive(nx, ny, original_set)):
if is_ng_alive(x, y, original_set):
return new_set

def print_cell_set(cell_set, x_size=10, y_size=10):
for x in range(-x_size, x_size):
print ''.join('*' if (x, y) in cell_set else '.' for y in range(-y_size, y_size))

def generate_cells(cell_set, generations=1500):
for i in range(1, generations + 1):
cell_set = sim(cell_set)
print "{} generation population: {}".format(i, len(cell_set))
yield len(cell_set), i

cell_set = {(0, 1), (0, 2), (1, 0), (1, 1), (2, 1)}
print "{1}-{0}".format(*max(generate_cells(cell_set)))


Terminologies I used here may not be right, and sorry for possible poor expression.

A different evolution scheme could be used instead.
As is implied by the rules, A cell with no neighbors alive dies in the next generation. Who cares about people left alone?

• Traversing alive cells once, add the contribution to its neighborhood for each cell.
• Then we got cells that have alive neighbors.
• Apply survival test on them to execute the evolution.

This way we can avoid duplicate computations for dead bits that have multiple neighbors alive (and slightly simplify the code).

• As is supposed by Joe Wallis, dx and dy can be replaced by [(-1, -1), ..., (1, 1)]. BTW, assignments for nx and ny can be modified as nx, ny= x + dx[i], y + dy[i] . (If you are not familiar with this, see Sequence Unpacking in python.
• The enumerating neighbors operation should be wrapped as a function.
• Keyword elif could be used instead of nested else-if.

Here is my solution without the visualization part (Ignore naming issues, please):

from collections import Counter

def neighbor(x, y):
N = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
return [(x+i, y+j) for (i, j) in N]

def evolve(c, heat, life):
if heat in (2, 3) and c in life:
return True
elif heat == 3 and c not in life:
return True
return False

def evolution(life):
heats = Counter()
for (x, y) in life:
for cell in neighbor(x, y):
heats[cell] += 1
return {cell for (cell, heat) in heats.items() if evolve(cell, heat, life)}

life = {(0, 0), (0, 1), (0, -1), (-1, 0), (1, 1)}
history = []
for _ in range(1200):
history.append(len(life))
life = evolution(life)

prosperity = max(history)
print("Maximum population %s achieved at generation %s"\
% (prosperity, history.index(prosperity)))