找到3×3 holepunch的所有组合 [英] Find all combinations of 3x3 holepunch
问题描述
我是在一个狂欢节，其中在每个位置它标志着一个特殊的打孔程序。打孔是3×3空间的网格。在每一个空间，有任何一个引脚，刺破你的文件或没有。这让我想知道有多少不同的模式，你可以使用这个工具。我首先想到的是：2 ^ 9 = 512，但所有的9位是无针是不是一个真正的一拳，所以真的：511
I was at a carnival where at each location they mark your program with a special hole punch. The hole punch is a grid of 3x3 spaces. In each space, there's either a pin that punctures your paper or there isn't. This got me to wondering how many different patterns you could make with this tool. My first thought was: 2^9 = 512, but all 9 spaces being pinless isn't really a punch, so really: 511.
那么复杂打我。特别是因为工人是不是所有的小心，当他们冲你的论文，这些都会看idential：
Then the complexity hit me. Especially since the workers aren't all that careful when they punch your paper, these would all look idential:
x.. .x. ... etc.
.x. x.. .x.
... ... ..x
问：如何能测试写入考虑旋转和移
勤奋和想法至今：
- 在二进制感觉这个方程的一个明显的部分
- 在当前的独特模式被发现，将其存储在内存中，以便将来模式可以针对它进行测试
- 有4个旋转的可能性
修改我的意思是轮换是，你可以采取任何形状和旋转90度。认为是在左上角的点的图案。您可以打开/旋转90度，并得到在右上角点。再次做到这一点，它的右下角。再次，它是在左下方。使用纯2 ^ 9计算，这些是4种不同的组合。对于这个问题，但是，这些正是那种重复我想淘汰了。 - 对于每一个旋转，有25个办法，使3×3格重叠：
- Binary feels like an obvious part of this equation
- When a unique pattern is found, store it in memory so future patterns can be tested against it
- There are 4 rotation possibilities.
what I mean by "rotations" is that you can take any shape and turn it 90 degrees. Consider the pattern that is a dot in the upper left corner. You can turn/rotate it 90 degrees and get the dot in the upper right corner. Do this again and it's in the lower right. Again and it's in the lower left. Using the pure 2^9 calculation, these are 4 different combinations. For this problem however, these are exactly the kind of duplicates I'm trying to weed out. - For each rotation, there are 25 ways to make 3x3 grids overlap:
重叠：
/ = the spaces in the new one to test
\ = the spaces in a verified unique one
1 2 25
/ / / . . . . . / / / . . . . . . . . . .
/ / / . . . . . / / / . . . . . . . . . .
/ / X \ \ . . . / X X \ . . . . \ \ \ . .
. . \ \ \ . . . . \ \ \ . . . . \ \ \ . .
. . \ \ \ . . . . \ \ \ . . . . \ \ X / /
. . . . . . . . . . . . . . . . . . / / /
. . . . . . . . . . . . . . . . . . / / /
- 的重叠并不需要进行测试，如果任一模式包含一个销不在重叠区域。按位并有助于在这里。
- 如果你让每个位置每个2模式转换为字符串，你可以只检查是否相等
- 在这些previous两个思路可以组合，以提高效率？
推荐答案
我们只需要考虑具有第一行和列的拳模式。如果第一行是空的，图案可以被移。如果第一列是空的，图案可以被向左移位。在这两种情况下，我们可以得出，我们并考虑了类似的模式。
We need to only consider patterns that have punches in the first row and column. If the first row is empty, the pattern can be shifted up. If the first column is empty, the pattern can be shifted left. In either case, we can derive a similar pattern that we do consider.
有关这些模式，我们需要检查经旋转版本相同。为此，我们通过将最多三个90度的旋转，可能左移去除导致空列（第一行是永远不会空），并找到最低的数值模式。
For these patterns, we need to check if the rotated versions are identical. We do this by applying up to three 90 degree rotations, possibly shifting left to remove leading empty columns (the first row is never empty) and finding the pattern with the lowest numeric value.
我们能够那么这个值添加到哈希集合，这将只保留唯一值。
We can then add this value to a hash set, which will only keep unique values.
空的模式是不包括在内，因为所有的行都是空的。
The empty pattern is not included because all its rows are empty.
要实现这一点，我们EN code模式作为连续的位：
To implement this, we encode patterns as successive bits:
012
345
678
大多是我们需要的操作非常简单：
The operations we will need are mostly very simple:
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)
最棘手的部分是旋转，这其实只是重新安排所有位：
The trickiest part is the rotation, which is really just rearranging all the bits:
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＃：</ P>
In 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.023ms。
This function returns 116. The time taken on my machine was 0.023ms.
修改：您可以通过使用4观察得到额外的7倍改进：
EDIT: You can get an additional 7x improvement by using 4 observations:
- 我们可以用一个简单的访问数组，而不是一个哈希集合。如果图案是之前看到的，我们不指望它。这也消除了需要跟踪的最低图案中的内部循环。如果模式被访问过，那么它的最低旋转图案参观了。
- 如果我们没有180度旋转对称，则第三旋转将不会产生原来的图案。第四旋转将一如既往，所以这是不必要的。
- 在旋转前pression可以稍微简化。
所以，如果我们将这些意见和展开内做循环，我们得到如下：
So, if we apply these observations and unroll the inner do loop, we get the following:
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的同一台机器上。
This runs in about 3μs on the same machine.
这篇关于找到3×3 holepunch的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
