Finde den besten Zug in einer Partie Tetris

10

Ich mag Tetris sehr, aber ich bin nicht sehr gut darin. Nur einmal möchte ich sehen, wie das Raumschiff vor meinen eigenen Augen abhebt! Und da Computer in allem ach so großartig sind, besteht die einzig mögliche Lösung darin, ein Programm zu erstellen, das es für mich spielt ... außer Sie werden das für mich tun!

Bei einem Tetromino (Form aus vier Quadraten) und einer Karte des Spielfelds müssen Sie das Tetromino so platzieren, dass es die größte Anzahl von Linien erzielt (die größte Anzahl von Zeilen vollständig mit Blöcken gefüllt ist) und die geringste Anzahl erzeugt von neuen Löchern (ein leerer Raum, der die Oberseite des Spielfeldes 1 nicht "sehen" kann ).

Eingang

Die Eingabe enthält ein Zeichen in einer einzelnen Zeile, das das fallende Tetromino darstellt, gefolgt von einem 10 * 18-Raster 2 aus Leerzeichen ( ) und Pluszeichen ( +).

Der Charakter repräsentiert eines der sieben in Tetris gefundenen Basistetrominoes. Alle Teile können um 90 Grad gedreht, aber nicht gedreht werden. Alle Tetrominoes und ihre Rotationen sind wie folgt:

         #
S =  ##  ##
    ##    #

          #
Z = ##   ##
     ##  #

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

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

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

O = ##
    ##

    #
I = #  ####
    #
    #

Das Gitter stellt das Spielfeld von Tetris dar, wobei +es sich um zuvor platzierte Blöcke handelt. Eine Beispieleingabe könnte also die folgende sein:

I











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

Ausgabe

Ihre Ausgabe ist identisch mit der Eingabe, jedoch mit dem Tetromino in der idealen Position. Das Tetromino sollte mit dargestellt werden #, um sie von den vorab platzierten Blöcken zu unterscheiden. Darüber hinaus müssen Sie auch ausgeben, wie viele Linien / Löcher Ihre Platzierung im Formular xL yHin einer neuen Linie erzeugt.

Die Ausgabe für das oben angegebene Beispiel wäre die folgende 3 :

I











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

Sie müssen nur die besten Ergebnisse ausgeben. Bei zwei oder mehr Fällen mit derselben Punktzahl müssen Sie alle ausgeben (durch eine Leerzeile getrennt). Die besten Ergebnisse werden ermittelt, indem zuerst nach der Anzahl der bewerteten Linien (absteigend) und dann nach der Anzahl der neu erstellten Löcher (aufsteigend) sortiert wird. Also, 1L 1Hist eine bessere Punktzahl als 0L 0H.

Ich werde daran arbeiten, eine Liste verschiedener Eingaben und erwarteter Ausgaben zu erstellen, anhand derer Sie Ihr Programm testen können. Beobachten Sie diesen Raum.

Regeln und Begriffsklärung

  • Dies ist , so dass die kürzeste korrekte Implementierung gewinnt.
  • Die Eingabe / Ausgabe kann in einem beliebigen Medium erfolgen, das zu Ihrer Zielsprache passt (z. B. Datei, Standard / Standardausgabe, Textbereich).
  • Wenn Ihre Zielsprache keine mehrzeilige Eingabe unterstützt (oder dies unpraktisch ist), können Sie stattdessen jede Zeile der Eingabe durch Kommas ( ,) abgrenzen .
  • Sie können die Ausgabe von Leerzeilen im Raster weglassen.
  • Denken Sie daran, dass der Tetromino von oben fällt - Sie dürfen das Stück nicht "unter der Erde" platzieren. Sie können daher davon ausgehen, dass sich alle möglichen Platzierungen des Stücks auf "Oberflächenebene" befinden (dh es befinden sich keine Blöcke zwischen dem Stück und der Oberseite des Bretts).
  • Angenommen, es wird niemals eine Situation geben, in der Sie zu einem Spiel gezwungen werden (der platzierte Tetromino berührt die obere Mitte des Feldes).
  • Lösungen, deren Ausgabe identisch ist, müssen weggelassen werden (z. B. gibt es 3 Lösungsausgaben, wenn Sie das OStück naiv drehen ).

1 Ich bin mir bewusst, dass dies zu Fehlalarmen führen wird, aber es ist eine Vereinfachung.

2 Dies ist die Rastergröße, die in der Game Boy-Version verwendet wird.

3 Ja, 0Hist richtig. Überprüfen Sie noch einmal, ich sagte neue Löcher; ^)

Sean Latham
quelle
Was wäre, wenn ein Stück 1 neues Loch verursachen würde, aber 2 Linien erzielen würde, anstatt nur 1 Linie zu erzielen?
Nathan Merrill
Zuerst nach Anzahl der Zeilen sortieren. 2 Linien> 1 Linie, also gewinnt es, egal wie viele Löcher es gibt.
Sean Latham
2
Wenn Sie ein Loch freigeben, gibt Ihnen das -1H?
Overactor
Hm, daran habe ich nicht gedacht - es könnte als Ergebnis der naiven Lochdefinition auftreten. Ja, ich denke es würde.
Sean Latham
In meiner Lösung habe ich nicht daran gedacht, Löcher freizugeben. Ich habe die Problemdefinition so verstanden, dass die vorhandenen Blöcke nicht geändert werden sollten. Es sollten also keine vollständigen Linien entfernt und keine Löcher freigesetzt werden.
Mikail Sheikh

Antworten:

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

Hier ist die 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);
}

Ich sah, dass die Hauptquelle für langwierigen Code wahrscheinlich die Definition der Kacheln sein würde. Deshalb habe ich beschlossen, sie als Bitmuster in einem 4x4-Bit-Array darzustellen. Dies führt zu 16 Bits, die leicht in ein einzelnes passen int. Das tilesArray enthält alle Muster für die 19 möglichen Umdrehungen der 7 Kacheln.

Ignorieren Sie beim Kompilieren die getsveraltete Warnung . Ich weiß, dass es so ist, aber es ist die kürzeste Art, eine Zeile von der Eingabe zu lesen.

Mikail Sheikh
quelle
Auf globaler Ebene können Sie das intwie angenommen löschen. Einige von Ihnen geben printfsnur ein einziges Zeichen aus. Möglicherweise können Sie sie durch ein Äquivalent ersetzen putchar, um einige Zeichen zu speichern. Zum Beispiel wechseln printf("\n")zu putchar(10):)
Josh
Puts ("") ist noch kürzer, wenn Sie nur eine neue Zeile möchten. Sie können auch return! C (kein Leerzeichen) verwenden. Wenn Sie zum ersten Mal einen Index einer for-Schleife verwenden, können Sie die Initialisierung auf 0 weglassen, da die Variablen global deklariert werden. Ich denke auch, dass Sie die Funktion E nur einmal verwenden, so dass es möglich sein sollte, sie einfach inline zu setzen.
Alchymist