^{Desafio retirado do meu concurso de desafio de código da universidade}

^{Na verdade, este é o dia 0, mas o desafio de ontem foi muito fácil e pode ser uma brincadeira de outra pergunta aqui.}

Tetris é um videogame que se tornou popular nos anos 80. Consiste em colocar uma série de peças com formas diferentes que caem em um tabuleiro, para que se encaixem da maneira mais compacta possível.

Neste problema, assumiremos uma sequência de peças que caem, cada uma em uma determinada posição e com uma certa orientação que não pode ser alterada. As peças são empilhadas quando caem e as linhas completas não são eliminadas (como no jogo original). O objetivo é determinar a altura final de cada coluna do tabuleiro depois que todas as peças caírem.

Há um total de 7 peças diferentes, mostradas na figura:

Desafio

Dada uma lista de peças, produza a altura de todas as colunas do tabuleiro depois que todas as peças caírem

Uma peça consiste em três números: I, R e P. O primeiro número, I, é o identificador da peça (um número entre 1 e 7, na mesma ordem que na figura). O segundo número, R, é a rotação da peça. Pode assumir os valores 0, 90, 180 ou 270 e representa o ângulo de rotação da peça no sentido anti-horário. O terceiro número, P, indica a posição da peça. Representa a coluna à esquerda ocupada pela peça (pode ser um índice de 1 ou 0. Por favor, especifique).

Exemplo e caso de teste (1 índice)

• Dado [[1, 0, 1], [4, 0, 1], [5, 90, 4]]

• Resultado [3, 3, 1, 3, 2]

• Dado [[6, 270, 4], [1, 180, 5], [1, 90, 6], [7, 0, 4]]

• Resultado [0, 0, 0, 9, 9, 8, 3, 3]

• [[3,0,1],[3,180,3]]Saída dada[1,1,4,4,4]

• [[2,180,1],[2,0,3]]Saída dada[2,2,4,3,3]

Notas

• Isso é código-golfe
• Linha / coluna pode ser 1 ou 0 índice. Por favor especifique.
• Você pode redefinir os valores de entrada (talvez queira chamar a peça 1 como A, etc.). Nesse caso, especifique

Questões

• Podemos usar 4 valores distintos em vez de um ângulo em graus ?: Sim

• Devemos lidar com "furos" se uma peça não se encaixar exatamente nas anteriores ?: Sim

• A altura ou a largura da placa são limitadas? Não. Nem a largura nem a altura são limitadas

Obrigado @Arnauld pelas imagens e pelos casos de teste *. *

JavaScript (Node.js) ,  286284 270266  bytes

$[0..3]$

a=>a.map(([p,r,x])=>(g=y=>y>3?g(+!Y--):b[Y+y]&(m[y]=('0x'+`717433667233ff4717333327661${1e12+0x5e7056a566ffff57efa65n.toString(4)}`[(p*2+r*56+y*99+13)%113])<<x)?m.map(v=>(g=x=>v&&g(x+1,H[x]=v&1?Y:~~H[x],v>>=1))(0,b[++Y]|=v)):g(y+1))(Y=a.length*4),m=[b=[-1]],H=[])&&H

Experimente online! ou tente uma versão aprimorada que também exiba o quadro final.

Codificação de forma

Todas as peças são armazenadas exatamente como 4 nibbles (4x4 bits), com as linhas classificadas na ordem inversa e o pixel mais à esquerda mapeado para o bit menos significativo. Em outras palavras, a representação binária da forma é espelhada vertical e horizontalmente.

Exemplo:

Função hash e tabela de pesquisa

$p \in [0..6]$$r \in [0..3]$$y \in [0..3]$$n$

Somente as primeiras entradas são armazenadas explicitamente. Tudo o resto é definido como .$82$$0$

Essas entradas são compactadas como:

`717433667233ff4717333327661${1e12+0x5e7056a566ffff57efa65n.toString(4)}`

que se expande para os seguintes 82 petiscos:

"717433667233ff47173333276611000000000000113213001112221112123333333311133233221211"

O uso de hexadecimal no formato final é necessário apenas para as duas representações horizontais da peça , portanto, na string acima.$I$"ff"

Os parâmetros da função hash foram forçados de maneira bruta de maneira a otimizar zeros à esquerda e à direita. O fato de a string poder ser compactada um pouco mais usando 1e12os zeros no meio e uma conversão da base 16 para a base 4 na parte certa é apenas um efeito colateral bem-vindo, mas inesperado. :-)

Aqui está uma demonstração do processo de desembalagem para todas as peças e todas as rotações.

Comentado

a => a.map(([p, r, x]) => (     // for each piece p with rotation r and position x:
  g = y =>                      //   g = recursive function taking y
    y > 3 ?                     //   if y is greater than 3:
      g(+!Y--)                  //     reset y to 0, decrement Y and try again
    :                           //   else:
      b[Y + y] & (              //     test if we have a collision of the board with
        m[y] =                  //     the y-th row m[y] of the current piece
          ('0x' + `717...`[     //     which is extracted from a lookup table
            (p * 2 + r * 56 +   //     using the hash function described in the
             y * 99 + 13) % 113 //     previous paragraph
          ]) << x               //     and shifted to the left according to x
      ) ?                       //     if we have a collision:
        m.map(v => (            //       we iterate again on the piece rows stored in m[]
          g = x =>              //         g = recursive function taking x
            v &&                //         if v is not equal to 0:
            g(                  //           do a recursive call:
              x + 1,            //             increment x
              H[x] =            //             update the height at x:
                v & 1 ?         //               if this bit is set:
                  Y             //                 set it to Y
                :               //               else:
                  ~~H[x],       //                 leave it unchanged or force it to 0
                                //                 if it was still undefined
              v >>= 1           //             shift v to the right
            )                   //           end of recursive call
          )(0,                  //         initial call to g with x = 0
               b[++Y] |= v)     //         increment Y and copy the piece row to the board
        )                       //     end of map()
      :                         //   else (no collision):
        g(y + 1)                //     do a recursive call to test the next row
  )(Y = a.length * 4),          //   initial call to g with y = Y = 4 * the number of pieces
                                //   (assuming the worst case: piled vertical I pieces)
  m = [b = [-1]], H = []        //   initialize m[], b[] and H[]
                                //   we set a full line at the bottom of b[]
) && H                          // end of map(); return H[]

C (clang) , 253 239 221 212 bytes

t(*a,*b,c){char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVWhU😎EQV😀RTYT😉UU";for(size_t*p,f,n,y,i;c--;b++){f=1<<(8-*b)/3;p=z+*b++*8+*b++%f*2;f=n=*p;for(y=i=0;i<=f%4;y=fmax(y,a[*b+i++]+n%4))n/=4;for(;i--;a[*b+i]=y+n%4)n/=4;}}

Experimente online!

ps Na verdade, o tamanho do código é 221 bytes (mas 212 caracteres) devido aos caracteres UNICODE codificados em UTF-8. Mas o tio.run o trata como código de 212 bytes ...

O tamanho do código no meu computador é 209 caracteres (218 bytes). Mas não pude substituir \225por char visível em tio.run 😞

Código ungolfed

// a - output array (must be zeroed), b - array of block info, c - number of blocks

// Figure codes: 2->0, 3->1, 6->2, 1->3, 5->4, 7->5, 4->6 (0,1 are L-figures, 2 is is T-figure, 3 is a line 1x4; 4,5 are zigzags; 6 is a cube 2x2)
// Vertical and horizontal positions are zero-indexed, angles = 0..3

t(*a,*b,c)
{
  char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVWhU😎EQV😀RTYT😉UU";  // UTF-8
//char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVW\1hU😎\26EQV😀RTYT😉UU";  // 3 bytes longer (use it if you can't copy previous string correctly) :)
  // Blocks
  for(size_t*p,f,n,y,i;c--;b++){
    f=1<<(8-*b)/3;  // number of figure variants
    p=z+*b++*8+*b++%f*2;
    // Get top base line position (y)
    f=n=*p;  // figure width, TBLs and HATs
    for(y=i=0;i<=f%4;
      y=fmax(y,a[*b+i++]+n%4))
      n/=4;
    // Add heights (HATs)
    for(;i--;
      a[*b+i]=y+n%4)
      n/=4;
  }
}  // 215 chars (224 bytes)

Descrição

Vamos encontrar a linha de base superior ( TBL ) de cada figura e descrevê-la como um número de células abaixo da TBL para cada posição horizontal. Também vamos descrever o número de células (altura) acima do TBL ( HAT ).

Por exemplo:

                       ________ ________
_ [] _____ HAT = 1,0,0 [] [] [] HAT = 0,0,0 ___ [] [] _ ​​HAT = 0,1,1 [] [] [] HAT = 0,0,0
 [] [] [] TBL = 1,1,1 [] TBL = 2,1,1 [] [] TBL = 1,1,0 [] TBL = 1,2,1

Vamos descrever TBLs e HATs para cada figura e cada ângulo de rotação:

Largura TBLs HATs
----- ------- -------
Figuras L:
  3 1 1 1 1 0 0 // 0 °
  2 1 1 0 2 // 90 °
  3 1 1 2 0 0 0 // 180 °
  2 3 1 0 0 // 270 °

  3 1 1 1 0 0 1 // 0 °
  2 1 3 0 0 // 90 °
  3 2 1 1 0 0 0 // 180 °
  2 1 1 2 0 // 270 °

Figura T:
  3 1 1 1 0 1 0 // 0 °
  2 1 2 0 1 // 90 °
  3 1 2 1 0 0 0 // 180 °
  2 2 1 1 0 // 270 °

Linha:
  4 1 1 1 1 0 0 0 0 // 0 °, 180 °
  1 4 0 // 90 °, 270 °

Ziguezagues:
  3 1 1 0 0 1 1 // 0 °, 180 °
  2 1 2 1 0 // 90 °, 270 °

  3 0 1 1 1 1 0 // 0 °, 180 °
  2 2 1 0 1 // 90 °, 270 °

Cubo:
  2 2 2 0 0 // qualquer ângulo

Agora devemos codificar esses números como uma sequência de 2 bits e colocar em uma matriz (substituindo 4 0por um 3 1ângulo de 90 ° da "linha" para caber em 2 bits - o resultado será o mesmo; e diminua as larguras em 1).

Codificaremos em ordem: largura (em 2 LSB), TBLs , HATs (para trás para loop para trás). Por exemplo 2 2 1 1 0 para 270 ° do ângulo de t-figura será codificado como 1 0 1 2 1(passado 1 é largura-1 ): 0b0100011001 = 281.

atualizado 12.02:

a) Eu converti uma matriz em uma string e salvei 18 caracteres (você pode ver o código anterior de 239 bytes ) :))

b) Mais otimização, o código é reduzido por 9 caracteres.
Esta é a minha última tentativa (acho que sim, lol!) 😀

Lisp comum, 634 bytes

(let((w(make-hash-table))(r 0))(defun z(c)(or(gethash c w)0))(defun x(c v)(setf r(max r c))(setf(gethash c w)v))(defun m(s)(dolist(c s)(apply(lambda(n u p)(let*((i(let*((j'(2 2 2))(k'(3 3))(l'(2 3))(m'(3 2))(o(case n(1(list'(1 1 1 1)'(4)))(2(list j k'(1 1 2)'(3 1)))(3(list j'(1 3)'(2 1 1)k))(4(list'(2 2)))(5(list'(2 2 1)l))(6(list j l'(1 2 1)m))(7(list'(1 2 2)m)))))(setf(cdr(last o))o)))(o(nth(+ u 2)i))(b(nth u i))(s(length o))(d 0)(h 0))(dotimes(i s)(let*((w(nth i b))(g(z(+ i p)))(m(+ g w)))(when(> m d)(setf d m)(setf h(- g(-(apply'max b)w))))))(dotimes(i s)(x(-(+ s p)i 1)(+(nth i o)h)))))c))(dotimes(i r)(print(z (+ i 1))))))

Verbose

(defun circular (list)
  (setf (cdr (last list)) list))

(defun get-piece (piece-number)
  (circular (case piece-number
              (1 (list '(1 1 1 1)
                       '(4)))
              (2 (list '(2 2 2)
                       '(3 3)
                       '(1 1 2)
                       '(3 1)))
              (3 (list '(2 2 2)
                       '(1 3)
                       '(2 1 1)
                       '(3 3)))
              (4 (list '(2 2)))
              (5 (list '(2 2 1)
                       '(2 3)))
              (6 (list '(2 2 2)
                       '(2 3)
                       '(1 2 1)
                       '(3 2)))
              (7 (list '(1 2 2)
                       '(3 2))))))

(let ((world (make-hash-table))
      (rightmost-column 0))
  (defun get-world-column (column)
    (or (gethash column world) 0))

  (defun set-world-column (column value)
    (setf rightmost-column (max rightmost-column column))
    (setf (gethash column world) value))

  (defun drop-piece (piece-number rotation position)
    (let* ((piece (get-piece piece-number))
           (top (nth (+ rotation 2) piece))
           (bottom (nth rotation piece))
           (size (length top))
           (max-combined-height 0)
           (contact-height 0))
      (dotimes (i size)
        (let* ((down-distance (nth i bottom))
               (height (get-world-column (+ i position)))
               (combined-height (+ height down-distance)))
          (when (> combined-height max-combined-height)
            (setf max-combined-height combined-height)
            (setf contact-height
                  (- height
                     (- (apply #'max bottom)
                        down-distance))))))
      (dotimes (i size)
        (set-world-column (- (+ size position) i 1)
                          (+ (nth i top) contact-height)))))

  (defun drop-pieces (pieces)
    (dolist (piece pieces)
      (apply #'drop-piece piece)))

  (defun print-world ()
    (loop for i from 1 to rightmost-column
          do (print (get-world-column i)))))

(defun play-tetris (pieces)
  (drop-pieces pieces)
  (print-world))

Teste-o

As peças são listas circulares de listas de números. Essas sub-listas representam cada lado da forma, os números indicando a que distância estão do lado oposto. Elas são da esquerda para a direita quando esse lado está na parte inferior, da direita para a esquerda quando em cima, de cima para baixo quando à esquerda e de baixo para cima quando à direita. Essas opções de design eliminam a necessidade de escrever código para rotação. Infelizmente, a falta de código de rotação não parece compensar as longas representações de forma ou a lógica um tanto complicada que usei para calcular novas alturas de coluna.

A rotação é um número inteiro não negativo. 0 = 0 graus, 1 = 90 graus, 2 = 180 graus, 4 = 270 graus

C # (compilador interativo do Visual C #) , 308 bytes

a=>{var o=new int[a.Max(x=>x.Item3+4)];foreach(var(i,r,p)in a){var b="\"4TqzŒª!\0\0HSš	Ó\0$\n\0!“A“š š@";int m=0,n=b[i],t=0,u=n/8+r%(n%8),v=b[u*=2]<<8|b[u-1];for(;t<v/8%8;m=m>n?m:n)n=o[p+t]+v%8-(n=(u=v>>6+3*t++)/2&1)-(n&u);for(;t-->0;)o[p+t]=m-(n=(u=v>>6+3*t)/4&1)-(n&u);}return o;}

Experimente online!

OK - Isso foi loucura ... Enviei uma resposta que usava técnicas comuns de golfe com código. Mas quando vi o que os outros estavam enviando, percebi que havia uma maneira melhor.

Cada (shape, rotation)tupla é codificada em uma literal de string C # com duplicatas removidas. O processo de codificação captura cada uma dessas configurações em 2 bytes.

Os 3 bits mais baixos armazenam a altura e os próximos 3 armazenam a largura. Como cada um desses valores nunca é superior a 4, eles podem ser lidos diretamente dos 3 bits sem qualquer conversão. aqui estão alguns exemplos:

  W   H
010 010 (2x2)
010 011 (2x3)
001 100 (1x4)
011 010 (3x2)
100 001 (4x1)

Em seguida, cada coluna é armazenada em 3 bits. A coisa mais útil para eu armazenar era o número de quadrados ausentes na parte superior e inferior da coluna.

// missing squares per column

+------ 0 top / 0 bottom
|+----- 0 top / 1 bottom
||+---- 0 top / 1 bottom
|||
HHH (L-Shape)         HH (Jagged-Shape)
H                    HH
                     |||
1 top / 0 bottom ----+||
0 top / 0 bottom -----+|
0 top / 1 bottom ------+

Nunca há mais de 2 quadrados ausentes na parte superior ou inferior e nunca há mais de 1 quadrado de ambos ao mesmo tempo. Dado esse conjunto de restrições, criei a seguinte codificação:

// column encoding of missing squares per column

000: none missing
100: 1 missing on top
101: 2 missing on top
010: 1 missing on bottom
011: 2 missing on bottom
110: 1 missing on top and bottom

Como temos que contabilizar no máximo 3 colunas com quadrados ausentes acima ou abaixo, podemos codificar cada (shape, rotation)tupla em 15 bits.

 C3  C2  C1   W   H
000 000 000 010 010 - 2x2 with no missing squares
000 000 000 100 001 - 4x1 with no missing squares
100 000 100 011 010 - 3x2 with missings square on top of columns 1 and 3
000 110 000 010 011 - 2x3 with missing squares on top and bottom of column 2

Por fim, formas duplicadas foram removidas. O exemplo a seguir mostra como várias (shape,rotation)tuplas podem produzir saídas duplicadas para a mesma forma em diferentes rotações:

// Square
HH  (0, 90, 180, 270)
HH
#-------------------------------#
// ZigZag
HH  (0, 180)    H  (90, 270)
 HH            HH
               H
#-------------------------------#
// T
 H  (0)        HHH  (180)
HHH             H

 H  (90)       H    (270)
HH             HH
 H             H

Todas as saídas exclusivas são determinadas e salvas em um byte[]e convertidas em um literal de string C #. Para pesquisar rapidamente onde uma forma se baseia Ie R, os primeiros 7 bytes da matriz consistem em uma chave de pesquisa codificada.

Abaixo está um link para o programa que eu usei para comprimir as peças.

Experimente online!

Código menos comentado e comentado:

// a: input list of (i,r,p) tuples
a=>{
  // create an output array that 4 more than
  // the largest position. this may result
  // in some trailing 0's
  var o=new int[a.Max(x=>x.Item3+4)];

  // iterate over each (i,r,p) tuple
  foreach(var(i,r,p)in a){
    // escaped string
    var b="\"4Tqzª!\0\0HS   Ó\0$\n\0!A @";
    // declare several variables that will be used later
    int m=0,n=b[i],t=0,
      // u is the decoded index into b for the current (i,r) pair
      u=n/8+r%(n%8),
      // convert 2 bytes from b into an encoded (shape,rotation) pair
      v=b[u*=2]<<8|b[u-1];
    // iterate over the columns, determining the top of the current
    // piece. The formula here is:
    //   piece_top = max(column_height + shape_height - shape_space_bottom)
    for(;t<v/8%8;m=m>n?m:n)
      n=o[p+t]+v%8-(n=(u=v>>6+3*t++)/2&1)-(n&u);
    // iterate over the columns again, saving the the new height
    // in each column. The formula here is:
    //   new_column_height = piece_top - shape_space_top
    for(;t-->0;)
      o[p+t]=m-(n=(u=v>>6+3*t)/4&1)-(n&u);
  }
  return o;
}

Carvão , 98 bytes

Ｆθ«≔§⪪§⪪”)¶∧↷"e«↨U∧0%3；D∧⁼~h⊟⁵h/₂dΦ↗(EＦ”2⊟ι1⊟ιη≔⊟ιζＷ‹Ｌυ⁺ζＬη⊞υ⁰≔⌈Ｅη⁻§υ⁺ζλ﹪Ｉκ³εＦＬη§≔υ⁺ζκ⁺ε⊕÷Ｉ§ηκ³»Ｉυ

Experimente online! Link é a versão detalhada do código. Recebe a entrada como uma matriz de valores [P, R, I], onde I é de 0 a 6, R é de 0 o 3 e P também é indexado em 0. Explicação:

Ｆθ«

Faça um loop sobre as peças de entrada.

≔§⪪§⪪”)¶∧↷"e«↨U∧0%3；D∧⁼~h⊟⁵h/₂dΦ↗(EＦ”2⊟ι1⊟ιη

Extraia a descrição da peça atual e a rotação. (Ver abaixo.)

≔⊟ιζ

Extraia a posição.

Ｗ‹Ｌυ⁺ζＬη⊞υ⁰

Verifique se há espaço horizontal suficiente para colocar a peça.

≔⌈Ｅη⁻§υ⁺ζλ﹪Ｉκ³ε

Verifique se há espaço vertical suficiente para colocar a peça.

ＦＬη§≔υ⁺ζκ⁺ε⊕÷Ｉ§ηκ³

Calcule as novas alturas das colunas afetadas.

»Ｉυ

Quando todas as peças tiverem sido processadas, imprima a lista final das alturas das colunas em linhas separadas.

A sequência compactada representa a sequência original 00001923001061443168200318613441602332034173203014614341642430137. Aqui, os 2são Iseparadores e os 1são Rseparadores. As peças, portanto, decodificam da seguinte forma:

P\R  0    1    2    3
0    0000 9
1    300  06   443  68
2    003  86   344  60
4    33
5    034  73
6    030  46   434  64
7    430  37

Os Rvalores ausentes são preenchidos ciclicamente automaticamente pelo carvão vegetal. Cada dígito é mapeado para dois valores, saliência e altura total, de acordo com a tabela a seguir:

\ O H
0 0 1
3 0 2
4 1 2
6 0 3
7 1 3
8 2 3
9 0 4

A saliência e a altura total estão relacionadas às alturas da coluna da seguinte maneira: Dada uma peça que queremos colocar em uma determinada posição e, pode ser possível colocá-la, mesmo que uma das colunas seja mais alta que e. A quantidade de espaço livre é fornecida pelo excesso. A nova altura da coluna após a colocação da peça é simplesmente a posição colocada mais a altura total.

Exemplo: suponha que começamos colocando uma 5peça na coluna 1. Como ainda não há mais nada, a peça é colocada na posição 0 e as colunas 1 e 3 agora têm a altura 1, enquanto a coluna 2 tem a altura 2. Então, queremos colocar uma 6peça com 1rotação na coluna 0. Aqui podemos colocar esta peça na posição 0; embora a coluna 1 tenha uma altura de 1, a peça tem uma saliência de 1 e, portanto, há espaço suficiente para colocá-la. A coluna 0 termina com uma altura de 2 e a coluna 1 termina com uma altura de 3.