Siapa raja turnamen?

13

Latar Belakang

Pertimbangkan turnamen round-robin, di mana setiap kontestan memainkan satu pertandingan melawan setiap kontestan lainnya. Tidak ada pengundian, sehingga setiap pertandingan memiliki pemenang dan pecundang. Seorang kontestan A adalah raja turnamen, jika untuk setiap lainnya kontestan B , baik A mengalahkan B , atau A mengalahkan lain kontestan C yang pada gilirannya beat B . Dapat ditunjukkan bahwa setiap turnamen memiliki setidaknya satu raja (walaupun mungkin ada beberapa). Dalam tantangan ini, tugas Anda adalah menemukan raja-raja dari turnamen yang diberikan.

Masukan dan keluaran

Input Anda adalah N × Nmatriks boolean T, dan opsional jumlah N ≥ 2kontestan. Setiap entri T[i][j]mewakili hasil pertandingan antara kontestan idan j, dengan nilai 1 mewakili menang untuk idan 0 menang untuk j. Perhatikan bahwa T[i][j] == 1-T[j][i]jika i != j. Diagonal Tterdiri dari 0s.

Output Anda akan menjadi daftar raja di turnamen yang Tmewakili, menggunakan pengindeksan berbasis 0 atau 1. Urutan raja tidak relevan, tetapi tidak boleh ada duplikat.

Baik input maupun output dapat diambil dalam format apa pun yang masuk akal.

Aturan dan penilaian

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji kasus

Kasing uji ini menggunakan pengindeksan berbasis 0. Untuk pengindeksan berbasis 1, tambahkan setiap nilai output.

 2 [[0,0],[1,0]] -> [1]
 3 [[0,1,0],[0,0,0],[1,1,0]] -> [2]
 3 [[0,1,0],[0,0,1],[1,0,0]] -> [0,1,2]
 4 [[0,1,1,1],[0,0,1,0],[0,0,0,0],[0,1,1,0]] -> [0]
 4 [[0,1,1,0],[0,0,1,0],[0,0,0,1],[1,1,0,0]] -> [0,2,3]
 5 [[0,1,0,0,1],[0,0,0,0,1],[1,1,0,0,0],[1,1,1,0,1],[0,0,1,0,0]] -> [3]
 5 [[0,1,0,1,0],[0,0,1,1,1],[1,0,0,0,0],[0,0,1,0,1],[1,0,1,0,0]] -> [0,1,4]
 5 [[0,0,0,0,0],[1,0,1,1,0],[1,0,0,0,1],[1,0,1,0,1],[1,1,0,0,0]] -> [1,3,4]
 6 [[0,0,0,0,0,0],[1,0,1,1,0,0],[1,0,0,1,1,0],[1,0,0,0,1,1],[1,1,0,0,0,1],[1,1,1,0,0,0]] -> [1,2,3,4,5]
 6 [[0,0,1,1,1,0],[1,0,0,1,1,1],[0,1,0,0,1,0],[0,0,1,0,0,1],[0,0,0,1,0,1],[1,0,1,0,0,0]] -> [0,1,2,3,5]
 6 [[0,1,1,0,0,1],[0,0,0,1,0,1],[0,1,0,1,1,0],[1,0,0,0,1,1],[1,1,0,0,0,0],[0,0,1,0,1,0]] -> [0,1,2,3,4,5]
 8 [[0,0,1,1,0,1,1,1],[1,0,1,0,1,1,0,0],[0,0,0,1,1,0,0,0],[0,1,0,0,0,1,0,0],[1,0,0,1,0,1,0,0],[0,0,1,0,0,0,1,0],[0,1,1,1,1,0,0,1],[0,1,1,1,1,1,0,0]] -> [0,1,4,6,7]
20 [[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1],[1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1],[0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1],[0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1],[1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1],[0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1],[0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0],[1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0],[1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1],[1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1],[1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0],[0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1],[0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1],[1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1],[0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1],[0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1],[0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1],[0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1],[1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]] -> [0,1,3,4,5,7,8,11,15,17,18]
code-golf array-manipulation Zgarb
sumber
(Apakah ada batas waktu berjalan atau memori?) Nevermind. Saya benar-benar salah mengerti spec.
Dennis
@Dennis Nggak. Selama program Anda secara teoritis akan bekerja mengingat waktu dan memori tidak terbatas, Anda baik-baik saja.
Zgarb
Hanya untuk memperjelas: T [a] [b] sama dengan T [b] [a] tetapi dilihat dari sudut yang berlawanan, jadi T [a] [b] ==! T [b] [a]
edc65
@ edc65 Itu pengamatan yang bagus. Saya mengeditnya menjadi tantangan.
Zgarb

Jawaban:

9

Matlab, 36 35 29 byte

@(T,N)find(sum(T*T>-T,2)>N-2)

Mari kita cari tahu apakah iitu raja. Kemudian untuk setiap jnilainya T[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1. Tetapi kondisi kedua juga bisa digantikan oleh sum_over_k(T[i][k] * T[k][l])>0, tetapi ini hanyalah entri dari matriks T*T(jika Anda anggap Tsebagai matriks). The ORkemudian dapat diputar dengan menambahkan Tuntuk hasil itu, jadi kami hanya harus memeriksa apakah n-1nilai-nilai dari barisi dari T*T+Tyang lebih besar dari nol, untuk melihat apakah iadalah raja. Inilah yang fungsi saya lakukan.

(Ini MATLAB, jadi indeksnya berbasis 1).

Matriks MATLAB harus dikodekan dengan titik koma sebagai pembatas garis:

[[0,0,0,0,0];[1,0,1,1,0];[1,0,0,0,1];[1,0,1,0,1];[1,1,0,0,0]]
cacat
sumber
Anda mungkin dapat menyimpan beberapa byte dengan mengambil jumlah kontestan sebagai input, alih-alih melakukannyasize(T,1)
Luis Mendo
7

Jelly, 13 12 11 byte

a"€¹o/€oḅ1M

Output berbasis 1. Cobalah online!

Atau, menggunakan operator bitwise alih-alih manipulasi array:

×Ḅ|/€|ḄBS€M

Sekali lagi, output berbasis 1. Cobalah online!

Latar Belakang

Untuk kontestan A , kita dapat menemukan semua B sehingga A mengalahkan C beat B dengan mengambil semua baris yang bersesuaian dengan C sehingga C mengalahkan A . IFR B th masuknya C th adalah 1 , kita mendapati bahwa C mengalahkan B .

Jika kita menghitung OR logis dari semua entri yang sesuai dari kolom yang dipilih, kita mendapatkan aa vektor tunggal yang menunjukkan apakah beat A dengan transitivity atau tidak. Akhirnya, ORing vektor yang dihasilkan dengan baris yang sesuai dari matriks input memberikan Boolean apakah A beat B , baik dengan transitivitas atau langsung.

Mengulangi ini untuk setiap baris, kita menghitung jumlah 1 's di setiap vektor, karena menghitung jumlah kontestan masing-masing A beat. Jumlah maksimal sesuai dengan raja-raja turnamen.

Bagaimana itu bekerja

a"€¹o/€oḅ1M  Main link. Argument: M (matrix)

   ¹         Yield M.
  €          For each row of M:
a"           Take the logical AND of each entry of that row and the corr. row of M.
    o/€      Reduce each resulting matrix by logical OR.
       o     Take the logical OR of the entries of the resulting maxtrix and the
             corr. entries of M.
        ḅ1   Convert each row from base 1 to integer, i.e. sum its elements.
          M  Get all indices of maximal sums.

×Ḅ|/€|ḄBS€M  Main link. Argument: M (matrix)

 Ḅ           Convert each row of M from base 2 to integer. Result: R
×            Multiply the entries of each column of M by the corr. integer.
  |/€        Reduce each row fo the resulting matrix by bitwise OR.
     |Ḅ      Bitwise OR the results with R.
       BS€   Convert to binary and reduce by sum.
             This counts the number of set bits for each integer.
          M  Get all indices of maximal popcounts.
Dennis
sumber
1
Anda tahu, orang-orang terus memposting ini dan mengatakan x "byte", tetapi apakah "ḅ" benar-benar dikodekan dalam 1 byte dalam pengkodean standar apa pun? Maaf, tapi saya menemukan bahasa berbasis tumpukan hiper-kondensasi ini benar-benar tidak menarik karena rasanya curang untuk hanya menetapkan setiap fungsi yang mungkin untuk karakter unicode.
MattPutnam
2
@MattPutnam Jelly menggunakan penyandian khusus sendiri. (Juga bukan berbasis tumpukan)
spaghetto
2
@MattPutnam Saya punya sentimen serupa, tetapi mereka tidak mengurangi sama sekali dari golf tradisional. Tidak ada yang meremehkan bahasa tradisional hanya karena ini ada, dan tidak seperti situs SE lainnya, ini tidak persis memiliki 'jawaban ini obyektif lebih baik daripada jawaban itu'. Juga, sementara secara teknis tidak diingkari, mereka tidak mengubah bahasa untuk mendukung pertanyaan (meskipun mereka mungkin, setelah kenyataan, menyadari jalan pintas yang berguna untuk pertanyaan di masa depan dan menjadikannya sebuah operasi).
corsiKa
Mengapa algoritma ini menampilkan raja?
xnor
@ Dennis Saya melihat sekarang, pada dasarnya perkalian matriks Boolean dilakukan melalui logika atau bit aritmatika. Multiplikasi matriks aktual tidak akan lebih pendek?
xnor
2

Python menggunakan numpy, 54 byte

import numpy
lambda M:(M**0+M+M*M).all(1).nonzero()[0]

Dibawa dalam matriks numpy, menghasilkan matriks baris numpy dari indeks berbasis 0.

Cara lain untuk memikirkan seorang raja adalah sebagai kontestan yang semua kontestan berada dalam persatuan raja, orang-orang yang dikalahkan raja, dan orang-orang yang dikalahkan orang. Dengan kata lain, untuk setiap kontestan, ada jalur panjang maksimal 2 dari raja ke mereka di antara hubungan "beat".

Matriks I + M + M*Mmengkodekan jumlah lintasan 0, 1, atau 2 langkah dari setiap sumber ke setiap target. Seorang pemain adalah raja jika baris mereka dari matriks ini hanya memiliki entri positif. Karena 0 adalah Falsey, beri alltahu kami jika satu baris tidak nol. Kami menerapkan ini pada setiap baris dan menampilkan indeks hasil bukan nol.

Tidak
sumber
Tampak persis seperti pendekatan saya tetapi dengan interpretasi yang berbeda, menarik =)
flawr
2

JavaScript (ES6), 83 byte

a=>a.map((b,i)=>b.every((c,j)=>c|i==j|b.some((d,k)=>d&a[k][j]))&&r.push(i),r=[])&&r
Neil
sumber
Anda dapat menyimpan 1 dengan a => a.map ((b, i) => b.every ((c, j) => c | i == j | b.some ((d, k) => d & a [ k] [j])) && i +1) .filter (a => a) tetapi itu berarti Anda harus menampilkan 1-diindeks yang merupakan gelandangan serius
Charlie Wynn
2

MATL , 12 10 9 byte

Xy+HY^!Af

Input adalah: pertama jumlah kontestan, dan pada baris terpisah sebuah matriks dengan baris yang dipisahkan oleh titik koma. Output berbasis 1.

Sebagai contoh, test case kelima memiliki input

4
[0,1,1,0; 0,0,1,0; 0,0,0,1; 1,1,0,0]

dan test case terakhir memiliki input

20
[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1; 1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1; 0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1; 0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1; 1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1; 0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1; 0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0; 1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0; 1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1; 1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1; 1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0; 0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1; 0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1; 1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1; 0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1; 0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1; 0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1; 0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1; 1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0; 0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]

Cobalah online!

Penjelasan

Xy    % Implicitly take input: number. Push identity matrix with that size
+     % Implicitly take input: matrix. Add to identity matrix
HY^   % Matrix square
!     % Transpose
A     % Row vector with true entries for columns that contain all nonzero values
f     % Indices of nonzero values
Luis Mendo
sumber
1
MATL <Jelly \ m /
flawr
1

Javascript 136 131 121 112 byte

(n,m)=>m.map((a,k)=>eval(a.map((o,i)=>o||eval(a.map((p,j)=>p&&m[j][i]).join`|`)).join`+`)>n-2&&k+1).filter(a=>a)

Panggilan menggunakan:

f=(n,m)=>m.map((a,k)=>eval(a.map((o,i)=>o||eval(a.map((p,j)=>p&&m[j][i]).join`|`)).join`+`)>n-2&&k+1).filter(a=>a)

f(20,[[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1],
     [1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1],
     [0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1],         
     [0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1],
     [1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1],         
     [0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1],
     [0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0],         
     [1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0],
     [1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1],         
     [1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1],
     [1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0],         
     [0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1],
     [0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1],         
     [1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1],
     [0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1],         
     [0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1],
     [0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1],         
     [0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1],
     [1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0],             
     [0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]])

hati-hati karena output 1-diindeks (disimpan beberapa byte tidak mencoba untuk menyaring 0s vs kesalahan)

Charlie Wynn
sumber