Fête LAN de l'Avènement du Code Day

Jour 23 : Soirée LAN

Repo Github - Solutions

Le défi d'aujourd'hui était plutôt couru et assez simple (ou du moins la première partie l'était).

Partie 1 :

Rassemblez toutes les connexions en trios où l'un des triangles informatiques commence par t. Aussi simple que cela, comptez le nombre de triangles.

Pour y parvenir, nous créons un mappage de nœud -> connexions (voisins) , donc notre objet connexions ressemblerait à :

connections = {
    'kh': {'tc', 'dr'},
    'tc': {'kh', 'dr', 'zx'},
    'dr': {'kh', 'tc', 'xy'},
    'zx': {'tc'},
    'xy': {'dr', 'tz'},
    'tz': {'xy'}
}

Pour gagner les trios, nous pouvons parcourir les connexions et récupérer leurs voisins - rappelez-vous qu'en Python, le nœud dans les connexions bouclera sur les clés et ne renverra pas les valeurs. Pour accéder aux valeurs, nous devons utiliser les clés (nœud) pour y accéder via un index connexions[nœud].

Pour chaque paire de nœuds voisins, il génère des combinaisons. Par exemple :

Si node = 'kh' et voisins = {'tc', 'dr'}, les paires sont ('tc', 'dr'). Il vérifie si les deux voisins (voisin1 et voisin2) sont également connectés entre eux (via connexions[voisin1]).

S'ils sont connectés, un triangle existe entre le nœud, le voisin1 et le voisin2.
Le triangle est trié et ajouté à un ensemble pour éviter les doublons.

Recherchez ensuite toutes les connexions dont l'un des nœuds commence par t en utilisant

triangles_with_t = [triangle for triangle in triangles if any(
    node.startswith('t') for node in triangle)]

Partie 2

Dans la partie 2, nous devons trouver le plus grand ensemble d'ordinateurs interconnectés. Lorsque vous travaillez avec une configuration de type graphique, les nœuds interconnectés que nous appelons une clique.

Décomposons cela en utilisant l'algorithme de Bron-Kerbosch. L'algorithme de Bron-Kerbosch est utilisé pour trouver les plus grands groupes (appelés cliques) dans un graphique. Dans ce contexte, un graphe n'est qu'un ensemble de nœuds (comme des ordinateurs) reliés par des arêtes (connexions). Voici comment fonctionne l'algorithme et son lien avec la résolution de notre puzzle.

Qu'est-ce qu'une clique ?

Une clique est un groupe de nœuds où chaque nœud est directement connecté à tous les autres nœuds.

Imaginez que vous êtes à une fête, tout le monde connaît tout le monde dans le groupe. Si même une personne ne connaît personne d’autre, ce n’est pas une clique.

Dans notre puzzle, le but est de trouver le plus grand groupe d'ordinateurs interconnectés lors de la LAN party. Ce groupe est la plus grande clique.

Qu'est-ce qu'un sous-ensemble ?

Un sous-ensemble est une partie plus petite d'un groupe plus grand, par exemple :

Si la plus grande clique est (A,B,C,D), alors les plus petits sous-ensembles pourraient êtreA,B,CorB C D` là où ils sont tous connectés. Ces sous-ensembles sont toujours des cliques car tous les nœuds du sous-ensemble sont connectés.

Pourquoi utiliser l’algorithme de Bron-Kerbosch ?

Trouver la plus grande clique par force brute (en essayant tous les groupes possibles) est lent pour les entrées volumineuses. Par exemple, s'il y a 3 000 ordinateurs, il y a des milliards de groupes possibles à vérifier.

L'algorithme de Bron-Kerbosch accélère ce processus en :

• Commencer par des groupes plus petits (sous-ensembles) et les élargir.

• S'arrêter tôt lorsqu'un groupe ne peut pas devenir une clique plus grande.

• Éviter les vérifications répétées des mêmes sous-ensembles.

Comment ça marche ?

L'algorithme de Bron-Kerbosch fonctionne de manière récursive, ce qui signifie qu'il continue de s'appeler pour créer des cliques étape par étape. Voici comment cela fonctionne :

Entrée :
R : Un groupe de nœuds qui pourraient former une clique (commence vide).
P : Une liste de nœuds qui peuvent encore rejoindre la clique (commence par tous les nœuds).
X : Une liste de nœuds que nous avons déjà vérifiés (commence vide).

Étapes :
Si P et X sont tous deux vides :
R est une clique maximale (vous ne pouvez pas y ajouter plus de nœuds). En conséquence, enregistrez R.

Sinon :
Choisissez un nœud dans P et ajoutez-le à R.
Mise à jour ? et ? pour inclure uniquement les nœuds connectés au nouveau R.

Appelez à nouveau l'algorithme avec les nouveaux R, P et
X.

Une fois terminé, déplacez le nœud de P à X (c'est traité).

Cela se répète jusqu'à ce que tous les nœuds soient traités, garantissant que toutes les cliques sont trouvées sans vérifications redondantes.

Comment cela résout-il le puzzle ?

Entrée : disons que nous avons une liste de connexions informatiques, comme :

python
AB
AC
B-C
BD
C-D

Ces connexions représentent un graphique où les nœuds (ordinateurs) sont reliés par des arêtes (fils).

Objectif : Trouver le plus grand groupe d'ordinateurs où chacun est directement connecté à tous les autres ordinateurs.

Processus :

L'algorithme commence par des groupes plus petits (sous-ensembles) et essaie de les transformer en cliques.
Cela s’arrête si un groupe ne peut plus grandir (cliques maximales).

Parmi toutes les cliques, il identifie la plus grande.

Sortie :
Pour l'exemple, la plus grande clique est
{B,C,D}.

Et les sous-ensembles ?
Dans le contexte du puzzle :

Les sous-ensembles d'une clique (par exemple {B,C} de {B,C,D}) ne sont pas intéressants car ils sont plus petits que la plus grande clique.

L'algorithme évite les vérifications redondantes de sous-ensembles en gardant une trace des nœuds traités (X).

Résumer:

Clique : Un groupe où chaque nœud est connecté à tous les autres nœuds.

Sous-ensemble : Un groupe plus petit issu d'une clique plus grande.

Bron-Kerbosch :
Trouve toutes les cliques dans un graphique.
Se concentre sur les plus grandes cliques sans perdre de temps sur des sous-ensembles plus petits.

Solution du puzzle :
Utilisez l'algorithme pour trouver le plus grand groupe d'ordinateurs interconnectés lors de la soirée LAN.

J'espère que cela vous a aidé à comprendre la solution, à en apprendre davantage sur l'algorithme de Bron-Kerbosch et à apprendre quelque chose de nouveau sur la syntaxe Python.

Comme toujours, n'hésitez pas à me suivre ou à me contacter sur Twitter.

Le résultat est la plus grande clique, qui est la réponse à l'énigme.

Autres points Python utiles :

L'appel récursif de Bron-Kerbosch, passe dans certaines propriétés modifiées r | nœud, p & connexions[nœud].

En Python

r | node - crée un nouvel ensemble avec tous les nœuds de l'ensemble actuel de nœuds dans la clique que nous construisons (r), plus un autre nœud que nous ajoutons.

p & connexions[node] - Cela crée un nouvel ensemble qui contient uniquement les nœuds qui :

• Sont dans les deux p (l'ensemble des nœuds qui peuvent encore faire partie de la clique).

• Sont également dans le nœud de connexions.

Explication :
& est l'opérateur d'intersection pour les ensembles.
connexions[node] est l'ensemble des nœuds directement connectés au nœud.

p & connexions[nœud] signifie « trouver les nœuds communs entre p et connexions[nœud] ».

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!