Hintergrund

Stellen Sie sich ein Round-Robin-Turnier vor, bei dem jeder Teilnehmer ein Spiel gegen jeden anderen Teilnehmer spielt. Es gibt keine Unentschieden, also hat jedes Spiel einen Gewinner und einen Verlierer. Ein Teilnehmer A ist ein König des Turniers, wenn für jeden anderen Teilnehmer B entweder A Schlag B oder A Schlag ein anderer Teilnehmer ist C ist, der seinerseits B schlägt . Es kann gezeigt werden, dass jedes Turnier mindestens einen König hat (obwohl es mehrere geben kann). In dieser Herausforderung besteht deine Aufgabe darin, die Könige eines bestimmten Turniers zu finden.

Ein- und Ausgabe

Ihre Eingabe ist eine N × Nboolesche Matrix Tund optional die Anzahl N ≥ 2der Teilnehmer. Jeder Eintrag T[i][j]repräsentiert das Ergebnis des Spiels zwischen Teilnehmern iund j, mit dem Wert 1 einen Gewinn für darstellte iund 0 einen Gewinn für j. Beachten Sie, dass T[i][j] == 1-T[j][i]wenn i != j. Die Diagonale von Tbesteht aus 0s.

Ihre Ausgabe soll die Liste der Könige des Turniers sein, Tfür die entweder eine 0-basierte oder eine 1-basierte Indexierung verwendet wird. Die Reihenfolge der Könige ist irrelevant, aber es sollte keine Duplikate geben.

Sowohl die Eingabe als auch die Ausgabe kann in jedem vernünftigen Format erfolgen.

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

Diese Testfälle verwenden eine 0-basierte Indizierung. Erhöhen Sie bei einer 1-basierten Indizierung jeden Ausgabewert.

 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]

Matlab, 36 35 29 Bytes

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

Lassen Sie uns herausfinden, ob i es ein König ist. Dann für jeden jden Wert T[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1. Die zweite Bedingung kann aber auch durch ersetzt werden sum_over_k(T[i][k] * T[k][l])>0, dies ist aber nur ein Eintrag der Matrix T*T(wenn Sie Tals Matrix betrachten). Das ORkann dann wiederholt werden, indem Tzu diesem Ergebnis addiert wird. Wir müssen also nur prüfen, ob die n-1Werte in der Zeile ivon T*T+Tgrößer als Null sind, um festzustellen, ob iKönig ist. Genau das macht meine Funktion.

(Dies ist MATLAB, daher basieren die Indizes auf 1.)

Die MATLAB-Matrizen sollten mit Semikolons als Zeilenbegrenzer codiert werden:

[[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]] 

Jelly, 13 12 11 Bytes

a"€¹o/€oḅ1M

Die Ausgabe ist 1-basiert. Probieren Sie es online!

Alternativ können Sie bitweise Operatoren anstelle der Array-Manipulation verwenden:

×Ḅ|/€|ḄBS€M

Auch hier ist die Ausgabe 1-basiert. Probieren Sie es online!

Hintergrund

Für Teilnehmer A können wir alle B so finden, dass A Schlag C Schlag B ist, indem wir alle Zeilen nehmen, die einem C entsprechen, so dass C Schlag A ist . Ifr der B - ^te Eingabe des C - ^ten ist 1 , haben wir , dass C B schlagen .

Wenn wir die logischen ODER-Verknüpfungen aller entsprechenden Einträge der ausgewählten Spalten berechnen, erhalten wir einen einzelnen Vektor, der angibt, ob A durch Transitivität B schlägt oder nicht. Durch ODER-Verknüpfung des resultierenden Vektors mit der entsprechenden Zeile der Eingabematrix erhält man schließlich Boolesche Werte ob A B schlägt , entweder durch Transitivität oder direkt.

Wiederholen dieses für jede Zeile, wir die Anzahl der Zählung 1 ‚s in jedem Vektor, also die Berechnung der Menge der Kandidaten jedes A Beat. Die maximale Anzahl entspricht den Königen des Turniers.

Wie es funktioniert

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.

Python mit Numpy, 54 Bytes

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

Nimmt eine Zahlenmatrix auf, gibt eine Zahlenzeilenmatrix mit 0-basierten Indizes aus.

Ein anderer Weg, sich einen König vorzustellen, ist, als Teilnehmer zu gelten, für den alle Teilnehmer in der Vereinigung des Königs stehen, des Volkes, das der König schlägt, und des Volkes, das das Volk schlägt. Mit anderen Worten, für jeden Wettkämpfer gibt es einen Längenweg von höchstens 2 vom König zu ihnen unter der "Schlag" -Beziehung.

Die Matrix I + M + M*Mcodiert die Anzahl der Pfade mit 0, 1 oder 2 Schritten von jeder Quelle zu jedem Ziel. Ein Spieler ist ein König, wenn seine Reihe dieser Matrix nur positive Einträge enthält. Da 0 Falsey ist, allwird angegeben, ob eine Zeile ungleich Null ist. Wir wenden dies auf jede Zeile an und geben die Indizes der Nicht-Null-Ergebnisse aus.

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

MATL , 12 10 9 Bytes

Xy+HY^!Af

Die Eingabe ist: Zuerst die Anzahl der Teilnehmer und in einer separaten Zeile eine Matrix mit durch Semikolons getrennten Zeilen. Die Ausgabe ist 1-basiert.

Zum Beispiel hat der fünfte Testfall eine Eingabe

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

und der letzte Testfall hat Eingang

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]

Probieren Sie es online!

Erläuterung

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

Javascript 136 131 121 112 Bytes

(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)

Anrufen mit:

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]])

Achtung, da die Ausgabe 1-indiziert ist (ein paar Bytes gespart, ohne zu versuchen, 0s gegen Falses herauszufiltern)