Posibles secuencias de Tetris

11

Escriba código para determinar si el algoritmo oficial de Tetris podría generar una serie de piezas de Tetris. Pocos bytes ganan.


Los juegos oficiales de Tetris generan la secuencia de piezas que caen de una manera especial. Las siete piezas se IJLOSTZdejan caer en un orden aleatorio, luego se deja caer otra permutación aleatoria, y así sucesivamente.

JTLOISZ STJOLIZ LISJOTZ ...

Este ejemplo contiene la serie contigua de piezas.

SZSTJOLIZLIS

Tenga en cuenta que atraviesa los límites de un grupo de 7. Pero, la serie de piezas

SZOTLZSOJSIT

no puede ser una subcadena de ninguna secuencia de Tetris, por lo que nunca se puede ver en un juego oficial de Tetris.


Entrada: una cadena de letras no vacía IJLOSTZ.

Salida: Un valor de Verdad o Falsey para determinar si la entrada es una subcadena de una secuencia que puede generar el generador aleatorio oficial de Tetris, es decir, una concatenación de permutaciones de las siete letras.

Casos de prueba:

Cierto:

T
JJ                        (unique breakdown: J J)
JTJ                     (possible breakdown: JT J)
LTOZIJS
SZSTJOLIZLIS            (possible breakdown: SZ STJOLIZ LIS)
JTLOISZSTJOLIZLISJOTZ   (possible breakdown: JTLOISZ STJOLIZ LISJOTZ)  
LIJZTSLIJZTS              (unique breakdown: LIJZTS LIJZTS)

Falso:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Tabla de clasificación

Cortesía de Martin Büttner .

xnor
fuente

Respuestas:

6

Pyth, 16 15 bytes

sm*F.{Mc+>Gdz7T

Imprime 0 para falso, un entero positivo para verdadero.

orlp
fuente
6

CJam, 23 20 16 bytes

q7{\+_7/_Lf|=},&

¡Créditos a Sp3000 para reducir 4 bytes!

Imprime un montón de dígitos como un valor verdadero o nada como un valor falso (antes de imprimir, estos son en realidad una lista no vacía o vacía, que de hecho son verdaderos y falsos en CJam).

Pruébalo aquí.

Explicación

Esto solo verifica las 7 particiones posibles de la entrada en fragmentos.

q      e# Read the input
7{     e# Select the numbers from 0 to 6 for which the following block is true.
  \+   e#   Prepend the number to the input. This shifts the string by one cell
       e#   without adding non-unique elements.
  _7/  e#   Make a copy and split into chunks of 7.
  _Lf| e#   Remove duplicates from each chunk.
  =    e#   Check if the last operation was a no-op, i.e. that there were no duplicates.
},
&      e# The stack now contains the input with [6 5 ... 1 0] prepended as well as a list
       e# of all possible splittings. We want to get rid of the former. To do this in one
       e# byte we take the set intersection of the two: since we've prepended all the
       e# integers to the list, this will always yield the list of splittings.
Martin Ender
fuente
4

Retina , 61 55 bytes

^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$

Dado que esta es solo una expresión regular, Retina se ejecutará en modo Match e informará el número de coincidencias que encontró, que será 1para secuencias válidas y de 0otro modo. Esto no es competitivo en comparación con los idiomas de golf, pero estoy bastante contento con eso, ya que comencé con un monstruo de 260 bytes.

Explicación

^((.)(?<!\2.+))*

Este bit consume un prefijo de letras únicas de longitud variable, es decir, coincide con el fragmento inicial potencialmente incompleto. El aspecto posterior asegura que cualquier carácter que coincida en este bit no haya aparecido en la cadena antes.

Ahora, para el resto de la entrada, queremos unir fragmentos de 7 sin repetir caracteres. Podríamos igualar un trozo como este:

(.)(?!.{0,5}\1)(.)(?!.{0,4}\2)(.)(?!.{0,3}\3)...(.)(?!.?\5).

Es decir, hacemos coincidir un personaje que no aparece para otros 6 caracteres, luego uno que no aparece para otros 5 caracteres y así sucesivamente. Pero esto requiere una repetición de código bastante horrible, y tendríamos que hacer coincidir un fragmento final (potencialmente incompleto) por separado.

Equilibrio de grupos al rescate! Una forma diferente de combinar

(.)(?!.{0,5}\1)

es empujar 5 partidos vacíos en una pila de captura e intentar vaciarla:

(){5}(.)(?!(?<-1>.)*\2)

El *permite un mínimo de cero repeticiones, al igual que {0,5}, y porque nos hemos llevado cinco capturas, no será capaz de hacer estallar más de 5 veces tampoco. Esto es más largo para una sola instancia de este patrón, pero es mucho más reutilizable. Dado que estamos haciendo estallar en una búsqueda anticipada negativa , esto no afecta la pila real una vez que la búsqueda anticipada se ha completado. Entonces, después de la búsqueda anticipada, todavía tenemos 5 elementos en la pila, sin importar lo que sucedió dentro. Además, simplemente podemos extraer un elemento de la pila antes de cada búsqueda anticipada, y ejecutar el código en un bucle, para disminuir automáticamente el ancho de búsqueda anticipada de 5 a 0. De modo que ese bit realmente largo puede acortarse a

(){7}((?<-1>)(.)(?!(?<-1>.)*\1\3))*

(Puede notar dos diferencias: estamos presionando 7 en lugar de 5. Una captura adicional es porque hacemos estallar antes de cada iteración, no después de ella. La otra es realmente necesaria para que podamos hacer estallar desde la pila 7 veces (ya que queremos para que el ciclo se ejecute 7 veces), podemos corregir ese error fuera de uno dentro de la búsqueda anticipada asegurándonos de \1que todavía queda al menos un elemento en la pila).

La belleza de esto es que también puede coincidir con el fragmento incompleto final, porque nunca lo exigimos que se repita 7 veces (ese es el máximo necesario, porque no podemos saltar de la pila con más frecuencia que eso). Entonces, todo lo que tenemos que hacer es envolver esto en otro bucle y asegurarnos de que hemos llegado al final de la cadena para obtener

^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$
Martin Ender
fuente