Séquences de Tetris possibles

11

Écrivez du code pour déterminer si une série de pièces Tetris pourrait être générée par l'algorithme officiel de Tetris. Le moins d'octets gagne.


Les jeux officiels de Tetris génèrent la séquence de pièces qui tombent d'une manière spéciale. Les sept morceaux IJLOSTZsont déposés dans un ordre aléatoire, puis une autre permutation aléatoire est supprimée, etc.

JTLOISZ STJOLIZ LISJOTZ ...

Cet exemple contient la suite de pièces contiguës

SZSTJOLIZLIS

Notez qu'il coupe à travers les limites d'un groupe de 7. Mais, la série de pièces

SZOTLZSOJSIT

ne peut pas être une sous-chaîne d'une séquence Tetris, donc elle ne peut jamais être vue dans un jeu Tetris officiel.


Entrée: une chaîne de lettres non vide IJLOSTZ.

Sortie: une valeur Truthy ou Falsey indiquant si l'entrée est une sous-chaîne d'une séquence qui peut être générée par le générateur aléatoire officiel Tetris, c'est-à-dire d'une concaténation de permutations des sept lettres.

Cas de test:

Vrai:

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)

Faux:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Classement

Avec l'aimable autorisation de Martin Büttner .

xnor
la source

Réponses:

6

Pyth, 16 15 octets

sm*F.{Mc+>Gdz7T

Imprime 0 pour faux, un entier positif pour vrai.

orlp
la source
6

CJam, 23 20 16 octets

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

Crédits à Sp3000 pour raser 4 octets!

Il imprime un tas de chiffres en tant que valeur véridique ou rien en tant que valeur falsifiée (avant d'imprimer, il s'agit en fait d'une liste non vide ou vide, qui est en effet véridique et fausse dans CJam).

Testez-le ici.

Explication

Cela vérifie simplement les 7 partitions possibles de l'entrée en morceaux.

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
la source
4

Rétine , 61 55 octets

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

Étant donné qu'il ne s'agit que d'une seule expression régulière, Retina s'exécutera en mode Match et signalera le nombre de correspondances trouvées, qui sera 1valable pour les séquences valides et 0autres. Ce n'est pas compétitif par rapport aux langues de golf, mais j'en suis assez content, vu que j'ai commencé avec un monstre de 260 octets.

Explication

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

Ce bit consomme un préfixe de lettres uniques de longueur variable, c'est-à-dire qu'il correspond au bloc de tête potentiellement incomplet. Le lookbehind garantit qu'aucun caractère correspondant à ce bit n'apparaît dans la chaîne auparavant.

Maintenant, pour le reste de l'entrée, nous voulons faire correspondre des morceaux de 7 sans répéter les caractères. Nous pourrions correspondre à un tel morceau comme ceci:

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

C'est-à-dire que nous faisons correspondre un caractère qui n'apparaît pas pour 6 autres caractères, puis un qui n'apparaît pas pour 5 autres caractères et ainsi de suite. Mais cela nécessite une répétition de code assez horrible, et nous devons faire correspondre séparément un fragment de fin (potentiellement incomplet).

Équilibrer les groupes à la rescousse! Une façon différente de faire correspondre

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

consiste à pousser 5 allumettes vides sur une pile de capture et essayez de la vider:

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

Le *permet un minimum de zéro répétitions, tout comme {0,5}, et comme nous avons poussé cinq captures, il ne pourra pas apparaître plus de 5 fois non plus. C'est plus long pour une seule instance de ce modèle, mais c'est beaucoup plus réutilisable. Étant donné que nous effectuons le saut dans une anticipation négative , cela n'affecte pas la pile réelle une fois la anticipation terminée. Donc, après l'anticipation, nous avons encore 5 éléments sur la pile, peu importe ce qui s'est passé à l'intérieur. De plus, nous pouvons simplement extraire un élément de la pile avant chaque anticipation, et exécuter le code en boucle, pour décrémenter automatiquement la largeur de l'anticipation de 5 à 0. Donc, ce très long bit là-bas peut en fait être raccourci en

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

(Vous pouvez remarquer deux différences: nous poussons 7 au lieu de 5. Une capture supplémentaire est parce que nous sautons avant chaque itération, pas après. L'autre est en fait nécessaire pour que nous puissions sortir de la pile 7 fois (puisque nous voulons la boucle doit être exécutée 7 fois), nous pouvons corriger cette erreur de coup par coup à l'intérieur de l'anticipation en s'assurant \1qu'il reste encore au moins un élément sur la pile.)

La beauté de cela est qu'il peut également correspondre au morceau incomplet de fin, car nous ne l'avons jamais exigé pour répéter 7 fois (c'est juste le maximum nécessaire, car nous ne pouvons pas sortir de la pile plus souvent que cela). Donc, tout ce que nous devons faire est de l'enrouler dans une autre boucle et de nous assurer que nous avons atteint la fin de la chaîne pour obtenir

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