Pour la partie 2, j'ai utilisé 2 propriétés de l'input
- les labels sont composés de deux lettres entre 'a' et 'z', ça me permet de parser plus rapidement et de faire quelques optimisations. Notamment pouvoir me passer de table de hash.
- et la plus importante: chaque sommet a exactement 13 voisins et on cherche une clique de taille 13.
Grace à la seconde propriété, pour trouver une clique maximum, je dois trouver un sommet v de voisinage N(v) tels que tous les sommets u de N(v) à l'exception d'un, qu'on appellera z, ont exactement 11 voisins en commun avec N(v). La clique sera donc {v} U N(v) \ {z}.
45 microsecondes pour les deux parties. Je pense pouvoir faire mieux en utilisant une représentation du voisinage par bitset. J'y travaille.
[^] # Re: jour 23 - cracra
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 2.
Pour la partie 2, j'ai utilisé 2 propriétés de l'input
- les labels sont composés de deux lettres entre 'a' et 'z', ça me permet de parser plus rapidement et de faire quelques optimisations. Notamment pouvoir me passer de table de hash.
- et la plus importante: chaque sommet a exactement 13 voisins et on cherche une clique de taille 13.
Grace à la seconde propriété, pour trouver une clique maximum, je dois trouver un sommet
vde voisinageN(v)tels que tous les sommetsudeN(v)à l'exception d'un, qu'on appelleraz, ont exactement 11 voisins en commun avecN(v). La clique sera donc{v} U N(v) \ {z}.45 microsecondes pour les deux parties. Je pense pouvoir faire mieux en utilisant une représentation du voisinage par
bitset. J'y travaille.