Find all combinations of 3x3 holepunch

Question

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.

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 

Question: How could a test be written to account for rotation and shifting?

---

Diligence and thoughts so far:

• 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.
  Edit: 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:

Overlaps:

/ = the spaces in the new one to test \ = the spaces in a verified unique one  1               2               25 / / / . . . .   . / / / . . .   . . . . . . . / / / . . . .   . / / / . . .   . . . . . . . / / X \ \ . .   . / X X \ . .   . . \ \ \ . . . . \ \ \ . .   . . \ \ \ . .   . . \ \ \ . . . . \ \ \ . .   . . \ \ \ . .   . . \ \ X / / . . . . . . .   . . . . . . .   . . . . / / / . . . . . . .   . . . . . . .   . . . . / / / 

• An overlap doesn't need to be tested if either pattern contains a pin that isn't in the overlap area. Bitwise AND could help here.
• If you make each position for each of the 2 patterns into strings, you can just check for equality
• Can these previous two ideas be combined to increase efficiency?

Answer 1

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.

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.

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); 

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; } 

This function returns 116. The time taken on my machine was 0.023ms.

EDIT: You can get an additional 7x improvement by using 4 observations:

1. We can use a simple visited array instead of a hash set. If a pattern was seen before, we don't count it. This also eliminates the need to keep track of the 'lowest' pattern in the inner loop. If a pattern was visited, then its lowest rotated pattern was visited, too.
2. If we don't have 180 degree rotation symmetry, then the 3rd rotation won't yield the original pattern. The 4th rotation will, always, so it is unnecessary.
3. The rotation expression can be slightly simplified.

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; } 

This runs in about 3μs on the same machine.

Answer 2

My solution: 116 unique shapes

When testing 2 shapes for equality, comparing the number of pins saves a lot of time. But my biggest breakthrough was realizing that all of those 25 positions can be replaced by this: for each of the two 3x3 shapes to be checked for equality, concatenate the lines with two zeros then trim leading and trailing zeros. The concat zeros are to prevent wrap-around. Example:

010 => 01000 => 0100010100000 => 1000101 101    10100 000    000  000 => 00000 => 0000001000101 => 1000101 010    01000 101    101 

Then just test the results for equality. That's 4 easy iterations (1 for each rotation) instead of 100 (25 positions * 4 rotations) more complex ones.

---

Time:
strings only:

• brute force, all 25 positions for each rotation: 2018ms
• ...00...00... trimmed: 75ms
• more optimization: 59ms

OOP and better caching: 17ms