Contexte
Au moment d'écrire ces lignes, le problème P vs NP n'est toujours pas résolu, mais vous avez peut-être entendu parler du nouveau document de Norbert Blum prétendant prouver que P! = NP, qui est déjà soupçonné d'être erroné (mais nous verrons).
Le problème discuté dans cet article est le problème de la clique . C'est du moins ce que j'ai lu dans un article de journal, alors corrigez-moi si je me trompe, mais en tout cas, j'aimerais que vous écriviez un programme qui résout la variante suivante:
La tâche
Supposons que nous ayons une grande école avec beaucoup d'étudiants. Chacun de ces élèves a des amis dans cette école. Une clique d'étudiants est un groupe composé uniquement d'étudiants qui sont amis entre eux .
Votre programme recevra des paires d'étudiants amis comme contribution. À partir de ces informations, le programme doit trouver la taille de la plus grande clique . Les étudiants sont identifiés par des identifiants entiers .
Si vous préférez les termes mathématiques, cela signifie que vous êtes alimenté par les bords d'un graphique non orienté, identifié par deux nœuds chacun.
Contribution
Votre entrée sera une liste non vide de paires entières positives, par exemple [[1,2],[2,5],[1,5]]. Vous pouvez prendre cette entrée sous n'importe quelle forme sensible, par exemple comme un tableau de tableaux, comme des lignes de texte contenant deux nombres chacune, etc ...
Sortie
La sortie attendue est un nombre unique n >= 2: la taille de la plus grande clique. Avec l'exemple saisi ci-dessus, le résultat serait 3, car tous les élèves ( 1, 2et 5) sont amis les uns avec les autres.
Cas de test
[[1,2]]
=> 2
[[1,2],[3,1],[3,4]]
=> 2
[[1,2],[2,5],[1,5]]
=> 3
[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])
[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])
[[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52],
[52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565],
[1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860],
[1296,1860],[1860,52],[711,1639]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])
Vous pouvez utiliser cette implémentation de référence (stupide) (imprime une sortie supplémentaire avec -dindicateur) pour vérifier les résultats d'autres cas de test.
Les règles
- Votre programme n'a pas besoin d'un résultat défini sur une entrée non valide. Vous pouvez donc supposer que:
- vous obtiendrez toujours au moins une paire d'identifiants
- chaque paire se compose de deux identifiants différents
- aucune paire n'apparaît deux fois (l'échange des emplacements des identifiants serait toujours la même paire)
- Votre algorithme n'est pas autorisé à définir une limite supérieure sur la taille d'entrée. Les limitations purement techniques et les limitations fixées par votre langage / environnement (comme la taille de la pile, le temps de calcul, etc.) sont bien sûr inévitables.
- Les failles standard sont interdites.
- C'est le code-golf , donc le code le plus court, mesuré en octets, gagne.
- Si votre algorithme a une complexité temporelle polynomiale, vous marquez
-1immédiatement quelle que soit la taille de votre code, mais dans ce cas, vous souhaiterez peut-être soumettre votre solution ailleurs. ;)
la source
-1c'est bien mérité ;)Réponses:
Gelée ,
15 1816 octets+3 octets pour corriger les bugs dans ma méthode.
-2 octets grâce aux miles (notant que n × (n-1) ÷ 2 = nC2 )
Un lien monadique prenant la liste des amitiés (bords) et renvoyant un entier.
Essayez-le en ligne! forme le jeu de puissance des bords en mémoire et est donc inefficace à la fois dans l'espace et dans le temps (oui, c'est O (2 n ) )!
Comment?
la source
Mathematica, 34 octets
Fondamentalement, FindClique fait le travail et "trouve une plus grande clique dans le graphique g."
Tout le reste convertit la liste d'entrées en graphique
Contribution
Sortie
Contribution
Sortie
merci @Kelly Lowder pour -10 octets
la source
Tr[1^#&@@FindClique[#<->#2&@@@#]]&FindCliqueಠ ___ ಠGelée , 20 octets
Essayez-le en ligne!
Bien sûr, cela ne mérite pas le million: p
Cela aurait battu Pyth, sinon pour le
µ(...)µet 2 octetsÐf.la source
J , 36 octets
Essayez-le en ligne!
Exécute dans le temps O (2 n ) où n est le nombre de paires.
Une solution plus rapide pour 65 octets est
Essayez-le en ligne!
Explication
la source
Pyth, 19 octets
Essayez-le ici.
la source
Python 2 , 180 octets
Essayez-le en ligne!
-2 grâce à shooqie .
-1 merci à M. Xcoder .
-3 grâce à récursif .
la source
lenà une variable(x not in y)signifie0**(x in y).0**par-~-.Pyth, 28 octets
Essayez-le en ligne
Explication
la source
Python 3 ,
162159 octetsEssayez-le en ligne!
La fonction c prend des sommets sous la forme d'un ensemble de tuples
triés({(x, y), ...} où x est inférieur à y).Une fonction appelée "entrée" se trouve dans l'en-tête TIO pour tester avec des données au format liste de listes non triées. Si clique, renvoie la longueur. Si ce n'est pas clique, renvoie la taille maximale de clique des sommets, moins un sommet pour chaque sommet des sommets. Dépasse le temps du dernier cas de test dans TIOMise à jour: "ou (z, y) dans x" partie ajoutée pour supprimer la dépendance au tri "f = lambda x: {i pour s dans x pour i dans s}" au lieu de itertools.chain enveloppé dans l'ensemble.
-minus 3 octets grâce à @Jonathan Allen
la source
c, vous pouvez donc supprimerc=(vous devez mettrec=\à la fin de l'en-tête et placer lelambdaen haut du bloc de code pour TIO)ségalement vous débarrasser de et remplacers(...)en{*...}permettant également la suppression de certains espaces.05AB1E , 19 octets
Essayez-le en ligne!
la source
Gelée , 28 octets
Essayez-le en ligne!
Solution plus rapide capable de résoudre le dernier cas de test en une seconde sur TIO.
la source
npeut n'apparaître que dans les bases :)Java + Guava 23,0, 35 + 294 = 329 octets
Cet algorithme n'est pas graphique, mais génère à la place toutes les combinaisons de paires, d'une taille spécifique. Je charge toutes les combinaisons de paires dans un multiset et vérifie qu'elles ont toutes la taille attendue (le nombre d'entrées uniques - 1). S'ils le font, j'ai trouvé une clique et je vais en chercher une plus grande.
Depuis la bibliothèque Guava, j'utilise la nouvelle
combinationsméthode et le type de collection d'outilsMultiset.Non golfé
la source
xest polynomiale " <- êtes-vous sûr? Je suppose que c'est la méthode utilisée . La valeur de retour est unAbstractSetavec un itérateur, et laforboucle suivante appellera cet itérateurx!fois si je ne me trompe pas ...x < n(avecnla taille complète de l'ensemble d'entrée), ce n'estn!/(x!(n-x)!)toujours pas polynomial :)combinationsméthode qui estX^n(ce qui est tout à fait possible), je peux l'obtenir? En attendant, je retire ma réclamation du "-1".Python 2 , 102 octets
Essayez-le en ligne!
la source
6502 code machine (C64),
774703 octets(Je viens dû à ce faire, mon C64 peut tout faire ... hehe)
hexdump:
Démo en ligne
Utilisation: Commencez par
sys49152, puis entrez les paires une par ligne comme par exempleL'arrière - plan n'est pas géré pendant la saisie (mais si vous l'utilisez
vice, copiez et collez simplement votre saisie dans l'émulateur). Saisissez une ligne vide pour démarrer le calcul.C'est trop grand pour publier une liste explicative de démontage ici, mais vous pouvez parcourir la source d'assemblage de style ca65 . L'algorithme est très inefficace, il génère toutes les permutations possibles des nœuds et avec chacun d'eux construit goulûment une clique en vérifiant tous les bords. Cela permet une efficacité d'espace de O (n) (un peu important sur une machine avec ce petit RAM), mais a une efficacité d'exécution horrible (*) . Les limites théoriques sont jusqu'à 256 nœuds et jusqu'à 8192 bords.
Il existe une version plus grande (
883805 octets) avec de meilleures fonctionnalités:Démo en ligne
Parcourir la source
(*) Le dernier cas de test prend entre 12 et 20 heures (je dormais quand il a finalement fini). Les autres cas de test se terminent au pire en quelques minutes.
la source