Latar Belakang
Pada saat penulisan ini, masalah P vs NP masih belum terpecahkan, tetapi Anda mungkin pernah mendengar tentang makalah baru Norbert Blum yang mengklaim bukti bahwa P! = NP, yang sudah diduga salah (tapi kita akan lihat nanti).
Masalah yang dibahas dalam makalah ini adalah masalah klik . Setidaknya itulah yang saya baca di artikel surat kabar, jadi perbaiki jika saya salah, tetapi dalam hal apa pun, saya ingin Anda menulis sebuah program yang memecahkan varian berikut:
Tugas
Anggaplah kita memiliki sekolah besar dengan banyak siswa. Masing-masing siswa memiliki beberapa teman di sekolah ini. Sebuah kelompok mahasiswa adalah kelompok yang terdiri hanya dari siswa yang berteman dengan setiap anggota lainnya .
Program Anda akan menerima pasangan siswa yang menjadi teman sebagai masukan. Dari informasi ini, program harus menemukan ukuran klik terbesar . Siswa diidentifikasi dengan ID integer .
Jika Anda lebih suka istilah matematika, ini berarti Anda mengumpankan tepi grafik yang tidak terarah, diidentifikasi oleh dua node masing-masing.
Memasukkan
Input Anda akan berupa daftar pasangan integer positif yang tidak kosong, mis [[1,2],[2,5],[1,5]]
. Anda dapat mengambil input ini dalam bentuk apa pun yang masuk akal, misalnya sebagai array array, sebagai baris teks yang masing-masing berisi dua angka, dll ...
Keluaran
Output yang diharapkan adalah angka tunggal n >= 2
: ukuran klik terbesar. Dengan contoh input di atas, hasilnya akan menjadi 3
, karena semua siswa ( 1
, 2
dan 5
) berteman satu sama lain.
Uji kasus
[[1,2]]
=> 2
[[1,2],[3,1],[3,4]]
=> 2
[[1,2],[2,5],[1,5]]
=> 3
[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])
[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])
[[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52],
[52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565],
[1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860],
[1296,1860],[1860,52],[711,1639]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])
Anda dapat menggunakan implementasi referensi (bodoh) ini (mencetak hasil tambahan dengan -d
bendera) untuk memverifikasi hasil dari kasus uji lainnya.
Aturan
- Program Anda tidak memerlukan hasil yang ditentukan pada input yang tidak valid. Jadi Anda dapat berasumsi bahwa:
- Anda akan selalu mendapatkan setidaknya sepasang ID
- setiap pasangan terdiri dari dua ID yang berbeda
- tidak ada pasangan yang muncul dua kali (menukar tempat ID akan tetap menjadi pasangan yang sama)
- Algoritme Anda tidak diizinkan untuk menetapkan batas atas pada ukuran input. Batasan dan batasan teknis murni yang ditentukan oleh bahasa / lingkungan Anda (seperti ukuran tumpukan, waktu komputasi, dll) tentu saja tidak dapat dihindari.
- Celah standar dilarang.
- Ini adalah kode-golf , jadi kode terpendek, diukur dalam byte, menang.
- Jika algoritme Anda memiliki kompleksitas waktu polinomial, Anda skor
-1
langsung terlepas dari ukuran kode Anda, tetapi dalam hal ini, Anda mungkin ingin mengirimkan solusi Anda di tempat lain. ;)
sumber
-1
itu memang layak ;)Jawaban:
Jelly ,
15 1816 byte+3 byte untuk memperbaiki bug dalam metode saya.
-2 byte berkat mil (mencatat bahwa n × (n-1) ÷ 2 = nC2 )
Tautan monadik dengan mengambil daftar pertemanan (tepian) dan mengembalikan integer.
Cobalah online! membentuk power-set tepi dalam memori sehingga tidak efisien baik dalam ruang dan waktu (ya, itu O (2 n ) orang)!
Bagaimana?
sumber
Mathematica, 34 byte
Pada dasarnya FindClique melakukan pekerjaannya dan "menemukan klik terbesar pada grafik g."
Semua hal lainnya adalah mengubah daftar input menjadi grafik
Memasukkan
Keluaran
Memasukkan
Keluaran
thanx @Kelly Lowder untuk -10 byte
sumber
Tr[1^#&@@FindClique[#<->#2&@@@#]]&
FindClique
ಠ ___ ಠJelly , 20 byte
Cobalah online!
Tentu saja ini tidak layak jutaan: p
Ini akan mengalahkan Pyth, jika bukan untuk
µ(...)µ
dan 2-byteÐf
.sumber
J , 36 byte
Cobalah online!
Berjalan dalam waktu O (2 n ) di mana n adalah jumlah pasangan.
Solusi yang lebih cepat untuk 65 byte adalah
Cobalah online!
Penjelasan
sumber
Pyth, 19 byte
Coba di sini.
sumber
Python 2 , 180 byte
Cobalah online!
-2 Berkat shooqie .
-1 terima kasih kepada Tn . Xcoder .
-3 Berkat rekursif .
sumber
len
ke variabel(x not in y)
berarti0**(x in y)
.0**
dengan-~-
.Pyth, 28 byte
Cobalah online
Penjelasan
sumber
Python 3 ,
162159 byteCobalah online!
Fungsi c mengambil simpul dalam bentuk satu set tupel yang
diurutkan({(x, y), ...} di mana x kurang dari y).Fungsi yang disebut "entri" ada di header TIO untuk menguji dengan data dalam daftar format daftar yang tidak disortir. Jika klik, kembalikan panjang. Jika tidak klik, kembalikan ukuran simpul klik maksimum, minus simpul untuk setiap simpul dalam simpul. Melebihi waktu pada test case terakhir di TIOPerbarui: "atau (z, y) dalam porsi x" yang ditambahkan untuk menghapus ketergantungan pada penyortiran "f = lambda x: {i untuk s di x untuk i dalam s}" "alih-alih itertools.chain yang dibungkus set.
-minus 3 byte terima kasih kepada @Jonathan Allen
sumber
c
, sehingga dapat menghapusc=
(Anda harus meletakkannyac=\
di akhir tajuk dan menempatkannyalambda
di bagian atas blok kode untuk TIO)s
juga dapat menyingkirkan dan menggantis(...)
dengan{*...}
memungkinkan penghapusan beberapa ruang juga.05AB1E , 19 byte
Cobalah online!
sumber
Jelly , 28 byte
Cobalah online!
Solusi lebih cepat yang mampu menyelesaikan kasus tes terakhir dalam sedetik di TIO.
sumber
n
mungkin hanya muncul di pangkalan :)Java + Jambu 23.0, 35 + 294 = 329 byte
Algoritma ini bukan grafik, melainkan menghasilkan semua kombinasi pasangan, dengan ukuran tertentu. Saya memberi makan semua kombinasi pasangan ke dalam multiset dan memeriksa apakah semuanya memiliki ukuran yang diharapkan (jumlah entri unik - 1). Jika mereka melakukannya, saya menemukan sebuah klik dan saya mencari yang lebih besar.
Dari perpustakaan Guava, saya menggunakan
combinations
metode baru , dan tipe koleksi alatMultiset
.Tidak disatukan
sumber
x
adalah polinomial " <- apakah Anda yakin? Saya kira itulah metode yang digunakan . Nilai pengembaliannya adalahAbstractSet
dengan iterator, danfor
loop berikut akan memanggil iterator inix!
kali jika saya tidak salah ...x < n
(dengann
ukuran lengkap set input), itun!/(x!(n-x)!)
, masih belum jumlahnya banyak :)combinations
metode ituX^n
(yang sepenuhnya mungkin), saya bisa mendapatkannya? Sementara itu, saya menghapus klaim saya atas "-1".Python 2 , 102 byte
Cobalah online!
sumber
6502 kode mesin (C64),
774703 byte(Saya hanya harus melakukan ini, C64 saya dapat melakukan segalanya ... hehe)
hexdump:
Demo online
Penggunaan: Mulai dengan
sys49152
, lalu masukkan pasangan satu per baris seperti misalnyaBacksapce tidak ditangani selama input (tetapi jika Anda menggunakan
vice
, cukup salin & tempel input Anda ke emulator). Masukkan baris kosong untuk memulai perhitungan.Ini terlalu besar untuk mengirim daftar pembongkaran penjelas di sini, tetapi Anda dapat menelusuri sumber perakitan bergaya ca65 . Algoritma ini sangat tidak efisien, menghasilkan setiap permutasi yang mungkin dari node dan dengan masing-masing dengan rakus membangun klik dengan memeriksa semua tepi. Hal ini memungkinkan untuk efisiensi ruang dari O (n) (jenis penting pada mesin dengan RAM kecil ini), tetapi memiliki mengerikan efisiensi runtime (*) . Batas teoritis hingga 256 node dan hingga 8192 tepi.
Ada versi yang lebih besar (
883805 byte) dengan fitur yang lebih baik:Demo online
Jelajahi sumber
(*) Test case terakhir membutuhkan waktu antara 12 dan 20 jam (saya tidur ketika akhirnya selesai). Kasus uji lainnya selesai paling buruk dalam beberapa menit.
sumber