Trouvez le meilleur coup dans une partie de Tetris

10

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 1 ).

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 2 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 3 :

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 , 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).

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

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

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

Sean Latham
la source
Et si un morceau provoquait 1 nouveau trou, mais marquait 2 lignes, contre seulement 1 ligne?
Nathan Merrill
Triez d'abord par nombre de lignes. 2 lignes> 1 ligne, donc il gagne quel que soit le nombre de trous.
Sean Latham
2
Si vous libérez un trou, cela vous donne-t-il -1H?
suracteur
Hm, je n'y ai pas pensé - cela pourrait se produire en raison de la définition naïve du trou. Oui, je suppose que oui.
Sean Latham
Dans ma solution, je n'ai pas envisagé de libérer des trous. J'ai compris la définition du problème de telle manière que les blocs existants ne devraient pas être modifiés. Aucune ligne complète ne doit donc être supprimée et aucun trou libéré.
mikail sheikh

Réponses:

3

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.

mikail sheikh
la source
À l'échelle mondiale, vous pouvez supprimer le intcomme il est supposé. Plusieurs de vos printfsseuls produisent un seul caractère. Vous pourrez peut-être les remplacer par des équivalents putcharpour enregistrer quelques caractères. Par exemple, changer printf("\n")pour putchar(10):)
Josh
put ("") est encore plus court si vous voulez juste une nouvelle ligne. Vous pouvez également utiliser return! C (pas d'espace). La première fois que vous utilisez un index d'une boucle for, vous pouvez omettre l'initialisation à 0 car les variables sont déclarées globalement. De plus, je pense que vous n'utilisez la fonction E qu'une seule fois, il devrait donc être possible de la mettre en ligne.
Alchymist du