JH Conway memorial Life program
ast
ast at invalid
Tue Apr 28 08:39:41 EDT 2020
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))
More information about the Python-list
mailing list