Возможные последовательности тетриса

11

Напишите код, чтобы выяснить, можно ли сгенерировать серию фигур Tetris с помощью официального алгоритма Tetris. Побеждает несколько байтов.

Официальные игры тетрис генерируют последовательность падающих фигур особым образом. Семь пьес IJLOSTZотбрасываются в случайном порядке, затем отбрасывается другая случайная перестановка и так далее.

JTLOISZ STJOLIZ LISJOTZ ...

Этот пример содержит непрерывный ряд частей

SZSTJOLIZLIS

Обратите внимание, что он пересекает границы группы из 7. Но, пробег частей

SZOTLZSOJSIT

не может быть подстрокой любой последовательности тетриса, поэтому ее нельзя увидеть в официальной игре тетрис.

Ввод: непустая строка букв IJLOSTZ.

Вывод: значение « Истина» или «Ложь» для того, является ли ввод подстрокой последовательности, которая может быть сгенерирована официальным генератором случайных чисел Тетриса, то есть для конкатенации перестановок из семи букв.

Тестовые случаи:

Правда: 

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)

Ложь:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Leaderboard

Предоставлено Мартином Бюттнером .

Показать фрагмент кода

code-golf string game permutations tetris XNOR
источник

Ответы:

6

Pyth, 16 15 байт

sm*F.{Mc+>Gdz7T

Выводит 0 для false, положительное целое для true.

orlp
источник
6

CJam, 23 20 16 байтов

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

Кредиты на Sp3000 для бритья 4 байта!

Он печатает группу цифр как истинное значение или ничего как ложное значение (перед печатью это фактически непустой или пустой список, который действительно верен и неверен в CJam).

Проверьте это здесь.

объяснение

Это просто проверяет все 7 возможных разделов ввода на куски.

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.
Мартин Эндер
источник
4

Retina , 61 55 байт

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

Поскольку это всего лишь одно регулярное выражение, Retina будет работать в режиме Match и сообщать о количестве найденных совпадений, что будет 1для правильных последовательностей и в 0противном случае. Это неконкурентоспособно по сравнению с языками игры в гольф, но я вполне доволен этим, так как начал с монстра в 260 байт.

объяснение

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

Этот бит использует префикс уникальных букв переменной длины, то есть соответствует потенциально неполному начальному фрагменту. Заглядывание гарантирует, что любой символ, соответствующий этому биту, ранее не появлялся в строке.

Теперь для остальной части ввода мы хотим сопоставить куски 7 без повторяющихся символов. Мы могли бы сопоставить такой кусок как это:

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

Т.е. мы сопоставляем символ, который не отображается для других 6 символов, затем символ, который не отображается для других 5 символов и так далее. Но это требует довольно ужасного повторения кода, и нам придется сопоставлять конечный (потенциально неполный) фрагмент отдельно.

Балансировка групп на помощь! Другой способ соответствовать

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

это вставить 5 пустых совпадений в стек захвата и попытаться очистить его:

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

*Позволяет как минимум ноль повторений, точно так же как {0,5}, и потому , что мы толкнул пять захватов, он не сможет выскочить более чем в 5 раз либо. Это дольше для одного экземпляра этого шаблона, но это гораздо более многократного использования. Поскольку мы выполняем всплывающее окно в отрицательном прогнозе, это не влияет на реальный стек после завершения просмотра. Итак, после просмотра у нас все еще есть 5 элементов в стеке, независимо от того, что произошло внутри. Кроме того, мы можем просто вытолкнуть один элемент из стека перед каждым заголовком и запустить код в цикле, чтобы автоматически уменьшить ширину заголовка с 5 до 0. Таким образом, этот действительно длинный бит на самом деле может быть сокращен до

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

(Вы можете заметить два отличия: мы нажимаем 7 вместо 5. Один дополнительный захват - это то, что мы выталкиваем перед каждой итерацией, а не после нее. Другой фактически необходим, чтобы мы могли выскочить из стека 7 раз (так как мы хотим цикл, который будет выполняться 7 раз), мы можем исправить эту ошибку в предпросмотре, убедившись, \1что в стеке остался хотя бы один элемент.)

Прелесть этого в том, что он также может соответствовать завершающему неполному фрагменту, потому что мы никогда не требовали, чтобы он повторялся 7 раз (это просто необходимый максимум, потому что мы не можем чаще выталкивать из стека). Так что все, что нам нужно сделать, это обернуть это в другой цикл и убедиться, что мы достигли конца строки, чтобы получить

^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$
Мартин Эндер
источник