Encuentra el mejor movimiento en un juego de Tetris

10

Me gusta mucho el Tetris, pero no soy muy bueno en eso. ¡Solo una vez me gustaría ver esa nave espacial despegar frente a mis propios ojos! Y dado que las computadoras son tan buenas en todo, la única solución posible es hacer un programa para que lo reproduzca por mí ... ¡excepto que vas a hacer eso por mí!

Dado un tetromino (forma hecha de cuatro cuadrados) y un mapa del campo de juego, debe colocar el tetromino de modo que obtenga el mayor número de líneas (hace que el mayor número de filas esté completamente lleno de bloques) y cree el menor número de nuevos agujeros (un espacio vacío que no puede "ver" la parte superior del campo de juego 1 ).

Entrada

La entrada contendrá un carácter en una sola línea que representa el tetromino que cae, seguido de una cuadrícula 10 * 18 2 de espacios ( ) y signos más ( +).

El personaje representa cualquiera de los siete tetrominoes básicos encontrados en Tetris. Todas las piezas se pueden girar 90 grados, pero no se pueden voltear. Todos los tetrominoes y sus rotaciones son los siguientes:

         #
S =  ##  ##
    ##    #

          #
Z = ##   ##
     ##  #

    #   ###  ##
L = #   #     #    #
    ##        #  ###

     #  ###  ##
J =  #    #  #     #
    ##       #   ###

          #   #   #
T = ###  ##  ###  ##
     #    #       #

O = ##
    ##

    #
I = #  ####
    #
    #

La cuadrícula representa el campo de juego de Tetris, con +bloques previamente colocados. Entonces, una entrada de ejemplo podría ser la siguiente:

I











+       ++
+    +++++
++ +++++++
++ +++++++
++ +++++++
++ +++++++
++++++ +++

Salida

Su salida será idéntica a la entrada, pero con el tetromino en la posición ideal. El tetromino debe representarse con #para diferenciarlos de los bloques colocados previamente. Además de esto, también debe mostrar cuántas líneas / agujeros crea su ubicación en el formulario xL yHen una nueva línea.

El resultado para el ejemplo dado anteriormente sería el siguiente 3 :

I











+       ++
+    +++++
++#+++++++
++#+++++++
++#+++++++
++#+++++++
++++++ +++
4L 0H

Debe generar solo los mejores resultados; en el caso de que dos o más casos den la misma puntuación, debe generarlos todos (separados por una línea en blanco). Los mejores resultados se determinarán ordenando primero el número de líneas marcadas (descendentes) y luego el número de nuevos agujeros creados (ascendentes). Entonces, 1L 1Hes un mejor puntaje que 0L 0H.

Trabajaré para crear una lista de varias entradas y salidas esperadas con las que pueda probar su programa. Mira este espacio.

Reglas y Desambiguación

  • Este es el , por lo que gana la implementación correcta más corta.
  • La entrada / salida puede estar en cualquier medio que se adapte a su idioma de destino (por ejemplo, archivo, stdin / stdout, área de texto).
  • Si su idioma de destino no admite la entrada de varias líneas (o no es conveniente hacerlo), puede delimitar cada línea de la entrada con comas ( ,).
  • Puede omitir la salida de cualquier línea en blanco en la cuadrícula.
  • Recuerde que el tetromino cae desde arriba, no puede colocar la pieza "bajo tierra". Por lo tanto, puede suponer que todas las ubicaciones posibles de la pieza estarán en "nivel de superficie" (es decir, no hay bloques entre la pieza y la parte superior del tablero).
  • Suponga que nunca habrá una situación en la que se vea obligado a terminar un juego (el tetromino colocado toca el centro superior del campo).
  • Las soluciones que son idénticas en la salida deben omitirse (por ejemplo, hay 3 salidas de soluciones si gira ingenuamente la Opieza).

1 Soy consciente de que esto creará algunos falsos positivos, pero es una simplificación.

2 Este es el tamaño de cuadrícula utilizado en la versión de Game Boy.

3 Sí, 0Hes correcto. Comprueba de nuevo, dije nuevos agujeros; ^)

Sean Latham
fuente
¿Qué pasaría si una pieza causara 1 hoyo nuevo, pero anotara 2 líneas, frente a solo anotar 1 línea?
Nathan Merrill
Ordenar por número de líneas primero. 2 líneas> 1 línea, por lo que gana sin importar el número de agujeros.
Sean Latham
2
Si liberas un hoyo, ¿eso te da -1H?
overactor
Hm, no pensé en eso, podría ocurrir como resultado de la definición ingenua del agujero. Sí, supongo que sí.
Sean Latham el
En mi solución, no consideré liberar agujeros. Entendí la definición del problema de tal manera que los bloques existentes no deberían modificarse. Por lo tanto, no se deben eliminar líneas completas ni liberar agujeros.
mikail sheikh

Respuestas:

3

C 1009 bytes

#include <stdio.h>
#define L for(n=0;n<18;++n)
int T[19]={54,561,99,306,785,23,547,116,802,71,275,116,39,562,114,305,51,4369,15},W[19]={3,2,3,2,2,3,2,3,2,3,2,3,3,2,3,2,2,1,4},O[7]={0,2,4,8,12,16,17},R[7]={2,2,4,4,4,1,2},G[18],F[24],t=0,I,x,y,S[99],X[99],Y[99],N[99],s,M=0,i,j,k,l,m,n,h,c;char B[99],*C="SZLJTOI";void A(){for(m=0;m<24;++m)F[m]=0;for(m=0;m<4;++m)F[y+m]=(T[I]>>(m*4)&15)<<x;}void D(){S[s]=0;L S[s]+=(G[n]|F[n])==1023;S[s]=200*(S[s])+199;for(m=0;m<10;++m){l=0;L{h=(G[n]|F[n])&1<<m;l|=h;S[s]-=l&&!h;}}}int E(){A();c=0;L c|=G[n]&F[n];return !c;}int main(){S[0]=0;gets(B);while(C[t]!=B[0])++t;I=O[t];L{G[n]=0;gets(B);for(m=0;m<10;++m)G[n]|=(B[m]=='+')?(1<<m):0;}s=0;D();for(i=0;i<R[t];++i){for(x=0;x<10-W[I];x++){y=0;while(E())y++;--y;++s;A();D();if(S[s]>M)M=S[s];X[s]=x;Y[s]=y;N[s]=I;}I++;}for(i=1;i<s;++i)if(S[i]==M){j=i;x=X[i];y=Y[i];I=N[i];A();for(n=1;n<18;++n){for(m=0;m<10;++m)printf((G[n]&1<<m)!=0?"+":((F[n]&1<<m)!=0?"#":" "));printf("\n");}}printf("%dL %dH\n",S[j]/200,S[0]%200-S[j]%200);}

Aquí está la versión sin golf

#include <stdio.h>

int tiles[19] = {54,561,99,306,785,23,547,116,802,71,275,116,39,562,114,305,51,4369,15};
int widths[19] = {3,2,3,2,2,3,2,3,2,3,2,3,3,2,3,2,2,1,4};
char *codes = "SZLJTOI";
int offsets[7] = {0,2,4,8,12,16,17};
int transformations[7] = {2,2,4,4,4,1,2};
int gameField[18], tileField[24];

int i,j,k,l,m,n,h;
char buffer[99];
int tile=0, tileIndex;
int xpos, ypos;
int scores[99], xplacements[99], yplacements[99], tindex[99];
int scoreIndex, maxScore=0;

void readGame()
{
  gets(buffer);
  while (codes[tile]!=buffer[0]) ++tile;
  tileIndex = offsets[tile];
  for (n=0;n<18;++n)
  {
    gameField[n] = 0;
    gets(buffer);
    for (m=0; m<10;++m)
      gameField[n] |= (buffer[m]=='+')?(1<<m):0;
  }
}

void writeGame()
{
  for (n=1;n<18;++n)
  {
    for (m=0; m<10;++m)
      printf( (tileField[n] & 1<<m) != 0 ? "#" :((gameField[n] & 1<<m) != 0 ? "+" :" "));
    printf("\n");
  }
}

void placeTile()
{
  for (m=0;m<24;++m) tileField[m] = 0;
  for (m=0;m<4;++m) 
    tileField[ypos+m] = (tiles[tileIndex]>>(m*4) & 15) << xpos;
}

void score()
{
  scores[scoreIndex] = 0;
  for (n=0;n<18;++n) 
    if ((gameField[n] | tileField[n])==1023) scores[scoreIndex]++;

  scores[scoreIndex] = 200*(scores[scoreIndex]) + 199;

  for (m=0;m<10;++m)
  {
    l=0;
    for (n=0;n<18;++n)
    {
      h = (gameField[n] | tileField[n]) & 1<<m;
      l |= h;
      scores[scoreIndex] -= l && !h;
    }
  }
}

int noCollision()
{
  placeTile();
  int coll = 0;
  for (n=0;n<18;++n) coll |= gameField[n] & tileField[n];
  return !coll;
}

int main()
{ scores[0] = 0;
  readGame();
  scoreIndex = 0;
  score();
  for (i=0; i<transformations[tile]; ++i)
  {
    for (xpos=0; xpos<10-widths[tileIndex]; xpos++)
    {
      ypos = 0;
      while (noCollision()) ypos++;
      --ypos;
      ++scoreIndex;
      placeTile();
      score();
      if (scores[scoreIndex]>maxScore) maxScore=scores[scoreIndex];
      xplacements[scoreIndex] = xpos;
      yplacements[scoreIndex] = ypos;
      tindex[scoreIndex] = tileIndex;
    }
    tileIndex++;
  }

  for (i=1;i<scoreIndex; ++i) 
    if (scores[i]==maxScore)
    {
      j=i;
      xpos = xplacements[i];
      ypos = yplacements[i];
      tileIndex = tindex[i];
      placeTile();
      writeGame();
    }

  printf("%dL %dH\n", scores[j]/200, scores[0]%200-scores[j]%200);
}

Vi que la fuente principal de código largo probablemente sería la definición de los mosaicos. Así que decidí representarlos como patrones de bits en una matriz de 4x4 bits. Esto da como resultado 16 bits que caben fácilmente en un solo int. La tilesmatriz contiene todos los patrones para las 19 rotaciones posibles de los 7 mosaicos.

Al compilar, ignore la advertencia que getsestá en desuso. Sé que es, pero es la forma más corta de leer una línea desde la entrada.

mikail sheikh
fuente
A escala global, puede soltar el intcomo se supone. Varios de sus printfsúnicos producen un solo carácter. Es posible que pueda reemplazarlos con un equivalente putcharpara guardar un par de caracteres. Por ejemplo, cambiar printf("\n")a putchar(10):)
Josh
pone ("") es aún más corto si solo desea una nueva línea. También puede usar return! C (sin espacio). La primera vez que utiliza un índice de un bucle for, puede omitir la inicialización a 0 ya que las variables se declaran globalmente. Además, creo que usa la función E solo una vez, por lo que debería ser posible simplemente ponerla en línea.
Alchymist