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):
                new_set.add((nx, ny))
        if is_ng_alive(x, y, original_set):
            new_set.add((x, y))
    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 populat

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)):
    new_set.add(item)

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)):
            new_set.add(item)
        if is_ng_alive(x, y, original_set):
            new_set.add((x, y))
    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)))

StackExchange Code Review Q#114033, answer score: 4