Trouver toutes les combinaisons de holepunch 3x3

Question

J'ai été à un carnaval où à chaque emplacement, ils marque de votre programme avec un trou spécial coup de poing. La perforatrice est une grille de 3x3 cases. Dans chaque espace, il y a soit un pin qui perfore votre papier ou il n'y en a pas. Cela m'a demandé comment de nombreux modèles différents vous pourriez faire avec cet outil. Ma première pensée a été: 2^9 = 512, mais tous les 9 espaces sans contact n'est pas vraiment un coup de poing, alors, vraiment: 511.

Ensuite, la complexité de me frapper. Surtout depuis que les travailleurs ne sont pas tous de faire preuve de prudence lorsqu'ils punch votre papier, tous ces look idential:

x..  .x.  ...  etc.
.x.  x..  .x.
...  ...  ..x

Question: Comment pourriez-un test écrit pour le compte de la rotation et de déplacement?

---

De la Diligence et de pensées à ce jour:

• Binaire se sent comme une partie évidente de cette équation
• Lorsqu'un motif unique est trouvé, de le stocker dans la mémoire afin que les futurs modèles peuvent être testés contre elle
• Il y a 4 possibilités de rotation.
  Edit: ce que je veux dire par "rotations", c'est que vous pouvez prendre n'importe quelle forme et la tourner à 90 degrés. Considérons le modèle qui est un point dans le coin supérieur gauche. Vous pouvez activer/faire pivoter de 90 degrés pour obtenir le point dans le coin supérieur droit. Le faire à nouveau et c'est en bas à droite. De nouveau et c'est en bas à gauche. À l'aide de la pure 2^9 calcul, ce sont 4 combinaisons différentes. Pour ce problème, toutefois, ce sont exactement le genre de doublons je suis en train de mauvaises herbes.
• Pour chaque rotation, il y a 25 façons de faire de 3x3 grilles de chevauchement:

Les chevauchements:

/ = the spaces in the new one to test
\ = the spaces in a verified unique one

1               2               25
/ / / . . . .   . / / / . . .   . . . . . . .
/ / / . . . .   . / / / . . .   . . . . . . .
/ / X \ \ . .   . / X X \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ X / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

• Un chevauchement n'a pas besoin d'être testé si en soit le motif contient une broche qui n'est pas dans la zone de chevauchement. Au niveau du bit ET peut aider à ici.
• Si vous faites chaque position pour chacun des 2 modèles en chaînes de caractères, vous pouvez simplement vérifier l'égalité
• Ces deux dernières idées être combinés afin d'augmenter l'efficacité?

Answer 1

Nous avons besoin de ne considérer que les modèles de coups de poing dans la première rangée et de colonne. Si la première ligne est vide, le motif peut être décalée vers le haut. Si la première colonne est vide, le motif peut être décalé à gauche. Dans les deux cas, on peut dériver un modèle similaire que nous considérons.

Pour ces motifs, nous avons besoin de vérifier si la rotation de versions sont identiques. Pour ce faire, nous appliquer jusqu'à trois rotations de 90 degrés, éventuellement déplaçant de gauche à supprimer des colonnes vides (la première ligne n'est jamais vide) et de trouver le modèle avec le moins de valeur numérique.

Nous pouvons alors ajouter cette valeur à une valeur de hachage ensemble, qui ne garde que des valeurs uniques.

Le modèle vide n'est pas inclus parce que toutes ses lignes sont vides.

Pour ce faire, nous codent pour des motifs que les bits suivants:

012
345
678

Les opérations dont nous aurons besoin sont pour la plupart très 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)

La partie la plus délicate est la rotation, qui est vraiment juste en réorganisant tous les 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);

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

Cette fonction renvoie 116. Le temps pris sur ma machine a été de 0,023 mme.

EDIT: Vous pouvez obtenir un supplément de 7x amélioration par l'utilisation de 4 observations:

1. On peut utiliser un simple visité tableau au lieu d'un ensemble de hachage. Si un modèle a été vu avant, nous n'avons pas les compter. Cela élimine également le besoin de garder une trace de "moins" motif à l'intérieur de la boucle. Si un modèle a été visité, puis plus bas de son modèle pivoté a été visité, trop.
2. Si nous n'avons pas de rotation à 180 degrés de symétrie, puis la 3ème rotation ne sera pas le rendement du modèle original. La 4e rotation, toujours, de sorte qu'il n'est pas nécessaire.
3. La rotation de l'expression peut être légèrement simplifiée.

Donc, si on applique ces observations et déroulez l'intérieure de la boucle, on obtient:

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

Cela fonctionne dans environ 3µs sur la même machine.

Answer 2

Ma solution: 116 formes uniques

Lors de l'essai 2 formes pour l'égalité, en comparant le nombre de broches permet d'économiser beaucoup de temps. Mais ma plus grande percée a été de réaliser que tous ceux qui ont 25 positions peut être remplacé par ceci: pour chacun des deux 3x3 formes à vérifier pour l'égalité, concaténer les lignes avec deux zéros puis couper attaque et de fuite des zéros. La méthode concat zéros sont à éviter wrap-around. Exemple:

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

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

Ensuite, il suffit de tester les résultats pour l'égalité. C'est 4 facile d'itérations (1 pour chaque rotation) au lieu de 100 (25 positions * 4 rotations) plus complexes.

---

Temps:
cordes:

• la force brute, tous les 25 positions pour chaque rotation: 2018ms
• ...00 00...... supprimés: 75ms
• plus d'optimisation: 59 ms

La programmation orientée objet et de la meilleure mise en cache: 17ms

Answer 3

Tout d'abord, nous pouvons voir deux coups de poing qui sont l'équivalent, à l'exception de la traduction, comme les rotations de chaque d'autres. Imaginez le coup de poing motif sur la surface d'une sphère: on peut "traduire" par la rotation de la sphère le long de l'axe vertical et horizontal (comme il est tenu à la main.)

Deux coups de poing qui sont équivalent à une rotation (comme un virage à 90 degrés) sont également pris en compte par nous tournant de notre sphère le long de la troisième, le reste de l'axe.

Maintenant, nous avons réduit le problème de "Comment de nombreux modes de punch sont là, sur la surface d'une sphère, à une rotation?" Pour le comptage des objets uniques jusqu'à la symétrie comme ça, vous voulez pas-Lemme de Burnside. Ce livre est une bonne amorce.

Answer 4

Je ne pense pas que c'est comme la sphère cas, puisque vous ne pouvez pas faire pivoter sur les bords? C'est à dire:

XOO
XXO
XOO

n'est pas le même que

OOX
XOX
OOX

J'ai essayé de comptage à la main sur papier pour voir ce que j'ai. Envisager la 2x2 cas, vous avez 1 avec 0 points, 1 avec 1 point, 2 avec 2 points (à côté ou en diagonale), 1 avec 3 points et 1 avec 4; pour un total de 5 (ou 4 si vous négligez le vide de cas). Notez que l'énumération est symétrique, puisque c'est le même pour compter les espaces vides que pleines. Pour le 3x3 cas, j'ai obtenu ceci:

C(0) = 1
C(1) = 1
C(2) = 5
C(3) = 10
C(4) = 21

et puis par symétrie, 21, 10, 5, 1, 1

Je reçois 76. Je pourrais très facilement miscounted, en particulier dans les 4/5 des cas.

La seule façon que je peux penser de l'énumération de ces automatiquement impliquerait le déplacement et la rotation des modèles pour voir s'ils correspondent à une précédemment énumérés à l'un. Le déplacement est difficile, puisque vous ne pouvez déplacer jusqu'à vous "bosse" à l'encontre d'un bord.

Answer 5

Il est intéressant de souligner que si vous avez vraiment besoin de chaque forme de "look" unique, peu importe comment elle est tournée ou décalé, vous avez très peu de choix. Par exemple, un seul coup de poing, peu importe OÙ il est dans la grille, ce sera toujours la même. En outre, en supposant un carré de la grille et tour de pins, et en supposant que les mineurs de l'espacement des différences (√2) sont insignifiants, puis 2 trous en diagonale dans une rangée aura le même aspect que les deux broches adjacentes, puisque tout le spectateur voit, c'est 2 trous rapprochés. De même, 3 en diagonale ressemble juste à 3 dans une ligne droite, ce qui limite considérablement vos options.

Notez que la forme est probablement un meilleur mot pour ce que nous sommes après que la combinaison, puisque nous ne sommes pas attentifs à ce que le réel combinaison a été, tout ce que la résultante de la forme sur le papier.

Je pense que nous pouvons poser que peu importe la forme, il peut être tourné et décalés tels que le haut-gauche de la broche est coup de poing (en particulier si vous permettre une rotation de 45 degrés), ce qui nous permet de limiter notre recherche encore plus loin. Nous accomplissons cela en utilisant les règles suivantes:

1. Si le coin est coup de poing, faire pivoter la grille jusqu'à ce que les coups de poing coin en haut à gauche
2. Sinon maj le motif de la mesure et de gauche.
3. Répétez l'étape 1
4. Si on en arrive là, alors nous savons que seul le haut en position intermédiaire est coup de poing (puisque nous savons que ni le coin est), auquel cas nous faire pivoter le motif de 45 degrés, ce qui rend le haut moyen-maintenant en haut à gauche. CQFD.

J'ai fait un très rapide de la plume et du papier de recherche par force brute pour les formes possibles et il semble que la liste des options viables est si petit que vous pouvez en faire la liste de tous en quelques minutes.