¿Qué tetromino es este?

54

Dado un número entero de 16 bits sin signo N , su tarea es determinar si su representación binaria asignada dentro de una matriz 4x4 coincide con una forma de tetromino y, de ser así, de qué forma es.

Matriz

Cada bit de N se asigna dentro de una matriz 4x4, de izquierda a derecha y de arriba a abajo, comenzando por la más significativa.

Ejemplo :

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

Formas Tetromino

Formas de base

Hay 7 formas de tetromino, identificadas por las letras O , I , S , Z , L , J y T :

tetrominoes

Rotaciones y traducciones

Si una forma se traslada y / o gira dentro de la matriz 4x4, todavía se considera una variación válida del mismo tetromino. Por ejemplo, 17600, 1136, 2272 y 1604 deberían identificarse como J tetrominoes:

ejemplos válidos de J

¡No lo envuelvas!

Sin embargo, las formas no pueden ajustarse o desplazarse más allá de cualquier límite de la matriz. Por ejemplo, ni 568 ni 688 deben identificarse como J tetrominoes (y mucho menos cualquier otra forma):

ejemplos J inválidos

Aclaraciones y reglas.

  • Puede tomar la entrada como un entero o directamente como 16 dígitos binarios en cualquier formato razonable, como una matriz 2D, una matriz plana o una cadena delimitada.
  • Se garantiza que la entrada sea un entero de 16 bits sin signo (o su representación equivalente como una matriz o una cadena).
  • Cuando se identifica una forma válida, debe imprimir o devolver la letra que identifica la forma, ya sea en mayúsculas o minúsculas.
  • Si no se identifica ninguna forma, debe imprimir o devolver un valor que no coincida con ninguna letra de tetromino. También puede optar por no devolver nada en absoluto.
  • Para ser considerada válida, la matriz debe contener la forma exacta de tetromino sin células adicionales (ver 1911 y 34953 en los casos de prueba).
  • Este es el , por lo que gana la respuesta más corta en bytes.

Casos de prueba

Puede seguir este enlace para obtener los casos de prueba como matrices 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
fuente
Curiosamente, estaba trabajando en un problema extremadamente similar el otro día antes de distraerme creando una técnica para usar cadenas de funciones func1 . func2 . func3en JS: P
ETHproductions
¿Puedo tomar datos como las cuatro filas unidas 0, es decir, 1111011110111101111para 65535?
ETHproductions
@ETHproductions Eso parece estar bien. He editado el desafío con un formato de entrada ligeramente relajado.
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
Engineer Toast
^ Generado usando la respuesta Python 3 de Lynn porque tenía formatos de entrada / salida convenientes.
Engineer Toast

Respuestas:

6

Gelatina ,  54 43 42  41 bytes

-1 byte gracias a Erik the Outgolfer (mover transposición dentro de la cadena repetida)

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

Un enlace monádico que toma una matriz 2D de enteros ( 1sy 0s) y devuelve una letra minúscula oiszljtpara el tetromino respectivo o wsi no es válido.

Pruébalo en línea! o ver el conjunto de pruebas .

Consulte también este programa que enumera todas las 1820 matrices binarias 2D posibles con exactamente cuatro bits establecidos junto con sus salidas, ordenadas por esas salidas.

¿Cómo?

Este primero toma las cuatro rotaciones de la entrada. Luego, desplaza los bits establecidos de cada uno lo más hacia la derecha y luego lo más hacia abajo posible y convierte los resultados en números binarios. Luego busca el resultado mínimo en una lista de las representaciones mínimas de cada tetromino válido y utiliza el resultado decrementado para indexar en las dos palabras concatenadas del diccionario zoist+ jowl, lo que produce wcuando no se encuentra ninguna coincidencia.

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étodo anterior (54 bytes)

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

Un enlace monádico que toma una matriz 2D de enteros ( 1sy 0s) y devuelve una letra minúscula oiszljtpara el tetromino respectivo o wsi no es válido.

Pruébalo en línea!

Esto comprueba que hay al menos tres líneas vacías (filas + columnas) y que ciertos patrones de bits no están presentes en ninguna línea (específicamente los números 5,9,10,11 y 13), estos juntos aseguran que el siguiente paso no produzca falsos positivos. Luego se aplana y luego desplaza el número binario (separando los ceros finales antes de la conversión) de cada una de las cuatro rotaciones, y busca el resultado mínimo en una lista de números, usando el resultado decrementado para indexar las dos palabras del diccionario concatenadas zoist+ jowl, cediendo wcuando no se encontró coincidencia.

Jonathan Allan
fuente
Y sabía que había una mejor manera que el hardcoding ...
Erik the Outgolfer
por cierto, creo que este código depende de una coincidencia (porque, de zoistjowllo contrario, normalmente no encajaría para una cadena: p)
Erik the Outgolfer
¿Qué quieres decir con "depende de una coincidencia"? (la búsqueda en el diccionario solo ahorra un byte de ...Ṁị“LZOISTJWtodos modos)
Jonathan Allan
Hmm ... sí, sabía que esto no duraría mucho ... por cierto creo que me robaste ZU$3С: p
Erik the Outgolfer
Intenté hacer el mismo método ayer después de enviar el anterior, pero creo que estaba un poco cansado.
Jonathan Allan
28

Python 3 , 124 bytes

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]

Pruébalo en línea!

Espera un número entero n que representa una matriz binaria 4 × 4. Lanza si no se encuentra tetromino.

La línea 2 desliza la forma hacia la derecha hasta que un 1 esté en la columna más a la derecha. (4369 está 0001 0001 0001 0001en binario.) La línea 3 baja la forma hasta que un 1 está en la fila inferior. Juntos, esto se convierte, por ejemplo:

    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

Luego buscamos el índice de nen esta lista:

 [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

Cada columna de índices de módulo equivalente 7 corresponde a una forma de tetromino. 64 ( @) se usa como un valor de relleno, ya nque no puede ser 64 en este punto del código.

NÓTESE BIEN. Se lanza una excepción para la entrada 0por computación en n/nlugar de 1.

Lynn
fuente
¿Por qué funciona tu cadena binaria? Tuve problemas con eso en Python 3, vea los comentarios codegolf.stackexchange.com/a/85201/53667
Karl Napf
Python usa UTF-8 como la codificación predeterminada para el código fuente y para la salida de texto. Pero los archivos PPM no se leen en UTF-8. Cuando ejecuta print("ÿ"), los bytes que se escriben son c3 bf 0a, no ff 0a, y la imagen PPM se convierte en basura.
Lynn
8

APL (Dyalog) , 95 94 93 89 87 bytes

-2 gracias a Zacharý

Requiere ⎕IO←0cuál es el predeterminado en muchos sistemas. Toma una matriz booleana (¡de cualquier forma!) Como argumento. No devuelve nada si el número dado de bits no es cuatro, y una línea en blanco si los cuatro bits dados no forman un tetromino.

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

Pruébalo en línea!

Funciona creando las cuatro rotaciones de la entrada, luego busca cada tetromino en cada rotación.

{... } función anónima donde el argumento está representado por :

,⍵ desentrañar (aplastar) el argumento

+/ sumalo

4= es cuatro igual a eso?

: si es así, entonces (si no devuelve nada)

  ⍳4 primeros cuatro Ɩ ndices; [0,1,2,3]

  ⍵∘{ Aplique la siguiente función en cada uno, usando la entrada como argumento izquierdo fijo

    el argumento izquierdo, es decir, la entrada

   ⊢⍺ rendimiento que (se separa de )

   ⌽∘⍉⍣⍵ espejo y transposición (es decir, girar 90 °) veces

  (... )∘.⍷ "producto" externo, pero usando Find *, de la siguiente lista y las rotaciones:

   3↑1 tome tres elementos de uno, rellenando con ceros; [1,0,0]

   K← almacenar eso como K

    tabla (convertir en vector de columna); [[1],[0],[0]]

   1, anteponer uno; [[1,1],[1,0],[1,0]]("J")

   J← almacenar como J

   (... )⊖¨⊂ rotar todo el J verticalmente, cada uno de los siguientes pasos:

    ⍳3 primeros tres Ɩ ntegers;[0,1,2]

   tenemos [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]]("J", "L," T ")

   (... ), anteponga la siguiente lista:

    2⊖J gire Jdos pasos verticalmente; [[1,0],[1,1],[1,0]]("T")

    K⌽ rotar las filas de eso en 1, 0 y 0 pasos respectivamente; [[0,1],[1,1],[1,0]]("Z")

    0 1⌽¨⊂ rotar todo el conjunto verticalmente, no veces y una vez; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] ("Z", "S")

    (... ), anteponga la siguiente lista:

     (2 2)4⍴¨1 remodelar uno en cada una de una matriz de 2 × 2 y una lista de 4 elementos; [[[1,1],[1,1]],[1,1,1,1]]("O", "I")

  1∊¨ para cada uno, ¿uno es miembro?

  ∨/ reducción horizontal OR (es decir, a través de rotaciones; un booleano para cada forma)

  'OIZSLJT'/⍨ usar eso para filtrar la cadena

* Buscar devuelve una matriz booleana de la misma forma que su argumento derecho, con unos que indican la esquina superior izquierda de todas las submatrices idénticas al argumento izquierdo.

Adán
fuente
¿Funcionaría esto? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Zacharý
@ Zacharý Sí, gracias, hecho.
Adám
7

JavaScript (ES6), 242 212 172 164 bytes

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*$`))

Se suponía que era solo para hacer rodar la pelota, pero llego un poco tarde para eso ¯ \ _ (ツ) _ / ¯

Toma una cadena de bits, con filas separadas por 0s (que '0001000110001000000'representan 0001 0011 0010 0000) y devuelve una matriz que contiene el carácter que representa el tetromino, o una matriz que no contiene nada.

Esto funciona comprobando cada rotación de tetromino para ver si la entrada en cualquier punto contiene el tetromino, rodeado completamente por ceros a cada lado. Cada tetromino está representado por uno o más números binarios:

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

Por lo tanto, para verificar si la entrada contiene un tetromino S, simplemente verificamos si contiene la representación binaria de uno 51u otro 2145, con solo 0s a cada lado.

Algunos de los tetrominoes tienen 4 orientaciones. Si nos fijamos en las representaciones binarias de estos, cada uno tiene 2 representaciones que son simplemente el espejo de los otros dos. Para ahorrar espacio, la representación binaria se construye hacia adelante y hacia atrás simultáneamente con la Cfunción recursiva , lo que nos permite poner solo dos de las orientaciones y tener las otras dos implícitas.


Enfoque alternativo con códigos de barras:

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*$`))
ETHproducciones
fuente
3

Retina , 125 bytes

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#$^`

Pruébalo en línea! El enlace incluye casos de prueba más un encabezado para convertir de enteros a una matriz 4 × 4. Explicación:

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

Elimine la entrada si contiene 5 1s.

{s`.*1111.*
I

Verifique todas las rotaciones de la entrada (ver abajo). Si la entrada contiene cuatro 1s consecutivos , es un I.

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

Si contiene tres 1s consecutivos más a 1en la siguiente línea debajo de uno de los tres, entonces asigne el número de caracteres intermedios a la letra de resultado apropiada.

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

Del mismo modo para dos 1s adyacentes adyacentes a dos 1s adyacentes en la línea siguiente.

T`2-90`S\OZ4-9

Pero también mantenga el recuento de la cantidad de rotaciones utilizando los 0s no utilizados .

s`.*4.*

Y renunciar si se han realizado demasiadas rotaciones.

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

Transponga e invierta la matriz, girándola.

Neil
fuente
3

MATL , 60 bytes

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

La entrada es una matriz binaria 4 × 4 (matriz), que se usa ;como separador de filas. Ouput es una letra o vacía para no tetromino.

Pruébalo en línea! O verifique todos los casos de prueba (la salida tiene un punto agregado para permitir identificar un resultado vacío).

Explicación

El código construye 4 rotaciones de la matriz de entrada 4 × 4 en pasos de 90 grados. Cada matriz girada está acolchada con 2 ceros hacia arriba y hacia abajo, lo que la transforma en una matriz de 8 × 4. Las 4 matrices se concatenan verticalmente en una matriz de 32 × 4. Los cuatro conjuntos rotados dentro de este conjunto concatenado están "aislados" gracias al relleno de cero.

Cada uno de los 7 patrones posibles se prueba para ver si está presente en la matriz de 32 × 4. Se usa un bucle para esto. Cada patrón está definido por dos números, que expresados ​​en binario dan la máscara 0/1 apropiada. Por ejemplo, los números 3, 6definen la forma de "S".

Los 7 conjuntos de 2 números están organizados en una matriz de 2 × 7, de la cual el ciclo seleccionará cada columna secuencialmente. La matriz se define empujando todos los números a la pila, poniéndolos en contacto en un vector y reconfigurando en una matriz de 2 filas. Dado que la forma "I" está definida por el número 15 seguido de 0, ponerla al final permite que el 0 se rellene implícitamente con la función de remodelación.

La máscara se rellena con 3 ceros en las cuatro direcciones. Esto es necesario para detectar valores no deseados en la entrada.

Para ver si la máscara está presente en la matriz de 32 × 4, esta última se transforma en forma bipolar (es decir, -1/1 en lugar de 0/1) y se convoluciona con la máscara. Como la máscara tiene 4 unos, la coincidencia ocurre si alguna entrada en el resultado de convolución es igual a 4.

Al final del ciclo, se han obtenido 7 resultados falsos / verdaderos, como máximo uno de los cuales es verdadero. Esto se utiliza para indexar en una cadena que contiene las posibles letras de salida.

Luis Mendo
fuente
3

Jalea , 53 bytes

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

Pruébalo en línea!

Programa completo Toma un 4x4. Imprime msi no es un tetromino, de lo contrario imprime en minúsculas.

Erik el Outgolfer
fuente
¿Es ... tomar una matriz de matrices de bits es legal? Eso me ahorraría como 40 bytes
ETHproductions
@ETHproductions Puede tomar la entrada como un entero, o directamente como una matriz 2D de dígitos binarios 4x4 o una matriz plana de 16 dígitos binarios.
Erik the Outgolfer
Huh, me sirve justo para pasar por alto la pregunta ...
ETHproductions
1

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

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".$_)}

Pruébalo en línea!

Toma una cadena de 16 bits como entrada. No genera nada si la entrada no es un solo tetromino.

¿Cómo?

Las dos sustituciones "mueven" la forma de entrada a la esquina inferior derecha. La cadena de bits resultante se convierte en un entero, luego se verifica en un hash de enteros válidos.

Xcali
fuente
1

APL (Dyalog) , 66 bytes

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

Pruébalo en línea!

El argumento es un vector booleano.

Calcula distancias firmadas de los puntos a su centro de gravedad como números complejos (la parte real e imaginaria son ∆x, ∆y) y multiplica los números complejos juntos. Esto resulta ser una invariante lo suficientemente buena como para distinguir entre los tetrominoes.

ngn
fuente
Método interesante
Arnauld