Estrategia de Tetris

18

Su tarea es implementar una estrategia de Tetris equilibrada en términos de puntuación frente al tamaño del código.

En esta versión del juego, los tetrominoes se giran y se dejan caer desde arriba en una cuadrícula de 20 filas y 10 columnas. Mientras caen, no se pueden girar ni mover horizontalmente. Como de costumbre, una pieza caída se detiene cuando llega al fondo de la cuadrícula o cuando un movimiento más hacia abajo provocaría una colisión con un cuadrado ya ocupado.

Cuando nlas líneas horizontales se llenan por completo, colapsan simultáneamente, la rejilla se rellena con nlíneas vacías en la parte superior y la puntuación se incrementa en 2 n -1 puntos. Para n= 1,2,3,4 eso es 1,3,7,15 puntos respectivamente. Después de que las líneas desaparecen, algunos bloques pueden permanecer flotando en el aire (no hay " reacción en cadena de gravedad ").

Cuando no hay espacio disponible para que la pieza actual aparezca donde se desea, la cuadrícula se borra, la pieza actual se ignora y el juego continúa con la siguiente pieza como actual. No hay penalidad por eso.

Debe leer una secuencia de tipos de piezas y decidir cómo rotarlas y dónde colocarlas. Se permite mirar hacia adelante para la siguiente pieza (solo una): puede mirar la pieza i+1antes de responder i, pero debe haber decidido el destino de iantes de mirar i+2. No hay anticipación disponible más allá de la última parte de la entrada.

Los tipos de Tetromino y sus rotaciones se codifican según la siguiente tabla:

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

La entrada es binaria: una secuencia de bytes cuyos restos, cuando se dividen entre 7, deben interpretarse como los OIZJLSTtetrominós. Ocurrirán con aproximadamente la misma probabilidad (excepto que los primeros tipos pueden aparecer un poco más a menudo debido a que 256 no es un múltiplo de 7, pero eso debería ser insignificante). La entrada puede ser desde stdin o desde un archivo llamado "i" o pasado como argumento. Puede leer todas las entradas a la vez, siempre que se asegure de cumplir con la restricción de anticipación.

La salida también es binaria: una secuencia de bytes de la misma longitud que la entrada. Puede ser stdout o un archivo llamado "o" o el resultado de una función. Cada byte codifica r*16 + x, donde res la rotación deseada y xes el índice basado en 0 de la columna donde debe ir el cuadrado más a la izquierda del tetromino girado. Esos ry xdeben ser válidos, es decir, 0 ≤ r ≤ 3y 0 ≤ x ≤ 10-w, donde wes el ancho de la pieza correspondiente.

Su programa debe ser determinista: dada la misma entrada, tiene que producir exactamente la misma salida. Usar un PRNG está bien siempre que sea constante.

La puntuación total es la puntuación del juego menos el tamaño de su código en bytes. Utilice el siguiente archivo (64 KB de ruido pseudoaleatorio) como entrada: https://gist.github.com/ngn/857bf2c99bfafc649b8eaa1e489e75e4/raw/880f29bd790638aa17f51229c105e726bce60235/i

El siguiente script python2 / python3 lee los archivos "i" y "o" del directorio actual, reproduce el juego e imprime el puntaje (recuerde restar el tamaño del código del puntaje):

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)

También lo hace el siguiente programa C mucho más rápido, pero está garantizado que funcionará solo en 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;}

El puntaje total más alto gana. Las lagunas estándar están prohibidas.

ngn
fuente
Cuando no hay espacio disponible para que la pieza actual aparezca donde lo desee Veamos si entiendo eso correctamente. Por ejemplo, si la columna más a la izquierda está completamente llena y el programa desea colocar la siguiente pieza allí, esto obligará a que se elimine la cuadrícula, incluso si hubiera mucho espacio en otro lugar. ¿Es eso correcto?
Arnauld
@Arnauld sí, correcto
NGN
¿Está bien optimizar para el archivo i ? Buen desafío, por cierto!
Arnauld
Sí, proviene de mi / dev / urandom, por lo que no espero que haya patrones explotables en él. Gracias :)
ngn
1
Más precisamente: ¿es legal almacenar datos de ayuda en nuestro código que es específico de i , como "borrar 2 líneas en el movimiento # 147 en lugar de esperar un Tetris, de lo contrario la pila irá demasiado alto"? (Esto no parece entrar en conflicto con 'no mirar la pieza i + 2 del archivo de entrada'.)
Arnauld

Respuestas:

7

C, puntuación: 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];}}

La idea es que los bloques S, Z, O, utilizo ubicaciones fijas y rotaciones:

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

El resto, J, L, T, se agrupan en las primeras tres columnas con algo de rotación cíclica.

Versión sin golf:

#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;
}
Lyth
fuente
simple y eficiente, ¡bien hecho!
ngn