Tulis program yang akan menentukan apakah matriks yang diberikan merepresentasikan quandle. Sebuah quandle adalah satu set dilengkapi dengan single (non-komutatif, non-asosiatif) operasi ◃ yang mematuhi aksioma-aksioma berikut:
- Operasi ditutup, artinya
a◃b = c
elemen selalu dari himpunan jikaa
danb
merupakan elemen himpunan. - Operasi ini kanan-diri distributif:
(a◃b)◃c = (a◃c)◃(b◃c)
. - Operasi ini dapat dibagi kanan: Untuk setiap pasangan yang dipilih
a
danb
, ada satu yang unikc
sehinggac◃a = b
- Operasi idempoten:
a◃a = a
Quandle terbatas dapat direpresentasikan sebagai matriks persegi. Di bawah ini adalah contoh dari quandle order-5 ( sumber ).
0 0 1 1 1
1 1 0 0 0
3 4 2 4 3
4 2 4 3 2
2 3 3 2 4
Nilai yang terletak di baris ke-n dan kolom ke-m (diindeks 0) adalah nilai dari n◃m. Misalnya, dalam quandle ini, 4◃1 = 3
. Beberapa properti quandle mudah dilihat dari matriks ini:
- Ditutup karena hanya nilai 0-4 yang muncul dalam matriks 5x5 ini.
- Ini idempoten karena matriks diagonal adalah 0 1 2 3 4
- Ini dapat dibagi kanan karena tidak ada kolom yang berisi nilai duplikat. (Baris bisa, dan biasanya akan.)
Properti dari distribusi-diri-kanan lebih sulit untuk diuji. Mungkin ada jalan pintas, tetapi metode paling sederhana adalah untuk beralih pada setiap kombinasi yang mungkin dari tiga indeks untuk memverifikasi itu m[m[a][b]][c] = m[m[a][c]][m[b][c]]
.
Memasukkan
Input akan menjadi daftar baris matriks persegi, menggunakan indeks-0 atau indeks-1 (pilihan Anda). Setiap entri akan menjadi satu digit angka dari 0
ke 8
(atau 1
sampai 9
). Saya akan fleksibel pada format input. Beberapa format yang dapat diterima meliputi:
- Format bahasa Anda yang paling alami untuk matriks atau daftar, seperti
[[0 0 0][2 1 1][1 2 2]]
atau(0,0,0,2,1,1,1,2,2)
. - Daftar nilai yang dibatasi oleh spasi, baris baru, koma, dll.
- String tunggal yang terdiri dari semua nilai yang disatukan, seperti
000211122
.
Anda juga diperbolehkan mengambil transpos matriks sebagai input (menukar baris dengan kolom). Pastikan untuk menyatakan ini dalam jawaban Anda.
Keluaran
Nilai kebenaran / falsey tunggal yang menunjukkan status matriks sebagai quandle.
Contoh pertengkaran
0
0 0
1 1
0 0 0
2 1 1
1 2 2
0 0 1 1
1 1 0 0
3 3 2 2
2 2 3 3
0 3 4 1 2
2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4
Contoh non-pertengkaran
tidak tertutup
1
0 0 0
2 1 1
1 9 2
tidak self-distributive
0 0 1 0
1 1 0 1
2 3 2 2
3 2 3 3
(3◃1)◃2 = 2◃2 = 2
(3◃2)◃(1◃2) = 3◃0 = 3
tidak bisa dibagi kanan
0 2 3 4 1
0 1 2 3 4
3 4 2 2 2
3 3 3 3 3
4 1 1 1 4
0 1 2 3
3 1 2 0
3 1 2 3
0 1 2 3
tidak idempoten
1 1 1 1
3 3 3 3
2 2 2 2
0 0 0 0
2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4
0 3 4 1 2
Jawaban:
Python 2 ,
104103102 byteInput dialihkan. Output melalui kode keluar, jadi 0 (sukses) benar dan 1 (gagal) salah.
Cobalah online!
Bagaimana itu bekerja
e(t)
mengembalikan baris disebutkan input matriks t - yang mewakili operator ◃ - sebagai (indeks, baris) pasang.for(a,A)in e(t)
, misalnya, mengulangi ini, menyimpan indeks dalam a dan baris itu sendiri dalam A , jadiA
menjadi jalan pintas untukt[a]
.Antara yang pertama,,
for(b,B)in e(t)
danfor C in t
, kita mengulangi semua kemungkinan tupel yang dipesan (a, b, c) dalam kekuatan Cartesian t 3 .Untuk masing-masing tupel ini, kami mengevaluasi ekspresi
Nilai Boolean yang dikurung adalah False jika dan hanya jika satu atau lebih dari perbandingan individu berikut melakukan hal yang sama.
a==A[a]
akan gagal (untuk beberapa nilai a ) iff ◃ tidak idempoten.A[a]in B
akan gagal jika B tidak mengandung semua indeks A .Karena A memiliki n indeks dan B memiliki n elemen, non-kegagalan berarti bahwa elemen B cocok dengan indeks A , jadi ◃ tertutup dan dapat dibagi kanan.
B>C[B[a]]
adalah tautologi, karena Python 2 dianggap angka "lebih kecil" daripada iterables.C[B[a]]==t[C[b]][C[a]]
akan gagal untuk beberapa nilai jika ◃ tidak self-distributive.Jika salah satu dari perbandingan mengembalikan False , ekspresi
(0%...)
akan melempar ZeroDivisionError . Juga, jika ◃ tidak ditutupA[a]
atauC[b]
mungkin juga melempar IndexError . Dalam kedua kasus, program keluar dengan kode status 1 (gagal).Jika semua tes lulus, program akan keluar secara normal dengan kode status 0 (berhasil).
sumber
Haskell, 100 byte
Jawaban ini menggunakan input yang dialihkan .
Sepertinya saya tidak bisa menggunakan penjaga pola untuk mengikat operator infiks, jadi saya gunakan
where
dalam kasus ini.(Versi pertama adalah 108 byte tetapi gagal tes idempotensi, versi tetap adalah 120 byte, versi kemudian memiliki 108, 103 dan 98 byte tetapi saya harus menyadari berkat @nimi bahwa mereka semua salah: tentu saja saya perlu melakukan yang benar- uji pembagian (yang menyiratkan penutupan) sebelum melakukan
!!
operasi berbahaya , tapi saya masih bisa menggunakan sebagian besar ide golf saya nanti dan dengan satu lagi, itu 102 byte, sekarang ditingkatkan dengan mengubah urutan operan#
(yang lebih baik pula untuk mengkompensasi transposisi) untuk memanfaatkan asosiasi yang lebih baik ke kiri)Gunakan seperti ini:
sumber
Python 2 , 138 byte
m
adalah daftar daftar bilangan bulat.Cobalah online!
sumber
JavaScript (ES6), 150 byte
Mengambil input sebagai array array kolom bilangan bulat.
sumber
Mathematica, 122 byte
Fungsi murni mengambil array 2D bilangan bulat (1-diindeks) sebagai input, dengan baris dan kolom dibalik dari konvensi dalam pertanyaan, dan mengembalikan
True
atauFalse
. Baris pertama mendefinisikan operasi infiks binern_±m_
sebagai operasi quandle.Untuk
l
xl
array, tertutup dan dapat dibagi kanan setara dengan setiap baris (dalam kasus saya) menjadi beberapa permutasi{1, ..., l}
, dan idempoten setara dengan diagonal utama yang tepat{1, ..., l}
. Jadi#&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]
mendeteksi untuk tiga kondisi ini. (Penggunaan diSort/@#
sini adalah mengapa saya memilih untuk menukar baris dan kolom.)Untuk distribusi-benar, kami benar-benar memeriksa semua kemungkinan menggunakan
Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}])
. (Catatan yang±##2±#
secara otomatis diperluas ke(#2±#3)±#
, karena##2
mewakili urutan argumen kedua dan ketiga untuk fungsi murni tiga variabel yang sedang diatur.) Kemudian&&And@@Flatten@
periksa apakah setiap tes tunggal dilewati. Untuk beberapa pertengkaran yang tidak tertutup, kesalahan mungkin terjadi ketika mencoba mengakses bagian dari matriks yang tidak ada, tetapi jawaban yang benar masih dikembalikan.sumber
±m__:=#[[m]];
Kupikir. Dan adaDiagonal
built-in. Dan±
yang tersisa-asosiatif sehingga Anda dapat menggunakan#2±#±(#3±#)
, tetapi jika aku tidak melakukan kesalahan maka itu lebih pendek untuk menetapkan kembali#
ke#3
dan melakukan#±#2±#3==#±#3±±##2&
. Dan itu juga harus mungkin menggantikan seluruhFlatten@
bagian dengan(...&~Array~{l,l,l}<>"")
l=Length
keRange@l
karena itu yang harus dievaluasi dulu, jadi jika Anda menggunakan fungsi berulang kali, saya pikirRange
masih mendapatkan yang sebelumnyal
, bukan?C ++ 14, 175 byte
Sebagai lambda tanpa nama, dengan asumsi
n
sepertistd::vector<std::vector<int>>
dan kembali melalui parameter referensi. 0 salah, semuanya benar.Tidak digabungkan dan digunakan:
sumber
int a,b,c,u,s=r=m.size()F
alih-alihint s=r=m.size(),a,b,c F
,u=0;r*=s==A.size()&&a==A[a]F
alih-alihr*=s==A.size()&&A[a]==a;int u=0 F
,r*=s>A[b]F
alih- alihr*=A[b]<s F
dan~u+(1<<s)
bukannyau-(1<<s)+1