[Question]
  [
## Background
[Tetris](https://en.wikipedia.org/wiki/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 `A`s 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 `A`s), 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](/questions/tagged/code-golf "show questions tagged '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]
# 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!](https://tio.run/##bVBhb9owEP3eX5ESrbHBMUlDKevqVKs0NCbopNEvNGSTCYZmSp1gexNojL/O7MxMZe1Zytnv3nt3ue/0J5WZyCvl83LO9guypySekbgR3PUvw4fR@zDqj4Ig6IfmDPrD8y@9QdQb3kcXl3dRt/exgZ@oyh5BG@P2EuJFzucDPmdrUGkfLMsnBoBAG0jiBGMsUgt9Q2sNnR4YEuWWQbVfBW6JILEXzLyWgGgXpHhRUDXSBUW02wRRzd6BFQGgokKyAVegQlEXbredqPsWxjGY@BvY7JyFF/D6eo3UlqzOaDJphSlambu42QVXArbOm02JC8aX6vFmdQVy30dJCmGSp19vgYTbUwV1vAk7cRzuBVv9yAUD3kJ6EAtG5/28YOMNz0AAsSrHSuR8CSCWVZEr0J5yvzXlbb2VUnygeknSIbHz68RxEoqcWeoQR1quN@VTrk3Nz9esZwULCwML3bYqaMb0wttL5GQGbAGdiOO5nhn2nfbPSi7LguGiXILGp@H94PPDuJEsAIVgBlNN@Q33uI4Tm3R23fpZJ/@/qHHXNWyT3L@vk2MPy3lFi4@0h4bPRRZ9oTXTmPJROmi10KKv9v1XxZZjhUffl9Ma13oe11LsvcYP2iOSe0D@AA "JavaScript (Node.js) – 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 1st entry is `0N` in base 36, which is \$23\$ in decimal and \$0000010111\$ in binary. This is a `J`.
* The 6th entry is `FM` in base 36, which is \$562\$ in decimal and \$1000110010\$ in binary. This is a `T`.
[![examples](https://i.stack.imgur.com/Ex28K.png)](https://i.stack.imgur.com/Ex28K.png)
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]
# [Brachylog](https://github.com/JCumin/Brachylog), 156 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!](https://tio.run/##SypKTM6ozMlPN/r/P8Oz@lHH8oc7umofbp1waJO/tWd1VRWQqQ3m1lobGT7ctfPh1umP2qYkVz/qXPhw6@xDmzJqgHoMgTp6k4DKqnUfNTVClJ/akFxXYq@WUQ0y1AhkJFDoUdsuoAJr/0dtGx41NSU/6ug2Bsr6V1cfWmP7qKlBrfb0ophasGR7dQzQHqCumtpqIAPOzgHpSwY6pO7hjuZqQ9MaI@MaY4MaU8MaU/MaM4Pa2hrD//@jo6MNdUDQCARjddB4RjqGMBgL5EYbIvEhao2wq439HwUA) or [try all test cases (with nicer I/O)!](https://tio.run/##VVAxS8NAFN79FeUdZLENJqV2KOpcETLoZNvBBjVgQVCh2LsrGiG2iuAgiDjpooNDKRTajh31V9z9kfjuLmmTDPe@@9733fde2hdHfnDdOT914wLtQqG0XYCuRcXsvn1GwQY5@HIYEFVdLibPi7E6ZTSS0VuFOhXkwQPmqFoHVqkqsAtsc0OBPWBlDfaBuWUFDlCjxYdgcTEfysE3nBx1Lo9twJt6Ow7qFAVi@mDyvFqd9noI1018zXXEfCYmrzJ68akcfojJ@2IcMDUpOp7aKKMlGd4a@e/I71/tWAGl6QpIyWiOgppn9qj6cvCopvMoXfxsyfDG4n@fTW66jkubGIVGximCJe7IMPR9nKUvpnf4K3BD3BbXw7@A@3POnDhuNGDN1l9aoKgYQjSjC7SKDcMRolSqEHMz4qw9kaUeO@fJBGTFaUN7VKTiciXjQUPSWOUsKTtprAy5M5lKPaFDScInWPMZZ05Hlgy0Wv8) (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.
]