I have written code to take a cellular automaton configuration and determine a state that could have existed one time-step prior, according to Game of Life rules.
The algorithm goes roughly as follows:
- Take a cell, and iterate through every possible 3x3 configuration of cells that could've evolved into this cell after one time step.
- If the configuration does not produce the correct state (i.e. live or dead), check the next.
- If the configuration does not overlap with the other proposed prior configurations in the area, check the next.
- If no configurations work, go back to the prior cell and recurse: continue iterating through possible cell configurations.
- If the configuration fits, put it on the grid. Go to the next cell.
from collections import deque
from itertools import product
class CellularAutomaton:
configs = tuple(product((False, True), repeat=9))
def __init__(self, rows, cols, fill=None):
self.rows = rows
self.cols = cols
self.size = rows * cols
"""Cells can be False=dead, True=alive, None=undetermined. """
self.g = [[fill] * rows for _ in range(cols)]
def __getitem__(self, i):
r, c = i
return self.g[r % self.rows][c % self.cols]
def __setitem__(self, i, v):
r, c = i
self.g[r % self.rows][c % self.cols] = v
def __eq__(self, t):
"""
Compare two automata.
"""
return all(self[i] == t[i] for i in self)
def __iter__(self):
yield from product(range(self.rows), range(self.cols))
def neighborhood(self, i):
"""
Return the indices of all adjacent cells and cell itself.
"""
r, c = i
return (
(r-1,c-1), (r-1,c), (r-1,c+1),
(r ,c-1), (r ,c), (r ,c+1),
(r+1,c-1), (r+1,c), (r+1,c+1)
)
def index(self, i):
"""
Converts 1-dimensional indices.
"""
return (i // self.cols, i % self.cols)
def reverse(self):
"""
Return a new CellularAutomaton that evolves into this one after
one evolution.
"""
rows, cols, size = self.rows, self.cols, self.size
ret = CellularAutomaton(rows, cols)
"""Hypothesis: a stack to keep track of which cell is using which
configuration. """
hypo = deque([iter(CellularAutomaton.configs)], maxlen=size+1)
"""A stack to keep track of which cells are changed with each
configuration so if a configuration needs to be undone, we know which
cells to revert. """
undo = deque([] , maxlen=size)
while len(hypo)-1 < size:
i = ret.index(len(hypo)-1)
for cfg in hypo[-1]:
nbhd = ret.neighborhood(i)
"""Does the configuration produce the right state? """
if self[i] != ((cfg[4] and sum(cfg) in (3, 4)) or (not cfg[4] and sum(cfg) == 3)):
continue
"""Does the configuration fit on the automaton with previously-
decided configurations? """
if any(ret[n] != c and ret[n] is not None for n, c in zip(nbhd, cfg)):
continue
"""Only add undetermined cells to the undo stack because all
other cells' states were determined by other nearby
configurations. """
undo.append(tuple(n for n in nbhd if ret[n] is None))
"""Update the return board with the configuration. """
for n, c in zip(nbhd, cfg):
ret[n] = c
hypo.append(iter(CellularAutomaton.configs))
break
else:
"""We iterated through every configuration and none of them
worked. We need to go back to a previous cell. """
hypo.pop()
for c in undo.pop():
ret[c] = None
continue
return ret
def forward(self):
"""
Evolve one time-step forward.
"""
rows, cols = self.rows, self.cols
ret = CellularAutomaton(rows, cols)
for i in self:
nbhd = sum(self[j] for j in self.neighborhood(i)) - self[i]
ret[i] = True if nbhd == 3 else (self[i] if nbhd == 2 else False)
return ret
"""This is a smiley face. """
end = CellularAutomaton(10, 10, False)
end[2,2] = 1
end[2,3] = 1
end[7,2] = 1
end[7,3] = 1
end[1,5] = 1
end[2,6] = 1
end[3,7] = 1
end[4,7] = 1
end[5,7] = 1
end[6,7] = 1
end[7,6] = 1
end[8,5] = 1
assert end == end.reverse().forward(), "Not equal."
An important constraint of this problem is that I intend to use it on automata with dimensions potentially on the order of thousands of cells, so I don't believe I can use actual recursion here due to memory constraints. Instead, I am faking recursion with stacks.
I am looking for advice to make this code faster. It takes several minutes to reverse some configurations on my machine by just a single time-step. I am more concerned here about the result than the process, so I welcome algorithm changes, language/library recommendations, or even large-scale changes such as different automata systems, different boundary conditions, or other deviations from the project scope.
I am not very interested in style or organization improvements, but will welcome comments on these matters nonetheless.
