Bayangkan kita memiliki beberapa polyomino dan ingin mengidentifikasinya secara unik, namun polyomino dapat diputar, jadi membabi buta dengan hashing tidak akan memberi kita sidik jari yang sama untuk sebuah karya dan rotasi darinya (secara umum).
Sebagai contoh jika kita memiliki L-tetromino
x
x
xx
kami ingin memiliki sidik jari yang sama dengan yang berikut ini:
xx
x x xxx
xxx , x or x
Catatan: Kami hanya mengizinkan rotasi di pesawat (mis., Itu adalah polyominos satu sisi) dan karenanya polyomino berikut akan berbeda:
x
x
xx
Tantangan
Tugas untuk tantangan ini adalah untuk mengimplementasikan fungsi-fungsi / program sidik jari yang membutuhkan Boolean / -nilai matriks / daftar daftar / string / .. menyandikan sebuah polyomino dan mengembalikan sebuah string - sidik jari dari sebuah polyomino . Sidik jari harus sama untuk semua kemungkinan rotasi (secara umum 4).
Input output
- dan (mis. tidak ada polyomino kosong)
- Anda dijamin bahwa sekecil mungkin (mis. semua dipangkas agar sesuai dengan dan
- Anda dijamin inputnya
- cukup terhubung
- tidak memiliki lubang
- output harus berupa string yang sama untuk setiap kemungkinan rotasi polomino
Contohnya
Berikut adalah beberapa kelas kesetaraan, untuk setiap kelas sidik jari harus sama & untuk setiap dua polyominos dari dua kelas berbeda, mereka harus berbeda.
Rotasi L-tetromino dari contoh:
[[1,0],[1,0],[1,1]]
[[0,0,1],[1,1,1]]
[[1,1],[0,1],[0,1]]
[[1,1,1],[1,0,0]]
J-tetromino:
[[0,1],[0,1],[1,1]]
[[1,1,1],[0,0,1]]
[[1,1],[1,0],[1,0]]
[[1,0,0],[1,1,1]]
Unit polyomino:
[[1]]
A bar:
[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]
Sebuah sudut:
[[1,1],[1,0]]
[[1,0],[1,1]]
[[0,1],[1,1]]
[[1,1],[0,1]]
W-pentomino:
[[1,0,0],[1,1,0],[0,1,1]]
[[0,0,1],[0,1,1],[1,1,0]]
[[1,1,0],[0,1,1],[0,0,1]]
[[0,1,1],[1,1,0],[1,0,0]]
""
(string kosong), sudahkah saya memenuhi semua persyaratan?Jawaban:
Python 2 , 48 byte
Cobalah online!
Mengambil yang terbesar dari empat rotasi dalam hal perbandingan daftar. Berdasarkan solusi FlipTack .
Kode ini menggunakan kemampuan Python 2 untuk membandingkan objek dari berbagai jenis. Nilai huruf dasar dari
0
tidak berbahaya untukmax
karena lebih kecil dari daftar mana pun. Selain itu,zip
menghasilkan daftar tupel sementara inputnya adalah daftar daftar, tetapi tupel lebih besar dari daftar sehingga daftar input daftar tidak pernah menjadi pesaing. Inilah sebabnya kami memutar 5 kali daripada 4, sehingga kami kembali ke versi tuplified dari daftar awal. (Mengambil daftar tupel juga akan berfungsi, jika itu bentuk input yang diizinkan.)sumber
Python 3 , 63 byte
Cobalah online!
Temukan rotasi dengan minimum leksografis, dan cetaklah itu.
Formulir lambda masuk pada jumlah byte yang sama:
Cobalah online!
sumber
lambda
dapat membuat Anda mencapai 58lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M)
.. Berfungsi karenaexec
selalu kembaliNone
.M
yang sudah diisi ...M[-4:]
bisa membawa Anda ke jumlah byte yang sama.Jelly , 5 byte
Cobalah online!
Program lengkap.
Cukup hasilkan semua rotasi yang mungkin dan pilih minimum leksikografis.
Perhatikan bahwa daftar singleton tidak terbungkus dalam
[]
output. Itu tidak masalah, karena satu-satunya kasus di mana daftar tunggal akan ada dalam input akan menjadi garis vertikal (termasuk unit polyomino), yang sama dengan garis horizontal dengan ukuran yang sama (di mana yang tidak dibungkus ). Satu-satunya kasus di mana bagian luar[]
tidak akan ada adalah unit polyomino.sumber
Bersih , 136 byte
Cobalah online!
Termasuk penguji verifikasi.
sumber
K (ngn / k) , 16 byte
Cobalah online!
min rotasi
{
}
berfungsi dengan argumenx
{+|x}
memutar, yaitu membalikkan (|
) dan mengubah posisi (+
)3{
}\
berlaku 3 kali mempertahankan hasil antara; ini mengembalikan daftar 4 rotasia:
menetapkan kea
<
ascend (hitung permutasi sort-ascending)*
pertamaa@
indeksa
dengan itusumber
Japt
-g
, 6 byteCobalah
sumber
-g
bendera itu perlu? Sortir harus berarti bahwa semua rotasi awal berakhir dengan daftar yang sama sehingga daftar lengkap harus berfungsi dengan baik seperti sidik jari kecuali saya kehilangan sesuatu.J , 16 byte
-2 byte terima kasih kepada Shaggy
Cobalah online!
J , 18 byte
Cobalah online!
Mengembalikan item pertama dalam daftar rotasi polyomino yang diurutkan secara leksikografis.
Penjelasan:
sumber
05AB1E ,
108 byte-2 byte terima kasih kepada @Shaggy .
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
CATATAN: Mengambil minimum dengan
ß
atauW
secara implisit akan meratakan, demikian juga output0
. Dan menyortir dengan{
sepertinya tidak berfungsi untuk daftar matriks, itulah sebabnya saya menggunakanΣ˜
sebagai gantinya.sumber
}
dilakukan secara implisit jika tidak ada yang muncul setelahnya.