Stratégie Tetris

18

Votre tâche consiste à mettre en œuvre une stratégie Tetris équilibrée en termes de score par rapport à la taille du code.

Dans cette version du jeu, les tétrominos sont tournés et déposés par le haut dans une grille de 20 lignes et 10 colonnes. En tombant, ils ne peuvent pas être tournés ou déplacés horizontalement. Comme d'habitude, une pièce tombée s'arrête lorsqu'elle atteint le bas de la grille ou lorsqu'un mouvement vers le bas entraînerait une collision avec un carré déjà occupé.

Lorsque nles lignes horizontales sont complètement remplies, elles s'effondrent simultanément, la grille est remplie de nlignes vides en haut et le score est incrémenté de 2 n -1 points. Pour n= 1,2,3,4, c'est 1,3,7,15 points respectivement. Après la disparition des lignes, certains blocs peuvent rester flottants dans l'air (il n'y a pas de " réaction en chaîne par gravité ").

Lorsqu'aucune pièce n'est disponible pour que la pièce actuelle apparaisse où vous le souhaitez, la grille est effacée, la pièce actuelle est ignorée et le jeu continue avec la pièce suivante comme actuelle. Il n'y a aucune pénalité pour cela.

Vous devriez lire un flux de types de pièces et décider comment les faire pivoter et où les déposer. L'anticipation de la pièce suivante (une seule) est autorisée: vous pouvez regarder la pièce i+1avant de répondre i, mais vous devez avoir décidé du sort iavant de la regarder i+2. Aucune anticipation n'est disponible au-delà de la dernière partie de l'entrée.

Les types de tétromino et leurs rotations sont codés selon le tableau suivant:

        type 0    1    2    3    4    5    6
             O    I    Z    J    L    S    T
            ┌────┬────┬────┬────┬────┬────┬────┐
 rotation 0 │##  │#   │##  │ #  │#   │ ## │### │
            │##  │#   │ ## │ #  │#   │##  │ #  │
            │    │#   │    │##  │##  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          1 │##  │####│ #  │### │  # │#   │#   │
            │##  │    │##  │  # │### │##  │##  │
            │    │    │#   │    │    │ #  │#   │
            │    │    │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          2 │##  │#   │##  │##  │##  │ ## │ #  │
            │##  │#   │ ## │#   │ #  │##  │### │
            │    │#   │    │#   │ #  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          3 │##  │####│ #  │#   │### │#   │ #  │
            │##  │    │##  │### │#   │##  │##  │
            │    │    │#   │    │    │ #  │ #  │
            │    │    │    │    │    │    │    │
            └────┴────┴────┴────┴────┴────┴────┘

L'entrée est binaire - une séquence d'octets dont les restes lorsqu'ils sont divisés par 7 doivent être interprétés comme les OIZJLSTtétrominoes. Ils se produiront avec à peu près la même probabilité (sauf que les premiers types peuvent apparaître un peu plus souvent car 256 n'est pas un multiple de 7, mais cela devrait être négligeable). L'entrée peut provenir de stdin ou d'un fichier nommé "i" ou être passée en argument. Vous pouvez lire toutes les entrées à la fois, à condition de vous assurer de respecter la restriction d'anticipation.

La sortie est également binaire - une séquence d'octets de la même longueur que l'entrée. Il peut s'agir de stdout ou d'un fichier nommé "o" ou du résultat d'une fonction. Chaque octet code r*16 + x, où rest la rotation souhaitée et xest l'index basé sur 0 de la colonne où le carré le plus à gauche du tétromino tourné doit aller. Celles-ci ret xdoivent être valables, c'est-à 0 ≤ r ≤ 3- dire et 0 ≤ x ≤ 10-w, où west la largeur de la pièce correspondante.

Votre programme doit être déterministe - étant donné la même entrée, il doit produire exactement la même sortie. L'utilisation d'un PRNG est acceptable tant qu'il est semé de const.

Le score total est le score du jeu moins la taille de votre code en octets. Veuillez utiliser le fichier suivant (64 Ko de bruit pseudo-aléatoire) en entrée: https://gist.github.com/ngn/857bf2c99bfafc649b8eaa1e489e75e4/raw/880f29bd790638aa17f51229c105e726bce60235/i

Le script python2 / python3 suivant lit les fichiers "i" et "o" du répertoire actuel, rejoue le jeu et imprime le score (n'oubliez pas de soustraire la taille de votre code du score):

a = [0] * 23 # grid (1square=1bit, 1row=1int, LSB is left, 3 empty rows on top)
#      O     I         Z       J       L       S       T        tetrominoes
t = [[[3,3],[1,1,1,1],[3,6],  [2,2,3],[1,1,3],[6,3],  [7,2]  ],
     [[3,3],[15],     [2,3,1],[7,4],  [4,7],  [1,3,2],[1,3,1]],
     [[3,3],[1,1,1,1],[3,6],  [3,1,1],[3,2,2],[6,3],  [2,7]  ],
     [[3,3],[15],     [2,3,1],[1,7],  [7,1],  [1,3,2],[2,3,2]]]
tw = [[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2]] # widths
th = [[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3]] # heights
score = 0
for p, rx in zip(bytearray(open('i', 'rb').read()),
                 bytearray(open('o', 'rb').read())):
    p %= 7; r = rx >> 4; x = rx & 15  # p:piece type, r:rotation, x:offset
    b = [u << x for u in t[r][p]]     # as a bit-matrix (list of ints)
    bw = tw[r][p]; bh = th[r][p]      # width and height
    y = 0                             # drop it
    while y <= 23 - bh and all((a[y + i] & b[i]) == 0 for i in range(bh)):
        y += 1
    y -= 1
    if y < 3:                         # no room?
        a = [0] * len(a)              # clear the grid and carry on
    else:
        for i in range(bh):           # add the piece to the grid
            a[y + i] |= b[i]
        n = 0
        for i in reversed(range(bh)): # collapse full lines
            if a[y + i] == (1 << 10) - 1:
                n += 1; del a[y + i]; a = [0] + a
        score += (1 << n) - 1
print(score)

Le programme C suivant est beaucoup plus rapide, mais il est garanti de fonctionner uniquement sous Linux:

#include<stdio.h>
#include<fcntl.h>
#include<sys/mman.h>
#include<sys/stat.h>
#define F(i,n,b...)for(i=0;i<n;i++){b;}
typedef int I;typedef char C;
I a[23],t[]={
51,4369,99,802,785,54,39,51,15,306,71,116,561,305,
51,4369,99,275,547,54,114,51,15,306,113,23,561,562};
C*th="2423322213223324233222132233";
I main(){
 struct stat h;stat("i",&h);I i,j,k,l=h.st_size,z=0;
 C*mi=mmap(0,l,1,1,open("i",0,0),0),*mo=mmap(0,l,1,1,open("o",0,0),0);
 F(k,l,
  I p=(mi[k]&255)%7,r=3&mo[k]>>4,q=r*7+p,x=mo[k]&15,y=0,h=th[q]-'0',b[4];
  F(i,h,b[i]=(t[q]>>(4*i)&15)<<x)
  while(y<=23-h){I u=0;F(i,h,u|=a[y+i]&b[i])if(u)break;y++;}
  if(--y<3){F(i,23,a[i]=0)continue;}
  F(i,h,a[y+i]|=b[i])
  I n=0;F(i,23,n+=a[i]==1023)
  if(n){j=23;F(i,20,a[j]=a[22-i];j-=a[j]!=1023)F(i,j,a[i]=0);z+=(1<<n)-1;})
 printf("%d\n",z);return 0;}

Le score total le plus élevé l'emporte. Les failles standard sont interdites.

ngn
la source
Lorsqu'aucune pièce n'est disponible pour que la pièce actuelle apparaisse à l'endroit souhaité Voyons si je comprends bien. Par exemple, si la colonne la plus à gauche est entièrement remplie et que le programme souhaite y placer la pièce suivante, cela forcera l'effacement de la grille, même s'il y avait beaucoup de place ailleurs. Est-ce exact?
Arnauld
@Arnauld yes, correct
ngn
Peut-on optimiser le fichier i ? Beau défi, BTW!
Arnauld
Oui, cela vient de mon / dev / urandom, donc je ne m'attends pas à ce qu'il y ait des modèles exploitables dedans. Merci :)
ngn
1
Plus précisément: est-il légal de stocker des données d'assistance dans notre code spécifique à i , comme "effacer 2 lignes au coup # 147 au lieu d'attendre un Tetris, sinon la pile ira trop haut"? (Cela ne semble pas entrer en conflit avec «ne regardez pas la pièce i + 2 du fichier d'entrée».)
Arnauld

Réponses:

7

C, score: 4136 (4290 - 154 octets)

#include <stdio.h>
main(){int c,p=0,t[]={7,9,21,0,0,51,1,32,16,48,0,33,0,32,16,49};for(;(c=getchar())>=0;putchar(c)){c%=7;c=t[!c||!(10%c)?c:2*c+p++%4];}}

L'idée est que les blocs S, Z, O, j'utilise des emplacements fixes et des rotations:

                  |
      s     z     |
      s s z z # # |
        s z   # # |
0 1 2 3 4 5 6 7 8 9

Les autres - J, L, T - sont regroupés dans les trois premières colonnes avec une rotation cyclique.

Version non golfée:

#include <stdio.h>
int main() {
    int c,p=0,t[] = {7,9,21,51, 1,32,16,48, 16,48,0,33, 0,32,16,49 };
    while ((c=getchar())!=EOF) {
            switch(c%7) {
            case 0: c = t[0]; break;
            case 1: c = t[1]; break;
            case 2: c = t[2]; break;
            case 3: c = t[4+p++%4]; break;
            case 4: c = t[8+p++%4]; break;
            case 5: c = t[3]; break;
            case 6: c = t[12+p++%4]; break;
            }
            putchar(c);
    }
    return 0;
}
Lyth
la source
simple et efficace - bravo!
ngn