3D Cubic Infinite Cellular Automata Challenge

Question

I'm working on a challenge involving a 3D (cubic) infinite cellular automata defined as:

• Initial State: We start with 8 cells positioned at the vertices of a cube and each cell is in one of 4 states {0: pink, 1: red, 2: green, 3: blue}.

• Growth: At each step, the cube expands by inserting new cells between each pair of existing cells. The new cell's state is determined by the sum of the states of its closest neighbors modulo 4. Note that depending on its position, a new cell has 2,4 or 8 closest neighbors (it is the 3D Moore neighborhood).

To illustrate this, here are illustration of the first steps:

Initial state

Step 1

The central node for example will be Green because it has 8 neighbours, the sum of their type is 2 (Green) + 1 (Red) + 1 (Red) + 0 (Pink) + 2 (Green) + 0 (Pink) + 3 (Blue) + 1 (Red) = 10 % 4 = 2 (Green)

Step 2

We are interested in tracking the evolution of the number of cell of each states [0, 1, 2, 3]. Here are the counts for the first steps:

• Initial: 2, 3, 2, 1
• Step 1: 6, 10, 7, 4
• Step 2: 30, 36, 31, 28
• Step 3: 196, 192, 155, 186
• Step 4: 1'162, 1'276, 1'207, 1'268

Our goal is to determine the count of each cell state at step 19. Given the exponential growth, brute force is not feasible. I was told it is possible to solve it in less than a second. Does anyone have any ideas on how to solve this problem?

Thanks in advance for your help!

Answer 1

We can create a counter for every possible "little" cube, i.e. a cube whose 8 corners are direct neighbors. So we would have one counter for a cube with the ordered corner sequence of RED, RED, GREEN, PINK, PINK, GREEN, BLUE, BLUE, and likewise distinct counters for each distinct sequence of eight colors (NB: order matters).

Every time we "expand" to the next step (generation), such a 2x2x2 cube becomes a 3x3x3 cube: we have all the information to know each of the 27 colors of that 3x3x3 cube. Then we subtract the count we had for the 2x2x2 cube (as it no longer exists as such), but then increase the counters for the eight sub-2x2x2 cubes that are contained in the 3x3x3 cube. Again, we know the relevant colors, so we know which counters to increase.

At the 19th generation (or at each generation if we wish), we can aggregate those counters per the color that the "first" corner (i.e. the one closest to the origin) has in each possible 2x2x2 cube. This way we will have counted all "nodes" in the final generation, except for the nodes that are on one of the 3 planes that are at the outer side of the complete structure and include the (last) node that is furthest away from the origin (the top-red node in the example input). For those planes we can maintain counters for the 2D faces that are on it, and at the end count the counters for the "first" corners of those faces. Again, this will account for almost every node, except for the nodes that are on the three outer 1D lines that include the (last) node that is furthest away from the origin. We can also maintain counters for those edges (which are node pairs), and aggregate them based on the first color of each pair. This leaves us with just one node that is not accounted for, which is the last node that is furthest away from the origin.

This array of counters has this number of entries:

• For counting (color combinations of) cubes: 4⁸ = 65536
• For counting (color combinations of) faces: 4⁴ = 256
• For counting (color combinations of) edges: 4² = 16
• For the color of the furthest node = 4 (the count of exactly one of those will be 1, and will not change)

This is a reasonable chunk of memory that in most programming languages can be iterated and updated in a matter of a few milliseconds.

As I wrote this in JavaScript, I found that the end result overshoots 2⁵³, so I had to use the BigInt data type for the counters. However, the numbers fit in 64-bit integers, so if you have a programming language with that data type, there is no need for a dynamic Big Integer data type.

Here is the implementation in JavaScript which you can run here:

const FACE = 1 << 16; // The start index for counters that relate to 2D faces
const EDGE = FACE + (1 << 8); // The start index for counters that relate to 1D edges
const POINT = EDGE + (1 << 4); // The start index for the counters that relate to the 0D point
const colorNames = ["PINK", "RED", "GREEN", "BLUE"];

function sumColors(cube, ...corners) {
    // Extract the colors for the given corners from the encoded cube and sum them modulo 4
    let result = 0;
    for (const corner of corners) {
        result += cube >> (corner * 2);
    }
    return result & 3;
}

function shape(colors, ...indices) {
    // Take the colors at the given indices of the array and encode those in a single integer (2 bits per color)
    let result = 0;
    for (let j = indices.length - 1; j >= 0; j--) {
        result = (result << 2) | colors[indices[j]];
    }
    // If there are just 2 indices, the two colors are the endpoints of an edge
    if (indices.length == 2) result |= EDGE;
    // If there are 4 indices, the four colors are the corners of a face
    else if (indices.length == 4) result |= FACE;
    // Otherwise there are 8 indices, the 8 corners of a cube
    return result;
}

function report(step, counters) {
    // aggregate the counters per the color of the first corner in each shape
    const results = [0n, 0n, 0n, 0n];
    for (let state = 0; state < counters.length; state++) {
        const count = counters[state];
        results[state & 3] += count;
    }

    console.log(`STEP ${step}: ${results[0]} times ${colorNames[0]}, ${results[1]} times ${colorNames[1]}, ${results[2]} times ${colorNames[2]}, ${results[3]} times ${colorNames[3]}`);
}

function solve(cube) {
    let colors = [];
    // flatten the given 3D cube to a flat array of colors
    for (let face of cube) {
        for (let edge of face) {
            for (let color of edge) {
                colors.push(color);
            }
        }
    }
    // Create a counter for every possible cube (in terms of colors), every face and every edge
    const counters = Array(POINT + 4).fill(0n); // The n-suffix denotes BigInteger type
    // Initialise the counters with the cube we start with:
    counters[shape(colors, 0, 1, 2, 3, 4, 5, 6, 7)] += 1n; // We have one cube
    // Faces on the "far" side of X, Y and Z directions
    counters[shape(colors, 1, 3, 5, 7)] += 1n;
    counters[shape(colors, 2, 3, 6, 7)] += 1n;
    counters[shape(colors, 4, 5, 6, 7)] += 1n;
    // Edges on the "far" side of X, Y and Z directions
    counters[shape(colors, 3, 7)] += 1n;
    counters[shape(colors, 5, 7)] += 1n;
    counters[shape(colors, 6, 7)] += 1n;
    // The furthest color:
    counters[POINT + colors.at(-1)] = 1n;
    // Output the counters for the initial state
    report(0, counters);
    // loop to next generations
    for (let step = 1; step <= 19; step++) {
        const copy = [...counters];
        for (let state = 0; state < counters.length - 4; state++) {
            const count = copy[state];
            if (!count) continue;
            counters[state] -= count;
            const cube3x3x3 = [
                sumColors(state, 0),
                sumColors(state, 0, 1),
                sumColors(state, 1),
                sumColors(state, 0, 2),
                sumColors(state, 0, 1, 2, 3),
                sumColors(state, 1, 3),
                sumColors(state, 2),
                sumColors(state, 2, 3),
                sumColors(state, 3),
                sumColors(state, 0, 4),
                sumColors(state, 0, 1, 4, 5),
                sumColors(state, 1, 5),
                sumColors(state, 0, 2, 4, 6),
                sumColors(state, 0, 1, 2, 3, 4, 5, 6, 7),
                sumColors(state, 1, 3, 5, 7),
                sumColors(state, 2, 6),
                sumColors(state, 2, 3, 6, 7),
                sumColors(state, 3, 7),
                sumColors(state, 4),
                sumColors(state, 4, 5),
                sumColors(state, 5),
                sumColors(state, 4, 6),
                sumColors(state, 4, 5, 6, 7),
                sumColors(state, 5, 7),
                sumColors(state, 6),
                sumColors(state, 6, 7),
                sumColors(state, 7),
            ];
            if ((state & EDGE) === EDGE) { // Treat as edge
                counters[shape(cube3x3x3, 0, 1)] += count;
                counters[shape(cube3x3x3, 1, 2)] += count;
            } else if ((state & FACE) === FACE) { // Treat as face
                counters[shape(cube3x3x3, 0, 1, 3, 4)] += count;
                counters[shape(cube3x3x3, 1, 2, 4, 5)] += count;
                counters[shape(cube3x3x3, 3, 4, 6, 7)] += count;
                counters[shape(cube3x3x3, 4, 5, 7, 8)] += count;
            } else { // Cube -- normal case
                counters[shape(cube3x3x3, 0, 1, 3, 4, 9, 10, 12, 13)] += count; 
                counters[shape(cube3x3x3, 1, 2, 4, 5, 10, 11, 13, 14)] += count; 
                counters[shape(cube3x3x3, 3, 4, 6, 7, 12, 13, 15, 16)] += count; 
                counters[shape(cube3x3x3, 4, 5, 7, 8, 13, 14, 16, 17)] += count; 
                counters[shape(cube3x3x3, 9, 10, 12, 13, 18, 19, 21, 22)] += count; 
                counters[shape(cube3x3x3, 10, 11, 13, 14, 19, 20, 22, 23)] += count; 
                counters[shape(cube3x3x3, 12, 13, 15, 16, 21, 22, 24, 25)] += count; 
                counters[shape(cube3x3x3, 13, 14, 16, 17, 22, 23, 25, 26)] += count; 
            }
        }
        report(step, counters);
    }
}

const PINK = 0;
const RED = 1;
const GREEN = 2;
const BLUE = 3;
// The cube given as example in the question:
const cube = [[[RED, PINK], [GREEN, GREEN]],[[BLUE, RED], [PINK, RED]]];
solve(cube);

Even with the output generated, this finishes well within one second on my laptop. Written in a lower-level language (like C) it should even be faster.