Cellular Automata

CellularAutomata.md

Cellular Automata

Whilst being very bored recently I started playing around with simulating cellular automata once again. But to challenge myself a bit more than usual I set three specific limitations that made this a bit harder than I was used to:

1. The simulation functions should be able to handle n-dimensional rules and states.
2. The rules should be given as integers.
3. The state should be represented as an integer, making use of the fact that the whole state consists of a n-dimensional array of booleans that can be flattened.

Another additional burden I put on to myself was to implement two unique styles of rules:

1. Pattern based rules, such as the popular 110 or 30.
2. Neighbor count based rules, such as conway's game of life.

This implementation is able to simulate the rule integer 6152, i.e. Conway's Game of Life:

simulations.py

from typing import Iterator, Tuple
from random import randrange
from functools import reduce
from itertools import product as iter_product


__all__ = ("count", "pattern",)


def product(*scalars: int) -> int:
    return reduce(lambda acc, scalar: acc * scalar, scalars, 1)


def count(
    dimensions: Tuple[int, ...],
    rule: int,
    neighborhood_radius: int = 1,
    initial_state: int = -1,
    iterations: int = -1,
) -> Iterator[int]:
    """Simulate nD cellular automata based on neighbor counting rules.
    
    Parameters
    ----------
    dimensions : Tuple[int, ...]
        The dimensions of the state to simulate.
    rule : int
        The rule to simulate in rule integer format [1].
    neighborhood_radius : int
        The radius of the Moors-Neighborhood to count the neighbors in. (the default is 1)
    initial_state : int
        The state to start the simulation with. (the default is -1, which forces the
        random generation of an initial state)
    iterations : int
        The number of iterations to simulate. (the default is -1, which causes the
        simulation to run indefinitely)

    Yields
    ------
    state : int
        The current state of the simulation.
        
    References
    ----------
    .. [1] https://www.conwaylife.com/wiki/Rule_integer
    """

    n_neighbors = ((2 * neighborhood_radius + 1) ** len(dimensions)) - 1
    b = rule >> 0                 & (2 ** (n_neighbors + 2)) - 1
    s = rule >> (n_neighbors + 1) & (2 ** (n_neighbors + 2)) - 1

    state_size = product(*dimensions)
    slice_sizes = [product(*dimensions[:j]) for j in range(len(dimensions))]
    max_state = 2 ** state_size

    if initial_state < 0:
        initial_state = randrange(max_state)

    iteration, state = 0, initial_state
    yield state
    while iterations < 0 or iteration < iterations:
        iteration += 1
        state = sum(
            (
                b * (~state >> i & 1) +
                s * ( state >> i & 1)
                >> sum(
                    state >> sum(
                        (
                            i
                            // slice_sizes[j]
                            + offset
                        )
                        % dimensions[j]
                        * slice_sizes[j]
                        for j, offset in enumerate(offsets)
                    ) & 1
                    for offsets in iter_product(*(
                        range(-neighborhood_radius, neighborhood_radius+1)
                        for _ in dimensions
                    ))
                    if any(offset != 0 for offset in offsets)
                )
                & 1
            ) << i
            for i in range(state_size)
        ) & max_state - 1
        yield state


def pattern(
    dimensions: Tuple[int, ...],
    rule: int,
    neighborhood_radius: int = 1,
    initial_state: int = -1,
    iterations: int = -1,
) -> Iterator[int]:
    """Simulate nD cellular automata based on neighbor pattern rules.
    
    Parameters
    ----------
    dimensions : Tuple[int, ...]
        The dimensions of the state to simulate.
    rule : int
        The rule to simulate in wolfram code format [1].
    neighborhood_radius : int
        The radius of the Moors-Neighborhood to match the patterns in. (the default is 1)
    initial_state : int
        The state to start the simulation with. (the default is -1, which forces the
        random generation of an initial state)
    iterations : int
        The number of iterations to simulate. (the default is -1, which causes the
        simulation to run indefinitely)

    Yields
    ------
    state : int
        The current state of the simulation.
        
    References
    ----------
    .. [1] Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata".
       Reviews of Modern Physics. 55: 601–644. Bibcode:1983RvMP...55..601W.
    """

    patterns = {
        i: rule >> i & 1
        for i in range(2 ** ((2 * neighborhood_radius + 1) ** len(dimensions)))
    }

    state_size = product(*dimensions)
    slice_sizes = [product(*dimensions[:j]) for j in range(len(dimensions))]
    max_state = 2 ** state_size - 1

    if initial_state < 0:
        initial_state = randrange(max_state + 1)

    iteration, state = 0, initial_state
    yield state
    while iterations < 0 or iteration < iterations:
        iteration += 1
        state = sum(
            patterns[(
                sum(
                    (state >> sum(
                        (
                            i
                            // slice_sizes[k]
                            + offset
                        )
                        % dimensions[k]
                        * slice_sizes[k]
                        for k, offset in enumerate(offsets)
                    ) & 1) << j
                    for j, offsets in enumerate(iter_product(*(
                        range(-neighborhood_radius, neighborhood_radius+1)
                        for _ in dimensions
                    )))
                )
            )] << i
            for i in range(state_size)
        ) & max_state
        yield state