18
\$\begingroup\$

Your task is to implement a Tetris strategy balanced in terms of score vs code size.

In this version of the game tetrominoes are rotated and dropped from above into a grid of 20 rows and 10 columns. While falling, they cannot be rotated or moved horizontally. As usual, a dropped piece stops when it reaches the bottom of the grid or when further downwards motion would cause collision with an already occupied square.

When n horizontal lines get filled completely, they collapse simultaneously, the grid is replenished with n empty lines at the top, and the score is incremented by 2n-1 points. For n=1,2,3,4 that's 1,3,7,15 points respectively. After the lines disappear, some blocks may remain floating in the air (there's no "gravity chain reaction").

When no room is available for the current piece to appear where desired, the grid is cleared, the current piece ignored, and the game continues with the next piece as current. There's no penalty for that.

You should read a stream of piece types and decide how to rotate them and where to drop them. Look-ahead for the next piece (just one) is allowed: you can look at piece i+1 before responding to i, but you must have decided the fate of i before looking at i+2. No look-ahead is available beyond the last piece of the input.

Tetromino types and their rotations are encoded per the following table:

        type 0    1    2    3    4    5    6
             O    I    Z    J    L    S    T
            ┌────┬────┬────┬────┬────┬────┬────┐
 rotation 0 │##  │#   │##  │ #  │#   │ ## │### │
            │##  │#   │ ## │ #  │#   │##  │ #  │
            │    │#   │    │##  │##  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          1 │##  │####│ #  │### │  # │#   │#   │
            │##  │    │##  │  # │### │##  │##  │
            │    │    │#   │    │    │ #  │#   │
            │    │    │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          2 │##  │#   │##  │##  │##  │ ## │ #  │
            │##  │#   │ ## │#   │ #  │##  │### │
            │    │#   │    │#   │ #  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          3 │##  │####│ #  │#   │### │#   │ #  │
            │##  │    │##  │### │#   │##  │##  │
            │    │    │#   │    │    │ #  │ #  │
            │    │    │    │    │    │    │    │
            └────┴────┴────┴────┴────┴────┴────┘

Input is binary - a sequence of bytes whose remainders when divided by 7 should be interpreted as the OIZJLST tetrominoes. They will occur with roughly the same probability (except that the first few types may appear slightly more often due to 256 not being a multiple of 7, but that should be negligible). Input can be from stdin or from a file named "i" or passed as an argument. You can read all of the input at once, provided you make sure to abide by the look-ahead restriction.

Output is binary too - a sequence of bytes of the same length as the input. It can be stdout or a file named "o" or the result from a function. Each byte encodes r*16 + x, where r is the desired rotation and x is the 0-based index of the column where the leftmost square of the rotated tetromino should go. Those r and x must be valid, i.e. 0 ≤ r ≤ 3 and 0 ≤ x ≤ 10-w, where w is the width of the corresponding piece.

You program must be deterministic - given the same input, it has to produce exactly the same output. Using a PRNG is ok as long as it's const-seeded.

The total score is the score from the game minus the size of your code in bytes. Please use the following file (64kiB of pseudo-random noise) as input: https://gist.github.com/ngn/857bf2c99bfafc649b8eaa1e489e75e4/raw/880f29bd790638aa17f51229c105e726bce60235/i

The following python2/python3 script reads files "i" and "o" from the current directory, replays the game and prints the score (please remember to subtract your code size from the score):

a = [0] * 23 # grid (1square=1bit, 1row=1int, LSB is left, 3 empty rows on top)
#      O     I         Z       J       L       S       T        tetrominoes
t = [[[3,3],[1,1,1,1],[3,6],  [2,2,3],[1,1,3],[6,3],  [7,2]  ],
     [[3,3],[15],     [2,3,1],[7,4],  [4,7],  [1,3,2],[1,3,1]],
     [[3,3],[1,1,1,1],[3,6],  [3,1,1],[3,2,2],[6,3],  [2,7]  ],
     [[3,3],[15],     [2,3,1],[1,7],  [7,1],  [1,3,2],[2,3,2]]]
tw = [[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2]] # widths
th = [[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3]] # heights
score = 0
for p, rx in zip(bytearray(open('i', 'rb').read()),
                 bytearray(open('o', 'rb').read())):
    p %= 7; r = rx >> 4; x = rx & 15  # p:piece type, r:rotation, x:offset
    b = [u << x for u in t[r][p]]     # as a bit-matrix (list of ints)
    bw = tw[r][p]; bh = th[r][p]      # width and height
    y = 0                             # drop it
    while y <= 23 - bh and all((a[y + i] & b[i]) == 0 for i in range(bh)):
        y += 1
    y -= 1
    if y < 3:                         # no room?
        a = [0] * len(a)              # clear the grid and carry on
    else:
        for i in range(bh):           # add the piece to the grid
            a[y + i] |= b[i]
        n = 0
        for i in reversed(range(bh)): # collapse full lines
            if a[y + i] == (1 << 10) - 1:
                n += 1; del a[y + i]; a = [0] + a
        score += (1 << n) - 1
print(score)

So does the following much faster C program but it's guaranteed to work only on Linux:

#include<stdio.h>
#include<fcntl.h>
#include<sys/mman.h>
#include<sys/stat.h>
#define F(i,n,b...)for(i=0;i<n;i++){b;}
typedef int I;typedef char C;
I a[23],t[]={
51,4369,99,802,785,54,39,51,15,306,71,116,561,305,
51,4369,99,275,547,54,114,51,15,306,113,23,561,562};
C*th="2423322213223324233222132233";
I main(){
 struct stat h;stat("i",&h);I i,j,k,l=h.st_size,z=0;
 C*mi=mmap(0,l,1,1,open("i",0,0),0),*mo=mmap(0,l,1,1,open("o",0,0),0);
 F(k,l,
  I p=(mi[k]&255)%7,r=3&mo[k]>>4,q=r*7+p,x=mo[k]&15,y=0,h=th[q]-'0',b[4];
  F(i,h,b[i]=(t[q]>>(4*i)&15)<<x)
  while(y<=23-h){I u=0;F(i,h,u|=a[y+i]&b[i])if(u)break;y++;}
  if(--y<3){F(i,23,a[i]=0)continue;}
  F(i,h,a[y+i]|=b[i])
  I n=0;F(i,23,n+=a[i]==1023)
  if(n){j=23;F(i,20,a[j]=a[22-i];j-=a[j]!=1023)F(i,j,a[i]=0);z+=(1<<n)-1;})
 printf("%d\n",z);return 0;}

The highest total score wins. Standard loopholes are forbidden.

\$\endgroup\$
  • \$\begingroup\$ When no room is available for the current piece to appear where desired Let's see if I understand that correctly. For instance, if the leftmost column is entirely filled and the program want to place the next piece there, this will force the grid to be cleared, even if there was plenty of room elsewhere. Is that correct? \$\endgroup\$ – Arnauld Feb 17 '18 at 16:38
  • \$\begingroup\$ @Arnauld yes, correct \$\endgroup\$ – ngn Feb 17 '18 at 16:41
  • \$\begingroup\$ Is it OK to optimize for the i file? Nice challenge, BTW! \$\endgroup\$ – Arnauld Feb 17 '18 at 16:48
  • \$\begingroup\$ Yes, it comes from my /dev/urandom, so I don't expect there to be exploitable patterns in it. Thanks :) \$\endgroup\$ – ngn Feb 17 '18 at 16:58
  • 1
    \$\begingroup\$ More precisely: is it legal to store helper data in our code which is specific to i, such as "clear 2 lines at move #147 instead of waiting for a Tetris, otherwise the stack will go too high"? (This doesn't seem to conflict with 'don't look at piece i+2 from the input file'.) \$\endgroup\$ – Arnauld Feb 17 '18 at 17:05
7
+500
\$\begingroup\$

C, score: 4136 (4290 - 154 bytes)

#include <stdio.h>
main(){int c,p=0,t[]={7,9,21,0,0,51,1,32,16,48,0,33,0,32,16,49};for(;(c=getchar())>=0;putchar(c)){c%=7;c=t[!c||!(10%c)?c:2*c+p++%4];}}

The idea is that blocks S,Z,O,I use fixed locations and rotations:

                  |
      s     z     |
      s s z z # # |
        s z   # # |
0 1 2 3 4 5 6 7 8 9

The rest - J,L,T - are packed into first three columns with some cyclic rotation.

Ungolfed version:

#include <stdio.h>
int main() {
    int c,p=0,t[] = {7,9,21,51, 1,32,16,48, 16,48,0,33, 0,32,16,49 };
    while ((c=getchar())!=EOF) {
            switch(c%7) {
            case 0: c = t[0]; break;
            case 1: c = t[1]; break;
            case 2: c = t[2]; break;
            case 3: c = t[4+p++%4]; break;
            case 4: c = t[8+p++%4]; break;
            case 5: c = t[3]; break;
            case 6: c = t[12+p++%4]; break;
            }
            putchar(c);
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ simple and efficient - well done! \$\endgroup\$ – ngn Feb 26 '18 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.