Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Background

Consider a round-robin tournament, in which each contestant plays one game against every other contestant. There are no draws, so every game has a winner and a loser. A contestant A is a king of the tournament, if for every other contestant B, either A beat B, or A beat another contestant C who in turn beat B. It can be shown that every tournament has at least one king (although there may be several). In this challenge, your task is to find the kings of a given tournament.

Input and output

Your input is an N × N boolean matrix T, and optionally the number N ≥ 2 of contestants. Each entry T[i][j] represents the outcome of the game between contestants i and j, with value 1 representing a win for i and 0 a win for j. Note that T[i][j] == 1-T[j][i] if i != j. The diagonal of T consists of 0s.

Your output shall be the list of kings in the tournament that T represents, using either 0-based or 1-based indexing. The order of the kings is irrelevant, but there should not be duplicates.

Both input and output can be taken in any reasonable format.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

These test cases use 0-based indexing. For 1-based indexing, increment each output value.

 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]
share|improve this question
    
(Are there any run time or memory limits?) Nevermind. I completely misunderstood the spec. – Dennis Mar 28 at 18:27
    
@Dennis Nope. As long as your program would theoretically work given unlimited time and memory, you're fine. – Zgarb Mar 28 at 18:30
    
Just to clarify: T[a][b] is the same match as T[b][a] but viewed from opposite angle, so T[a][b] == !T[b][a] – edc65 Mar 28 at 21:04
    
@edc65 That's a good observation. I edited it into the challenge. – Zgarb Mar 28 at 21:10

Jelly, 13 12 11 bytes

a"€¹o/€oḅ1M

Output is 1-based. Try it online!

Alternatively, using bitwise operators instead of array manipulation:

×Ḅ|/€|ḄBS€M

Again, output is 1-based. Try it online!

Background

For contestant A, we can find all B such that A beat C beat B by taking all rows that correspond to a C such that C beat A. Ifr the Bth entry of the Cth is 1, we have that C beat B.

If we compute the logical ORs of all corresponding entries of the selected columns, we get a a single vector indicating whether A beat B by transitivity or not. Finally, ORing the resulting vector with the corresponding row of the input matrix gives Booleans whether A beat B, either by transitivity or directly.

Repeating this for every row, we count the number of 1's in each vector, therefore computing the amount of contestants each A beat. Maximal counts correspond to kings of the tournament.

How it works

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.
share|improve this answer
1  
You know, people keep posting these and saying x "bytes", but is "ḅ" really encoded in 1 byte in any standard encoding? Sorry, but I find these hyper-condensed stack-based languages completely uninteresting because it feels like cheating to just assign every conceivable function to a unicode character. – MattPutnam Mar 28 at 19:26
2  
@MattPutnam Jelly uses its own custom encoding. (Also it isn't stack-based) – quartata Mar 28 at 19:27
2  
@MattPutnam I've had similar sentiments, but they don't detract at all from traditional golfing. No one looks down on the traditional languages just because these exist, and unlike other SE sites, this doesn't exactly have the 'this answer is obvjectively better than that answer'. Also, while technically not disallowed, they don't alter the language to support a question (although they may, after the fact, realize a useful shortcut for future questions and make that an operation). – corsiKa Mar 28 at 19:31
    
Why do these algorithms output the kings? – xnor Mar 28 at 20:01
    
@Dennis I see now, its basically Boolean matrix multiplication done via logic or bit arithmetic. Actual matrix multiplication wouldn't be shorter? – xnor Mar 28 at 20:37

Matlab, 36 35 29 bytes

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

Let us find out if i is a king. Then for each j the value T[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1. But the second condition can also be replaced by sum_over_k(T[i][k] * T[k][l])>0, but this is just an entry of the matrix T*T (if you consider T as a matrix). The OR can then be replayed by adding T to that result, so we just have to check if n-1 values of the row i of T*T+T are greater than zero, to see whether i is king. This is exactly what my function does.

(This is MATLAB, so the indices are 1-based.)

The MATLAB matrices should be encoded with semicolons as line delimiters:

[[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]] 
share|improve this answer
    
You can probably save a few bytes taking the number of contestants as input, instead of doing size(T,1) – Luis Mendo Mar 28 at 22:06
    
Thank you, somehow I did not notice=) – flawr Mar 29 at 8:17

Python using numpy, 54 bytes

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

Takes in a numpy matrix, outputs a numpy row matrix of 0-based indices.

Another way to think of a king is as a contestant for which all contestants are in the union of the king, the people the king beat, and the people those people beat. In other words, for every contestant, there is a path of length at most 2 from the king to them among the "beat" relation.

The matrix I + M + M*M encodes the numbers of paths of 0, 1, or 2 steps from each source to each target. A player is a king if their row of this matrix has only positive entries. Since 0 is Falsey, all tells us if a row is all nonzero. We apply this to each row and output the indices of the nonzero results.

share|improve this answer
    
Looks exactly like my approach but with a differnt interpretation, interesting=) – flawr Mar 28 at 19:19

MATL, 12 10 9 bytes

Xy+HY^!Af

Input is: first the number of contestants, and on a separate line a matrix with rows separated by semicolons. Output is 1-based.

For example, the fifth test case has input

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

and the last test case has 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]

Try it online!

Explanation

Xy    % implicit 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
share|improve this answer
1  
MATL < Jelly \m/ – flawr Mar 29 at 17:38

JavaScript (ES6), 83 bytes

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
share|improve this answer
    
You can save 1 with 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) but it means you have to output 1-indexed which is a serious bummer – Charlie Wynn Mar 29 at 13:55

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)

Call using:

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

watchout because output is 1-indexed (saved a few bytes not trying to filter out 0s vs falses)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.