Find the best move in a game of Tetris

Question

I like Tetris a lot, but I'm not very good at it. Just once I'd like to see that spaceship take off in front of my own eyes! And since computers are oh-so great at everything, the only possible solution is to make a program to play it for me... except you're going to do that bit for me!

Given a tetromino (shape made of four squares) and a map of the playing field, you are to place the tetromino such that it scores the greatest number of lines (makes the greatest number of rows completely full of blocks) and creates the least number of new holes (an empty space that cannot "see" the top of the playing field¹).

Input

The input will contain a character on a single line that represents the dropping tetromino, followed by a 10*18 grid² of spaces () and plus signs (+).

The character represents any of the seven base tetrominoes found in Tetris. All of the pieces can be rotated by 90 degrees, but not flipped. All the tetrominoes and their rotations are as follows:

         #
S =  ##  ##
    ##    #

          #
Z = ##   ##
     ##  #

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

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

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

O = ##
    ##

    #
I = #  ####
    #
    #

The grid represents the playing field of Tetris, with + being previously-placed blocks. So, an example input might be the following:

I











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

Output

Your output will be identical to the input, but with the tetromino in the ideal position. The tetromino should be represented with # to differentiate them from the pre-placed blocks. In addition to this, you are also to output how many lines/holes your placement creates in the form xL yH on a new line.

The output for the example given above would be the following³:

I











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

You are to output only the best result(s); in the case of two or more cases giving the same score, you are to output all of them (separated by a blank line). The best results are to be determined by sorting by the number of lines scored (descending) first, then the number of new holes created (ascending). So, 1L 1H is a better score than 0L 0H.

I will work on creating a list of various inputs and expected output(s) that you can test your program against. Watch this space.

Rules and Disambiguation

• This is code-golf, so shortest correct implementation wins.
• Input/output may be in any medium that suits your target language (e.g. file, stdin/stdout, text area).
• If your target language does not support multiple line input (or it is inconvenient to do so), you may instead delimit each line of the input with commas (,).
• You may omit the output of any blank lines in the grid.
• Remember that the tetromino falls from above - you may not place the piece "underground". You may therefore assume that all possible placements of the piece will be at "surface-level" (i.e. there are no blocks between the piece and the top of the board).
• Assume that there will never be a situation in which you are forced into a game over (the placed tetromino touches the top-center of the field).
• Solutions that are identical in output must be omitted (e.g. there are 3 solutions outputs if you naively rotate the O piece).

---

¹ I'm aware that this will create some false positives, but it's a simplification.

² This is the grid size used in the Game Boy version.

³ Yes, 0H is correct. Check again, I said new holes ;^)

Answer 1

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

Here is the ungolfed version

#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);
}

I saw that the main source of lengthy code would probably be the definition of the tiles. So I decided to represent them as bit patterns in a 4x4 bit array. This results in 16 bits that easily fit into a single int. The tiles array holds all the patterns for the 19 possible rotations of the 7 tiles.

When compiling, ignore the warning that gets is deprecated. I know it is but it is the shortest way of reading a line from the input.