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 and sum(cfg) in (3, 4)) or (not cfg 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.