Game of life python code11/19/2023 Let's call the tuple for cells 2, 3, 6, 7, 10, 11 the "right_key" of cell 6. That's 8 possible configurations instead of 512, a 98% reduction. Given what is known, there are at most 8 possibilities for cells 4, 8, and 12. When pushing possible configurations for cell 7, we know the current state of cell 7 and the proposed configuration for cell 6. When cell 6 has a possible configuration, it has proposed values for cells 2, 3, 6, 7, 10 and 11 which are in the neighborhood of cell 7. This can be used to further prune the search space. The neighborhoods of adjacent cells overlap. With the simple changes above, the code takes about 2.3 seconds.about 33% faster! Reduce it some more. On my machine, the original code takes about 3.6 seconds to run the example provided. Hypo.append(iter(CellularAutomaton_A.configs])) Lastly, after updating the return board with the configuration, we push on the stack the possible configurations for the next cell based on it's current state: nr, nc = ret.index(len(hypo)) The test to make sure the chosen config produces the right state can be eliminated, because it's precomputed in the way configs was built. Then, in reverse(), the first thing to push on the hypo stack, are the configs that could result in cell: hypo = deque(])], maxlen=size+1) Organize configs so that the configurations that would result in a live cell are in configs and those that would result in a dead cell are in configs: class CellularAutomaton:įor t in product((False, True), repeat=9): Similarly, if the cell is dead, there are only 386 possible configurations for the previous generation, a 25% reduction. There are only 126 of those configurations, so only considering those would reduce the search space by about 75%. However, if the cell is currently alive, you know that the previous configuration must have had 3 or 4 live cells. I am not very interested in style or organization improvements, but will welcome comments on these matters nonetheless.įor each cell, it looks like the code always considers all 512 possible 9x9 configurations for the previous generation. 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. It takes several minutes to reverse some configurations on my machine by just a single time-step. I am looking for advice to make this code faster. Instead, I am faking recursion with stacks. Ret = True if nbhd = 3 else (self if nbhd = 2 else False)Īssert end = end.reverse().forward(), "Not equal."Īn 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. Nbhd = sum(self for j in self.neighborhood(i)) - self """We iterated through every configuration and none of them """Update the return board with the configuration. Undo.append(tuple(n for n in nbhd if ret is None)) Other cells' states were determined by other nearby """Only add undetermined cells to the undo stack because all If any(ret != c and ret is not None for n, c in zip(nbhd, cfg)): """Does the configuration fit on the automaton with previously. If self != ((cfg and sum(cfg) in (3, 4)) or (not cfg and sum(cfg) = 3)): """Does the configuration produce the right state? """ """A stack to keep track of which cells are changed with eachĬonfiguration so if a configuration needs to be undone, we know which """Hypothesis: a stack to keep track of which cell is using which Rows, cols, size = self.rows, ls, self.size Return a new CellularAutomaton that evolves into this one after Return the indices of all adjacent cells and cell itself. Yield from product(range(self.rows), range(ls)) """Cells can be False=dead, True=alive, None=undetermined. Go to the next cell.Ĭonfigs = tuple(product((False, True), repeat=9))ĭef _init_(self, rows, cols, fill=None): If the configuration fits, put it on the grid.If no configurations work, go back to the prior cell and recurse: continue iterating through possible cell configurations.If the configuration does not overlap with the other proposed prior configurations in the area, check the next.If the configuration does not produce the correct state (i.e.Take a cell, and iterate through every possible 3x3 configuration of cells that could've evolved into this cell after one time step.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.
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |