Deskripsi tantangan
Mari kita mulai dengan beberapa definisi:
- sebuah relasi adalah satu set pasang memerintahkan elemen (dalam tantangan ini, kita akan menggunakan bilangan bulat)
Misalnya, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]
adalah suatu relasi.
suatu relasi disebut transitif jika untuk setiap dua pasang elemen
(a, b)
dan(b, c)
dalam relasi ini, suatu pasangan(a, c)
juga hadir,[(1, 2), (2, 4), (6, 5), (1, 4)]
transitif, karena mengandung(1, 2)
dan(2, 4)
, tetapi(1, 4)
juga,[(7, 8), (9, 10), (15, -5)]
bersifat transitif, karena tidak ada dua pasangan(a, b)
,(c, d)
sajikan sedemikian sehinggab
=c
.[(5, 9), (9, 54), (0, 0)]
tidak transitif, karena mengandung(5, 9)
dan(9, 54)
, tetapi tidak(5, 54)
Diberikan daftar pasangan bilangan bulat, tentukan apakah suatu relasi transitif atau tidak.
Input output
Anda akan diberi daftar pasangan bilangan bulat dalam format apa pun yang masuk akal. Pertimbangkan suatu hubungan
[(1, 6), (9, 1), (6, 5), (0, 0)]
Format berikut ini setara:
[(1, 6), (9, 1), (6, 5), (0, 0)] # list of pairs (2-tuples)
[1, 9, 6, 0], [6, 1, 5, 0] # two lists [x1, x2, ..., xn] [y1, y2, ..., yn]
[[1, 6], [9, 1], [6, 5], [0, 0] # two-dimentional int array
[4, 1, 6, 9, 1, 6, 5, 0, 0] # (n, x1, y1, ..., xn, yn)
[1+6i, 9+i, 6+5i, 0+0i] # list of complex numbers
... many others, whatever best suits golfing purposes
Output: nilai kebenaran untuk hubungan transitif, jika tidak palsu. Anda dapat mengasumsikan bahwa input akan terdiri dari setidaknya satu pasangan, dan pasangan tersebut unik.
sumber
(1,3) (2,1) (3,4) (1,4) (2,4)
. Jika pasangan tidak dipesan, ini tidak akan transitif karena(2,3)
tidak ada.[(7, 8), (9, 10), (15, -5)]
) tidak transitif?Jawaban:
Haskell, 42 byte
Contoh penggunaan:
f [(1,2), (2,4), (6,5), (1,4)]
->True
.(Luar) loop atas semua pasangan
(a,b)
dan (dalam) loop atas pasangan yang sama, sekarang dipanggil(c,d)
dan setiap kalib==c
memeriksa apakah(a,d)
juga ada pasangan. Gabungkan hasilnya dengan logisand
.sumber
Prolog, 66 byte
Relasi tidak transitif jika kita dapat menemukan (A, B) dan (B, C) sehingga (A, C) tidak berlaku.
sumber
MATL ,
2725 byteFormat input adalah matriks (menggunakan
;
sebagai pemisah baris) di mana setiap pasangan relasi adalah sebuah kolom. Misalnya, uji kasusmasing-masing dimasukkan sebagai
Truthy output matriks yang dibentuk oleh orang-orang. Falsy adalah matriks yang mengandung setidaknya satu nol.
Cobalah online!
Penjelasan
Kode pertama mengurangi integer input ke nilai integer berbasis 1 yang unik. Dari nilai-nilai itu menghasilkan matriks adjacency; matrix-mengalikannya dengan sendirinya; dan mengonversi nilai-nilai bukan nol dalam matriks hasil menjadi matriks. Akhirnya, ia memeriksa bahwa tidak ada entri dalam matriks yang terakhir melebihi yang ada di matriks adjacency.
sumber
JavaScript (ES6),
6967 byteDisimpan 2 byte berkat sebuah ide oleh @Cyoce. Ada empat formulasi 69 byte sebelumnya:
sumber
.every
[e]
, jadi meskipun biayanya 8 byte untuk menetapkane
Anda masih menyimpan byte. Namun, saya melangkah lebih jauh dengan membuat singkatana.every
, yang menghemat byte kedua.Brachylog , 24 byte
Cobalah online!
Penjelasan:
Dengan kata lain, jika input berisi pasangan
[A:B]
dan[B:C]
, kita dapat mengubah input untuk menempatkan[A:B]
dan[B:C]
pada awalnya, menghapus semua elemen lainnya, dan menghasilkan daftar[A:B:B:C]
. Kemudian kita mengembalikan kebenaran dari predikat batin (falsey dari seluruh program) jika[A:C]
tidak ada.sumber
CJam (22 byte)
Test suite online . Ini adalah blok anonim (fungsi) yang mengambil elemen sebagai array dua tingkat, tetapi test suite melakukan manipulasi string untuk memasukkan input ke dalam format yang sesuai terlebih dahulu.
Pembedahan
sumber
Pyth, 14 byte
Suite uji
Format input diharapkan
[[0, 0], [0, 1], ... ]
sumber
Mathematica, 49 byte
Fungsi murni yang mengambil daftar pasangan. Jika daftar input berisi
{a,b}
dan{b,c}
tetapi tidak{a,c}
untuk sebagian oranga, b, c
, gantikan dengan0
. Kebenaran adalah daftar input, falsy adalah0
.sumber
C ++ 14, 140 byte
Sebagai lambda tanpa nama kembali melalui parameter referensi. Membutuhkan inputnya untuk menjadi wadah
pair<int,int>
. Mengambil pendekatan O (n ^ 3) yang membosankan.Tidak digabungkan dan digunakan:
sumber
Python 2 ,
916755 byteCobalah online!
-24 bytes berkat Leaky Nun
-12 bytes berkat Bubbler
sumber
lambda x
kelambda s
.for
s.Aksioma 103 byte
ungolfed:
Latihan
sumber
Pyth -
2221 byteTest Suite .
sumber
Clojure,
5653 bytePembaruan: Alih-alih menggunakan
:when
saya hanya akan memeriksa semua pasangan dari[a b]
[c d]
salah satub != c
atau[a d]
ditemukan dari set input.Asli:
Wow, Clojure untuk loop keren: D Ini memeriksa bahwa
for
loop tidak menghasilkan nilai falsy, yang terjadi jika[a d]
tidak ditemukan dari set input.Input ini harus berupa kumpulan vektor dua elemen:
Jika input harus seperti daftar maka
(%[a d])
harus diganti dengan((set %)[a d])
tambahan 6 byte.sumber
Kedua solusi ini adalah fungsi yang tidak disebutkan namanya dengan mengambil daftar pasangan yang dipesan sebagai masukan dan pengembalian
True
atauFalse
.Mathematica, 65 byte
#~Permutations~{2}]
membuat daftar semua pasangan yang dipesan dari pasangan yang dipesan dari input, danJoin@@@
mengonversinya menjadi empat kali lipat yang dipesan. Mereka kemudian dioperasikan oleh fungsiIf[#2==#3,{#,#4},Nothing]&@@@
, yang memiliki properti dingin: jika dua elemen tengah sama, itu mengembalikan pasangan yang diurutkan yang terdiri dari angka pertama dan terakhir; jika tidak kembaliNothing
, token Mathematica khusus yang secara otomatis menghilang dari daftar. Jadi hasilnya adalah himpunan pasangan berurutan yang perlu di input agar transitif;SubsetQ[#,...]
mendeteksi properti itu.Mathematica, 70 byte
Table[...,{i,#},{j,#}]
menciptakan array 2D yang diindeks olehi
danj
, yang diambil langsung dari input (karenanya keduanya pasangan yang dipesan). Fungsi dari kedua indeks tersebut adalahLast@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}
, yang diterjemahkan menjadi "elemen keduai
dan elemen pertamaj
tidak cocok, atau inputnya berisi pasangan berurutan yang terdiri dari elemen pertamai
dan elemen terakhirj
". Ini menciptakan array 2D boolean, yangAnd@@And@@@
rata menjadi boolean tunggal.sumber
APL (NARS), 39 karakter, 78 byte
uji:
'solusi' satu detik ikuti cara goto:
sumber
Common Lisp, 121 byte
Cobalah online!
sumber