3x3 ホールパンチのすべての組み合わせを見つける質問する

Question

最初の行と列にパンチがあるパターンのみを考慮する必要があります。最初の行が空の場合、パターンを上にシフトできます。最初の列が空の場合、パターンを左にシフトできます。どちらの場合でも、考慮する類似のパターンを導き出すことができます。

これらのパターンについては、回転したバージョンが同一であるかどうかを確認する必要があります。これを行うには、最大 3 回の 90 度回転を適用し、先頭の空の列を削除するために左にシフトし (最初の行が空になることはありません)、数値が最も小さいパターンを見つけます。

次に、この値をハッシュセットに追加して、一意の値のみを保持することができます。

空のパターンは、すべての行が空であるため含まれません。

これを実装するには、パターンを連続するビットとしてエンコードします。

012
345
678

必要な操作はほとんどが非常に簡単です。

Test for an empty row:    (n & 7) == 0     // bits 0,1,2 not set
Test for an empty column: (n & 73) == 0    // bits 0,3,6 not set
Shift pattern up:         n -> (n >> 3)
Shift pattern left:       n -> (n >> 1)

最も難しい部分は回転です。これは実際にはすべてのビットを並べ替えるだけです。

n -> ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
   + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
   + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);

C# の場合:

public static int Count3x3() {
    HashSet<int> patterns = new HashSet<int>();
    for (int i = 0; i < 512; i++) {
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        int nLowest = i;
        int n = i;
        do {
            nLowest = Math.Min(nLowest, n);
            n = ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
                + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
                + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);
            while ((n & 73) == 0)
                n >>= 1;
        } while (n != i);
        patterns.Add(nLowest);
    }
    return patterns.Count;
}

この関数は 116 を返します。私のマシンでかかった時間は 0.023 ミリ秒でした。

編集: 4 つの観察結果を使用することで、さらに 7 倍の改善が得られます。

ハッシュセットの代わりに、単純なアクセス済み配列を使用できます。パターンが以前に見つかった場合は、それをカウントしません。これにより、内部ループで「最低」のパターンを追跡する必要もなくなります。パターンがアクセスされた場合、その最低の回転パターンもアクセスされます。
180 度の回転対称性がない場合、3 回目の回転では元のパターンは生成されません。4 回目の回転では必ず元のパターンが生成されるため、不要です。
回転式は少し簡略化できます。

したがって、これらの観察を適用して内部の do ループを展開すると、次のようになります。

static int Rotate(int n) {
    n = ((n & (1+32)) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
        + ((n & (8+256)) >> 2) + (n & 16)
        + ((n & 64) >> 6) + ((n & 128) >> 4);
    while ((n & 73) == 0) 
        n >>= 1;
    return n;
}
public static int Count3x3_3() {
    bool[] visited = new bool[512];
    int count = 0, r;
    for (int i = 0; i < 512; i++) {
        if (visited[i])
            continue;
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        count++;
        if ((r = Rotate(i)) == i) continue;
        visited[r] = true;
        if ((r = Rotate(r)) == i) continue;
        visited[r] = true;
        visited[Rotate(r)] = true;
    }
    return count;
}

これは同じマシン上で約 3μs で実行されます。

Answer 1