3D 立方无限元胞自动机挑战

Question

我正在研究一个涉及 3D（立方）无限元胞自动机的挑战，定义为：

• 初始状态：我们从位于立方体顶点的 8 个单元开始，每个单元处于 4 种状态之一 {0：洋红色，1：红色，2：绿色，3：蓝色}。

• 增长：在每一步中，立方体都会通过在每对现有单元之间插入新单元来扩展。新细胞的状态由其最近邻居模 4 的状态总和确定。请注意，根据其位置，新细胞有 2,4 或 8 个最近邻居（这是 3D 摩尔邻域）。

为了说明这一点，以下是第一步的说明：

初始状态

步骤1

第2步

我们有兴趣跟踪每个状态 [0, 1, 2, 3] 的单元数量的演变。以下是第一步的计数：

• 初始：2,3,2,1
• 第 1 步：6、10、7、4
• 第 2 步：30、36、31、28
• 第3步：196、192、155、186
• 第 4 步：1'162、1'276、1'207、1'268

我们的目标是确定第 19 步中每个细胞状态的计数。考虑到指数增长，暴力破解是不可行的。有人告诉我可以在不到一秒钟的时间内解决这个问题。有人对如何解决这个问题有任何想法吗？

预先感谢您的帮助！

Answer 1

我们可以为每个可能的“小”立方体（即 8 个角是直接邻居的立方体）创建一个计数器。因此，我们将为立方体提供一个计数器，其角点顺序为红色、红色、绿色、粉色、粉色、绿色、蓝色、蓝色，并且为八种颜色的每种不同序列提供不同的计数器。

每次我们“扩展”到下一步（生成）时，这样的 2x2x2 立方体就会变成 3x3x3 立方体：我们拥有了解该 3x3x3 立方体的 27 种颜色中每种颜色的所有信息。然后我们减去 2x2x2 立方体的计数（因为它不再存在），然后增加 3x3x3 立方体中包含的八个子 2x2x2 立方体中每一个的计数器。同样，我们知道相关颜色，因此我们知道要增加哪些计数器。

在第 19 代，我们可以根据每个可能的 2x2x2 立方体中“第一个”角（即最接近原点的角）的颜色聚合这些计数器。这样我们就可以计算出最终生成中的所有“节点”，除了位于完整结构外侧的 3 个平面之一上的节点，并包括距离最远的（最后一个）节点从原点（示例输入中的顶部红色节点）。对于这些平面，我们可以维护其上的 2D 面的计数器，并在最后计算这些面的“第一个”角的计数器。同样，这将考虑几乎每个节点，除了位于三个外部 1D lines 上的节点，其中包括距离原点最远的（最后一个）节点。我们还可以维护这些边（节点对）的计数器，并根据每对的第一种颜色聚合它们。这使得我们只剩下一个未被考虑的节点，它是距离原点最远的最后一个节点。

这个计数器数组有以下数量的条目：

• 用于计数立方体（颜色组合）：4⁸ = 65536
• 用于计算面（颜色组合）：4⁴ = 256
• 用于计算边缘（颜色组合）：4² = 16
• 最远节点的颜色= 4（其中恰好一个节点的计数将为1，并且不会改变）

这是一个合理的内存块，在大多数编程语言中都可以在几毫秒内迭代和更新。

当我用 JavaScript 编写此代码时，我发现最终结果超过了 2⁵³，因此我必须使用 BigInt 数据类型作为计数器。但是，这些数字适合 2⁶⁴ 整数，因此如果您有具有该数据类型的编程语言，则不需要动态大整数数据类型。

这是 JavaScript 中的实现，您可以在此处运行：

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(FACE + EDGE + 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, 8)] += 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 example cube given in the question:
const cube = [[[RED, PINK], [GREEN, GREEN]],[[BLUE, RED], [PINK, RED]]];
solve(cube);

即使生成了输出，这在我的笔记本电脑上也能在一秒钟内完成。用较低级语言（如 C）编写它甚至应该更快。