7
\$\begingroup\$

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 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?

\$\endgroup\$
4
\$\begingroup\$

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)))
\$\endgroup\$
2
\$\begingroup\$

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).

Other advice:

  • 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)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.