StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFind all combinations of 3x3 holepunch
text
Body
copied!<p>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.</p> <p>Then the complexity hit me. Especially since the workers aren't all that careful when they punch your paper, these would all look idential:</p> <pre><code>x.. .x. ... etc. .x. x.. .x. ... ... ..x </code></pre> <p>Question: <strong>How could a test be written to account for rotation and shifting?</strong></p> <hr> <p>Diligence and thoughts so far:</p> <ul> <li>Binary feels like an obvious part of this equation</li> <li>When a unique pattern is found, store it in memory so future patterns can be tested against it</li> <li>There are 4 rotation possibilities.<br /><strong>Edit:</strong> 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.</li> <li>For each rotation, there are 25 ways to make 3x3 grids overlap:</li> </ul> <p>Overlaps:</p> <pre><code>/ = the spaces in the new one to test \ = the spaces in a verified unique one 1 2 25 / / / . . . . . / / / . . . . . . . . . . / / / . . . . . / / / . . . . . . . . . . / / X \ \ . . . / X X \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ X / / . . . . . . . . . . . . . . . . . . / / / . . . . . . . . . . . . . . . . . . / / / </code></pre> <ul> <li>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.</li> <li>If you make each position for each of the 2 patterns into strings, you can just check for equality</li> <li>Can these previous two ideas be combined to increase efficiency?</li> </ul>

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