Contexte
Considérez un tournoi à la ronde, dans lequel chaque concurrent joue un match contre tous les autres concurrents. Il n'y a pas de tirage, donc chaque match a un gagnant et un perdant. Un concurrent A est un roi du tournoi, si pour tous les concurrent B , soit A battu B ou A battre un autre concurrent C qui , à son tour battre B . Il peut être démontré que chaque tournoi a au moins un roi (bien qu'il puisse y en avoir plusieurs). Dans ce défi, votre tâche consiste à trouver les rois d'un tournoi donné.
Entrée et sortie
Votre entrée est une N × N
matrice booléenne T
, et éventuellement le nombre N ≥ 2
de candidats. Chaque entrée T[i][j]
représente le résultat du jeu entre les concurrents i
et j
, avec la valeur 1 représentant une victoire pour i
et 0 une victoire pour j
. Notez que T[i][j] == 1-T[j][i]
si i != j
. La diagonale de se T
compose de 0.
Votre résultat sera la liste des rois du tournoi qui T
représente, en utilisant une indexation basée sur 0 ou 1. L'ordre des rois n'est pas pertinent, mais il ne devrait pas y avoir de doublons.
L'entrée et la sortie peuvent être prises dans n'importe quel format raisonnable.
Règles et notation
Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.
Cas de test
Ces cas de test utilisent une indexation basée sur 0. Pour une indexation basée sur 1, incrémentez chaque valeur de sortie.
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]
Réponses:
Matlab,
36 3529 octetsVoyons si
i
c'est un roi. Puis pour chacunj
la valeurT[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1
. Mais la deuxième condition peut également être remplacée parsum_over_k(T[i][k] * T[k][l])>0
, mais ce n'est qu'une entrée de la matriceT*T
(si vous la considérezT
comme une matrice). LeOR
peut ensuite être rejoué en ajoutantT
à ce résultat, il nous suffit donc de vérifier si lesn-1
valeurs de la lignei
deT*T+T
sont supérieures à zéro, pour voir sii
est roi. C'est exactement ce que fait ma fonction.(Il s'agit de MATLAB, donc les indices sont basés sur 1.)
Les matrices MATLAB doivent être codées avec des points-virgules comme délimiteurs de ligne:
la source
size(T,1)
Gelée,
131211 octetsLa sortie est basée sur 1. Essayez-le en ligne!
Alternativement, en utilisant des opérateurs au niveau du bit au lieu de la manipulation de tableaux:
Encore une fois, la sortie est basée sur 1. Essayez-le en ligne!
Contexte
Pour concurrent A , nous pouvons trouver tous les B tels que A TIRE C battement B en prenant toutes les lignes qui correspondent à un C tel que C a battu A . ICR le B e entrée du C e est 1 , nous avons que C a battu B .
Si nous calculons les OR logiques de toutes les entrées correspondantes des colonnes sélectionnées, nous obtenons un vecteur unique indiquant si A bat B par transitivité ou non. Enfin, ORing le vecteur résultant avec la ligne correspondante de la matrice d'entrée donne des booléens que ce soit A battu B , soit par transitivité ou directement.
En répétant cela pour chaque ligne, nous comptons le nombre de 1 dans chaque vecteur, calculant ainsi le nombre de candidats à chaque battement A. Le nombre maximum correspond aux rois du tournoi.
Comment ça fonctionne
la source
Python utilisant numpy, 54 octets
Prend une matrice numpy, produit une matrice de lignes numpy d'indices basés sur 0.
Une autre façon de penser à un roi est en tant que candidat pour lequel tous les candidats sont dans l'union du roi, du peuple que le roi a battu et du peuple que ce peuple a battu. Autrement dit, pour chaque concurrent, il y a un chemin de longueur au plus 2 du roi vers eux parmi la relation "beat".
La matrice
I + M + M*M
code les nombres de chemins de 0, 1 ou 2 pas de chaque source à chaque cible. Un joueur est un roi si sa rangée de cette matrice n'a que des entrées positives. Puisque 0 est Falsey,all
nous indique si une ligne est entièrement différente de zéro. Nous appliquons cela à chaque ligne et produisons les indices des résultats non nuls.la source
JavaScript (ES6), 83 octets
la source
MATL ,
12109 octetsL'entrée est: d'abord le nombre de candidats, et sur une ligne séparée une matrice avec des lignes séparées par des points-virgules. La sortie est basée sur 1.
Par exemple, le cinquième cas de test a une entrée
et le dernier cas de test a une entrée
Essayez-le en ligne!
Explication
la source
Javascript
136131121112 octetsAppelez en utilisant:
Attention car la sortie est indexée sur 1 (enregistré quelques octets sans essayer de filtrer les 0 contre les fausses)
la source