¿Quién es el rey del torneo?

13

Antecedentes

Considere un torneo round-robin, en el que cada participante juegue un juego contra cualquier otro participante. No hay sorteos, por lo que cada juego tiene un ganador y un perdedor. Un concursante A es un rey del torneo, si para cada otro competidor B , ya sea A venció B , o A vencer a otro concursante C que a su vez latido B . Se puede demostrar que cada torneo tiene al menos un rey (aunque puede haber varios). En este desafío, tu tarea es encontrar a los reyes de un torneo determinado.

Entrada y salida

Su entrada es una N × Nmatriz booleana T, y opcionalmente el número N ≥ 2de concursantes. Cada entrada T[i][j]representa el resultado del juego entre los concursantes iy j, con el valor 1 representa una victoria para iy 0 una victoria para j. Tenga en cuenta que T[i][j] == 1-T[j][i]si i != j. La diagonal de Tconsiste en 0s.

Su salida será la lista de reyes en el torneo que Trepresenta, usando indexación basada en 0 o en 1. El orden de los reyes es irrelevante, pero no debe haber duplicados.

Tanto la entrada como la salida se pueden tomar en cualquier formato razonable.

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

Estos casos de prueba usan indexación basada en 0. Para la indexación basada en 1, incremente cada valor de salida.

 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
fuente
(¿Hay algún tiempo de ejecución o límites de memoria?) No importa. Entendí completamente mal la especificación.
Dennis
@ Dennis Nope. Mientras su programa funcione teóricamente con tiempo y memoria ilimitados, está bien.
Zgarb
Solo para aclarar: T [a] [b] es la misma coincidencia que T [b] [a] pero se ve desde el ángulo opuesto, entonces T [a] [b] ==! T [b] [a]
edc65
@ edc65 Esa es una buena observación. Lo edité en el desafío.
Zgarb

Respuestas:

9

Matlab, 36 35 29 bytes

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

Averigüemos si ies un rey. Luego para cada uno jel valor T[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1. Pero la segunda condición también se puede reemplazar por sum_over_k(T[i][k] * T[k][l])>0, pero esto es solo una entrada de la matriz T*T(si se considera Tcomo una matriz). El ORentonces se pueden reproducir mediante la adición Ta ese resultado, por lo que sólo tenemos que comprobar si n-1los valores de la fila ide T*T+Tson mayores que cero, para ver si ies el rey. Esto es exactamente lo que hace mi función.

(Esto es MATLAB, por lo que los índices están basados ​​en 1).

Las matrices de MATLAB deben codificarse con punto y coma como delimitadores de línea:

[[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]]
falla
fuente
Probablemente pueda guardar algunos bytes tomando la cantidad de concursantes como entrada, en lugar de hacerlosize(T,1)
Luis Mendo
7

Jalea, 13 12 11 bytes

a"€¹o/€oḅ1M

La salida está basada en 1. Pruébalo en línea!

Alternativamente, usando operadores bit a bit en lugar de manipulación de matriz:

×Ḅ|/€|ḄBS€M

Nuevamente, la salida se basa en 1. Pruébalo en línea!

Antecedentes

Para concursante A , podemos encontrar toda B tal que A venció C latido B mediante la adopción de todas las filas que corresponden a un C tal que C vencer a una . IFR el B º entrada del C º es 1 , tenemos que C venció B .

Si calculamos los OR lógicos de todas las entradas correspondientes de las columnas seleccionadas, obtenemos un único vector que indica si A venció a B por transitividad o no. Finalmente, ORing el vector resultante con la fila correspondiente de la matriz de entrada le da a Booleanos si A vence a B , ya sea por transitividad o directamente.

Repitiendo esto para cada fila, contamos el número de 1 en cada vector, por lo tanto, calculamos la cantidad de concursantes cada latido A. Los recuentos máximos corresponden a los reyes del torneo.

Cómo funciona

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
fuente
1
Ya sabes, la gente sigue publicando estos y diciendo x "bytes", pero ¿está realmente "ḅ" codificado en 1 byte en alguna codificación estándar? Lo sentimos, pero encuentro que estos lenguajes basados ​​en la pila hipercondensados ​​son completamente poco interesantes porque se siente como una trampa asignar solo cada función concebible a un carácter unicode.
MattPutnam
2
@MattPutnam Jelly usa su propia codificación personalizada. (Además, no está basado en la pila)
un spaghetto
2
@MattPutnam He tenido sentimientos similares, pero no restan nada al golf tradicional. Nadie desprecia los idiomas tradicionales simplemente porque existen, y a diferencia de otros sitios de SE, esto no tiene exactamente el 'esta respuesta es obviamente mejor que esa respuesta'. Además, aunque técnicamente no están prohibidos, no alteran el lenguaje para admitir una pregunta (aunque pueden, después del hecho, darse cuenta de un atajo útil para preguntas futuras y hacer que sea una operación).
corsiKa
¿Por qué estos algoritmos dan salida a los reyes?
xnor
@Dennis Ahora veo, es básicamente una multiplicación de matriz booleana realizada mediante lógica o aritmética de bits. ¿La multiplicación de matriz real no sería más corta?
xnor
2

Python usando numpy, 54 bytes

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

Toma una matriz numpy, genera una matriz de fila numpy de índices basados ​​en 0.

Otra forma de pensar en un rey es como un concursante para el cual todos los concursantes están en la unión del rey, la gente que el rey venció y la gente que esa gente venció. En otras palabras, para cada concursante, hay un camino de longitud como máximo 2 desde el rey hasta ellos entre la relación "beat".

La matriz I + M + M*Mcodifica el número de rutas de 0, 1 o 2 pasos desde cada fuente a cada destino. Un jugador es un rey si su fila de esta matriz solo tiene entradas positivas. Como 0 es Falsey, allnos dice si una fila no es cero. Aplicamos esto a cada fila y mostramos los índices de los resultados distintos de cero.

xnor
fuente
Se ve exactamente como mi enfoque pero con una interpretación diferente, interesante =)
error
2

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
Neil
fuente
Puede guardar 1 con 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) pero significa que tiene que generar 1 indexado, lo cual es un fastidio grave
Charlie Wynn
2

MATL , 12 10 9 bytes

Xy+HY^!Af

La entrada es: primero el número de concursantes, y en una línea separada una matriz con filas separadas por punto y coma. La salida está basada en 1.

Por ejemplo, el quinto caso de prueba tiene entrada

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

y el último caso de prueba tiene entrada

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]

Pruébalo en línea!

Explicación

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
fuente
1
MATL <Jelly \ m /
flawr
1

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)

Llamar usando:

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

cuidado porque la salida está indexada en 1 (se guardaron algunos bytes sin intentar filtrar 0s frente a falsos)

Charlie Wynn
fuente