Sidik jari invarian rotasi

15

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 m×n Boolean / 0,1 -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

  • m1 dann1 (mis. tidak ada polyomino kosong)
  • Anda dijamin bahwa m,n sekecil mungkin (mis. semua 0 dipangkas agar sesuai dengan m dan n
  • 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 5×1 bar:

[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]

Sebuah 2×2 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]]
ბიმო
sumber
Terkait .
ბიმო
Jika saya selalu menampilkan ""(string kosong), sudahkah saya memenuhi semua persyaratan?
Daniel Wagner
@DanielWagner: "[..] untuk dua polyominos dari dua kelas yang berbeda [sidik jari] harus berbeda " - jadi tidak, itu tidak valid.
ბიმო
Apakah mengeluarkan semua kemungkinan rotasi array, diurutkan secara konsisten, valid? Contoh
Shaggy
1
@Shaggy: Ya, itu akan memenuhi semua kriteria.
ბიმო

Jawaban:

7

Python 2 , 48 byte

f=lambda l,z=5:z and max(l,f(zip(*l)[::-1],z-1))

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 0tidak berbahaya untuk maxkarena lebih kecil dari daftar mana pun. Selain itu, zipmenghasilkan 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.)

Tidak
sumber
4

Python 3 , 63 byte

def f(m):M=[];exec("m=[*zip(*m[::-1])];M+=m,;"*4);return min(M)

Cobalah online!

Temukan rotasi dengan minimum leksografis, dan cetaklah itu.

Formulir lambda masuk pada jumlah byte yang sama:

lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M[-4:])

Cobalah online!

FlipTack
sumber
Menulis ulang sebagai lambdadapat membuat Anda mencapai 58 lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M).. Berfungsi karena execselalu kembali None.
nedla2004
@ nedla2004 Itu hanya dapat dijalankan sekali, dan kemudian menjadi cerdik seperti Myang sudah diisi ...
FlipTack
@ nedla2004 ... tetapi memperhitungkan masalah dengan M[-4:]bisa membawa Anda ke jumlah byte yang sama.
FlipTack
Saya melihat, tes yang saya gunakan hanya memeriksa input dengan "hash" yang sama, jadi saya tidak pernah menemukan itu. Itu masuk akal.
nedla2004
2

Jelly , 5 byte

ZU$ƬṂ

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.

Erik the Outgolfer
sumber
ketika saya membaca tantangan saya tahu ini akan terjadi :)
ngn
2

Bersih , 136 byte

import StdEnv,Data.List
r=reverse;t=transpose;f=flatten
$l=[if((a==b)==(c==d))'x''X'\\a<-f l&b<-f(r(map r l))&c<-f(r(t l))&d<-f(t(r l))]

Cobalah online!

Termasuk penguji verifikasi.

Suram
sumber
2

K (ngn / k) , 16 byte

{a@*<a:3{+|x}\x}

Cobalah online!

min rotasi

{ } berfungsi dengan argumen x

{+|x}memutar, yaitu membalikkan ( |) dan mengubah posisi ( +)

3{ }\berlaku 3 kali mempertahankan hasil antara; ini mengembalikan daftar 4 rotasi

a: menetapkan ke a

< ascend (hitung permutasi sort-ascending)

* pertama

a@indeks adengan itu

ngn
sumber
1

Japt -g, 6 byte

4Æ=zÃñ

Cobalah

           :Implicit input of 2d-array U
4Æ         :Map the range [0,4)
   z       :  Rotate U 90 degrees
  =        :  Reassign to U
    Ã      :End map
     ñ     :Sort
           :Implicit output of first element
Shaggy
sumber
Apakah -gbendera 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.
Kamil Drakari
@ KamilDrakari, Anda mungkin benar - seperti yang saya katakan, saya tidak yakin saya sepenuhnya memahami tantangannya. Tidak ada salahnya meninggalkannya, meskipun, itu tidak memerlukan biaya byte.
Shaggy
@ KamilDrakari: Tidak perlu, tapi tidak ada salahnya karena tidak dihitung terhadap bytecount.
ბიმო
1

J , 16 byte

-2 byte terima kasih kepada Shaggy

[:/:~|.@|:^:(<4)

Cobalah online!

J , 18 byte

0{[:/:~|.@|:^:(<4)

Cobalah online!

Mengembalikan item pertama dalam daftar rotasi polyomino yang diurutkan secara leksikografis.

Penjelasan:

            ^:(<4)  - do the verb on the left 4 times, storing all the steps
       |.@|:        - tranpose and reverse
    /:~             - sort up the 4 matrices
  [:                - cap the fork
0{                  - take the first matrix  
Galen Ivanov
sumber
@Shaggy Terima kasih!
Galen Ivanov
0

05AB1E , 10 8 byte

3FÂø})Σ˜

-2 byte terima kasih kepada @Shaggy .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

3F  }       # Loop 3 times
  Â         #  Bifurcate (short for Duplicate & Reverse) the top of the stack
            #  (which is the input-matrix implicitly the first iteration)
   ø        #  Transpose: swap rows/columns
     )      # After the loop, wrap everything on the stack in a list
      Σ˜    # Sort this list of matrices by their flattened array (and output implicitly)

CATATAN: Mengambil minimum dengan ßatau Wsecara implisit akan meratakan, demikian juga output 0. Dan menyortir dengan {sepertinya tidak berfungsi untuk daftar matriks, itulah sebabnya saya menggunakan Σ˜sebagai gantinya.

Kevin Cruijssen
sumber
1
@Shaggy Terima kasih! :) Dalam hal ini dua byte terakhir dapat dihapus, karena }dilakukan secara implisit jika tidak ada yang muncul setelahnya.
Kevin Cruijssen
1
Hari ini saya belajar sesuatu tentang 05AB1E! :) Sama di Japt.
Shaggy