Possíveis seqüências de Tetris

11

Escreva um código para descobrir se uma execução de peças do Tetris pode ser gerada pelo algoritmo oficial do Tetris. Menos bytes ganha.

Os jogos oficiais do Tetris geram a sequência de peças que caem de uma maneira especial. As sete peças IJLOSTZsão descartadas em uma ordem aleatória, depois outra permutação aleatória é descartada, e assim por diante.

JTLOISZ STJOLIZ LISJOTZ ...

Este exemplo contém a sequência de peças contígua

SZSTJOLIZLIS

Observe que ele atravessa os limites de um grupo de 7. Mas, a corrida de pedaços

SZOTLZSOJSIT

não pode ser uma substring de nenhuma sequência do Tetris, portanto nunca pode ser vista em um jogo oficial do Tetris.

Entrada: uma sequência de letras não vazia IJLOSTZ.

Saída: Um valor Truthy ou Falsey para se a entrada é uma subcadeia de uma sequência que pode ser gerada pelo gerador aleatório oficial do Tetris, ou seja, de uma concatenação de permutações das sete letras.

Casos de teste:

Verdade: 

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

Entre os melhores

Cortesia de Martin Büttner .

Mostrar snippet de código

code-golf string game permutations tetris xnor
fonte

Respostas:

6

Pitão, 16 15 bytes

sm*F.{Mc+>Gdz7T

Imprime 0 para falso, um número inteiro positivo para verdadeiro.

orlp
fonte
6

CJam, 23 20 16 bytes

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

Créditos ao Sp3000 por reduzir 4 bytes!

Ele imprime um monte de dígitos como um valor verdadeiro ou nada como um valor falso (antes de imprimir, esses são realmente uma lista não-vazia ou vazia, que são realmente verdadeiros e falsos no CJam).

Teste aqui.

Explicação

Isso apenas verifica todas as 7 partições possíveis da entrada em pedaços.

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

Retina , 61 55 bytes

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

Como esse é apenas um único regex, o Retina será executado no modo de Correspondência e relatará o número de correspondências encontradas, que serão 1para seqüências válidas e 0outras. Isso não é competitivo em comparação com os idiomas do golfe, mas estou muito feliz com isso, pois comecei com um monstro de 260 bytes.

Explicação

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

Este bit consome um prefixo de letras únicas de comprimento variável, ou seja, corresponde ao pedaço inicial potencialmente incompleto. O lookbehind garante que qualquer caractere correspondente a esse bit não tenha aparecido antes na string.

Agora, para o restante da entrada, queremos combinar partes de 7 sem repetir caracteres. Poderíamos igualar um pedaço assim:

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

Ou seja, combinamos um caractere que não aparece para outros 6 caracteres, depois um que não aparece para outros 5 caracteres e assim por diante. Mas isso requer uma repetição de código bastante horrível, e teríamos que combinar um pedaço (potencialmente incompleto) à parte separadamente.

Grupos de equilíbrio para o resgate! Uma maneira diferente de combinar

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

é colocar 5 correspondências vazias em uma pilha de captura e tentar esvaziá-la:

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

Ele *permite um mínimo de zero repetições, assim como {0,5}, e como fizemos cinco capturas, também não será possível exibir mais de 5 vezes. Isso é mais longo para uma única instância desse padrão, mas é muito mais reutilizável. Como estamos fazendo o popping em um lookahead negativo , isso não afeta a pilha real depois que o lookahead é concluído. Então, depois do lookahead, ainda temos 5 elementos na pilha, não importa o que aconteceu lá dentro. Além disso, podemos simplesmente exibir um elemento da pilha antes de cada lookahead e executar o código em um loop, para diminuir automaticamente a largura do lookahead de 5 para 0. Portanto, esse pedaço muito longo pode ser reduzido para

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

(Você pode notar duas diferenças: estamos pressionando 7 em vez de 5. Uma captura adicional é porque pop antes de cada iteração, não depois dela. A outra é realmente necessária para que possamos sair da pilha 7 vezes (já que queremos o loop é executado 7 vezes), podemos corrigir o erro de um por um dentro da cabeça de impressão, garantindo \1que ainda exista pelo menos um elemento na pilha.)

A vantagem disso é que ele também pode corresponder ao pedaço incompleto à direita, porque nunca precisamos repetir 7 vezes (isso é apenas o máximo necessário, porque não podemos sair da pilha com mais frequência do que isso). Então, tudo o que precisamos fazer é agrupar isso em outro loop e garantir que chegamos ao final da string para obter

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