Wait, which tetromino was that?

Question

Background

Tetris is a single-player game played on a rectangular grid with tetromino pieces.

When you fill one or more lines with tetrominoes, the filled lines are removed, and all blocks above them move down accordingly. In the following diagrams, . is an empty space, # is an existing block, and the tetromino marked with As is the one just placed:

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####    ##.#.##.
####.###    ####.###

Challenge

Two board states will be given as input. One is right before a specific tetromino appears (the left-side state of the above diagrams, without As), and the other is right after the tetromino is placed and line clears are completed (the right-side state). Given this information, recover the type of the tetromino placed between the two states, which is one of the following seven types:

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

You can assume the following:

• The input is valid; the two boards have the same dimensions, and the game state can be changed from the first to the second by placing a single tetromino. Also, the placed tetromino is completely inside the grid before line clearing occurs (i.e. it won't be placed above the ceiling of the given grid, even partially).
• The answer is unique.
• The width of the board is at least 5.

For this challenge, ignore the rotation rules of actual Tetris games, and assume that any tetromino placement is valid, as long as the tetromino does not overlap with existing blocks or float in the air. This allows placing a tetromino inside a closed room (which actually happens in some exotic games).

You can take the input as a matrix (or equivalent) consisting of two distinct values for spaces and blocks. You can output the type of the tetromino as one of seven distinct values of your choice. Allowed output formats include numbers, strings, and possibly nested or multi-dimensional arrays of numbers and/or strings.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

The notation is the same as the above example. Before and After are the two input grids, Answer is the expected output (given as alphabet code), and Explanation shows where the tetromino is placed.

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#
.###.

Answer 1

JavaScript (ES10),  286  282 bytes

Expects (a)(b), where \$a\$ and \$b\$ are 2 lists of binary strings. Returns an integer between \$0\$ and \$6\$ for JLTIOZS, or \$-1\$ if there's no solution (but we're not supposed to support that).

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

Try it online!

How?

Shape encoding

Each shape is encoded with 2 digits in base 36, which allows to store:

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

The bits are arranged in a \$4\times 4\$ matrix, with the piece wedged in the upper right corner. The least significant bit is mapped to the top-right cell and there are 6 implicit leading zeros.

Examples:

• The 1^st entry is 0N in base 36, which is \$23\$ in decimal and \$0000010111\$ in binary. This is a J.

• The 6^th entry is FM in base 36, which is \$562\$ in decimal and \$1000110010\$ in binary. This is a T.

All shapes can be encoded that way, except the vertical I. This one is encoded as 00 and its actual value (\$4369\$ in decimal) is hard-coded separately.

Main algorithm

The main algorithm consists of 5 nested loops where we try to put each shape \$p\$ at each possible position \$(x,y)\$ in the grid \$a\$ and figure out which one leads to the grid \$b\$.

Whenever a row is completed, we yield an empty array so that .flatMap() deletes this row and we decrement the index \$i\$ of the entry that needs to be read in the resulting array to account for the row shift.

We may end up with a negative \$i\$. But because we use a XOR for the comparison, undefined rows behave like they were set to \$0\$, which is what we want.

"...".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()

Final result

The shapes are stored in the following order:

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

which is why the final result is the value returned by .findIndex() modulo \$14\$, divided by \$2\$ and rounded towards \$0\$.

(NB: The shape O is stored twice so that it doesn't break the pattern.)

Answer 2

Brachylog, ¹⁵⁶ 124 bytes

Takes two matrices, 1 indicating an empty tile, 2 indicating a tile with a piece. 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

Try it online! or try all test cases (with nicer I/O)! (Byte count is a bit longer because the header increases the predicate numbers.)

How it works

We search for a matrix O so that the input plus O after the removal rules will be equal to the output. We then trim O to contain a submatrix, bounded by the tetromino. Trying all orientations, it either fits in a 2 by x matrix – then we can convert it from base 2. Otherwise it is the I piece.

h{∧Ḋ}ᵐ²O

Before this challenge, I would have created a matrix of the same dimension by taking the input length, mapping the rows length over it, and say every element should be a number … but this is much neater: O is the input, but every element in it is just any number. This is much neater!

;I{zzᵐ+ᵐ²}

O + Input

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

This is a very convoluted way to split in the rows into ((contains only 2s), (doesn't contain only 2s)). There are technically shorter versions, but all my attempts forced labelization of the numbers, slowing the program down to pure brute force. (This was really frustrating finding a version that works at all.)

 {-₁ᵐ²}ʰc~t?

Subtract 1 from the removed rows, and join ((contained only 2s, now only 1s), (rest)) back together. This should be equal to the second input matrix.

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

If we take the input matrix, set the top row to only 2s, rotate it up, and after adding O there should be a 3: then the tetromino wasn't floating.

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

Trim O so it only contains the tetromino. It would be nice if this could end here. However, O isn't guaranteed to be a tetromino by now and could be some disconnected 1s. So …

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

Check all rotations, and if it is a 2 by x matrix, convert to base 2 and check if one of the numbers matches. If nothing matches, it is the I piece.

Answer 3

Python3, 618 bytes

E=enumerate
V=lambda u,I,x:I<0 or I>=len(u[0])or u[x][I]
def J(x,y,B,U):
 u=eval(str(U))
 for X,r in E(B):
  for Y,v in E(r):
   if x+X>=len(u)or y+Y>=len(u[0])or(u[x+X][y+Y]and int(v)):return
   u[x+X][y+Y]=[u[x+X][y+Y],1][int(v)]
 return u
O=lambda v,n:[v]+O([*zip(*v)],n-1)+O(v[::-1],n-1)if n else[]
def f(b,B):
 for P,S in E([['11','11'],['100','111'],['001','111'],['011','110'],['010','111'],['110','011'],['1111']]):
  for x,r in E(b):
   for y,v in E(r):
    for W in O(S,4):
     if(U:=J(x,y,W,b)):
      j,k=[],[]
      for i in U:
       if all(i):j+=[[0]*len(i)]
       else:k+=[i]
      if j+k==B:return P

Try it online!