Tetris! Final heights (Day 3)

Question

^{Challenge Taken from my university code challenge contest}

^{This is actually Day 0 but yesterdays' challenge was too easy and can be a dupe of another question here.}

---

Tetris is a video game that became popular in the 80s. It consists of placing a series of pieces with different shapes that fall on a board, so that they fit in the most compact way possible.

In this problem we will assume a sequence of pieces that fall, each in a certain position and with a certain orientation that can not be changed. The pieces are piled up as they fall and the complete rows are not eliminated (as in the original game). The objective is to determine the final height of each column of the board after all the pieces fall.

There are a total of 7 different pieces, shown in the figure:

Challenge

Given a list of pieces, output the height of all the columns from the board after all pieces falls

A piece consists of three numbers: I, R and P. The first number, I, is the identifier of the piece (a number between 1 and 7, in the same order as in the figure). The second number, R, is the rotation of the piece. It can take the values ​​0, 90, 180 or 270 and represents the angle of rotation of the piece in the anti-clockwise direction. The third number, P, indicates the position of the piece. Represents the column on the left occupied by the piece (this can be 1 or 0 Index. Please specify).

Example and Test case (1 Index)

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

• Output [3, 3, 1, 3, 2]

---

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

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

---

• Given [[3,0,1],[3,180,3]] Output [1,1,4,4,4]

• Given [[2,180,1],[2,0,3]] Output [2,2,4,3,3]

Notes

• This is code-golf
• Row/Column can be 1 or 0 Index. Please specify.
• You can redefine input values (maybe you want to call piece 1 as A, etc..). In that case please specify

Questions

• Can we use any 4 distinct values instead of an angle in degrees?: Yes

• Are we supposed to handle "holes" if a piece doesn't exactly fit over the previous ones?: Yes

• Is the height or the width of the board bounded? No. Neither the width nor the height are bounded

---

Thanks @Arnauld for the images and the test cases *.*

Answer 1

JavaScript (Node.js),  286 284 270  266 bytes

Pieces and positions are 0-indexed. Angles are in \$[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

Try it online! or try an enhanced version that also displays the final board.

Shape encoding

All pieces are stored as exactly 4 nibbles (4x4 bits) with the rows sorted in reverse order and the leftmost pixel mapped to the least significant bit. In other words, the binary representation of the shape is mirrored both vertically and horizontally.

Example:

Hash function and lookup table

Given a piece \$p \in [0..6]\$, a rotation \$r \in [0..3]\$ and a row \$y \in [0..3]\$, we use the following hash function to get the index \$n\$ of the corresponding bitmask from a lookup table:

$$n=(2p+56r+99y+13)\bmod 113$$

Only the first \$82\$ entries are explicitly stored. Everything else is set to \$0\$.

These entries are packed as:

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

which expands to the following 82 nibbles:

"717433667233ff47173333276611000000000000113213001112221112123333333311133233221211"

Using hexadecimal in the final format is only required for the two horizontal representations of the \$I\$ piece, hence the "ff" in the above string.

The parameters of the hash function were brute-forced in a way that optimizes leading and trailing zeros. The fact that the string can be compressed some more by using 1e12 for the zeros in the middle and a conversion from base-16 to base-4 for the right part is just a welcome but unexpected side effect. :-)

Here is a demonstration of the unpacking process for all pieces and all rotations.

Commented

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[]

Answer 2

C (clang), 253 239 221 212 bytes

t(*a,*b,c){char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVW
hU😎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;}}

Try it online!

p.s. Actually the code size is 221 bytes (but 212 chars) because of UNICODE chars coded in UTF-8. But tio.run treats it as 212 byte code...

Code size on my computer is 209 chars (218 bytes). But I couldn't replace \225 by visible char in tio.run 😞

Ungolfed code

// 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@EVW
hU😎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)

Description

Let's found top base line (TBL) of each figure and describe it as a number of cells below TBL for each horizontal position. Also let's describe number of cells (height) above TBL (HAT).

E.g.:

                       ________                                      ________
_[]_____ 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

Let's describe TBLs and HATs for each figure and each rotation angle:

Width  TBLs     HATs
-----  -------  -------
L-figures:
  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°

T-figure:
  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°

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

Zigzags:
  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°

Cube:
  2    2 2      0 0      // any angle

Now we should encode these numbers as a sequences of 2 bits and put into an array (replacing 4 0 by 3 1 for 90° angle of "line" to fit in 2 bits – result will be the same; and decrease widths by 1).

We'll encode in order: width (in 2 LSB), TBLs, HATs (backward for backward loop). E.g. 2 2 1 1 0 for 270° angle of T-figure will be encoded as 1 0 1 2 1 (last 1 is width-1): 0b0100011001 = 281.

updated 12.02:

a) I've converted an array to a string and saved 18 chars (you can see previous 239 bytes code) :))

b) More optimization, code is shrinked by 9 chars.
This is my last attempt (I think so, lol!) 😀

Answer 3

Common Lisp, 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))

Test it

The pieces are circular-lists of lists of numbers. These sub-lists each represent a side of the shape, the numbers indicating how far they are from the opposite side. They are left to right when that side is on the bottom, right to left when on top, top to bottom when on left, and bottom to top when on right. These design choices eliminate the need to write code for rotation. Unfortunately, the lack of rotation code does not seem to have made up for the lengthy shape representations, or the somewhat complicated logic I used for calculating new column heights.

Rotation is a non-negative integer. 0=0 degrees, 1=90 degrees, 2=180 degrees, 4=270 degrees

Answer 4

C# (Visual C# Interactive Compiler), 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;}

Try it online!

OK - That was madness... I submitted an answer that used run-of-the-mill code-golf techniques. But when I saw what others were submitting, I realized there was a better way.

Each (shape, rotation) tuple is encoded into a C# string literal with duplicates removed. The encoding process captures each of these configurations in 2 bytes.

The lowest 3 bits store height and the next 3 store width. Since each of these values is never more than 4, they can be read directly from the 3 bits without any conversion. Here are some examples:

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

Next, each column is stored in 3 bits. The most useful thing for me to store was the number of missing squares from the top and bottom of the column.

// 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 ------+

There is never more than 2 squares missing from the top or bottom, and there is never more than 1 square missing from both at the same time. Given this set of constraints, I came up with the following encoding:

// 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

Since we have to account for at most 3 columns with missing squares above or below, we can encode each (shape, rotation) tuple in 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

Lastly, duplicate shapes have been removed. The follow example show how multiple (shape,rotation) tuples can produce duplicate outputs for the same shape at different rotations:

// 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

All unique outputs are determined and saved to a byte[] and converted to a C# string literal. In order to quickly lookup where a shape is based on I and R, the first 7 bytes of the array consist of an encoded lookup key.

Below is a link to the program that I used to compress the pieces.

Try it online!

Less golfed and commented code:

// 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;
}

Answer 5

Charcoal, 98 bytes

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

Try it online! Link is to verbose version of code. Takes input as an array of [P, R, I] values, where I is from 0 to 6, R is from 0 o 3 and P is also 0-indexed. Explanation:

Ｆθ«

Loop over the input pieces.

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

Extract the description of the current piece and rotation. (See below.)

≔⊟ιζ

Extract the position.

Ｗ‹Ｌυ⁺ζＬη⊞υ⁰

Ensure that there is enough horizontal room to place the piece.

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

Ensure that there is enough vertical room to place the piece.

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

Calculate the new heights of the affected columns.

»Ｉυ

When all the pieces have been processed, output the final list of column heights on separate lines.

The compressed string represents the original string 00001923001061443168200318613441602332034173203014614341642430137. Here the 2s are I separators and the 1s are R separators. The pieces therefore decode as follows:

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

Missing R values are automatically filled cyclically by Charcoal. Each digit then maps to two values, overhang and total height, according to the following table:

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

The overhang and total height relate to the column heights as follows: Given a piece that we want to place at a given position e, it may be possible to place the piece even though one of the columns is taller than e. The amount of spare space is given by the overhang. The new height of the column after placing the piece is simply the placed position plus the total height.

Example: Suppose we start by placing a 5 piece in column 1. Since there is nothing else yet the piece is therefore placed at position 0 and columns 1 and 3 now have height 1 while column 2 has height 2. We then want to place a 6 piece with 1 rotation in column 0. Here we can actually place this piece at position 0; although column 1 has a height of 1, the piece has an overhang of 1, and so there is enough space to place it. Column 0 ends up with a height of 2 and column 1 ends up with a height of 3.