De quel tetromino s'agit-il?

54

Avec un entier non signé de 16 bits N , votre tâche consiste à déterminer si sa représentation binaire mappée dans une matrice 4x4 correspond à une forme de tétromino et, dans l'affirmative, de quelle forme il s'agit.

Matrice

Chaque bit de N est cartographié dans une matrice 4x4, de gauche à droite et de haut en bas, en commençant par le plus significatif.

Exemple :

N = 17600
binary representation: 0100010011000000
matrix: [ [ 0, 1, 0, 0 ],
          [ 0, 1, 0, 0 ],
          [ 1, 1, 0, 0 ],
          [ 0, 0, 0, 0 ] ]

Formes de tetromino

Formes de base

Il existe 7 formes de tétrominos, identifiées par les lettres O , I , S , Z , L , J et T :

tetrominoes

Rotations et traductions

Si une forme est traduite et / ou pivotée dans la matrice 4x4, elle est toujours considérée comme une variation valide du même tétromino. Par exemple, 17600, 1136, 2272 et 1604 doivent tous être identifiés en tant que J tétrominoes:

exemples J valides

Ne pas emballer!

Cependant, les formes ne peuvent pas être enroulées ou déplacées au-delà des limites de la matrice. Par exemple, ni 568 ni 688 ne doivent être identifiés comme des tétrominoes J (sans parler de toute autre forme):

exemples J invalides

Clarifications et règles

  • Vous pouvez entrer les données sous forme d’entier ou directement sous forme de 16 chiffres binaires dans n’importe quel format raisonnable, tel qu’un tableau 2D, un tableau plat ou une chaîne délimitée.
  • Il est garanti que l’entrée est un entier non signé de 16 bits (ou sa représentation équivalente sous la forme d’un tableau ou d’une chaîne).
  • Lorsqu'une forme valide est identifiée, vous devez imprimer ou renvoyer la lettre d' identification de la forme, en minuscule ou en majuscule.
  • Si aucune forme n'est identifiée, vous devez imprimer ou renvoyer une valeur qui ne correspond à aucune lettre de tetromino. Vous pouvez également choisir de ne rien retourner du tout.
  • Pour être considérée comme valide, la matrice doit contenir la forme exacte du tétromino sans aucune cellule supplémentaire (voir 1911 et 34953 dans les cas de test).
  • C'est du , donc la réponse la plus courte en octets gagne!

Cas de test

Vous pouvez suivre ce lien pour obtenir les scénarios de test sous forme de tableaux 2D.

0      -> false
50     -> false
51     -> 'O'
1911   -> false
15     -> 'I'
34952  -> 'I'
34953  -> false
1122   -> 'S'
3168   -> 'Z'
785    -> 'L'
1136   -> 'J'
568    -> false
688    -> false
35968  -> 'T'
19520  -> 'T'
Arnauld
la source
Fait intéressant, je travaillais sur un problème extrêmement similaire l'autre jour avant que je ne sois distrait par la création d'une technique permettant d'utiliser des chaînes de fonctions func1 . func2 . func3dans JS: P
ETHproductions
Puis-je prendre en entrée les quatre lignes jointes 0, c'est- 1111011110111101111à- dire pour 65535?
ETHproductions
@ETHproductions Cela semble bien. J'ai modifié le défi avec un format de saisie légèrement détendu.
Arnauld
3
I: 15,240,3840,4369,8738,17476,34952,61440J: 71,113,142,226,275,550,802,1100,1136,1604,1808,2272,3208,3616,4400,8800,12832,17600,18176,25664,28928,36352,51328,57856L: 23,46,116,232,368,547,736,785,1094,1570,1856,2188,3140,3712,5888,8752,11776,12560,17504,25120,29696,35008,50240,59392O: 51,102,204,816,1632,3264,13056,26112,52224S: 54,108,561,864,1122,1728,2244,8976,13824,17952,27648,35904T: 39,78,114,228,305,562,610,624,1124,1220,1248,1824,2248,3648,4880,8992,9760,9984,17984,19520,19968,29184,35968,58368Z:99,198,306,612,1224,1584,3168,4896,9792,19584,25344,50688
Ingénieur Toast
^ Généré à l'aide de la réponse Python 3 de Lynn, car elle disposait de formats d'entrée / sortie pratiques.
Ingénieur Toast

Réponses:

6

Gelée ,  54 43 42  41 octets

-1 octet grâce à Erik l'Outgolfer (déplacer la transposition dans la chaîne répétée)

T€FṀ⁸ṙ€Zµ⁺F
ZU$3СǀḄṂ“çc3Ð6'G‘i’ị“¥Çıƭ⁵»

Un lien monadique prenant un tableau 2D d'entiers ( 1s et 0s) et renvoyant une lettre minuscule oiszljtpour le tétromino correspondant ou ws'il est invalide.

Essayez-le en ligne! ou voir la suite de tests .

Voir également ce programme qui répertorie tous les 1820 tableaux binaires 2D possibles avec exactement quatre bits définis avec leurs sorties, triés par ces sorties.

Comment?

Cette première prend les quatre rotations de l’entrée. Ensuite, il déplace les bits définis de chaque élément aussi loin que possible vers le bas, puis vers la droite et convertit les résultats en nombres binaires. Il recherche ensuite le résultat minimal dans une liste des représentations minimales de chaque tetromino valide et utilise le résultat décrémenté pour l'indexation dans les deux mots du dictionnaire concaténés zoist+ jowl, donnant lieu wà l'absence de correspondance.

T€FṀ⁸ṙ€Zµ⁺F - Link 1, shift set bits right & then down : list of lists of bits          
        µ⁺  - perform the following twice, 1st with x=input, then with x=result of that):
T€          -   truthy indexes of €ach
  F         -   flatten into a single list
   Ṁ        -   maximum (the index of the right-most bit)
    ⁸       -   chain's left argument, x
     ṙ€     -   rotate €ach left by that amount
       Z    -   transpose the result
          F - flatten (avoids an € in the main link moving this into here)

ZU$3СǀḄṂ“çc3Ð6'G‘i’ị“¥Çıƭ⁵» - Main link: list of lists of bits (the integers 0 or 1)
   3С                        - repeat this 3 times collecting the 4 results:
  $                           -   last two links as a monad:
Z                             -     transpose
 U                            -     upend (reverse each) -- net effect rotate 90° CW
      Ç€                      - call the last link as a monad for €ach
        Ḅ                     - convert from binary (vectorises)
         Ṃ                    - minimum (of the four results)
          “çc3Ð6'G‘           - code-page indexes = [23,99,51,15,54,39,71]
                              -   ...the minimal such results for l,z,o,i,s,t,j shapes
                   i          - 1-based index of minimum in there or 0 if not found
                    ’         - decrement
                      “¥Çıƭ⁵» - compressed words: "zoist"+"jowl" = "zoistjowl"
                     ị        - index into (1 indexed & modular, so -1 yields 'w',
                              -             0 yields 'l', 1 yields 'z', ...)

Méthode précédente (54 octets)

Fœr0Ḅ“çc3Ðñ'G‘i
;Z$Ḅ©f“¦µ½¿Æ‘ȯ®¬S>2ȧZU$3СǀṀ’ị“¥Çıƭ⁵»

Un lien monadique prenant un tableau 2D d'entiers ( 1s et 0s) et renvoyant une lettre minuscule oiszljtpour le tétromino correspondant ou ws'il est invalide.

Essayez-le en ligne!

Ceci vérifie qu’il y a au moins trois lignes vides (lignes + colonnes) et que certains modèles de bits ne sont présents dans aucune ligne (en particulier les nombres 5,9,10,11 et 13). faux positifs. Il aplatit et décale ensuite le nombre binaire (en rayant les zéros à la fin avant la conversion) de chacune des quatre rotations et recherche le résultat minimal dans une liste de nombres, en utilisant le résultat décrémenté pour indexer dans les deux mots du dictionnaire concaténés. zoist+ jowl, cédant wquand aucune correspondance n'a été trouvée.

Jonathan Allan
la source
Et je savais qu'il y avait un meilleur moyen que de coder en dur ...
Erik the Outgolfer
btw Je pense que ce code dépend d'une coïncidence (parce que, eh bien, zoistjowlne conviendrait pas normalement pour une chaîne sinon: p)
Erik the Outgolfer
Que voulez-vous dire "dépend d'une coïncidence"? (la recherche dans le dictionnaire n'enregistre de ...Ṁị“LZOISTJWtoute façon qu'un octet )
Jonathan Allan
Hmm ... ouais je savais que ça ne durerait pas longtemps ... en fait, je pense que vous avez volé mon ZU$3С: p
Erik the Outgolfer
J'essayais de faire la même méthode hier après avoir soumis la précédente mais je pensais être un peu fatiguée.
Jonathan Allan
28

Python 3 , 124 octets

def f(n):
 while n&4369<n/n:n>>=1
 while n&15<1:n>>=4
 return'TJLZSIO'["rēȣc63ıGtIJȱᄑ@'̢̑@@@@Ȳq".index(chr(n))%7]

Essayez-le en ligne!

Attend un entier n représentant une matrice binaire 4 × 4. Lance si aucun tetromino n'est trouvé.

La ligne 2 fait glisser la forme vers la droite jusqu'à ce qu'un 1 se trouve dans la colonne la plus à droite. (4369 est 0001 0001 0001 0001en binaire.) La ligne 3 abaisse la forme jusqu'à ce qu'un 1 apparaisse dans la rangée du bas. Ensemble cela tourne par exemple:

    0 1 0 0        0 0 0 0
    1 1 1 0  into  0 0 0 0
    0 0 0 0        0 0 1 0
    0 0 0 0        0 1 1 1

Ensuite, nous cherchons l'index de ndans cette liste:

 [114  275  547   99   54   15   51
  305   71  116  306  561 4369   64
   39  802  785   64   64   64   64
  562  113   23]
#   T    J    L    Z    S    I    O

Chaque colonne d'indice équivalent modulo 7 correspond à une forme tétromino. 64 ( @) est utilisé comme valeur de remplissage car nil ne peut pas être 64 à ce stade du code.

NB Une exception est levée pour entrée 0par informatique n/nau lieu de 1.

Lynn
la source
Pourquoi votre chaîne binaire fonctionne-t-elle? J'ai eu des problèmes avec cela dans Python 3, voir les commentaires codegolf.stackexchange.com/a/85201/53667
Karl Napf
Python utilise UTF-8 comme codage par défaut pour le code source et pour la sortie texte. Mais les fichiers PPM ne sont pas lus en UTF-8. Lorsque vous exécutez print("ÿ"), les octets écrits ne le sont c3 bf 0apas ff 0aet l'image PPM se transforme en fouillis.
Lynn
8

APL (Dyalog) , 95 94 93 89 87 octets

-2 grâce à Zacharý

Nécessite ⎕IO←0ce qui est la valeur par défaut sur de nombreux systèmes. Prend la matrice booléenne (de n'importe quelle forme!) Comme argument. Ne retourne rien si le nombre donné de bits n'est pas quatre et une ligne vide si les quatre bits donnés ne forment pas un tétromino.

{4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K2J),(⍳3)⊖¨⊂J1,⍪K31)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}

Essayez-le en ligne!

Fonctionne en créant les quatre rotations de l’entrée, puis en cherchant chaque tétromino dans chaque rotation.

{} Fonction anonyme où l'argument est représenté par :

,⍵ défaire (aplatir) l'argument

+/ résumer

4= est quatre égal à cela?

: si oui, alors (sinon rien ne retourne):

  ⍳4 quatre premières ɩ ndices; [0,1,2,3]

  ⍵∘{ Applique la fonction suivante sur chacun, en utilisant l'entrée comme argument gauche fixe

    l'argument de gauche c'est-à-dire l'entrée

   ⊢⍺ céder que (se sépare de )

   ⌽∘⍉⍣⍵ miroir et transposition (rotation de 90 °) fois

  ()∘.⍷ "Produit" extérieur, mais en utilisant Rechercher *, de la liste suivante et des rotations:

   3↑1 prenez trois éléments d'un, en complétant avec des zéros; [1,0,0]

   K← stocker cela comme K

    table (transforme en vecteur colonne); [[1],[0],[0]]

   1, ajouter un un; [[1,1],[1,0],[1,0]]("J")

   J← stocker comme J

   ()⊖¨⊂ Faire tourner tout le J verticalement, chacune des étapes suivantes:

    ⍳3 trois premiers ɩ ntegers;[0,1,2]

   nous avons [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]]("J", "L," T ")

   (), Ajoutez la liste suivante:

    2⊖J faire pivoter Jdeux pas verticalement; [[1,0],[1,1],[1,0]]("T")

    K⌽ faire pivoter les rangées de celle-ci de 1, 0 et 0 pas respectivement; [[0,1],[1,1],[1,0]]("Z")

    0 1⌽¨⊂ faire pivoter tout le tableau verticalement, pas de fois et une fois; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] ("Z", "S")

    (), Ajoutez la liste suivante:

     (2 2)4⍴¨1 remodeler un un en une matrice de 2 × 2 et une liste de 4 éléments; [[[1,1],[1,1]],[1,1,1,1]]("O", "I")

  1∊¨ pour chacun, est-ce un membre?

  ∨/ réduction OU horizontale (c.-à-d. entre les rotations; un booléen pour chaque forme)

  'OIZSLJT'/⍨ l'utiliser pour filtrer la chaîne

* Find renvoie un tableau booléen de même forme que son argument de droite, ceux-ci indiquant le coin supérieur gauche de tous les sous-tableaux identiques à l'argument de gauche.

Adam
la source
Cela fonctionnerait-il? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Zacharý
@ Zacharý Oui, merci, c'est fait.
Adám
7

JavaScript (ES6), 242 212 172 164 octets

x=>[...'OISZLJT'].filter((z,y)=>x.match(`^0*(${'99,33825|15,51|2145,195|561,2115|57,1059|135,71|1073'.split`,`[y].replace(/\d+/g,C=x=>x?x%2+C(x>>1)+x%2:'|')})0*$`))

Était censé être juste pour lancer le processus, mais je suis un peu en retard pour ça ¯ \ _ (ツ) _ / ¯

Prend une chaîne de bits, avec des lignes séparées par 0s ( '0001000110001000000'représentant 0001 0011 0010 0000) et retourne un tableau contenant le caractère représentant le tétromino, ou un tableau ne contenant rien.

Cela fonctionne en vérifiant chaque rotation de tetromino pour voir si l'entrée en tout point contient le tetromino, entouré entièrement par des zéros de chaque côté. Chaque tetromino est représenté par un ou plusieurs nombres binaires:

0 0 0 0   -> 0000 0110 1100 0000
0 1 1 0   -> 0000001100110000000
1 1 0 0   -> 110011
0 0 0 0   -> 51

0 1 0 0   -> 0100 0110 0010 0000
0 1 1 0   -> 0100001100001000000
0 0 1 0   -> 100001100001
0 0 0 0   -> 2145

Donc, pour vérifier si l’entrée contient un S tetromino, nous vérifions simplement si elle contient la représentation binaire de 51ou 2145, avec seulement 0s de chaque côté.

Quelques-uns des tétrominos ont 4 orientations. Si vous regardez leurs représentations binaires, chacune a 2 représentations qui ne sont que le miroir des deux autres. Pour économiser de l'espace, la représentation binaire est construite en avant et en arrière simultanément à la Cfonction récursive , ce qui nous permet de ne mettre que deux des orientations et d'impliquer les deux autres.


Autre approche avec les codes de caractères:

x=>[...'OISZLJT'].filter((z,y)=>x.match(`^0*(${[...'÷,êÿ,óî,ûÝ,ëúüÏ,çöïþ,ßýíÞ'.split`,`[y]].map(c=>(C=n=>n?'1e'+(n%4+2)%5-0+C(n>>2):'')(c.charCodeAt())).join`|`})0*$`))
ETHproductions
la source
3

Retina , 125 octets

s`(.*1){5}.*

{s`.*1111.*
I
s`.*111(.{2,4})1.*
$.1
T`234`\LTJ
s`.*11(.{2,4})11.*
$.1
T`2-90`S\OZ4-9
s`.*4.*

O#$`.
$.%`
O#$^`

Essayez-le en ligne! Link inclut des scénarios de test et un en-tête permettant de convertir des entiers en matrice 4x4. Explication:

s`(.*1){5}.*

Supprimez l'entrée si elle contient 5 1s.

{s`.*1111.*
I

Vérifiez toutes les rotations de l'entrée (voir ci-dessous). Si l’entrée contient quatre secondes consécutives 1, c’est un I.

s`.*111(.{2,4})1.*
$.1
T`234`\LTJ

S'il contient trois 1s consécutifs et un a 1sur la ligne suivante sous l'un des trois, mappez le nombre de caractères intermédiaires sur la lettre de résultat appropriée.

s`.*11(.{2,4})11.*
$.1

De la même manière pour deux 1s adjacents adjacents à deux 1s adjacents sur la ligne suivante.

T`2-90`S\OZ4-9

Mais aussi, comptez le nombre de rotations en utilisant les 0s autrement inutilisés .

s`.*4.*

Et abandonnez si trop de rotations ont été effectuées.

O#$`.
$.%`
O#$^`

Transposez et inversez le tableau en le faisant pivoter.

Neil
la source
3

MATL , 60 octets

Itt6tIl7tl7H15vHe"4:"G@X!HYa]4$v@BIthYaEqY+4=aa]v'OSZLJTI'w)

L'entrée est un tableau binaire 4 × 4 (matrice), utilisant ;comme séparateur de lignes. Ouput est une lettre ou vide pour no tetromino.

Essayez-le en ligne! Ou vérifiez tous les cas de test (un point est ajouté en sortie pour permettre d'identifier un résultat vide).

Explication

Le code construit 4 rotations du tableau 4 × 4 en entrée par pas de 90 degrés. Chaque tableau pivoté est complété par 2 zéros de haut en bas, ce qui le transforme en tableau de 8 × 4. Les 4 tableaux sont concaténés verticalement en un tableau 32 × 4. Les quatre tableaux en rotation dans ce tableau concaténé sont "isolés" grâce au remplissage à zéro.

Chacun des 7 modèles possibles est testé pour voir s'il est présent dans le tableau 32 × 4. Une boucle est utilisée pour cela. Chaque motif est défini par deux nombres qui, exprimés en binaire, donnent le masque 0/1 approprié. Par exemple, les chiffres 3, 6définissent la forme « S ».

Les 7 séries de 2 nombres sont disposées dans une matrice 2x7, à partir de laquelle la boucle choisira chaque colonne de manière séquentielle. La matrice est définie en plaçant tous les nombres dans la pile, en les transformant en un vecteur et en les transformant en une matrice à 2 lignes. Étant donné que la forme en "I" est définie par le nombre 15 suivi de 0, sa position à la fin permet de remplir implicitement le 0 par la fonction de remodelage.

Le masque est ensuite complété avec 3 zéros dans les quatre directions. Cela est nécessaire pour détecter les valeurs indésirables dans l'entrée.

Pour voir si le masque est présent dans le tableau 32 × 4, celui-ci est transformé en forme bipolaire (c'est-à-dire −1/1 au lieu de 0/1) et convolué avec le masque. Comme le masque en a 4, la correspondance est obtenue si une entrée du résultat de la convolution est égale à 4.

À la fin de la boucle, 7 résultats faux / vrai ont été obtenus, dont au plus un est vrai. Ceci est utilisé pour indexer une chaîne contenant les lettres de sortie possibles.

Luis Mendo
la source
3

Gelée , 53 octets

ZL0ẋW⁸tZµ⁺ZU$3С“©©“œ“Ç¿“¦©¦“ƽ‘;Uḃ2$’¤iЀṀị“÷¶Ė¡µỵỤ»

Essayez-le en ligne!

Programme complet. Prend un 4x4. Imprime ms'il ne s'agit pas d'un tétromino, sinon imprime en minuscule.

Erik l'Outgolfeur
la source
Est-il légal de prendre un tableau de tableaux de bits? Cela me sauverait comme 40 octets
ETHproductions
@ETHproductions Vous pouvez utiliser les entrées sous forme de nombre entier ou directement sous forme de tableau 2D de 4x4 chiffres binaires ou de tableau plat de 16 chiffres binaires.
Erik the Outgolfer
Euh, me sert bien pour écumer la question ...
ETHproductions
1

Perl 5 , 197 + 1 (-p) = 198 octets

s/(0000)*$//;1while s/(...)0(...)0(...)0(...)0/0${1}0${2}0${3}0${4}/;$_={51,O,15,I,4369,I,54,S,561,S,99,Z,306,Z,547,L,23,L,785,L,116,L,275,J,113,J,802,J,71,J,114,T,562,T,39,T,609,T}->{oct("0b".$_)}

Essayez-le en ligne!

Prend une chaîne de 16 bits en entrée. N'émet rien si l'entrée n'est pas un seul tétromino.

Comment?

Les deux substitutions "déplacent" la forme de saisie dans le coin inférieur droit. La chaîne de bits résultante est convertie en un entier, puis vérifiée dans un hachage d’entiers valides.

Xcali
la source
1

APL (Dyalog) , 66 octets

{'TIOJSLZ-'[(¯51 144 64,,∘+⍨12J96 ¯48J64)⍳×/(+/-4×⊢)⍵/,0j1⊥¨⍳4 4]}

Essayez-le en ligne!

L'arg est un vecteur booléen.

Calcule les distances signées des points par rapport à leur centre de gravité sous forme de nombres complexes (les parties réelles et imaginaires sont x, ∆y) et multiplie les nombres complexes ensemble. Cela s'avère être un invariant suffisant pour distinguer les tétrominoes.

ngn
la source
Méthode intéressante.
Arnauld