Rule 110

from tys import progress, frame, probe

def simulate(cfg: dict):

    width = cfg["width"]
    steps = cfg["steps"]

    state = 1 << (width // 2)
    mask = (1 << width) - 1

    rule = [0, 1, 1, 1, 0, 1, 1, 0]

    def row_from_state(s: int) -> list[int]:
        return [1 if (s >> (width - 1 - i)) & 1 else 0 for i in range(width)]

    rows: list[list[int]] = []
    for step in range(steps):
        row = row_from_state(state)
        rows.append(row)
        probe("ones", step, sum(row))
        progress(int(100 * (step + 1) / steps))

        new_state = 0
        for i in range(width):
            left = (state >> (width - i)) & 1 if i > 0 else 0
            center = (state >> (width - 1 - i)) & 1
            right = (state >> (width - 2 - i)) & 1 if i < width - 1 else 0
            index = (left << 2) | (center << 1) | right
            if rule[index]:
                new_state |= 1 << (width - 1 - i)
        state = new_state & mask

    row = row_from_state(state)
    rows.append(row)
    frame(0, rows)
    ones = sum(row)
    return {"ones": ones}


def requirements():
    return {
        "builtin": ["micropip", "pyyaml"],
        "external": []
    }