Imaginez que nous ayons du polyomino et que nous aimerions les identifier de manière unique, mais les polyominos peuvent être tournés, donc les hacher aveuglément ne nous donnera pas la même empreinte digitale pour un morceau et une rotation de celui-ci (en général).

Par exemple, si nous avons le L-tetromino

x
x
xx

nous aimerions qu'il ait la même empreinte digitale que n'importe lequel d'entre eux:

         xx
  x       x      xxx
xxx  ,    x  or  x

Remarque: Nous n'autorisons que les rotations sur le plan (c'est-à-dire qu'il s'agit de polyominos unilatéraux) et, par conséquent, le polyomino suivant serait différent:

 x
 x
xx 

Défi

La tâche pour ce défi est d'implémenter une fonction / un programme d'empreintes digitales qui prend une matrice booléenne / évaluée / liste de listes / chaîne / .. encodant un polyomino et renvoyant une chaîne - l'empreinte digitale d'un polyomino. L'empreinte doit être égale pour toutes les rotations possibles (en général 4).$m\times n$$0,1$

Entrée sortie

• $m \geq 1$ et (c'est-à-dire pas de polyomino vide)$n \geq 1$
• vous êtes assuré que sont aussi petits que possible (c'est-à-dire que tous les sont coupés pour s'adapter à et$m,n$$0$$m$$n$
• vous êtes assuré que l'entrée est
  • simplement connecté
  • n'a pas de trous
• la sortie doit être une chaîne qui est la même pour chaque rotation possible d'un polyomino

Exemples

Voici quelques classes d'équivalence, pour chaque classe, l'empreinte digitale doit être la même et pour deux polyominos de deux classes distinctes, elles doivent différer.

Les rotations du L-tétromino de l'exemple:

[[1,0],[1,0],[1,1]]
[[0,0,1],[1,1,1]]
[[1,1],[0,1],[0,1]]
[[1,1,1],[1,0,0]]

Le J-tétromino:

[[0,1],[0,1],[1,1]]
[[1,1,1],[0,0,1]]
[[1,1],[1,0],[1,0]]
[[1,0,0],[1,1,1]]

L'unité polyomino:

[[1]]

Une barre $5\times 1$ :

[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]

Un coin $2\times 2$ :

[[1,1],[1,0]]
[[1,0],[1,1]]
[[0,1],[1,1]]
[[1,1],[0,1]]

W-pentomino:

[[1,0,0],[1,1,0],[0,1,1]]
[[0,0,1],[0,1,1],[1,1,0]]
[[1,1,0],[0,1,1],[0,0,1]]
[[0,1,1],[1,1,0],[1,0,0]]

Python 2 , 48 octets

f=lambda l,z=5:z and max(l,f(zip(*l)[::-1],z-1))

Essayez-le en ligne!

Prend la plus grande des quatre rotations en termes de comparaison de liste. Basé sur la solution de FlipTack .

Le code utilise la capacité de Python 2 pour comparer des objets de différents types. La valeur de cas de base de 0est inoffensive maxcar elle est plus petite que n'importe quelle liste. Produit également zipune liste de tuples alors que l'entrée est une liste de listes, mais les tuples sont plus gros que les listes, de sorte que la liste de listes d'entrée n'est jamais un concurrent. C'est pourquoi nous effectuons une rotation 5 fois plutôt que 4, afin de revenir à une version tuplifiée de la liste initiale. (Prendre une liste de tuples fonctionnerait également, si c'est une forme d'entrée autorisée.)

Python 3 , 63 octets

def f(m):M=[];exec("m=[*zip(*m[::-1])];M+=m,;"*4);return min(M)

Essayez-le en ligne!

Recherche la rotation avec le minimum lexographique et l'imprime.

Une forme lambda arrive au même nombre d'octets:

lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M[-4:])

Essayez-le en ligne!

Gelée , 5 octets

ZU$ƬṂ

Essayez-le en ligne!

Programme complet.

Génère simplement toutes les rotations possibles et sélectionne le minimum lexicographique.

Notez que les listes singleton ne sont pas encapsulées []dans la sortie. Cela n'a pas d'importance, car le seul cas où des listes singleton existeraient dans l'entrée serait une ligne verticale (y compris l'unité polyomino), qui est la même qu'une ligne horizontale de même taille (où celles-ci ne sont pas encapsulées) ). Le seul cas où l'extérieur []n'existera pas non plus est l'unité polyomino.

Nettoyer , 136 octets

import StdEnv,Data.List
r=reverse;t=transpose;f=flatten
$l=[if((a==b)==(c==d))'x''X'\\a<-f l&b<-f(r(map r l))&c<-f(r(t l))&d<-f(t(r l))]

Essayez-le en ligne!

Comprend un vérificateur de test.

K (ngn / k) , 16 octets

{a@*<a:3{+|x}\x}

Essayez-le en ligne!

min de rotations

{ } fonction avec argument x

{+|x}tourner, c.-à-d. inverser ( |) et transposer ( +)

3{ }\appliquer 3 fois en préservant les résultats intermédiaires; cela renvoie une liste des 4 rotations

a: affecter à a

< ascend (calculer la permutation de tri croissant)

* premier

a@index aavec cela

Japt -g, 6 octets

4Æ=zÃñ

Essayez-le

           :Implicit input of 2d-array U
4Æ         :Map the range [0,4)
   z       :  Rotate U 90 degrees
  =        :  Reassign to U
    Ã      :End map
     ñ     :Sort
           :Implicit output of first element

J , 16 octets

-2 octets grâce à Shaggy

[:/:~|.@|:^:(<4)

Essayez-le en ligne!

J , 18 octets

0{[:/:~|.@|:^:(<4)

Essayez-le en ligne!

Renvoie le premier élément de la liste des rotations triées lexicograpiquement du polyomino.

Explication:

            ^:(<4)  - do the verb on the left 4 times, storing all the steps
       |.@|:        - tranpose and reverse
    /:~             - sort up the 4 matrices
  [:                - cap the fork
0{                  - take the first matrix  

05AB1E , 10 8 octets

3FÂø})Σ˜

-2 octets grâce à @Shaggy .

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

3F  }       # Loop 3 times
  Â         #  Bifurcate (short for Duplicate & Reverse) the top of the stack
            #  (which is the input-matrix implicitly the first iteration)
   ø        #  Transpose: swap rows/columns
     )      # After the loop, wrap everything on the stack in a list
      Σ˜    # Sort this list of matrices by their flattened array (and output implicitly)

REMARQUE: Prendre le minimum avec ßou Ws'aplatira implicitement, ainsi sortira 0. Et le tri avec {ne semble pas fonctionner pour une liste de matrices, c'est pourquoi j'utilise à la Σ˜place.