Mögliche Tetris-Sequenzen

11

Schreiben Sie Code, um herauszufinden, ob mit dem offiziellen Tetris-Algorithmus eine Reihe von Tetris-Teilen generiert werden kann. Wenig Bytes gewinnen.

Offizielle Tetris-Spiele erzeugen auf besondere Weise die Folge fallender Teile. Die sieben Teile IJLOSTZwerden in zufälliger Reihenfolge abgelegt, dann wird eine weitere zufällige Permutation abgelegt und so weiter.

JTLOISZ STJOLIZ LISJOTZ ...

Dieses Beispiel enthält die zusammenhängende Stückfolge

SZSTJOLIZLIS

Beachten Sie, dass es die Grenzen einer Gruppe von 7 überschreitet. Aber die Reihe der Teile

SZOTLZSOJSIT

kann keine Teilzeichenfolge einer Tetris-Sequenz sein, daher kann sie in einem offiziellen Tetris-Spiel niemals gesehen werden.

Eingabe: Eine nicht leere Buchstabenfolge IJLOSTZ.

Ausgabe: Ein Truthy- oder Falsey- Wert dafür, ob die Eingabe eine Teilzeichenfolge einer Sequenz ist, die vom offiziellen Tetris-Zufallsgenerator generiert werden kann, dh einer Verkettung von Permutationen der sieben Buchstaben.

Testfälle:

Wahr: 

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)

Falsch:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Bestenliste

Mit freundlicher Genehmigung von Martin Büttner .

Code-Snippet anzeigen

code-golf string game permutations tetris xnor
quelle

Antworten:

6

Pyth, 16 15 Bytes

sm*F.{Mc+>Gdz7T

Gibt 0 für false aus, eine positive Ganzzahl für true.

orlp
quelle
6

CJam, 23 20 16 Bytes

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

Dank an Sp3000 für das Rasieren von 4 Bytes!

Es werden eine Reihe von Ziffern als wahrer Wert oder nichts als falscher Wert gedruckt (vor dem Drucken handelt es sich tatsächlich um eine nicht leere oder leere Liste, die in CJam tatsächlich wahr und falsch ist).

Testen Sie es hier.

Erläuterung

Dies überprüft nur alle 7 möglichen Partitionen der Eingabe in Chunks.

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
quelle
4

Netzhaut , 61 55 Bytes

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

Da dies nur eine einzelne Regex ist, wird Retina im Match-Modus ausgeführt und gibt die Anzahl der gefundenen Matches an, die 1für gültige Sequenzen und 0andere gelten. Dies ist im Vergleich zu den Golfsprachen nicht wettbewerbsfähig, aber ich bin ziemlich zufrieden damit, da ich mit einem Monster von 260 Bytes angefangen habe.

Erläuterung

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

Dieses Bit verwendet ein Präfix aus eindeutigen Buchstaben variabler Länge, dh es entspricht dem möglicherweise unvollständigen führenden Block. Das Lookbehind stellt sicher, dass kein in diesem Bit übereinstimmendes Zeichen zuvor in der Zeichenfolge angezeigt wurde.

Für den Rest der Eingabe möchten wir nun 7er-Blöcke abgleichen, ohne die Zeichen zu wiederholen. Wir könnten so ein Stück zusammenbringen:

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

Das heißt, wir stimmen mit einem Zeichen überein, das für weitere 6 Zeichen nicht angezeigt wird, dann mit einem Zeichen, das für weitere 5 Zeichen nicht angezeigt wird, und so weiter. Dies erfordert jedoch eine ziemlich schreckliche Code-Wiederholung, und wir müssten einen nachfolgenden (möglicherweise unvollständigen) Block separat abgleichen.

Ausgleichsgruppen zur Rettung! Eine andere Art zu passen

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

Schieben Sie 5 leere Streichhölzer auf einen Erfassungsstapel und versuchen Sie, ihn zu leeren:

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

Das *erlaubt ein Minimum von null Wiederholungen, genau wie {0,5}, und da wir fünf Captures verschoben haben, kann es auch nicht mehr als fünf Mal platzen. Dies ist für eine einzelne Instanz dieses Musters länger, aber viel wiederverwendbarer. Da wir das Knallen in einem negativen Lookahead durchführen, wirkt sich dies nicht auf den tatsächlichen Stapel aus, sobald der Lookahead abgeschlossen ist. Nach dem Lookahead haben wir also noch 5 Elemente auf dem Stapel, egal was im Inneren passiert ist. Darüber hinaus können wir einfach vor jedem Lookahead ein Element aus dem Stapel entfernen und den Code in einer Schleife ausführen, um die Lookahead-Breite automatisch von 5 auf 0 zu verringern

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

(Möglicherweise stellen Sie zwei Unterschiede fest: Wir drücken 7 statt 5. Eine zusätzliche Erfassung besteht darin, dass wir vor jeder Iteration und nicht danach platzen. Die andere ist tatsächlich erforderlich, damit wir sieben Mal vom Stapel springen können (da wir wollen) Wenn die Schleife siebenmal ausgeführt werden soll, können wir diesen Fehler im Lookahead beheben, indem wir sicherstellen, \1dass noch mindestens ein Element auf dem Stapel vorhanden ist.)

Das Schöne daran ist, dass es auch mit dem nachfolgenden unvollständigen Block übereinstimmen kann, da wir ihn nie siebenmal wiederholen mussten (das ist nur das notwendige Maximum, da wir nicht öfter vom Stapel springen können). Alles, was wir tun müssen, ist, dies in eine andere Schleife zu packen und sicherzustellen, dass wir das Ende der Zeichenfolge erreicht haben, um sie zu erhalten

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