Dada una lista de movimientos de Tetris, devuelve el número de líneas completadas

37

Descripción

Consideramos una versión ligeramente simplificada de Tetris donde cada movimiento consiste en:

  • girando la pieza en sentido horario, 0 a 3 veces
  • posicionar la pieza en una columna dada
  • caída rápida

El objetivo es determinar el número de líneas completadas, dada una lista de tales movimientos de Tetris.

Las filas completas se eliminan a medida que se sueltan las piezas, siguiendo las reglas estándar de Tetris.

Campo de juego

El campo de juego tiene 10 columnas de ancho. No hay Game Over y se supone que siempre hay suficiente espacio y tiempo para realizar las acciones anteriores, sin importar la configuración del campo de juego. La altura del campo de juego realmente no importa aquí, pero puede usar las 22 filas estándar como límite superior.

Formas de tetrominoes

formas

De entrada y salida

Entrada

Una lista separada por comas de movimientos de Tetris codificados con 3 caracteres. Los dos primeros caracteres describen la forma de Tetromino que se utilizará y el último describe la posición donde se dejó caer.

  1. Tetromino: I, O, T, L, J, Zo S, en el mismo orden que anteriormente.
  2. Número de rotaciones en sentido horario: 0a3
  3. Columna: 0a 9. Esta es la columna en la que se encuentra la esquina superior izquierda de la pieza (marcada con un xen la imagen de arriba) después de la rotación 1

Se supone que todos los movimientos en la lista proporcionada son válidos. No es necesario verificar las entradas no válidas, como I07( Iforma horizontal colocada demasiado a la derecha).

1 Usted es libre de implementar un algoritmo de rotación real o de codificar todas las formas diferentes, siempre que xesté ubicado en la columna dada por el tercer carácter del movimiento.

Salida

Número de líneas completadas.

Ejemplo

ejemplo

O00,T24generará la primera posición y O00,T24,S02,T01,L00,Z03,O07,L06,I05generará la segunda posición.

Por lo tanto, la siguiente secuencia generará un Tetris y debería regresar 4:

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

Casos de prueba

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

Página de prueba

Puede usar este JSFiddle para probar una lista de movimientos.

Arnauld
fuente
1
¿Sobre qué eje giran las piezas?
1
@Arnauld Le sugiero que eche un vistazo al sistema de súper rotación y edite la imagen un poco. tetris.wikia.com/wiki/SRS
1
Entonces, ¿podemos tratar estos como 25 (15 si no cuenta duplicados) diferentes formas, entonces?
1
¿Pueden las soluciones tomar la entrada como una matriz en lugar de una cadena separada por comas?
Jordania
1
Esta es la mejor pregunta de PCG que he visto en mucho tiempo. ¡Que buena idea! Mejor en el sentido subjetivo de interesante y práctico y no demasiado grande pero tampoco demasiado pequeño.
GreenAsJade

Respuestas:

5

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

(con el mapeo de bloques 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;

programa, realiza movimientos como argumentos separados, imprime el resultado

desglose para funcionar:

toma movimientos como matriz, devuelve el resultado

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
}

para referencia: el viejo mapeo

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

pruebas

ver mi otra respuesta PHP

¿quiero ver?

elimine la #fuente de la función y agregue esto:

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

algunos pasos de golf

Rev. 5: Un salto grande (399- 21 = 378) fue simplemente moviendo el cambio de columna
de un circuito separado para los dos bucles existentes.

Rev. 8: Cambiar de la matriz a la base 16 para la pieza ($ s) no dio mucho,
pero dio paso a un poco más de golf.

Rev. 17: analizó los valores base64_encode(pack('V*',<values>))
y utilizó la indexación de bytes en lugar de unpackguardar 16 bytes

Rev. 25 a 29: inspirado en el código de Dave: nuevo hashing (-2), nuevo diseño de bucle (-9), goto (-10)
sin cambio previo; eso costaría 17 bytes.

más potencial

Con /2%9, podría guardar 15 bytes (solo 14 bytes con /4%5)
colocando datos binarios en un archivo by luego indexandofile(b)[0] .
¿Quiero eso?

Los caracteres UTF-8 costarían mucho para la transformación.

en el hash

Solía ZJLO.ST /2%9 -> 0123.56; Pero T.ZJLOS /3%7 -> 0.23456es tan bueno.
un byte más largo O.STJLZ %13/2 -> 0.23456
y tres más:OSTZJ.L %17%12%9 -> 01234.6

No pude encontrar un hash corto (máx. 5 bytes) que no deja espacio;
pero Dave encontróSTZJL /4%5 -> 01234 , dejando caer el O de la lista. wtg!

BTW: TIJSL.ZO (%12%8) -> 01234.67deja espacio para la Iforma
(y un ficticio A, Mo Yforma). %28%8y %84%8, haga lo mismo (pero con en Elugar de A).

Titus
fuente
Agradable; ¡Me gusta la detección combinada de pintura + línea, y break 2es mucho más limpia de lo que tenía que hacer en C! Es posible que pueda guardar algunos bytes usando array_diff(establezca las líneas completas en un valor fijo en lugar de usar y unsetluego reemplace array_valuescon array_diff), pero no puedo decir por los documentos si eso aplanaría los valores repetidos (por ejemplo, array_diff ([1,2, 2,3], [1]) -> [2,2,3] o simplemente [2,3])
Dave
@Dave: array_diffno elimina valores duplicados; y ya tengo el valor fijo (1023); pero no reindexa la matriz. Gran idea, pero costaría un byte.
Titus
wow eso fue un fuerte silbido cuando pasaste volando a mi lado! ¡Parece que tengo que ponerme al día!
Dave
¡Felicidades por llegar a 300! Implementaré su último cambio sugerido (no había pensado en simplificar la verificación de rotación ahora que no lo necesito por /10todas partes), pero de lo contrario creo que he terminado. Estoy sorprendido de lo directamente que resultaron ser PHP y C competitivos. Esto fue divertido, ¡espero que el OP acepte tu respuesta!
Dave
@Dave & Titus: desearía poder aceptar ambas respuestas. Ustedes hicieron un gran trabajo. De todos modos, felicidades a Titus por llegar a 300. Y creo que en realidad es 299 ya que tienes un espacio inútil después de a if.
Arnauld
16

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

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

Toma una entrada separada por comas en stdin, devuelve la puntuación en el estado de salida.

Requiere charestar firmado (que es el valor predeterminado para GCC) y '3Z3Z'debe interpretarse como 861549402 (que es el caso para GCC en máquinas little endian, al menos).


Ejemplo de uso:

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

Explicación de alto nivel:

Todas las formas, excepto la línea, pueden caber en una cuadrícula de 3x3 sin una esquina:

6 7 -
3 4 5
0 1 2

Eso significa que es fácil almacenarlos en un byte cada uno. Por ejemplo:

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

(alineamos cada pieza en la parte inferior izquierda de la caja para que sea más fácil soltarla)

Como obtenemos al menos 4 bytes por int, esto significa que podemos almacenar las 4 rotaciones de cada pieza en un solo entero, con un caso especial para la línea. También podemos ajustar cada fila de la cuadrícula del juego en un int (solo necesita 10 bits), y la pieza que cae actualmente en un largo (4 líneas = 40 bits).


Descompostura:

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 gracias a @Titus, y -23, -11 con inspiración de su respuesta

Dave
fuente
¡Buena esa! ¿Podrías hacerlo s+=(d[A-x]=d[A])sin usar x?
Arnauld
Lamentablemente, xes necesario realizar un seguimiento de cuántas filas colapsar en el paso actual (cada fila Ase establece en el valor de la fila a A-xmedida que avanza el bucle)
Dave
D'oh! Mi error. Perdón por una sugerencia tan tonta. :)
Arnauld
1
@Titus es un abuso de la indexación de matriz de C. En pocas palabras, 1[a]y a[1]hacer lo mismo (o más precisamente, se a[b]traduce en *(a+b)). Se abusa de esta manera como una forma de evitar los corchetes. En este caso, 1[*v]== (*v)[1], es decir, la segunda letra del comando, es decir, la rotación.
Dave
1
¿Puedes deshacerte del Imarcador de posición? Si es así, intente /2%9como hash en lugar de %12. %12%8si no.
Titus
2

Ruby, 474 443 428 379 + 48 = 427 bytes

-1 gracias a @Titus

Esto definitivamente se puede jugar más al golf.

Lee un diccionario binario de piezas (ver más abajo) de STDIN o un nombre de archivo y toma una lista de movimientos como argumento, por ejemplo $ 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

Datos de piezas binarias (formato 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.\

Véalo en repl.it (con argumentos codificados, diccionario): https://repl.it/Cqft/2

Sin golfos y explicación

# 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
Jordán
fuente
1 byte: m >> 10podría serm >> x
Tito
@Titus Buen ojo. ¡Gracias!
Jordania
No es necesario requerir explícitamente \ds en la expresión regular: /(\w)(\d)(\d)//(\w)(.)(.)/
manatwork
2

PHP, 454 435 427 420 414 bytes

campos de bits para piezas y mapa; pero no hay un caso especial para la Iforma como el 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;

toma argumentos de la línea de comando, imprime el resultado

no golfed como función

toma argumentos como matriz, devuelve el resultado

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

pruebas (en función)

$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
fuente
427? ¡Estás en!
Jordania
@Jordan: y esos 427 incluyen los <?gastos generales :)
Titus