Espera, que tetrominó era esse?

Sep 14 2020

fundo

Tetris é um jogo para um jogador jogado em uma grade retangular com peças de tetromino.

Quando você preenche uma ou mais linhas com tetrominós, as linhas preenchidas são removidas e todos os blocos acima delas se movem para baixo de acordo. Nos diagramas a seguir, .é um espaço vazio, #é um bloco existente, e o tetrominó marcado com As é o que acabou de ser colocado:

One line cleared example

#...AA.. -> ........
####AA##    #...##..

---

Two lines cleared example
(note that the 3rd line moved down once, while the top line moved twice)

...A....    ........
###A####    ........
##.A.##. -> ...#....
###A####    ##.#.##.
####.###    ####.###

Desafio

Dois estados da placa serão fornecidos como entrada. Um é logo antes de um tetrominó específico aparecer (o estado do lado esquerdo dos diagramas acima, sem As), e o outro está logo após o tetrominó ser colocado e as limpezas de linha serem completadas (o estado do lado direito). Dada essa informação, recupere o tipo de tetrominó colocado entre os dois estados, que é um dos sete tipos a seguir:

O   J      L   S    T    Z    I
##  #      #   ##   #   ##   ####
##  ###  ###  ##   ###   ##

Você pode assumir o seguinte:

A entrada é válida; os dois tabuleiros têm as mesmas dimensões e o estado do jogo pode ser alterado do primeiro para o segundo, colocando um único tetromino. Além disso, o tetrominó colocado está completamente dentro da grade antes que ocorra a limpeza da linha (ou seja, ele não será colocado acima do teto da grade fornecida, mesmo parcialmente).
A resposta é única.
A largura do tabuleiro é de pelo menos 5.

Para este desafio, ignore as regras de rotação dos jogos reais de Tetris e assuma que qualquer colocação de tetrominó é válida, desde que o tetrominó não se sobreponha a blocos existentes ou flutue no ar. Isso permite colocar um tetromino dentro de uma sala fechada (o que realmente acontece em alguns jogos exóticos).

Você pode considerar a entrada como uma matriz (ou equivalente) consistindo em dois valores distintos para espaços e blocos. Você pode enviar o tipo de tetrominó como um dos sete valores distintos de sua escolha. Os formatos de saída permitidos incluem números, strings e, possivelmente, matrizes aninhadas ou multidimensionais de números e / ou strings.

Aplicam-se as regras padrão de golfe de código . O código mais curto em bytes vence.

Casos de teste

A notação é a mesma do exemplo acima. Beforee Aftersão as duas grades de entrada, Answeré a saída esperada (fornecida como código alfabético) e Explanationmostra onde o tetrominó é colocado.

Before:
......
......

After:
..##..
..##..

Answer: O
Explanation:
..AA..
..AA..

----------------

Before:
..####
...###
#.####

After:
......
......
..####

Answer: T
Explanation:
..####
AAA###
#A####

----------------

Before:
...###
...###
#.....

After:
......
..####
#.....

Answer: L (J doesn't work since the piece will be floating)
Explanation:
..A###
AAA###
#.....

----------------

Before:
##..##
##..##
##..##

After:
......
###.##
##.###

Answer: S
Explanation:
##A.##
##AA##
##.A##

----------------

Before:
##.##
##..#
##.##

After:
.....
.....
.....

Answer: T
Explanation: self-explanatory

----------------

Before:
.###.
#...#
.....
#...#
.###.

After:
.....
.###.
#...#
..#..
.###.

Answer: T
Explanation:
.###.
#...#
..A..
#AAA#
.###.

Respostas

14 Arnauld Sep 14 2020 at 12:16

JavaScript (ES10), 286 282 bytes

Espera (a)(b), onde \$a\$e \$b\$são 2 listas de strings binárias. Retorna um número inteiro entre \$0\$e \$6\$para JLTIOZS, ou \$-1\$ se não houver solução (mas não devemos apoiar isso).

a=>b=>"0NF71ZMA13FM000F1F1F1IFL2R8I38LT357N368H".match(/../g).findIndex(p=>b.some((r,y)=>[...r].some((_,x)=>!b.some((s,i)=>[...a.map(B=r=>'0b'+r),~0].flatMap(t=(r,Y,a)=>~(q=((parseInt(p,36)||4369)>>(Y-y)*4&15)<<x,t|=q&a[Y+1],q|=q&r?~0:r)+2**s.length?q:(i--,[]))[i]^B(s)|!t))))%14>>1

Experimente online!

Quão?

Codificação de forma

Cada forma é codificada com 2 dígitos na base 36, o que permite armazenar:

$$\lfloor 2\times\log_2 36\rfloor=10\text{ bits}$$

Os bits são organizados em um \$4\times 4\$matriz, com a peça encaixada no canto superior direito. O bit menos significativo é mapeado para a célula superior direita e existem 6 zeros iniciais implícitos.

Exemplos:

O 1 ^r entrada é 0Nna base 36, o qual é \$23\$em decimal e \$0000010111\$em binário. Este é um J.
A 6 ^th entrada é FMna base 36, o qual é \$562\$em decimal e \$1000110010\$em binário. Este é um T.

Todas as formas podem ser codificadas dessa forma, exceto a vertical I. Este é codificado como 00e seu valor real ( \$4369\$ em decimal) é codificado separadamente.

Algoritmo principal

O algoritmo principal consiste em 5 loops aninhados onde tentamos colocar cada forma \$p\$em cada posição possível \$(x,y)\$na grade \$a\$e descobrir qual leva para a grade \$b\$.

Sempre que uma linha é completada, nós produzimos um array vazio de forma que .flatMap()deleta esta linha e nós decrementamos o índice \$i\$ da entrada que precisa ser lida na matriz resultante para contabilizar a mudança de linha.

Podemos acabar com um negativo \$i\$. Mas porque usamos um XOR para a comparação, as linhas indefinidas se comportam como se estivessem definidas para \$0\$, que é o que queremos.

"...".match(/../g)              // list of shapes
.findIndex(p =>                 // for each shape p:
  b.some((r, y) =>              //   for each y:
    [...r].some((_, x) =>       //     for each x:
      !b.some((s, i)=>          //       for each row s at position i in b:
        [ ...a.map(             //         using the helper function B, decode a[] by
            B = r => '0b' + r   //         converting each binary string to an integer
          ), ~0                 //         and append a full line at the bottom
        ].flatMap(t =           //         initialize t to a non-numeric value
        (r, Y, a) =>            //         for each row r at position Y in this array:
          ~(                    //
            q = (               //           q is the 4-bit mask of the shape
              ( parseInt(p, 36) //           decoded from the base-36 value p,
                || 4369 )       //
              >> (Y - y) * 4    //           keeping only the bits for this row
              & 15              //
            ) << x,             //           and left-shifting by x
            t |= q & a[Y + 1],  //           update the 'touching' mask
            q |= q & r ? ~0     //           invalidate the row if q overlaps r
                       : r      //           otherwise, merge q and r
          ) + 2 ** s.length ?   //           if the resulting line is not full:
            q                   //             yield q
          :                     //           else:
            (i--, [])           //             decrement i and yield an empty array,
                                //             which results in the deletion of this
                                //             line by flatMap()
        )[i]                    //         end of flatMap(); extract the i-th row
        ^ B(s)                  //         the test fails if this row is not equal to s
        | !t                    //         or the shape is floating in the air
      )                         //       end of some()
    )                           //     end of some()
  )                             //   end of some()
)                               // end of findIndex()

Resultado final

As formas são armazenadas na seguinte ordem:

0N F7 1Z MA 13 FM 00 0F 1F 1F 1I FL 2R 8I 38 LT 35 7N 36 8H
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19
J  J  L  L  T  T  I  I  O  O  Z  Z  S  S  J  J  L  L  T  T

é por isso que o resultado final é o valor retornado pelo .findIndex()módulo \$14\$, dividido por \$2\$e arredondado para \$0\$.

(NB: a forma Oé armazenada duas vezes para não quebrar o padrão.)

10 xash Sep 14 2020 at 09:18

Brachylog , ¹⁵⁶ 124 bytes

Pega duas matrizes, 1indicando um ladrilho vazio, 2indicando um ladrilho com uma peça. Maps O => 15, I => 1, J => 57, L => 60, S => 30, T => 23, Z => 51.

hI{∧Ḋ}ᵐ²O;I{zzᵐ+ᵐ²};21ẹᵗ↔c{≡ᵛ²h|∧1}ᵍbᵐ{-₁ᵐ²}ʰc~t?&h{{∧2}ᵐ}ʰ↺₁;O↰₂c∋3∧O{{¬=₀&}ˢ\}↰₇{\↔ᵐ|}{↔↔ᵐ|}{l₂ccẹ~ḃ{15|23|30|51|57|60}}|1

Experimente online! ou tente todos os casos de teste (com E / S mais agradável)! (A contagem de bytes é um pouco mais longa porque o cabeçalho aumenta os números do predicado.)

Como funciona

Procuramos uma matriz Opara que o sinal de adição Oapós as regras de remoção seja igual ao resultado. Em seguida O, aparamos para conter uma submatriz, limitada pelo tetrominó. Tentando todas as orientações, ele se encaixa em uma matriz 2 por x - então podemos convertê-lo da base 2. Caso contrário, é a Ipeça.

h{∧Ḋ}ᵐ²O

Antes deste desafio, eu teria criado uma matriz da mesma dimensão pegando o comprimento de entrada, mapeando o comprimento das linhas sobre ela, e dizer que cada elemento deveria ser um número ... mas isso é muito mais puro: Oé a entrada, mas cada elemento em é apenas qualquer número. Isso é muito mais puro!

;I{zzᵐ+ᵐ²}

O + Entrada

;21ẹᵗ↔c{≡ᵛ²h|∧1}ᵍbᵐ

Esta é uma maneira muito complicada de dividir as linhas em ((contém apenas 2s), (não contém apenas 2s)). Existem versões tecnicamente mais curtas, mas todas as minhas tentativas forçaram a rotulagem dos números, desacelerando o programa até a força bruta pura. (Foi muito frustrante encontrar uma versão que funcionasse.)

 {-₁ᵐ²}ʰc~t?

Subtraia 1 das linhas removidas e junte ((continha apenas 2s, agora apenas 1s), (resto)) novamente. Isso deve ser igual à segunda matriz de entrada.

 &h{{∧2}ᵐ}ʰ↺₁;O↰₃c∋3

Se pegarmos a matriz de entrada, defina a linha superior para apenas 2s, gire-a para cima e, depois de adicionar O, deve haver um 3: então o tetrominó não estava flutuando.

∧O{{¬=₀&}ˢ\}↰₅

Apare Opara que contenha apenas o tetromino. Seria bom se isso acabasse aqui. No entanto, Onão é garantido que seja um tetrominó agora e pode ser algum 1s desconectado. Então …

{\↔ᵐ|}{↔↔ᵐ|}{l₂ccẹ~ḃ{15|23|30|51|57|60}}|1

Verifique todas as rotações e, se for uma matriz 2 por x, converta para a base 2 e verifique se um dos números corresponde. Se nada corresponder, é a peça I.