Kemungkinan urutan Tetris

11

Tulis kode untuk mengetahui apakah serangkaian potongan Tetris dapat dihasilkan oleh algoritma Tetris resmi. Bytes paling sedikit menang.

Game Tetris resmi menghasilkan urutan potongan yang jatuh dengan cara khusus. Tujuh potongan IJLOSTZdijatuhkan secara acak, lalu permutasi acak lainnya dijatuhkan, dan seterusnya.

JTLOISZ STJOLIZ LISJOTZ ...

Contoh ini berisi potongan yang berdekatan

SZSTJOLIZLIS

Perhatikan bahwa itu melintasi batas-batas kelompok 7. Tapi, potongan-potongan

SZOTLZSOJSIT

tidak bisa menjadi substring dari urutan Tetris apa pun, sehingga tidak pernah bisa dilihat dalam game Tetris resmi.

Input: String huruf yang tidak kosong IJLOSTZ.

Output: Nilai Truthy atau Falsey untuk apakah input adalah substring dari urutan yang dapat dihasilkan oleh Tetris Random Generator resmi, yaitu gabungan dari permutasi dari tujuh huruf.

Kasus uji:

Benar: 

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)

Salah:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Papan peringkat

Atas perkenan Martin Büttner .

Tampilkan cuplikan kode

code-golf string game permutations tetris Tidak
sumber

Jawaban:

6

Pyth, 16 15 byte

sm*F.{Mc+>Gdz7T

Mencetak 0 untuk false, bilangan bulat positif untuk true.

orlp
sumber
6

CJam, 23 20 16 byte

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

Kredit ke Sp3000 untuk mencukur 4 byte!

Ini mencetak banyak angka sebagai nilai kebenaran atau tidak sama sekali sebagai nilai palsu (sebelum mencetak ini sebenarnya adalah daftar kosong atau kosong, yang memang benar dan salah dalam CJam).

Uji di sini.

Penjelasan

Ini hanya memeriksa semua 7 partisi yang mungkin dari input ke dalam 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
sumber
4

Retina , 61 55 byte

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

Karena ini hanya satu regex, Retina akan berjalan dalam mode Match dan melaporkan jumlah pertandingan yang ditemukan, yang akan 1untuk urutan yang valid dan 0sebaliknya. Ini tidak kompetitif dibandingkan dengan bahasa golf, tapi saya cukup senang dengan itu, melihat saya mulai dengan monster sebesar 260 byte.

Penjelasan

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

Bit ini menggunakan awalan huruf unik dengan panjang variabel, yaitu cocok dengan potongan terkemuka yang berpotensi tidak lengkap. Lookbehind memastikan bahwa karakter apa pun yang cocok dengan bit ini belum muncul di string sebelumnya.

Sekarang untuk sisa input, kami ingin mencocokkan potongan 7 tanpa mengulangi karakter. Kami dapat mencocokkan potongan seperti ini:

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

Yaitu kami mencocokkan karakter yang tidak muncul untuk 6 karakter lainnya, kemudian yang tidak muncul untuk 5 karakter lainnya dan seterusnya. Tetapi ini membutuhkan pengulangan kode yang cukup mengerikan, dan kami harus mencocokkan potongan trailing (berpotensi tidak lengkap) secara terpisah.

Menyeimbangkan kelompok untuk menyelamatkan! Cara yang berbeda untuk mencocokkan

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

adalah untuk mendorong 5 pertandingan kosong ke tumpukan tangkapan dan mencoba mengosongkannya:

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

The *memungkinkan minimal nol pengulangan, seperti {0,5}, dan karena kami telah mendorong lima menangkap, itu tidak akan dapat pop lebih dari 5 kali baik. Ini lebih lama untuk satu contoh pola ini, tetapi ini jauh lebih dapat digunakan kembali. Karena kita melakukan popping di lookahead negatif , ini tidak mempengaruhi stack yang sebenarnya setelah lookahead selesai. Jadi setelah lookahead, kami masih punya 5 elemen di stack, tidak peduli apa yang terjadi di dalam. Lebih jauh lagi, kita dapat dengan mudah mengeluarkan satu elemen dari stack sebelum setiap lookahead, dan menjalankan kode dalam satu lingkaran, untuk secara otomatis mengurangi lebar lookahead dari 5 ke 0. Jadi sedikit sangat lama di sana sebenarnya dapat disingkat menjadi

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

(Anda mungkin melihat dua perbedaan: kami mendorong 7 bukannya 5. Satu tangkapan tambahan adalah karena kami meletus sebelum setiap iterasi, bukan setelahnya. Yang lain sebenarnya diperlukan agar kami dapat meloncat dari tumpukan 7 kali (karena kami ingin loop untuk menjalankan 7 kali), kita dapat memperbaikinya dengan kesalahan satu-per-satu di dalam lookahead dengan memastikan \1bahwa masih ada setidaknya satu elemen yang tersisa di stack.)

Keindahan dari ini adalah ia juga bisa cocok dengan potongan trailing tidak lengkap, karena kami tidak pernah meminta untuk mengulangi 7 kali (itu hanya maksimum yang diperlukan, karena kami tidak bisa pop dari tumpukan lebih sering dari itu). Jadi yang perlu kita lakukan adalah membungkus ini dalam loop lain dan memastikan kita telah mencapai akhir dari string

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