Étant donné la liste des déplacements de Tetris, retourne le nombre de lignes complétées

37

La description

Nous considérons une version légèrement simplifiée de Tetris où chaque mouvement consiste en:

  • tourner la pièce dans le sens des aiguilles d'une montre, 0 à 3 fois
  • positionner la pièce sur une colonne donnée
  • chute rapide

Le but est de déterminer le nombre de lignes terminées, à partir d’une liste de ces déplacements de Tetris.

Les lignes terminées sont supprimées au fur et à mesure que les pièces sont déposées, conformément aux règles standard de Tetris.

Playfield

Le terrain de jeu est large de 10 colonnes. Il n'y a pas de Game Over et on suppose qu'il y a toujours assez d'espace et de temps pour effectuer les actions ci-dessus, quelle que soit la configuration du terrain. La hauteur du champ de jeu n’importe pas vraiment ici, mais vous pouvez utiliser les 22 lignes standard comme limite supérieure.

Formes de tetrominoes

formes

Entrée sortie

Contribution

Une liste de mouvements de Tetris séparés par des virgules, codés avec 3 caractères. Les deux premiers caractères décrivent la forme de Tetromino à utiliser et le dernier décrit la position où il est abandonné.

  1. Tetromino: I, O, T, L, J, Zou S, dans le même ordre que ci - dessus.
  2. Nombre de rotations dans le sens des aiguilles d'une montre: 0à3
  3. Colonne: 0à 9. C'est la colonne dans laquelle se trouve le coin supérieur gauche de la pièce (marqué d'un xsur l'image ci-dessus) après la rotation 1

Il est supposé que tous les déplacements dans la liste fournie sont valides. Il n'est pas nécessaire de vérifier les entrées non valides telles que I07( Iforme horizontale trop éloignée à droite).

1 Vous êtes libre d'implémenter un algorithme de rotation réel ou de coder en dur toutes les formes, tant que le xest situé dans la colonne indiquée par le troisième caractère du déplacement.

Sortie

Nombre de lignes complétées.

Exemple

Exemple

O00,T24générera la première position et O00,T24,S02,T01,L00,Z03,O07,L06,I05générera la deuxième position.

Par conséquent, la séquence suivante générera un Tetris et devrait renvoyer 4:

O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19

Cas de test

1) "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19" -> 4
2) "S00,J03,L27,Z16,Z18,I10,T22,I01,I05,O01,L27,O05,S13" -> 5
3) "I01,T30,J18,L15,J37,I01,S15,L07,O03,O03,L00,Z00,T38,T01,S06,L18,L14" -> 4
4) "S14,T00,I13,I06,I05,I19,L20,J26,O07,Z14,Z10,Z12,O01,L27,L04,I03,S07,I01,T25,J23,J27,O01,
    I10,I10" -> 8
5) "O00,T24,L32,T16,L04,Z11,O06,L03,I18,J30,L23,Z07,I19,T05,T18,L30,I01,I01,I05,T02" -> 8

Page de test

Vous pouvez utiliser ce JSFiddle pour tester une liste de déplacements.

Arnauld
la source
1
Sur quel axe sont tournées les pièces?
1
@Arnauld Je vous suggère de jeter un coup d'œil au système de super rotation et de modifier l'image un bit de précision. tetris.wikia.com/wiki/SRS
1
Nous pouvons donc les traiter comme 25 (15 si vous ne comptez pas les doublons), alors?
1
Les solutions peuvent-elles prendre l’entrée comme un tableau plutôt que comme une chaîne séparée par des virgules?
Jordanie
1
C’est la meilleure question de PCG que je connaisse depuis longtemps. Quelle bonne idée! Meilleur dans le sens subjectif d'intéressant et pratique et pas trop grand mais pas trop petit.
GreenAsJade

Réponses:

5

PHP, 405 399 378 372 368 360 354 347 331 330 328 319 309 300 octets

(avec la cartographie de bloc de Dave )

<?$f=[~0];L:for($y=0;$f[++$d+$y]|$s;$s>>=4)$y-=1022<$f[$d+$y]=$f[$d]|$s%16<<$x;$c-=$y;if(list($p,$r,$x)=$argv[++$z])for($s=I==$p?$r&1?4369:15:hexdec(decoct(O==$p?27:ord(base64_decode('M1ozWjqaF1kemR6ZPJMPyTnSJ0s')[ord($p)/4%5*4+$r])));;$d--)for($y=4;$y--;)if ($f[$d+$y]>>$x&$s>>$y*4&15)goto L;echo$c;

programme, prend les mouvements comme arguments séparés, affiche le résultat

panne à fonction:

prend des coups comme tableau, retourne le résultat

function t($a)
{
    $f=[~$z=0];             // init field $f (no need to init $z in golfed version)
    L:                      // jump label
                            // A: paint previous piece at line $d+1:
#   if($s)paint($f,$s,$d+1,$x);
    for($y=0;               // $y = working line offset and temporary score
        $f[++$d-$y]|$s;$s>>=4)// next field line; while field or piece have pixels ...
        $s>>=4)                 // next piece line
        $y+=1022<               // 3: decrease temp counter if updated line is full
            $f[$d-$y]=$f[$d]    // 2: use $y to copy over dropped lines
                |$s%16<<$x;     // 1: set pixels in working line
    $c+=$y;                         // add temp score to global score
#   paint($f);var_dump($c);
    if(list($p,$r,$x)=$a[$z++])// B: next piece: $p=name; $r=rotation, $x=column
#   {echo"<b>$z:$p$r-$x</b><br>";
        for(                // C: create base 16 value:
            $s=I==$p
                ? $r&1?4369:15  // I shape (rotated:0x1111, not rotated:0xf)
                : hexdec(decoct(    // 5: convert from base 8 to base 16
                    O==$p ? 27  // O shape (rotation irrelevant: 033)
                    : ord(          // 4: cast char to byte
                                    // 0: 4 bytes for each remaining tetromino
                        base64_decode('M1ozWjqaF1kemR6ZPJMPyTnSJ0s')[
                            ord($p)/4%5 // 1: map STZJL to 01234
                            *4      // 2: tetromino offset
                            +$r]    // 3: rotation offset
            )));;$d--
        )
            for($y=4;$y--;) // D: loop $y through piece lines
                if ($f[$d+$y]>>$x & $s>>$y*4 & 15) // if collision ...
                    goto L;         // goto Label: paint piece, tetris, next piece
#   }
    return$c;               // return score
}

pour référence: l'ancienne cartographie

            hexdec(decoct(          // 3. map from base 8 to base 16
                                    // 0. dword values - from high to low: rotation 3,2,1,0
                [0x991e991e,0xc90f933c,0x4b27d239,0x1b1b1b1b,0,0x5a335a33,0x59179a3a]
                [ord($m[0])/2%9]    // 1. map ZJLO.ST to 0123.56 -> fetch wanted tetromino
                >>8*$m[1]&255       // 2. the $m[1]th byte -> rotated piece
            ))

essai

voir mon autre réponse PHP

vouloir regarder?

supprime la #source de la fonction et ajoute ceci:

function paint($f,$s=0,$d=0,$x=0){echo'<pre>';for($y=count($f)+5;$y--;$g=0)if(($t=(($z=$y-$d)==$z&3)*($s>>4*$z&15)<<$x)|$r=$f[$y]|0){$z=$t?" $r|$t=<b".(1022<($z=$t|$r)?' style=color:green':'').">$z":" <b>$r";for($b=1;$b<513;$b*=2)$z=($t&$b?'<b>'.($r&$b?2:1).'</b>':($r&$b?1:'.')).$z;printf("%02d $z</b>\n",$y);}echo'</pre>';}

quelques marches de golf

Apocalypse 5: Un grand bond en avant (399- 21 = 378) est venu en déplaçant simplement le déplacement de la colonne
d'une boucle séparée pour les deux boucles existantes.

Rév. 8: Passer de la matrice à la base 16 pour la pièce ($ s) ne donnait pas grand chose,
mais laissait la place à un peu plus de golf.

Rév. 17: regroupement des valeurs avec base64_encode(pack('V*',<values>))
et utilisation de l'indexation d'octets au lieu d' unpackenregistrer 16 octets

Rév. 25 à 29: inspiré par le code de Dave: nouveau hachage (-2), nouveau design de boucle (-9), goto (-10)
pas de pré-décalage cependant; cela coûterait 17 octets.

plus de potentiel

Avec /2%9, je pourrais économiser 15 octets (seulement 14 octets avec /4%5)
en mettant des données binaires dans un fichier b, puis en les indexant file(b)[0].
Est-ce que je veux ça?

Les caractères UTF-8 coûteraient cher pour la transformation.

sur le hachage

J'ai utilisé ZJLO.ST /2%9 -> 0123.56; mais T.ZJLOS /3%7 -> 0.23456est aussi bon.
un octet de plus: O.STJLZ %13/2 -> 0.23456
et trois autres:OSTZJ.L %17%12%9 -> 01234.6

Je ne pouvais pas trouver un hachage court (max. 5 octets) qui ne laisse aucun espace;
mais Dave a trouvé STZJL /4%5 -> 01234, supprimant le O de la liste. wtg!

BTW: TIJSL.ZO (%12%8) -> 01234.67salle de feuilles pour la Iforme
(et fictive A, Mou la Yforme). %28%8et %84%8faites de même (mais avec Eau lieu de A).

Titus
la source
Agréable; J'aime la combinaison peinture + détection de ligne, et break 2c'est beaucoup plus propre que ce que je devais faire en C! Vous pourrez peut- être économiser des octets en utilisant array_diff(définissez les lignes complétées sur une valeur fixe au lieu d’utiliser unsetpuis de remplacer array_valuespar array_diff), mais je ne saurais dire à partir de la documentation si cela aplatirait les valeurs répétées (par exemple, array_diff ([1,2, 2,3], [1]) -> [2,2,3] ou juste [2,3])
Dave
@Dave: array_diffne supprime pas les valeurs en double; et j'ai déjà la valeur fixe (1023); mais il ne réindexe pas le tableau. Excellente idée, mais cela coûterait un octet.
Titus
wow c'était un crissement de voix alors que vous passiez près de moi! On dirait que j'ai du rattrapage à faire!
Dave
Félicitations pour avoir atteint les 300! Je vais mettre en œuvre votre dernier changement suggéré (je n'avais pas pensé à simplifier la vérification de la rotation maintenant que je n'en ai plus besoin /10partout), mais sinon je pense que j'ai terminé. Je suis surpris de voir à quel point PHP et C sont compétitifs. C'était amusant - espérons que le PO accepte votre réponse!
Dave
@ Dave & Titus - J'aimerais pouvoir accepter les deux réponses. Vous avez fait un excellent travail. Félicitations quand même à Titus pour avoir atteint les 300. Et je pense que c’est en fait 299 puisque vous avez un espace inutile après un if.
Arnauld
16

C, 401 392 383 378 374 351 335 324 320 318 316 305 octets

d[99]={'3Z3Z',983177049,513351321,1016270793,970073931,~0},*L=d+5,V,s;char c;main(x){B:for(c=0;c[++L]|V;V>>=4)c-=(L[c]=*L|(V&15)<<x)>1022;s-=c;if(scanf("%c%1d%d,",&c,&V,&x)>2)for(V=c^79?d[c/4%5]>>24-V*8:27,V=c^73?V/64%4<<8|V/8%8<<4|V%8:V&32?15:4369;;--L)for(c=4;c--;)if(L[c]>>x&V>>c*4&15)goto B;return s;}

Prend une entrée séparée par des virgules sur stdin, renvoie le score dans l'état de sortie.

Nécessite chard'être signé (ce qui est le comportement par défaut pour GCC) et doit '3Z3Z'être interprété comme 861549402 (ce qui est le cas pour GCC sur les machines little endian).


Exemple d'utilisation:

echo "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19" | ./tetris; echo "$?";

Explication de haut niveau:

Toutes les formes, à l'exception de la ligne, peuvent s'inscrire dans une grille 3x3 avec un coin manquant:

6 7 -
3 4 5
0 1 2

Cela signifie qu'il est facile de les stocker dans un octet chacun. Par exemple:

- - -         0 0 -
- # -   -->   0 1 0   -->   0b00010111
# # #         1 1 1

(nous alignons chaque morceau sur le coin inférieur gauche de la boîte pour le déposer plus facilement)

Étant donné que nous obtenons au moins 4 octets pour un int, cela signifie que nous pouvons stocker les 4 rotations de chaque pièce dans un seul entier, avec un cas spécial pour la ligne. Nous pouvons également adapter chaque ligne de la grille de jeu à un int (il ne faut que 10 bits), et à la pièce en chute longue (4 lignes = 40 bits).


Panne:

d[99]={             // General memory
  '3Z3Z',           //  Shape of "S" piece (multi-char literal, value = 861549402)
  983177049,        //  Shape of "T" piece
  513351321,        //  Shape of "Z" piece
  1016270793,       //  Shape of "J" piece
  970073931,        //  Shape of "L" piece
  ~0                //  Bottom of game grid (solid row)
},                  //  Rest of array stores lines in the game
*L=d+5,             // Working line pointer (start >= base of grid)
V,                  // Current piece after expansion (also stores rotation)
s;                  // Current score (global to initialise as 0)
char c;             // Input shape identifier (also counts deleted lines)
main(x){            // "x" used to store x location
  B:                                // Loop label; jumps here when piece hits floor
  for(c=0;c[++L]|V;V>>=4)           // Paint latest piece & delete completed lines
    c-=(L[c]=*L|(V&15)<<x)>1022;
  s-=c;                             // Increment score
  if(scanf("%c%1d%d,",&c,&V,&x)>2)  // Load next command
    for(V=c^79?                     // Identify piece & rotation
          d[c/4%5]>>24-V*8          //  Not "O": load from data
        :27,                        //  Else "O": always 27
        V=c^73?                     // If not "I" (line):
          V/64%4<<8|V/8%8<<4|V%8    //  expand shape to 16-bits
        :                           // Else we are a line:
          V&32?                     //  "I" coincides with "J"; use this to check
               15:4369;             //  horizontal/vertical
        ;--L)                       // Loop from top-to-bottom of grid
      for(c=4;c--;)                 //  Loop through rows of piece
        if(L[c]>>x&V>>c*4&15)       //   If collides with existing piece:
          goto B;                   //    Exit loops
  return s;                         // Return score in exit status
}

-4, -1 grâce à @Titus et -23, -11 inspirés par leur réponse

Dave
la source
Joli! Pourriez-vous juste faire s+=(d[A-x]=d[A])sans utiliser x?
Arnauld
Il xest malheureusement nécessaire de garder trace du nombre de lignes à réduire dans l'étape en cours (chaque ligne Aest définie sur la valeur de la ligne à A-xmesure que la boucle progresse)
Dave
D'oh! Ma faute. Désolé pour une suggestion aussi stupide. :)
Arnauld
1
@ Titus c'est un abus de l'indexation sur les tableaux de C. En termes simples, 1[a]et a[1]faire la même chose (ou plus précisément, se a[b]traduit par *(a+b)). C'est abusé comme ça pour éviter les parenthèses. Dans ce cas, 1[*v]== (*v)[1], c'est-à-dire la deuxième lettre de la commande, c'est-à-dire la rotation.
Dave
1
Pouvez-vous vous débarrasser de l' Iespace réservé? Si c'est le cas, essayez /2%9comme hash au lieu de %12. %12%8si non.
Titus
2

Ruby, 474 443 428 379 + 48 = 427 octets

-1 grâce à @Titus

Cela peut certainement être joué au golf plus.

Lit un dictionnaire binaire de morceaux (voir ci-dessous) à partir de STDIN ou d'un nom de fichier et prend une liste de déplacements en argument, par exemple $ cat pieces | ruby script.rb O00,T24,S02,....

q=$*.pop
z=$<.read.unpack('S*')
b=c=g=i=0
x=10
u=1023
r=->n{n&2**x-1>0?n:r[n>>x]}
y=->n{n>0?[n&u]+y[n>>x]:[]}
l=->c,n{z.find{|m|m>>x==c<<2|n.to_i}||l[c,n-2]}
q.scan(/(\w)(\d)(\d)/){n=l["IOTLJSZ".index($1),$2.to_i]
v=(n&1|(n&6)<<9|(n&56)<<17|(n&960)<<24)<<$3.to_i
(y[b].size+1).times{t=b<<40
t&v>0&&break
g=t|v
v<<=x}
b=0
a=y[r[g]]
a.grep_v(u){|o|b|=o<<x*i
i+=1}
c+=a.count u}
p c

Données de morceaux binaires (format xxd)

0000000: c003 4b04 d810 d814 b820 9c24 d029 5a2c  ..K...... .$.)Z,
0000010: 7830 9634 e039 ca3c 3841 d444 c849 4e4c  x0.4.9.<8A.D.INL
0000020: 9861 9869 5c64 5c6c f050 f058 9a54 9a5c  .a.i\d\l.P.X.T.\

Voir sur repl.it (avec les arguments codés en dur, dictionnaire): https://repl.it/Cqft/2

Ungolfed & explication

# Move list from ARGV
q = $*.pop

# Read piece dictionary; pieces are 16-bit integers: 3 for letter,
# 2 for rotation, 10 for shape (and 1 wasted)
z = $<.read.unpack('S*')

# Empty board and various counters
b = c = g = i = 0
x = 10 # Magic numbers
u = 1023

# A function to remove empty lines
r = ->n{ n & 2**x - 1 > 0 ? n : r[n >> x] }

# A function to split the board into lines
y = ->n{ n > 0 ? [n & u] + y[n >> x] : [] }

# A function to lookup a piece by letter and rotation index
l = ->c,n{ z.find {|m| m >> x == c << 2 | n.to_i } || l[c, n-2] }

# Read the move list
q.scan(/(\w)(\d)(\d)/) {
  # Look up the piece
  n = l["IOTLJSZ".index($1), $2.to_i]

  # Convert the 10-bit piece to a 40-bit piece (4 rows of 10 columns)
  v = (n & 1 |
        (n & 6) << 9 |
        (n & 56) << 17 |
        (n & 960) << 24
      ) << $3.to_i # Shift by the appropriate number of columns

  # Drop the piece onto the board
  (y[b].size + 1).times {
    t = b << 40
    t & v > 0 && break
    g = t | v
    v <<= x
  }

  # Clear completed rows
  b = 0
  a = y[r[g]]
  a.grep_v(u) {|o|
    b |= o << x * i
    i += 1
  }

  c += a.count u # Count cleared rows
}
p c
Jordan
la source
1 octet: m >> 10pourrait êtrem >> x
Titus
@Titus Bon oeil. Merci!
Jordanie
Pas besoin d'exiger explicitement \ds dans l'expression régulière: /(\w)(\d)(\d)//(\w)(.)(.)/
manatwork
2

PHP, 454 435 427 420 414 octets

champs de bits pour les morceaux et la carte; mais pas de cas particulier pour la Iforme comme le golf de Dave.

<?$t=[I=>[15,4369],O=>[51],T=>[114,562,39,305],L=>[113,802,71,275],J=>[116,547,23,785],Z=>[54,561],S=>[99,306]];foreach($argv as$z=>$m)if($z){$s=$t[$m[0]][$m[1]%count($t[$m[0]])];for($d=$i=0;$i<4;$i++)for($k=0;$k<4;$k++)if($s>>4*$k&1<<$i){for($y=0;$y++<count($f);)if($f[$y-1]&1<<$m[2]+$i)$d=max($d,$y-$k);$k=3;}for($k=$d;$s;$k++,$s>>=4)if(1022<$f[$k]|=$s%16<<$m[2]){$c++;unset($f[$k]);}$f=array_values($f);}echo$c;

prend les arguments de la ligne de commande, affiche le résultat

non golfé comme fonction

prend les arguments en tant que tableau, retourne le résultat

function t($a)
{
    // bitwise description of the stones and rotations
    $t=[I=>[15,4369],O=>[51],T=>[114,562,39,305],L=>[113,802,71,275],J=>[116,547,23,785],Z=>[54,561],S=>[99,306]];
    foreach($a as$m)
    {
        $s=$t[$m[0]][$m[1]%count($t[$m[0]])];   // $s=stone
        // find dropping space
        for($d=$i=0;$i<4;$i++)
            // a) lowest pixel of stone in column i
            for($k=0;$k<4;$k++)
                if($s>>4*$k&1<<$i)
                {
                    // b) top pixel of field in column x+i 
                    for($y=0;$y++<count($f);)
                        if($f[$y-1]&1<<$m[2]+$i)$d=max($d,$y-$k);
                    $k=3; // one byte shorter than `break;`
                }
        // do drop
        for($k=$d;$s;$k++,$s>>=4)
            if(1022<$f[$k]|=$s%16<<$m[2])   // add block pixels to line pixels ... if full,
            {$c++;unset($f[$k]);}           // tetris
        $f=array_values($f);
    }
    return$c;
}

tests (sur la fonction)

$data=[
    "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19"=>4,
    "S00,J03,L27,Z16,Z18,I10,T22,I01,I05,O01,L27,O05,S13" => 5,
    "I01,T30,J18,L15,J37,I01,S15,L07,O03,O03,L00,Z00,T38,T01,S06,L18,L14" => 4,
    "S14,T00,I13,I06,I05,I19,L20,J26,O07,Z14,Z10,Z12,O01,L27,L04,I03,S07,I01,T25,J23,J27,O01,I10,I10" => 8,
    // additional example for the two last tetrominoes:
    'O00,T24,L32,T16,L04,Z11,O06,L03,I18,J30,L23,Z07,I19,T05,T18,L30,I01,I01,I05,T02' => 8,
];
function out($a){if(is_object($a)){foreach($a as$v)$r[]=$v;return'{'.implode(',',$r).'}';}if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function cmp($a,$b){if(is_numeric($a)&&is_numeric($b))return 1e-2<abs($a-$b);if(is_array($a)&&is_array($b)&&count($a)==count($b)){foreach($a as $v){$w = array_shift($b);if(cmp($v,$w))return true;}return false;}return strcmp($a,$b);}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
foreach($data as $v=>$e)
{
    $x=explode(',',$v);
    test($x,$e,t($x));
}
Titus
la source
427? Vous êtes sur!
Jordanie
@Jordan: et ces 427 comprennent les <?frais généraux :)
Titus