J'aime beaucoup Tetris, mais je ne suis pas très bon dans ce domaine. Juste une fois, j'aimerais voir ce vaisseau spatial décoller devant mes propres yeux! Et comme les ordinateurs sont tellement géniaux en tout, la seule solution possible est de créer un programme pour le jouer pour moi ... sauf que vous allez faire ça pour moi!

Étant donné un tetromino (forme composée de quatre carrés) et une carte du terrain de jeu, vous devez placer le tetromino de telle sorte qu'il marque le plus grand nombre de lignes (rend le plus grand nombre de lignes complètement remplies de blocs) et crée le moins de nombres de nouveaux trous (un espace vide qui ne peut pas "voir" le haut du terrain de jeu ¹ ).

Contribution

L'entrée contiendra un caractère sur une seule ligne qui représente le tétromino en baisse, suivi d'une grille 10 * 18 ² d'espaces ( ) et de signes plus ( +).

Le caractère représente l'un des sept tétrominoes de base trouvés dans Tetris. Toutes les pièces peuvent être tournées de 90 degrés, mais pas retournées. Tous les tétrominoes et leurs rotations sont les suivants:

         #
S =  ##  ##
    ##    #

          #
Z = ##   ##
     ##  #

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

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

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

O = ##
    ##

    #
I = #  ####
    #
    #

La grille représente le terrain de jeu de Tetris, avec +des blocs précédemment placés. Ainsi, un exemple d'entrée peut être le suivant:

I











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

Production

Votre sortie sera identique à l'entrée, mais avec le tetromino dans la position idéale. Le tétromino doit être représenté par #pour les différencier des blocs pré-placés. En plus de cela, vous devez également afficher le nombre de lignes / trous que votre placement crée dans le formulaire xL yHsur une nouvelle ligne.

La sortie de l'exemple donné ci-dessus serait la suivante ³ :

I











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

Vous ne devez produire que le ou les meilleurs résultats; dans le cas de deux ou plusieurs cas donnant le même score, vous devez tous les afficher (séparés par une ligne vierge). Les meilleurs résultats doivent être déterminés en triant d'abord le nombre de lignes marquées (décroissantes), puis le nombre de nouveaux trous créés (ascendants). Donc, 1L 1Hc'est un meilleur score que 0L 0H.

Je vais travailler sur la création d'une liste de diverses entrées et sorties attendues sur lesquelles vous pouvez tester votre programme. Surveillez cet endroit.

Règles et désambiguïsation

• Il s'agit de code-golf , donc la mise en œuvre correcte la plus courte l'emporte.
• L'entrée / sortie peut se faire sur tout support adapté à votre langue cible (par exemple fichier, stdin / stdout, zone de texte).
• Si votre langue cible ne prend pas en charge la saisie sur plusieurs lignes (ou si cela n'est pas pratique), vous pouvez à la place délimiter chaque ligne de la saisie avec des virgules ( ,).
• Vous pouvez omettre la sortie de toutes les lignes vides de la grille.
• N'oubliez pas que le tétromino tombe d'en haut - vous ne pouvez pas placer la pièce "sous terre". Vous pouvez donc supposer que tous les emplacements possibles de la pièce seront au "niveau de la surface" (c'est-à-dire qu'il n'y a pas de bloc entre la pièce et le haut de la planche).
• Supposons qu'il n'y aura jamais de situation dans laquelle vous serez obligé de reprendre la partie (le tétromino placé touche le haut du centre du terrain).
• Les solutions identiques en sortie doivent être omises (par exemple, il existe 3 sorties de solutions si vous faites naïvement tourner la Opièce).

¹ Je sais que cela va créer des faux positifs, mais c'est une simplification.

² Il s'agit de la taille de grille utilisée dans la version Game Boy.

³ Oui, 0Hc'est correct. Vérifiez encore, j'ai dit de nouveaux trous; ^)

C 1009 octets

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

Voici la version non golfée

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

J'ai vu que la principale source de code long serait probablement la définition des tuiles. J'ai donc décidé de les représenter sous forme de motifs binaires dans un tableau 4x4 bits. Il en résulte 16 bits qui s'intègrent facilement dans un seul int. Le tilestableau contient tous les modèles pour les 19 rotations possibles des 7 tuiles.

Lors de la compilation, ignorez l'avertissement getsobsolète. Je le sais, mais c'est le moyen le plus court de lire une ligne depuis l'entrée.