Możliwe sekwencje Tetris

11

Napisz kod, aby dowiedzieć się, czy oficjalny algorytm Tetris może wygenerować szereg elementów Tetris. Wygrywa najmniej bajtów.


Oficjalne gry Tetris w specjalny sposób generują sekwencje spadających elementów. Siedem elementów IJLOSTZupuszcza się w losowej kolejności, następnie upuszcza kolejną losową permutację i tak dalej.

JTLOISZ STJOLIZ LISJOTZ ...

Ten przykład zawiera ciągły ciąg elementów

SZSTJOLIZLIS

Zauważ, że przecina granice grupy 7. Ale bieg kawałków

SZOTLZSOJSIT

nie może być podciągiem żadnej sekwencji Tetris, więc nigdy nie można go zobaczyć w oficjalnej grze Tetris.


Dane wejściowe: niepusty ciąg liter IJLOSTZ.

Wyjście: Truthy lub Falsey wart, czy wejście jest podciąg sekwencji, które mogą być generowane przez urzędowego Tetris generator liczb losowych, tj konkatenacją permutacji siedmiu liter.

Przypadki testowe:

Prawdziwe:

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)

Fałszywe:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Tabela liderów

Dzięki uprzejmości Martina Büttnera .

xnor
źródło

Odpowiedzi:

6

Pyth, 16 15 bajtów

sm*F.{Mc+>Gdz7T

Wyświetla 0 dla false, dodatnia liczba całkowita dla true.

orlp
źródło
6

CJam, 23 20 16 bajtów

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

Kredyty dla Sp3000 za golenie 4 bajtów!

Drukuje wiązkę cyfr jako prawdziwą wartość lub nic jako wartość fałszowania (przed wydrukowaniem są one w rzeczywistości niepustą lub pustą listą, które w rzeczywistości są prawdziwe i fałszywe w CJam).

Sprawdź to tutaj.

Wyjaśnienie

To po prostu sprawdza wszystkie 7 możliwych partycji wejścia na części.

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
źródło
4

Siatkówka , 61 55 bajtów

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

Ponieważ jest to tylko jedno wyrażenie regularne, Retina uruchomi się w trybie dopasowania i zgłosi liczbę znalezionych dopasowań, które będą dotyczyć 1prawidłowych sekwencji i 0nie tylko. Nie jest to konkurencyjne w porównaniu z językami golfowymi, ale jestem z tego całkiem zadowolony, ponieważ zacząłem od potwora 260 bajtów.

Wyjaśnienie

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

Ten bit zużywa prefiks unikalnych liter o zmiennej długości, tzn. Pasuje do potencjalnie niekompletnej wiodącej porcji. Lookbehind zapewnia, że ​​żaden znak pasujący do tego bitu nie pojawił się wcześniej w ciągu.

Teraz dla reszty danych wejściowych chcemy dopasować fragmenty po 7 bez powtarzania znaków. Możemy dopasować taki fragment:

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

Oznacza to, że dopasowujemy znak, który nie pojawia się dla kolejnych 6 znaków, a następnie taki, który nie pojawia się dla kolejnych 5 znaków i tak dalej. Ale wymaga to dość okropnego powtarzania kodu i musielibyśmy osobno dopasować końcową (potencjalnie niekompletną) część.

Równoważenie grup na ratunek! Inny sposób dopasowania

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

polega na wypchnięciu 5 pustych zapałek na stos przechwytywania i spróbuj go opróżnić:

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

*Pozwala minimum zero powtórzeń, jak {0,5}i dlatego, że mamy pięć przechwytuje popchnął, nie będą mogli pop więcej niż 5 razy albo. Jest to dłuższe w przypadku pojedynczego wystąpienia tego wzorca, ale jest to o wiele bardziej użyteczne. Ponieważ wyskakujemy z ujemnym wyprzedzeniem, nie ma to wpływu na rzeczywisty stos po zakończeniu przeglądu. Tak więc po lookahead wciąż mamy 5 elementów na stosie, bez względu na to, co się wydarzyło w środku. Ponadto możemy po prostu usunąć jeden element ze stosu przed każdym wyprzedzeniem i uruchomić kod w pętli, aby automatycznie zmniejszyć szerokość wyprzedzenia od 5 do 0. Tak więc naprawdę długi fragment można skrócić do

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

(Możesz zauważyć dwie różnice: wypychamy 7 zamiast 5. Jedno dodatkowe przechwytywanie polega na tym, że strzelamy przed każdą iteracją, a nie po niej. Druga jest w rzeczywistości konieczna, abyśmy mogli wyskoczyć ze stosu 7 razy (ponieważ chcemy pętla, która ma zostać uruchomiona 7 razy), możemy naprawić ten błąd jeden po drugim w ramach lookahead, upewniając się, \1że na stosie pozostał co najmniej jeden element.)

Piękno tego polega na tym, że może on również pasować do końcowego niekompletnego fragmentu, ponieważ nigdy nie wymagaliśmy powtarzania go 7 razy (to tylko niezbędne maksimum, ponieważ nie możemy wyskakiwać ze stosu częściej). Więc wszystko, co musimy zrobić, to owinąć to w kolejną pętlę i upewnić się, że doszliśmy do końca łańcucha, aby uzyskać

^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$
Martin Ender
źródło