StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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. </p> <p>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.</p> <p>We can then add this value to a hash set, which will only keep unique values.</p> <p>The empty pattern is not included because all its rows are empty.</p> <p>To implement this, we encode patterns as successive bits:</p> <pre><code>012 345 678 </code></pre> <p>The operations we will need are mostly very simple:</p> <pre><code>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) </code></pre> <p>The trickiest part is the rotation, which is really just rearranging all the bits:</p> <pre><code>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); </code></pre> <p>In C#:</p> <pre><code>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; } </code></pre> <p>This function returns 116. The time taken on my machine was 0.023ms.</p> <p><strong>EDIT</strong>: You can get an additional 7x improvement by using 4 observations:</p> <ol> <li>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.</li> <li>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.</li> <li>The rotation expression can be slightly simplified.</li> </ol> <p>So, if we apply these observations and unroll the inner do loop, we get the following:</p> <pre><code>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; } </code></pre> <p>This runs in about 3μs on the same machine.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload