Que tetromino é esse?

54

Dado um número inteiro de 16 bits N não assinado , sua tarefa é determinar se sua representação binária mapeada dentro de uma matriz 4x4 corresponde a uma forma de tetromino e, em caso afirmativo, qual é a forma.

Matriz

Cada bit de N é mapeado dentro de uma matriz 4x4, da esquerda para a direita e de cima para baixo, começando pela mais significativa.

Exemplo :

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

Formas de Tetromino

Formas básicas

Existem 7 formas de tetromino, identificadas pelas letras O , I , S , Z , L , J e T :

tetrominoes

Rotações e traduções

Se uma forma é traduzida e / ou girada dentro da matriz 4x4, ainda é considerada uma variação válida do mesmo tetromino. Por exemplo, 17600, 1136, 2272 e 1604 devem ser todos identificados como J tetrominos:

exemplos J válidos

Não embrulhe!

No entanto, as formas não podem ser contornadas ou deslocadas além de qualquer limite da matriz. Por exemplo, nem 568 nem 688 devem ser identificados como J tetrominós (quanto mais qualquer outra forma):

exemplos J inválidos

Esclarecimentos e regras

  • Você pode receber a entrada como um número inteiro ou diretamente como 16 dígitos binários em qualquer formato razoável, como uma matriz 2D, uma matriz plana ou uma sequência delimitada.
  • A entrada é garantida como um número inteiro de 16 bits não assinado (ou sua representação equivalente como uma matriz ou uma sequência de caracteres).
  • Quando uma forma válida é identificada, você deve imprimir ou retornar a letra que a identifica, em maiúsculas ou minúsculas.
  • Se nenhuma forma for identificada, você deverá imprimir ou retornar um valor que não corresponda a nenhuma letra tetromina. Você também pode optar por não devolver nada.
  • Para ser considerada válida, a matriz deve conter a forma exata de tetromino sem células adicionais (consulte 1911 e 34953 nos casos de teste).
  • Isso é , então a resposta mais curta em bytes vence!

Casos de teste

Você pode seguir este link para obter os casos de teste como matrizes 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
fonte
Curiosamente, eu estava trabalhando em um problema extremamente semelhante no outro dia antes de eu me distraí criar uma técnica para cadeias de função uso func1 . func2 . func3em JS: P
ETHproductions
Posso receber informações como as quatro linhas se juntaram 0, ou seja, 1111011110111101111para 65535?
ETHproductions
@ETHproductions Parece bom. Editei o desafio com um formato de entrada um pouco relaxado.
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
^ Gerado usando a resposta Python 3 de Lynn, porque tinha formatos convenientes de entrada / saída.
Engenheiro Toast

Respostas:

6

Geléia ,  54 43 42  41 bytes

-1 byte graças a Erik the Outgolfer (movimento de transposição dentro da cadeia repetida)

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

Um link monádico tomar uma matriz 2D de inteiros ( 1s e 0s) e retornando uma letra minúscula oiszljtpara o respectivo tetromino ou wse inválido.

Experimente Online! ou veja a suíte de testes .

Veja também este programa que lista todos os 1820 arrays binários 2D possíveis com exatamente quatro bits configurados junto com suas saídas, classificados por essas saídas.

Quão?

Isso primeiro realiza todas as quatro rotações da entrada. Em seguida, desloca os bits definidos de cada um para a direita e depois para o fundo possível e converte os resultados em números binários. Em seguida, procura o resultado mínimo em uma lista das representações mínimas de cada tetromino válido e usa o resultado decrementado para indexar as duas palavras concatenadas do dicionário zoist+ jowl, produzindo wquando nenhuma correspondência foi encontrada.

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СǀṀ’ị“¥Çıƭ⁵»

Um link monádico tomar uma matriz 2D de inteiros ( 1s e 0s) e retornando uma letra minúscula oiszljtpara o respectivo tetromino ou wse inválido.

Experimente online!

Isso verifica se há pelo menos três linhas vazias (linhas + colunas) e se certos padrões de bits não estão presentes em nenhuma linha (especificamente os números 5,9,10,11 e 13); juntos, eles garantem que o próximo passo não produzirá falso-positivo. Em seguida, nivela e desloca o número binário (eliminando zeros à direita antes da conversão) de cada uma das quatro rotações e procura o resultado mínimo em uma lista de números, usando o resultado decrementado para indexar as duas palavras concatenadas do dicionário zoist+ jowl, produzindo wquando nenhuma correspondência foi encontrada.

Jonathan Allan
fonte
E eu sabia que havia uma maneira melhor de codificar ...
Erik o Outgolfer
btw eu acho que este código depende de uma coincidência (porque, bem, zoistjowlnormalmente não se encaixam em uma corda de outra forma: p)
Erik o Outgolfer
O que você quer dizer com "depende de uma coincidência"? (a pesquisa de dicionário só economiza um byte mais de ...Ṁị“LZOISTJWqualquer maneira)
Jonathan Allan
Hmm ... sim, eu sabia que isso não duraria muito ... btw acho que você roubou o meu ZU$3С: p
Erik the Outgolfer
Eu estava tentando fazer o mesmo método ontem depois de enviar o anterior, mas acho que estava um pouco 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]

Experimente online!

Espera um número inteiro n representando uma matriz binária 4 × 4. Lança se nenhum tetromino for encontrado.

A linha 2 desliza a forma para a direita até que 1 esteja na coluna mais à direita. (4369 está 0001 0001 0001 0001em binário.) A linha 3 diminui a forma até que 1 esteja na linha inferior. Juntos, isso gira, por exemplo:

    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

Em seguida, procuramos o índice ndesta 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 coluna de índices equivalente ao módulo 7 corresponde a uma forma de tetromino. 64 ( @) é usado como um valor de preenchimento, pois nnão pode ser 64 neste momento no código.

NB Uma exceção é lançada para entrada 0pela computação em n/nvez de 1.

Lynn
fonte
Por que sua string binária funciona? Eu tive problemas com isso em Python 3, ver os comentários codegolf.stackexchange.com/a/85201/53667
Karl Napf
O Python usa UTF-8 como a codificação padrão para o código-fonte e a saída de texto. Mas os arquivos PPM não são lidos no UTF-8. Quando você executa print("ÿ"), os bytes gravados c3 bf 0anão são ff 0ae a imagem PPM se transforma em lixo.
Lynn
8

APL (Dyalog) , 95 94 93 89 87 bytes

-2 graças a Zacharý

Requer ⎕IO←0qual é o padrão em muitos sistemas. Pega a matriz booleana (de qualquer forma!) Como argumento. Retorna nada se o número especificado de bits não for quatro e uma linha em branco se os quatro bits fornecidos não formarem um tetromino.

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

Experimente online!

Funciona criando todas as quatro rotações da entrada e procurando cada tetromino em cada rotação.

{} Função anônima em que o argumento é representado por :

,⍵ desviar (achatar) o argumento

+/ somar

4= quatro é igual a isso?

: se sim, então (caso contrário, não retorne nada):

  ⍳4 primeiros quatro Ɩ ndices; [0,1,2,3]

  ⍵∘{ Aplique a seguinte função em cada um, usando a entrada como argumento fixo à esquerda

    o argumento esquerdo, ou seja, a entrada

   ⊢⍺ rendimento que (separa de )

   ⌽∘⍉⍣⍵ espelhar e transpor (ou seja, girar 90 °) vezes

  ()∘.⍷ "Produto" externo, mas usando Localizar *, da lista a seguir e as rotações:

   3↑1 pegue três elementos de um, preenchendo com zeros; [1,0,0]

   K← guarde isso como K

    tabela (transformar em vetor de coluna); [[1],[0],[0]]

   1, acrescente um; [[1,1],[1,0],[1,0]]("J")

   J← armazenar como J

   ()⊖¨⊂ Gire o J inteiro verticalmente, cada uma das seguintes etapas:

    ⍳3 primeiros três Ɩ ntegers;[0,1,2]

   nós temos [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]]("J", "L," T ")

   (), Anteceda a seguinte lista:

    2⊖J gire Jdois passos verticalmente; [[1,0],[1,1],[1,0]]("T")

    K⌽ gire as linhas disso por 1, 0 e 0 etapas, respectivamente; [[0,1],[1,1],[1,0]]("Z")

    0 1⌽¨⊂ gire toda a matriz verticalmente, sem uma e outra vez; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] ("Z", "S")

    (), Anteceda a seguinte lista:

     (2 2)4⍴¨1 remodelar um em cada uma de uma matriz 2 × 2 e uma lista de 4 elementos; [[[1,1],[1,1]],[1,1,1,1]]("O", "I")

  1∊¨ para cada um, é um membro?

  ∨/ redução OR horizontal (ou seja, entre rotações; um booleano para cada forma)

  'OIZSLJT'/⍨ use isso para filtrar a string

* Find retorna uma matriz booleana da mesma forma que o argumento da direita, com as que indicam o canto superior esquerdo de todas as sub-matrizes idênticas ao argumento da esquerda.

Adão
fonte
Isso funcionaria? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Zachary
@ Zacharý Sim, obrigado, pronto.
Adám 10/08/19
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*$`))

Era para ser apenas para fazer a bola rolar, mas estou um pouco atrasado para isso ¯ \ _ (ツ) _ / ¯

Pega uma sequência de bits, com linhas separadas por 0s ( '0001000110001000000'representando 0001 0011 0010 0000) e retorna uma matriz que contém o caractere que representa o tetromino, ou uma matriz que não contém nada.

Isso funciona verificando cada rotação do tetromino para ver se a entrada em qualquer ponto contém o tetromino, cercado inteiramente por zeros em ambos os lados. Cada tetromino é representado por um ou mais números binários:

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

Portanto, para verificar se a entrada contém um S tetromino, basta verificar se ela contém a representação binária de um 51ou de 2145, com apenas 0s em ambos os lados.

Alguns dos tetrominos têm 4 orientações. Se você olhar para as representações binárias, cada uma tem 2 representações que são simplesmente o espelho das outras duas. Para economizar espaço, a representação binária é construída para frente e para trás simultaneamente com a Cfunção recursiva , permitindo colocar apenas duas orientações e ter as outras duas implícitas.


Abordagem alternativa com códigos:

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

Experimente online! O link inclui casos de teste mais um cabeçalho para converter números inteiros em uma matriz 4 × 4. Explicação:

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

Exclua a entrada se ela contiver 5 1s.

{s`.*1111.*
I

Verifique todas as rotações da entrada (veja abaixo). Se a entrada contém quatro 1s consecutivos , é um I.

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

Se ele contiver três 1s consecutivos mais um 1na próxima linha abaixo de um dos três, mapeie o número de caracteres intermediários para a letra do resultado apropriado.

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

Da mesma forma, para dois 1s adjacentes adjacentes a dois 1s adjacentes na próxima linha.

T`2-90`S\OZ4-9

Mas também conte o número de rotações usando os 0s não utilizados .

s`.*4.*

E desista se muitas rotações foram realizadas.

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

Transponha e inverta a matriz, girando-a.

Neil
fonte
3

MATL , 60 bytes

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

A entrada é uma matriz binária 4 × 4 (matriz), usando ;como separador de linhas. Ouput é uma letra ou está vazio para nenhum tetromino.

Experimente online! Ou verifique todos os casos de teste (a saída possui um ponto anexado para permitir a identificação de um resultado vazio).

Explicação

O código cria 4 rotações da matriz 4 × 4 de entrada em etapas de 90 graus. Cada matriz rotacionada é preenchida com 2 zeros para cima e para baixo, o que a transforma em uma matriz 8 × 4. As 4 matrizes são concatenadas verticalmente em uma matriz 32 × 4. As quatro matrizes rotacionadas nessa matriz concatenada são "isoladas" graças ao preenchimento zero.

Cada um dos 7 padrões possíveis é testado para verificar se está presente na matriz 32 × 4. Um loop é usado para isso. Cada padrão é definido por dois números, que expressos em binário, fornecem a máscara 0/1 apropriada. Por exemplo, números 3, 6defina a forma "S".

Os 7 conjuntos de 2 números são organizados em uma matriz 2 × 7, a partir da qual o loop seleciona cada coluna seqüencialmente. A matriz é definida empurrando todos os números para a pilha, contatenando-os em um vetor e remodelando-os em uma matriz de 2 linhas. Como a forma "I" é definida pelo número 15 seguido por 0, colocá-la no final permite que o 0 seja preenchido implicitamente pela função de remodelagem.

A máscara é preenchida com 3 zeros nas quatro direções. Isso é necessário para detectar valores indesejados na entrada.

Para verificar se a máscara está presente no arranjo 32 × 4, o último é transformado para a forma bipolar (ou seja, -1/1 em vez de 0/1) e convolvido com a máscara. Como a máscara possui 4, a correspondência ocorre se alguma entrada no resultado da convolução for igual a 4.

No final do loop, foram obtidos 7 resultados falsos / verdadeiros, no máximo um deles verdadeiro. Isso é usado para indexar em uma string contendo as possíveis letras de saída.

Luis Mendo
fonte
3

Geléia , 53 bytes

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

Experimente online!

Programa completo. Toma um 4x4. Imprime mse não for um tetromino, caso contrário, imprime em minúsculas.

Erik, o Outgolfer
fonte
É ... tomar um conjunto de matrizes de bits é legal? Isso me pouparia como 40 bytes
ETHproductions
@ETHproductions Você pode receber a entrada como um número inteiro ou diretamente como uma matriz 2D de dígitos binários 4x4 ou uma matriz plana de 16 dígitos binários.
Erik the Outgolfer
Huh, serve-me à direita para deslizando sobre a questão ...
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".$_)}

Experimente online!

Leva uma string de 16 bits como entrada. Não produz nada se a entrada não for um único tetromino.

Quão?

As duas substituições "movem" a forma de entrada para o canto inferior direito. A sequência de bits resultante é convertida em um número inteiro e, em seguida, verificada em um hash de números inteiros válidos.

Xcali
fonte
1

APL (Dyalog) , 66 bytes

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

Experimente online!

O arg é um vetor booleano.

Calcula distâncias sinalizadas dos pontos até o centro de gravidade como números complexos (a parte real e imaginária é x, y) e multiplica os números complexos juntos. Isso acaba sendo um invariante bom o suficiente para distinguir entre os tetrominós.

ngn
fonte
Método interessante.
Arnauld