最长不重复生命游戏序列

Question

给定正整数N，确定non网格上的起始模式，在生命游戏规则下产生最长的非重复序列，并以在环面上播放的固定模式(长度为1的周期)结束。

目标不是最短的计划，而是最快的。

由于世界是有限的，你最终会在一个循环中结束，从而重复一个已经访问过的状态。如果此循环有句点1，则起始模式是有效的候选模式。

输出:开始模式和序列中唯一状态的总数(包括启动模式)。

现在，1x1-环面是特殊的，因为一个细胞可能被认为是与自己相邻的，但实际上，没有问题，一个活的细胞在任何情况下都会死亡(过度拥挤或孤独)。因此，输入1产生一个长度为2的序列，该序列是一个活的细胞，然后永远死亡。

这个问题的动机是类似于繁忙的海狸功能，但肯定不那么复杂，因为我们对记忆有限制。这将是一个很好的序列，包括在OEIS，以及。

对于N=3，序列长度为3，左手边的任何图案都达到一个完全黑色的3x3正方形，然后死亡。(移除一个周期中的所有模式)。

Answer 1

我看到以下可能的解决办法：

• 沉重的理论。我知道有一些关于“环抱”的关于生命的文献，但我没有读多少。
• 蛮力前进:对每一个可能的板，检查它的分数。这基本上就是马修和基思的方法，尽管基思将需要检查的板数减少了4倍。
  • 优化:规范表示。如果我们能够检查一个板的标准表示是否比评估它的分数要快得多，我们可以得到一个大约8N^2的因子的加速。(还有一些较小的等价类的部分方法)。
  • 优化: DP。将每个棋盘的得分缓存起来，这样我们就能找到一块我们以前见过的棋盘，而不是一直走到它们汇合或发散为止。原则上，这将使平均分数/周期长度(可能20或更多)的速度加快，但在实践中，我们可能会进行大量的交换。例如，对于N=6，我们需要2^36分的容量，以每分16‘t的字节计算，我们需要随机访问，所以我们不能期望良好的缓存局部性。
  • 把两者结合起来。对于N=6，完整的规范表示将允许我们将DP缓存减少到大约60分。这是一种很有希望的做法。

• 蛮力向后。这在一开始看起来很奇怪，但是如果我们假设我们可以很容易地找到静物，并且我们可以很容易地反转Next(board)函数，我们就会发现它有一些好处，尽管没有我最初希望的那么多。
  • 我们根本就不想分道扬镳了。节省不了多少，因为它们很少见。
  • 我们不需要为所有的董事会存储分数，所以应该有较少的内存压力的前进DP方法。
  • 在列举静物的背景下，通过改变我在文学中看到的一种技巧，倒向工作其实是相当容易的。它的工作原理是将每一列视为字母中的一个字母，然后观察到三个字母的顺序决定了下一代的中间一个字母。枚举静物的并行非常接近，因此我将它们重新分解为一个稍微有些尴尬的方法，Prev2。
  • 似乎我们可以将静物规范化，并以极低的成本获得8N^2的加速。然而，从经验上看，如果我们在每一步都进行规范化，我们所考虑的董事会数量仍会大幅减少。
  • 出奇的高比例的董事会有2或3分，所以仍然存在记忆压力。我发现有必要在飞行中规范化，而不是建立上一代，然后规范化。通过深度优先而不是广度优先搜索来减少内存的使用可能很有趣，但是这样做并不会溢出堆栈，也不需要重复计算，这需要一种共同例程/连续的方法来枚举以前的板。

我不认为微优化会让我赶上基思的代码，但为了感兴趣，我会发布我所拥有的。这在使用Mono2.4或.Net (不使用PLINQ)的2 2GHz机器上用大约一分钟的时间解决了.Net问题，使用PLINQ解决了大约20秒的问题；N=6运行了许多小时。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox {
    class Codegolf9393 {
        internal static void Main() {
            new Codegolf9393(4).Solve();
        }

        private readonly int _Size;
        private readonly uint _AlphabetSize;
        private readonly uint[] _Transitions;
        private readonly uint[][] _PrevData1;
        private readonly uint[][] _PrevData2;
        private readonly uint[,,] _CanonicalData;

        private Codegolf9393(int size) {
            if (size > 8) throw new NotImplementedException("We need to fit the bits in a ulong");

            _Size = size;
            _AlphabetSize = 1u << _Size;

            _Transitions = new uint[_AlphabetSize * _AlphabetSize * _AlphabetSize];
            _PrevData1 = new uint[_AlphabetSize * _AlphabetSize][];
            _PrevData2 = new uint[_AlphabetSize * _AlphabetSize * _AlphabetSize][];
            _CanonicalData = new uint[_Size, 2, _AlphabetSize];

            InitTransitions();
        }

        private void InitTransitions() {
            HashSet<uint>[] tmpPrev1 = new HashSet<uint>[_AlphabetSize * _AlphabetSize];
            HashSet<uint>[] tmpPrev2 = new HashSet<uint>[_AlphabetSize * _AlphabetSize * _AlphabetSize];
            for (int i = 0; i < tmpPrev1.Length; i++) tmpPrev1[i] = new HashSet<uint>();
            for (int i = 0; i < tmpPrev2.Length; i++) tmpPrev2[i] = new HashSet<uint>();

            for (uint i = 0; i < _AlphabetSize; i++) {
                for (uint j = 0; j < _AlphabetSize; j++) {
                    uint prefix = Pack(i, j);
                    for (uint k = 0; k < _AlphabetSize; k++) {
                        // Build table for forwards checking
                        uint jprime = 0;
                        for (int l = 0; l < _Size; l++) {
                            uint count = GetBit(i, l-1) + GetBit(i, l) + GetBit(i, l+1) + GetBit(j, l-1) + GetBit(j, l+1) + GetBit(k, l-1) + GetBit(k, l) + GetBit(k, l+1);
                            uint alive = GetBit(j, l);
                            jprime = SetBit(jprime, l, (count == 3 || (alive + count == 3)) ? 1u : 0u);
                        }
                        _Transitions[Pack(prefix, k)] = jprime;

                        // Build tables for backwards possibilities
                        tmpPrev1[Pack(jprime, j)].Add(k);
                        tmpPrev2[Pack(jprime, i, j)].Add(k);
                    }
                }
            }

            for (int i = 0; i < tmpPrev1.Length; i++) _PrevData1[i] = tmpPrev1[i].ToArray();
            for (int i = 0; i < tmpPrev2.Length; i++) _PrevData2[i] = tmpPrev2[i].ToArray();

            for (uint col = 0; col < _AlphabetSize; col++) {
                _CanonicalData[0, 0, col] = col;
                _CanonicalData[0, 1, col] = VFlip(col);
                for (int rot = 1; rot < _Size; rot++) {
                    _CanonicalData[rot, 0, col] = VRotate(_CanonicalData[rot - 1, 0, col]);
                    _CanonicalData[rot, 1, col] = VRotate(_CanonicalData[rot - 1, 1, col]);
                }
            }
        }

        private ICollection<ulong> Prev2(bool stillLife, ulong next, ulong prev, int idx, ICollection<ulong> accum) {
            if (stillLife) next = prev;

            if (idx == 0) {
                for (uint a = 0; a < _AlphabetSize; a++) Prev2(stillLife, next, SetColumn(0, idx, a), idx + 1, accum);
            }
            else if (idx < _Size) {
                uint i = GetColumn(prev, idx - 2), j = GetColumn(prev, idx - 1);
                uint jprime = GetColumn(next, idx - 1);
                uint[] succ = idx == 1 ? _PrevData1[Pack(jprime, j)] : _PrevData2[Pack(jprime, i, j)];
                foreach (uint b in succ) Prev2(stillLife, next, SetColumn(prev, idx, b), idx + 1, accum);
            }
            else {
                // Final checks: does the loop round work?
                uint a0 = GetColumn(prev, 0), a1 = GetColumn(prev, 1);
                uint am = GetColumn(prev, _Size - 2), an = GetColumn(prev, _Size - 1);
                if (_Transitions[Pack(am, an, a0)] == GetColumn(next, _Size - 1) &&
                    _Transitions[Pack(an, a0, a1)] == GetColumn(next, 0)) {
                    accum.Add(Canonicalise(prev));
                }
            }

            return accum;
        }

        internal void Solve() {
            DateTime start = DateTime.UtcNow;
            ICollection<ulong> gen = Prev2(true, 0, 0, 0, new HashSet<ulong>());
            for (int depth = 1; gen.Count > 0; depth++) {
                Console.WriteLine("Length {0}: {1}", depth, gen.Count);
                ICollection<ulong> nextGen;

                #if NET_40
                nextGen = new HashSet<ulong>(gen.AsParallel().SelectMany(board => Prev2(false, board, 0, 0, new HashSet<ulong>())));
                #else
                nextGen = new HashSet<ulong>();
                foreach (ulong board in gen) Prev2(false, board, 0, 0, nextGen);
                #endif

                // We don't want the still lifes to persist or we'll loop for ever
                if (depth == 1) {
                    foreach (ulong stilllife in gen) nextGen.Remove(stilllife);
                }

                gen = nextGen;
            }
            Console.WriteLine("Time taken: {0}", DateTime.UtcNow - start);
        }

        private ulong Canonicalise(ulong board)
        {
            // Find the minimum board under rotation and reflection using something akin to radix sort.
            Isomorphism canonical = new Isomorphism(0, 1, 0, 1);
            for (int xoff = 0; xoff < _Size; xoff++) {
                for (int yoff = 0; yoff < _Size; yoff++) {
                    for (int xdir = -1; xdir <= 1; xdir += 2) {
                        for (int ydir = 0; ydir <= 1; ydir++) {
                            Isomorphism candidate = new Isomorphism(xoff, xdir, yoff, ydir);

                            for (int col = 0; col < _Size; col++) {
                                uint a = canonical.Column(this, board, col);
                                uint b = candidate.Column(this, board, col);

                                if (b < a) canonical = candidate;
                                if (a != b) break;
                            }
                        }
                    }
                }
            }

            ulong canonicalValue = 0;
            for (int i = 0; i < _Size; i++) canonicalValue = SetColumn(canonicalValue, i, canonical.Column(this, board, i));
            return canonicalValue;
        }

        struct Isomorphism {
            int xoff, xdir, yoff, ydir;

            internal Isomorphism(int xoff, int xdir, int yoff, int ydir) {
                this.xoff = xoff;
                this.xdir = xdir;
                this.yoff = yoff;
                this.ydir = ydir;
            }

            internal uint Column(Codegolf9393 _this, ulong board, int col) {
                uint basic = _this.GetColumn(board, xoff + col * xdir);
                return _this._CanonicalData[yoff, ydir, basic];
            }
        }

        private uint VRotate(uint col) {
            return ((col << 1) | (col >> (_Size - 1))) & (_AlphabetSize - 1);
        }

        private uint VFlip(uint col) {
            uint replacement = 0;
            for (int row = 0; row < _Size; row++)
                replacement = SetBit(replacement, row, GetBit(col, _Size - row - 1));
            return replacement;
        }

        private uint GetBit(uint n, int bit) {
            bit %= _Size;
            if (bit < 0) bit += _Size;

            return (n >> bit) & 1;
        }

        private uint SetBit(uint n, int bit, uint value) {
            bit %= _Size;
            if (bit < 0) bit += _Size;

            uint mask = 1u << bit;
            return (n & ~mask) | (value == 0 ? 0 : mask);
        }

        private uint Pack(uint a, uint b) { return (a << _Size) | b; }
        private uint Pack(uint a, uint b, uint c) {
            return (((a << _Size) | b) << _Size) | c;
        }

        private uint GetColumn(ulong n, int col) {
            col %= _Size;
            if (col < 0) col += _Size;
            return (_AlphabetSize - 1) & (uint)(n >> (col * _Size));
        }

        private ulong SetColumn(ulong n, int col, uint value) {
            col %= _Size;
            if (col < 0) col += _Size;

            ulong mask = (_AlphabetSize - 1) << (col * _Size);
            return (n & ~mask) | (((ulong)value) << (col * _Size));
        }
    }
}

Answer 2

因子

USING: arrays grouping kernel locals math math.functions math.parser math.order math.ranges math.vectors sequences sequences.extras ;
IN: longest-gof-pattern

:: neighbors ( x y game -- neighbors )
game length :> len 
x y game -rot 2array {
    { -1 -1 }
    { -1 0 }
    { -1 1 }
    { 0 -1 }
    { 0 1 }
    { 1 -1 }
    { 1 0 }
    { 1 1 }
} [
    v+ [
        dup 0 <
        [ dup abs len mod - abs len mod ] [ abs len mod ]
        if
    ] map
] with map [ swap [ first2 ] dip nth nth ] with map ;

: next ( game -- next )
dup [
    [
        neighbors sum
        [ [ 1 = ] [ 2 3 between? ] bi* and ]
        [ [ 0 = ] [ 3 = ] bi* and ] 2bi or 1 0 ?
    ] curry curry map-index
] curry map-index ;

: suffixes ( seq -- suffixes )
{ }
[ [ [ suffix ] curry map ] [ 1array 1array ] bi append ]
reduce ;

! find largest repeating pattern
: LRP ( seq -- pattern )
dup length iota
[ 1 + [ reverse ] dip group [ reverse ] map reverse ] with
map dup [ dup last [ = ] curry map ] map
[ suffixes [ t [ and ] reduce ] map [ ] count ] map
dup supremum [ = ] curry find drop swap nth last ;

: game-sequence ( game -- seq )
1array [
    dup [
        dup length 2 >
        [ 2 tail-slice* [ first ] [ last ] bi = not ]
        [ drop t ] if
    ] [ LRP length 1 > not ] bi and
] [ dup last next suffix ] while ;

: pad-to-with ( str len padstr -- rstr )
[ swap dup length swapd - ] dip [ ] curry replicate ""
[ append ] reduce prepend ;

:: all-NxN-games ( n -- games )
2 n sq ^ iota [
    >bin n sq "0" pad-to-with n group
    [ [ 48 = 0 1 ? ] { } map-as ] map
] map ;

: longest-gof-pattern ( n -- game )
all-NxN-games [ game-sequence ] map [ length ] supremum-by but-last ;

一些时间统计：

IN: longest-gof-pattern [ 3 longest-gof-pattern ] time dup length . . 
Running time: 0.08850873500000001 seconds

3
{
   { { 1 1 1 } { 0 0 0 } { 0 0 0 } }
   { { 1 1 1 } { 1 1 1 } { 1 1 1 } }
   { { 0 0 0 } { 0 0 0 } { 0 0 0 } }
}

IN: longest-gof-pattern [ 4 longest-gof-pattern ] time dup length . . 
Running time: 49.667698828 seconds

10
{
  { { 0 1 1 0 } { 0 1 0 0 } { 0 1 0 0 } { 1 1 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 1 0 0 } { 0 0 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 0 } { 1 1 0 0 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 0 } { 0 0 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 0 } { 1 1 0 1 } }
  { { 0 1 1 0 } { 0 1 0 0 } { 0 0 1 1 } { 0 0 0 1 } }
  { { 0 1 0 1 } { 0 1 0 1 } { 0 0 1 1 } { 1 1 0 1 } }
  { { 1 1 0 1 } { 1 1 0 1 } { 0 0 0 0 } { 1 1 0 0 } }
  { { 1 1 0 1 } { 1 1 0 1 } { 0 0 1 1 } { 1 1 1 1 } }
  { { 0 0 0 0 } { 0 0 0 0 } { 0 0 0 0 } { 0 0 0 0 } }
}

测试5使REPL崩溃。嗯。程序中最低效的部分可能是函数游戏序列。我以后也许能做得更好。