Tetromino yang mana ini?

54

Diberikan bilangan bulat 16-bit unsigned N , tugas Anda adalah menentukan apakah representasi binernya yang dipetakan di dalam matriks 4x4 cocok dengan bentuk tetromino , dan jika demikian, bentuk apa itu.

Matriks

Setiap bit N dipetakan di dalam matriks 4x4, dari kiri ke kanan dan dari atas ke bawah, dimulai dengan yang paling signifikan.

Contoh :

N = 17600
binary representation: 0100010011000000
matrix: [ [ 0, 1, 0, 0 ],
          [ 0, 1, 0, 0 ],
          [ 1, 1, 0, 0 ],
          [ 0, 0, 0, 0 ] ]

Bentuk tetromino

Bentuk dasar

Ada 7 bentuk tetromino, yang diidentifikasi oleh huruf O , I , S , Z , L , J dan T :

tetromino

Rotasi dan terjemahan

Jika bentuk diterjemahkan dan / atau diputar dalam matriks 4x4, itu masih dianggap sebagai variasi yang valid dari tetromino yang sama. Misalnya, 17600, 1136, 2272 dan 1604 semuanya harus diidentifikasi sebagai J tetromino:

contoh J yang valid

Jangan dibungkus!

Namun, bentuk tidak dapat membungkus atau digeser melampaui batas matriks apa pun. Misalnya, baik 568 maupun 688 tidak boleh diidentifikasi sebagai J tetromino (apalagi bentuk lain):

contoh J yang tidak valid

Klarifikasi dan aturan

  • Anda dapat mengambil input sebagai integer, atau langsung sebagai 16 digit biner dalam format yang masuk akal, seperti array 2D, array datar atau string yang dibatasi.
  • Input dijamin menjadi integer 16-bit yang tidak ditandatangani (atau representasi yang setara sebagai array atau string).
  • Ketika bentuk yang valid diidentifikasi, Anda harus mencetak atau mengembalikan surat yang mengidentifikasi bentuk, baik dalam huruf kecil atau huruf besar.
  • Jika tidak ada bentuk yang diidentifikasi, Anda harus mencetak atau mengembalikan nilai yang tidak cocok dengan huruf tetromino. Anda juga dapat memilih untuk tidak mengembalikan apa pun.
  • Agar dianggap valid, matriks harus mengandung bentuk tetromino yang tepat tanpa sel tambahan (lihat 1911 dan 34953 dalam kasus uji).
  • Ini , jadi jawaban tersingkat dalam byte menang!

Uji kasus

Anda dapat mengikuti tautan ini untuk mendapatkan test case sebagai array 2D.

0      -> false
50     -> false
51     -> 'O'
1911   -> false
15     -> 'I'
34952  -> 'I'
34953  -> false
1122   -> 'S'
3168   -> 'Z'
785    -> 'L'
1136   -> 'J'
568    -> false
688    -> false
35968  -> 'T'
19520  -> 'T'
Arnauld
sumber
Menariknya, saya sedang mengerjakan masalah yang sangat mirip beberapa hari yang lalu sebelum saya terganggu membuat teknik untuk menggunakan rantai fungsi func1 . func2 . func3di JS: P
ETHproduksi
Bisakah saya mengambil input saat keempat baris bergabung 0, yaitu 1111011110111101111untuk 65535?
ETHproduksi
@ ETHproductions Tampaknya baik-baik saja. Saya telah mengedit tantangan dengan format input yang sedikit santai.
Arnauld
3
I: 15,240,3840,4369,8738,17476,34952,61440J: 71,113,142,226,275,550,802,1100,1136,1604,1808,2272,3208,3616,4400,8800,12832,17600,18176,25664,28928,36352,51328,57856L: 23,46,116,232,368,547,736,785,1094,1570,1856,2188,3140,3712,5888,8752,11776,12560,17504,25120,29696,35008,50240,59392O: 51,102,204,816,1632,3264,13056,26112,52224S: 54,108,561,864,1122,1728,2244,8976,13824,17952,27648,35904T: 39,78,114,228,305,562,610,624,1124,1220,1248,1824,2248,3648,4880,8992,9760,9984,17984,19520,19968,29184,35968,58368Z:99,198,306,612,1224,1584,3168,4896,9792,19584,25344,50688
Engineer Toast
^ Dibuat menggunakan Lynn's Python 3 answer karena memiliki format input / output yang nyaman.
Engineer Toast

Jawaban:

6

Jelly ,  54 43 42  41 byte

-1 byte berkat Erik the Outgolfer (pindahkan transpos di dalam rantai berulang)

T€FṀ⁸ṙ€Zµ⁺F
ZU$3СǀḄṂ“çc3Ð6'G‘i’ị“¥Çıƭ⁵»

Tautan monadik yang mengambil array bilangan bulat 2D ( 1s dan 0s) dan mengembalikan huruf kecil oiszljtuntuk masing-masing tetromino atau wjika tidak valid.

Cobalah secara Online! atau lihat test suite .

Lihat juga program ini yang mencantumkan semua 1820 kemungkinan array biner 2D dengan tepat empat bit yang diset bersama dengan outputnya, diurutkan berdasarkan output tersebut.

Bagaimana?

Ini pertama kali mengambil keempat rotasi input. Kemudian ia menggeser set bit masing-masing sejauh ke kanan dan kemudian sejauh ke bawah sebanyak mungkin dan mengubah hasilnya ke angka biner. Kemudian mencari hasil minimum dalam daftar representasi minimal seperti itu dari setiap tetromino yang valid dan menggunakan hasil yang dikurangi untuk mengindeks ke dalam dua kata kamus gabungan zoist+ jowl, menghasilkan wketika tidak ditemukan kecocokan.

T€FṀ⁸ṙ€Zµ⁺F - Link 1, shift set bits right & then down : list of lists of bits          
        µ⁺  - perform the following twice, 1st with x=input, then with x=result of that):
T€          -   truthy indexes of €ach
  F         -   flatten into a single list
   Ṁ        -   maximum (the index of the right-most bit)
    ⁸       -   chain's left argument, x
     ṙ€     -   rotate €ach left by that amount
       Z    -   transpose the result
          F - flatten (avoids an € in the main link moving this into here)

ZU$3СǀḄṂ“çc3Ð6'G‘i’ị“¥Çıƭ⁵» - Main link: list of lists of bits (the integers 0 or 1)
   3С                        - repeat this 3 times collecting the 4 results:
  $                           -   last two links as a monad:
Z                             -     transpose
 U                            -     upend (reverse each) -- net effect rotate 90° CW
      Ç€                      - call the last link as a monad for €ach
        Ḅ                     - convert from binary (vectorises)
         Ṃ                    - minimum (of the four results)
          “çc3Ð6'G‘           - code-page indexes = [23,99,51,15,54,39,71]
                              -   ...the minimal such results for l,z,o,i,s,t,j shapes
                   i          - 1-based index of minimum in there or 0 if not found
                    ’         - decrement
                      “¥Çıƭ⁵» - compressed words: "zoist"+"jowl" = "zoistjowl"
                     ị        - index into (1 indexed & modular, so -1 yields 'w',
                              -             0 yields 'l', 1 yields 'z', ...)

Metode sebelumnya (54 byte)

Fœr0Ḅ“çc3Ðñ'G‘i
;Z$Ḅ©f“¦µ½¿Æ‘ȯ®¬S>2ȧZU$3СǀṀ’ị“¥Çıƭ⁵»

Tautan monadik yang mengambil array bilangan bulat 2D ( 1s dan 0s) dan mengembalikan huruf kecil oiszljtuntuk masing-masing tetromino atau wjika tidak valid.

Cobalah online!

Ini memeriksa setidaknya ada tiga baris kosong (baris + kolom) dan bahwa pola bit tertentu tidak ada di setiap baris (khususnya angka 5,9,10,11, dan 13), ini bersama-sama memastikan langkah berikutnya tidak akan menghasilkan salah-positif. Itu kemudian meratakan dan kemudian menggeser-geser angka biner (dengan menelusur angka nol sebelum konversi) dari masing-masing dari empat rotasi, dan mencari hasil minimal dalam daftar angka, menggunakan hasil yang dikurangi untuk mengindeks ke dalam dua kata kamus yang digabungkan. zoist+ jowl, menghasilkan wketika tidak ada kecocokan yang ditemukan.

Jonathan Allan
sumber
Dan saya tahu ada cara yang lebih baik daripada hardcoding ...
Erik the Outgolfer
btw saya pikir kode ini tergantung pada kebetulan (karena, yah, zoistjowlbiasanya tidak cocok untuk string sebaliknya: p)
Erik the Outgolfer
Apa maksudmu "tergantung pada suatu kebetulan"? (Pencarian kamus hanya menyimpan satu byte lebih dari ...Ṁị“LZOISTJWitu)
Jonathan Allan
Hmm ... ya saya tahu ini tidak akan bertahan lama ... tapi saya pikir Anda mencuri saya ZU$3С: p
Erik the Outgolfer
Saya mencoba melakukan metode yang sama kemarin setelah mengirimkan yang sebelumnya tetapi saya merasa sedikit lelah.
Jonathan Allan
28

Python 3 , 124 byte

def f(n):
 while n&4369<n/n:n>>=1
 while n&15<1:n>>=4
 return'TJLZSIO'["rēȣc63ıGtIJȱᄑ@'̢̑@@@@Ȳq".index(chr(n))%7]

Cobalah online!

Mengharapkan bilangan bulat n yang mewakili matriks biner 4 × 4. Melempar jika tidak ada tetromino yang ditemukan.

Baris 2 menggeser bentuk ke kanan sampai angka 1 berada di kolom paling kanan. (4369 0001 0001 0001 0001dalam biner.) Baris 3 menurunkan bentuk sampai 1 berada di baris bawah. Bersama-sama ini berubah misalnya:

    0 1 0 0        0 0 0 0
    1 1 1 0  into  0 0 0 0
    0 0 0 0        0 0 1 0
    0 0 0 0        0 1 1 1

Kemudian kami mencari indeks ndalam daftar ini:

 [114  275  547   99   54   15   51
  305   71  116  306  561 4369   64
   39  802  785   64   64   64   64
  562  113   23]
#   T    J    L    Z    S    I    O

Setiap kolom indeks setara modulo 7 sesuai dengan bentuk tetromino. 64 ( @) digunakan sebagai nilai padding karena ntidak dapat 64 pada saat ini dalam kode.

NB. Pengecualian diberikan untuk input 0dengan menghitung n/nalih-alih 1.

Lynn
sumber
Mengapa string biner Anda berfungsi? Saya punya masalah dengan itu di Python 3, lihat komentar codegolf.stackexchange.com/a/85201/53667
Karl Napf
Python menggunakan UTF-8 sebagai pengodean default untuk kode sumber dan untuk output teks. Tetapi file PPM tidak dibaca dalam UTF-8. Ketika Anda menjalankan print("ÿ"), byte yang ditulis adalah c3 bf 0a, tidak ff 0a, dan gambar PPM berubah menjadi sampah.
Lynn
8

APL (Dyalog) , 95 94 93 89 87 byte

-2 Terima kasih kepada Zacharý

Membutuhkan ⎕IO←0yang default pada banyak sistem. Membawa matriks Boolean (dalam bentuk apa pun!) Sebagai argumen. Tidak menghasilkan apa-apa jika jumlah bit yang diberikan bukan empat, dan garis kosong jika keempat bit yang diberikan tidak membentuk tetromino.

{4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K2J),(⍳3)⊖¨⊂J1,⍪K31)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}

Cobalah online!

Bekerja dengan membuat keempat rotasi input, lalu mencari setiap tetromino di setiap rotasi.

{... } fungsi anonim di mana argumen diwakili oleh :

,⍵ ravel (meratakan) argumen

+/ jumlahkan itu

4= Apakah empat sama dengan itu?

: jika demikian, maka (tidak ada yang kembali):

  ⍳4 empat penemuan pertama; [0,1,2,3]

  ⍵∘{...  terapkan fungsi berikut pada masing-masing, menggunakan input sebagai argumen kiri tetap

    argumen kiri yaitu input

   ⊢⍺ hasilkan itu (terpisah dari )

   ⌽∘⍉⍣⍵ mirror dan transpose (yaitu memutar 90 °) kali

  (... )∘.⍷ luar "produk", tetapi menggunakan Find *, dari daftar berikut dan rotasi:

   3↑1 ambil tiga elemen dari satu, padding dengan nol; [1,0,0]

   K← simpan itu sebagai K

    tabel (dibuat menjadi vektor kolom); [[1],[0],[0]]

   1, tambahkan satu; [[1,1],[1,0],[1,0]]("J")

   J← simpan sebagai J

   (... )⊖¨⊂ putar seluruh J secara vertikal, masing-masing dari sejumlah langkah berikut:

    ⍳3 tiga ɩ ntegers pertama;[0,1,2]

   kami punya [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]]("J", "L," T ")

   (... ), tambahkan daftar berikut:

    2⊖J putar Jdua langkah secara vertikal; [[1,0],[1,1],[1,0]]("T")

    K⌽ putar baris-barisnya masing-masing sebesar 1, 0, dan 0; [[0,1],[1,1],[1,0]]("Z")

    0 1⌽¨⊂ putar seluruh larik secara vertikal, tidak ada waktu dan sekali; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] ("Z", "S")

    (... ), tambahkan daftar berikut:

     (2 2)4⍴¨1 membentuk kembali satu menjadi masing-masing matriks 2 × 2 dan daftar 4-elemen; [[[1,1],[1,1]],[1,1,1,1]]("O", "I")

  1∊¨ untuk masing-masing, apakah satu anggota?

  ∨/ reduksi horizontal ATAU (mis. melintasi rotasi; satu Boolean untuk setiap bentuk)

  'OIZSLJT'/⍨ gunakan itu untuk menyaring string

* Find mengembalikan array Boolean dengan bentuk yang sama dengan argumen kanannya, dengan yang menunjukkan sudut kiri atas semua subarrays yang identik dengan argumen kiri.

Adm
sumber
Apakah ini akan berhasil? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Zacharý
@ Zacharý Ya, terima kasih, sudah selesai.
Adám
7

JavaScript (ES6), 242 212 172 164 byte

x=>[...'OISZLJT'].filter((z,y)=>x.match(`^0*(${'99,33825|15,51|2145,195|561,2115|57,1059|135,71|1073'.split`,`[y].replace(/\d+/g,C=x=>x?x%2+C(x>>1)+x%2:'|')})0*$`))

Seharusnya hanya untuk menggulirkan bola, tapi aku sedikit terlambat untuk itu ¯ \ _ (ツ) _ / ¯

Mengambil string bit, dengan baris yang dipisahkan oleh 0s ( '0001000110001000000'mewakili 0001 0011 0010 0000) dan mengembalikan array yang berisi karakter yang mewakili tetromino, atau array yang tidak mengandung apa-apa.

Ini bekerja dengan memeriksa setiap rotasi tetromino untuk melihat apakah input pada titik mana pun mengandung tetromino, dikelilingi seluruhnya oleh nol di kedua sisi. Setiap tetromino diwakili oleh satu atau lebih angka biner:

0 0 0 0   -> 0000 0110 1100 0000
0 1 1 0   -> 0000001100110000000
1 1 0 0   -> 110011
0 0 0 0   -> 51

0 1 0 0   -> 0100 0110 0010 0000
0 1 1 0   -> 0100001100001000000
0 0 1 0   -> 100001100001
0 0 0 0   -> 2145

Jadi untuk memeriksa apakah input mengandung tetromino S, kita cukup memeriksa apakah input tersebut berisi representasi biner dari salah satu , 51atau 2145hanya dengan 0s di kedua sisi.

Beberapa tetromino memiliki 4 orientasi. Jika Anda melihat representasi biner dari ini, masing-masing memiliki 2 representasi yang hanya merupakan cermin dari dua lainnya. Untuk menghemat ruang, representasi biner dibangun maju dan mundur bersamaan dengan Cfungsi rekursif , memungkinkan kita untuk hanya memasukkan dua orientasi dan menyiratkan dua lainnya.


Pendekatan alternatif dengan kode karakter:

x=>[...'OISZLJT'].filter((z,y)=>x.match(`^0*(${[...'÷,êÿ,óî,ûÝ,ëúüÏ,çöïþ,ßýíÞ'.split`,`[y]].map(c=>(C=n=>n?'1e'+(n%4+2)%5-0+C(n>>2):'')(c.charCodeAt())).join`|`})0*$`))
Produksi ETH
sumber
3

Retina , 125 byte

s`(.*1){5}.*

{s`.*1111.*
I
s`.*111(.{2,4})1.*
$.1
T`234`\LTJ
s`.*11(.{2,4})11.*
$.1
T`2-90`S\OZ4-9
s`.*4.*

O#$`.
$.%`
O#$^`

Cobalah online! Tautan mencakup test case plus header untuk mengkonversi dari bilangan bulat ke matriks 4 × 4. Penjelasan:

s`(.*1){5}.*

Hapus input jika mengandung 5 1s.

{s`.*1111.*
I

Periksa semua rotasi input (lihat di bawah). Jika input berisi empat berturut-turut 1, ini adalah I.

s`.*111(.{2,4})1.*
$.1
T`234`\LTJ

Jika itu berisi tiga berturut-turut 1ditambah satu 1pada baris berikutnya di bawah salah satu dari tiga, kemudian memetakan jumlah karakter menengah ke huruf hasil yang sesuai.

s`.*11(.{2,4})11.*
$.1

Demikian pula untuk dua 1s yang berdekatan berbatasan dengan dua 1s yang berdekatan pada baris berikutnya.

T`2-90`S\OZ4-9

Tetapi juga tetap menghitung jumlah rotasi menggunakan 0s jika tidak digunakan .

s`.*4.*

Dan menyerah jika terlalu banyak rotasi telah dilakukan.

O#$`.
$.%`
O#$^`

Transpos dan balikkan array, sehingga memutarnya.

Neil
sumber
3

MATL , 60 byte

Itt6tIl7tl7H15vHe"4:"G@X!HYa]4$v@BIthYaEqY+4=aa]v'OSZLJTI'w)

Input adalah array biner 4 × 4 (matriks), menggunakan ;sebagai pemisah baris. Ouput adalah huruf atau kosong tanpa tetromino.

Cobalah online! Atau verifikasi semua kasus uji (output memiliki titik ditambahkan untuk memungkinkan mengidentifikasi hasil kosong).

Penjelasan

Kode membangun 4 rotasi input 4 × 4 array dalam langkah 90 derajat. Setiap array yang diputar diisi dengan 2 nol ke atas dan ke bawah, yang mengubahnya menjadi array 8 × 4. Keempat array secara vertikal digabungkan menjadi array 32 × 4. Keempat array yang diputar dalam array bersambung ini "terisolasi" berkat zero-padding.

Masing-masing dari 7 pola yang mungkin diuji untuk melihat apakah ada dalam array 32 × 4. Loop digunakan untuk ini. Setiap pola didefinisikan oleh dua angka, yang dinyatakan dalam biner memberikan topeng 0/1 yang sesuai. Misalnya, angka 3, 6tentukan bentuk "S".

7 set 2 angka disusun menjadi matriks 2 × 7, dari mana loop akan memilih setiap kolom secara berurutan. Matriks didefinisikan dengan mendorong semua angka ke stack, mengontrasasinya menjadi vektor, dan membentuk kembali menjadi matriks 2-baris. Karena bentuk "I" didefinisikan oleh angka 15 diikuti oleh 0, menempatkannya pada akhirnya memungkinkan 0 untuk secara implisit diisi oleh fungsi pembentukan kembali.

Topeng kemudian diisi dengan 3 nol di empat arah. Ini diperlukan untuk mendeteksi nilai yang tidak diinginkan dalam input.

Untuk melihat apakah topeng hadir dalam array 32 × 4, yang terakhir ditransformasikan ke bentuk bipolar (yaitu /11/1 alih-alih 0/1) dan berbelit-belit dengan topeng. Karena topeng memiliki 4 yang, pencocokan terjadi jika beberapa entri dalam hasil konvolusi sama dengan 4.

Pada akhir loop, 7 hasil salah / benar telah diperoleh, paling banyak salah satunya adalah benar. Ini digunakan untuk mengindeks ke dalam string yang berisi kemungkinan surat keluaran.

Luis Mendo
sumber
3

Jelly , 53 byte

ZL0ẋW⁸tZµ⁺ZU$3С“©©“œ“Ç¿“¦©¦“ƽ‘;Uḃ2$’¤iЀṀị“÷¶Ė¡µỵỤ»

Cobalah online!

Program lengkap. Mengambil 4x4. Mencetak mjika bukan tetromino, sebaliknya mencetak huruf kecil.

Erik the Outgolfer
sumber
Apakah ... mengambil array array bit legal? Itu akan menyelamatkan saya seperti 40 byte
ETHproduksi
@ ETHproductions Anda dapat mengambil input sebagai integer, atau langsung sebagai array 2D 4x4 digit biner atau array datar 16 digit biner.
Erik the Outgolfer
Huh, melayani saya tepat untuk membaca pertanyaan ...
ETHproduksi
1

Perl 5 , 197 +1 (-p) = 198 byte

s/(0000)*$//;1while s/(...)0(...)0(...)0(...)0/0${1}0${2}0${3}0${4}/;$_={51,O,15,I,4369,I,54,S,561,S,99,Z,306,Z,547,L,23,L,785,L,116,L,275,J,113,J,802,J,71,J,114,T,562,T,39,T,609,T}->{oct("0b".$_)}

Cobalah online!

Mengambil string 16 bit sebagai input. Tidak menghasilkan apa-apa jika input bukan tetromino tunggal.

Bagaimana?

Dua pergantian "memindahkan" bentuk input ke sudut kanan bawah. Bit string yang dihasilkan dikonversi ke integer, kemudian diperiksa dalam hash integer yang valid.

Xcali
sumber
1

APL (Dyalog) , 66 byte

{'TIOJSLZ-'[(¯51 144 64,,∘+⍨12J96 ¯48J64)⍳×/(+/-4×⊢)⍵/,0j1⊥¨⍳4 4]}

Cobalah online!

Arg adalah vektor boolean.

Menghitung jarak titik-titik yang telah ditandatangani ke pusat gravitasi mereka sebagai bilangan kompleks (bagian nyata dan imajiner adalah ,x, ∆y) dan mengalikan bilangan kompleks bersama-sama. Ini ternyata menjadi invarian yang cukup baik untuk membedakan antara tetromino.

ngn
sumber
Metode yang menarik.
Arnauld