Le 12/04/2020 à 23:40, Paul Rubin a écrit :
You might have heard by now that John Horton Conway died yesterday at
age 82, of complications from the SARS-Cov2 aka Corona virus. Among his
many cool accomplishments was inventing the Game of Life, which was one
of my first exercises as a beginning programmer in middle school. That
program used the naive approach of representing the game board as a 2-d
array and scanning all its cells at each generation.
Far better programmers and mathematicians than I am worked on
fantastically optimized Life programs and made wonderful discoveries
about Life patterns. See https://conwaylife.com for a sample of that.
I never got too heavily into Life programming myself, but a year or two
ago I thought of a quite simple way to write a Life program whose
running time at each generation was linear in the number of active cells
(unlike my first program that I had written as a kid, whose running time
and space consumption was potentially unbounded even with a fixed
population).
In Conway's honor I'm appending the simple program (28 lines of Python)
below.
RIP, Prof. Conway.
================================================================
#!/usr/bin/python3
from itertools import chain
def adjacents(cell): # generate coordinates of cell neighbors
x, y = cell # a cell is just an x,y coordinate pair
return ((x+i,y+j) for i in [-1,0,1] for j in [-1,0,1] if i or j)
def update(living): # living = currently living set of cells
def ncount(cell): # number of living neighbors of cell
return sum(1 for c in adjacents(cell) if c in living)
def uninhabitable(cell): # check if occupied cell should die
return not(2 <= ncount(cell) <= 3)
def fertile(cell): # check if empty cell should have a birth
return ncount(cell) == 3
# get set of cells (living or not) that are adjacent to some living cell
neighbors = set(chain.from_iterable(adjacents(c) for c in living))
frontier = neighbors - living # the empty cells adjacent to living ones
births = set(filter(fertile, frontier)) # are where births can happen
deaths = set(filter(uninhabitable, living))
return (living - deaths) | births
if __name__ == '__main__':
r = set([(0,0),(0,1),(0,2),(1,2),(-1,1)]) # R-pentomino
for i in range(1,1110): # it should stabilize at generation 1104
print (i,len(r)) # show generation number and population
r = update(r)
I found in a Game Of Life program (not mine) a very clever method to
update a board of cell as a whole
It worths seeing it.
X is a numpy 2D ndarray
def evolve(X):
''' Evolves a board of Game of Life for one turn '''
# Dead cells as a boundary condition
# Count neighbours
# Alive if 3 neighbours or 2 neighbours and already alive
Xi = X.astype(int)
neigh = np.zeros(Xi.shape)
neigh[1:-1,1:-1] = (Xi[:-2,:-2] + Xi[:-2,1:-1] + Xi[:-2,2:] +
Xi[1:-1,:-2] + Xi[1:-1,2:] +
Xi[2:,:-2] + Xi[2:,1:-1] + Xi[2:,2:])
return np.logical_or(neigh==3,np.logical_and(Xi==1,neigh==2))
--
https://mail.python.org/mailman/listinfo/python-list
