Guillaume.B a écrit 54 commentaires

Je suis assez d'accord avec toi.

Le problème du jour 17 n'est pas vraiment l'assembleur mais plutôt qu'une grosse partie du calcul peut être fait à l'avance (à la compilation).
Mais, la majorité des problèmes ne sont pas ainsi, même si les auteurs des solutions ont tendance à faire de grosses suppositions sur les inputs.

Je pense que ça doit beaucoup dépendre de la manière de mesurer le temps.
520 microsecondes juste pour lire l'input me parait excessivement lent.

Personnellement, je fais 1000 itérations de mon code et je prend le temps médian. Je ne prend pas en compte le temps de chargement du programme, ni le temps pour lire le fichier en mémoire (mais je prend en temps le compte pour faire le parsing).
J'utilise la fonction Instant::now et la méthode elapsed().
https://doc.rust-lang.org/std/time/struct.Instant.html

Mes temps n'ont rien de fantaisistes. Sur un salon Discord consacré à Rust, certains ont des solutions bien plus rapides que les miennes.

Sinon, pour ceux que ça intéresse, voici le dépôt des mes solutions.
https://github.com/gbagan/advent-of-code-rust

Oui, je suis assez d'accord avec toi au niveau de la difficulté de cette année.

Pour le jour 25, j'ai trouvé une petite astuce qui consiste à encoder la grille sur un entier de 32 bits.

Par exemple, pour la grille

#####
##.##
.#.##
...##
...#.
.....
.....

je vais encoder le nombre de # par colonnes par des séquences de 4 bits.
sous forme de liste, ça donne [1, 2, 0, 4, 3] (je retire 1 à chaque colonne car il y a forcément un # par colonne).
et sous forme d'entiers 0001_0010_0000_0100_0011

De même, pour une grille partant du bas.

.....
...#.
...#.
..##.
.###.
.###.
#####

J'encode par la liste [2, 4, 5, 7, 2] (j'ajoute 2 à chaque colonne pour la somme avec le complément fasse 7).
ce qui donne en binaire 0010_0100_0101_0111_0010

Du coup, si il y a un overlap entre 2 colonnes, la somme des 4 bits les représentant va dépasser 7 et le bit de poids fort va être 1.

Donc pour tester si deux grilles g1 et g2 matchent ensemble, il faut que
(x + y) & MASK == 0 où x est l'encodage de g1, y est l'encodage de g2 et MASK=0b1000_1000_1000_1000_1000.

9 microsecondes pour ce problème et 4.6 millisecondes pour le temps cumulés de tous les problèmes de cette année.

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.

Ce jour-ci était globalement assez facile. Il suffisait de suivre ce qu'on nous disait.
Par contre, je n'ai pas vraiment trouvé de manière d'optimiser la solution de manière globale.

J'ai surtout fait des micro-optimisations comme:
- utiliser un tableau de taille 19⁴ plutôt qu'une table de hash pour représenter les prix par quadruplet ainsi que les quadruplets déjà vu;
- utiliser les bons types d'entiers: u32 pour stocker les secrets, u16 pour stocker les prix et les différences.
- réutiliser le même tableau pour les quadruplets déjà vus entre chaque secret sans le réinitialiser en utilisant l'astuce d'affecter avec seen[index] = i et de tester si seen[index] == i où i est l'indice du secret qu'on est en train de traiter.

En parallélisant le tout, je suis arrivé à 1.7ms alors que j'étais à 70ms sur mon premier jet.

De souvenir, les 23èmes jours sont assez difficiles. Voyons voir ce que cela donne demain.

Le jour le plus compliqué pour moi jusqu'à présent. J'ai mis beaucoup de temps à comprendre l'énoncé.

L'idée pour résoudre le problème est de remarquer que la complexité (la valeur qu'on cherche) ne dépend que des paires consécutives de lettres dans une séquence.
L'ordre de ces paires n'importe où.
Donc au lieu de représenter la séquence par une chaîne à caractères, on va le représenter par un tableau qui a une paire donnée associe son nombre d’occurrences dans la séquence.
Cela fait un tableau de 11x11 pour les séquences du clavier numérique et 5x5 pour les séquences du clavier analogique.
Ensuite il faut écrire deux fonctions numpad_step et dirpad_step qui a une paire de touches (x, y) donnée respectivement par le clavier numérique et le clavier de direction, associe la séquence de lettres pour passer de x à y à la profondeur +1.
Étant donné un tableau d'occurrences pour la profondeur p, on peut trouver le tableau d’occurrences pour la profondeur suivante de la manière suivante.

Soit current le tableau d'occurrences pour la profondeur p
créer un tableau next de 25 éléments initialisés à 0  
pour x dans ['<', '>', 'v', '>', A']
    pour y dans ['<', '>', 'v', '>', A']
         pour chaque paire consécutive (x2, y2) de dirpad_step(x, y):
             next[(x2, y2)] += current[(x, y)]
renvoyer next

En optimisant un peu, je suis arrivé à 6 microsecondes de temps d'exécution.
J'ai essayé d'aller plus loin en remarquant qu'on pouvait précalculer à la compilation un tableau qui à chaque paire du clavier numérique associe la longueur pour obtenir cette paire à profondeur 2 et à profondeur 25.
Avec cette approche, je suis arrivé à 70 nanosecondes de temps d'exécution, sans utiliser de code unsafe et en restant générique sur l'input (je ne suppose par exemple pas que chaque ligne fait exactement 4 caractères).

Aujourd'hui, j'ai pas trouvé de manière maligne de faire la partie 2.
Du coup, brute-force.
Pour chaque sommet u du chemin, je regarde tous les sommets v à distance au plus 20 et je teste si dist[u] <= dist[v] - 100 - manhattan(u, v). Si c'est le cas, j'incrémente le compteur représentant le nombre de cheats.

Une remarque cependant: le graphe de la grille est juste un chemin entre S et E.
Du coup, ça simplifie le calcul des distances. Pas besoin de BFS, DFS ou Dijkstra.
On part de S et on suit le chemin jusqu'à arriver à E.

Pour la partie 2, j'ai parallélisé en utilisant des threads. 640 microsecondes (et 4ms en séquentiel). Mon plus long temps d'exécution de cet AOC 2024 pour l'instant.

Jusqu'à présent, je suis un peu déçu de cet AOC par rapport aux années précédentes.
A quelques exceptions, tous les problèmes peuvent se résoudre par brute-force. J'ai l'impression que c'était moins le cas dans les années précédentes.

Comme d'habitude, j'essaie de trouver le meilleur algorithme pour résoudre le problème même si ce n'est pas nécessaire.

Aujourd'hui, la structure donnée à utiliser m'a paru naturelle: les prefix trees (également appelés tries).

https://fr.wikipedia.org/wiki/Trie_(informatique)

J'ai passé pas mal de temps à bien optimiser mon implémentation.
Au début, j'avais également fait une fonction récursive avec cache mais de la programmation dynamique s'est avérée plus rapide (3x fois plus rapide pour être précis).

L'algo en pseudo-code est le suivant

fonction(trie, design):
   initialiser t un tableau de (len(design)+1) entiers à 0
   t[0] = 1
   pour i de 0 à len(design) - 1:
      pour chaque prefixe p de design[i..] dans trie:
         t[i + len(p)] += t[i]
   renvoyer t[design]

La structure de données trie permet de très efficacement trouver les préfixes d'un mot appartenant à une liste.
170 microsecondes partie + partie 2.

La première était un juste un parcours en largeur classique.

Pour la seconde partie, j'ai plusieurs idées de plus en plus efficaces.

• l'approche brute-force. Tester pour tous les moments t si on peut trouver un chemin alors que es t premiers bytes sont tombés. Ca fonctionne mais c'est assez long.

• l'approche recherche binaire/dichotomique. On part d'un intervalle [0, nombre de bytes], on teste pour la valeur au milieu de l'intervalle et on divise à l'intervalle par deux à chaque itération.
  Ca donne un algorithme en temps O(N log M) où N est la taille de la grille et M le nombre de bytes. 70 microsecondes pour mon implémentation.

• l'approche union-find. On part de la grille complètement remplie par les bytes. On calcule les composantes connexes. On retire progressivement les bytes dans le sens inverse et on met à jour les composantes en utilisant une structure union-find.
  https://fr.wikipedia.org/wiki/Union-find
  30 microsecondes pour mon implémentation.

• La dernière approche consiste encore de partir de la grille complètement remplie par les bytes et de retirer progressivement les bytes dans le sens inverse.
  Sauf que cette fois ci, on va faire un parcours en profondeur depuis le sommet de départ, noter les sommets visités.
  Pour chaque byte (dans le sens inverse), si celui est adjacent à au moins un sommet déjà visité, on reprend le parcours en profondeur à partir de la position du byte en gardant les sommets déjà visités. On s'arrête dès que le sommet final est visité.
  Ca donne un algorithme en temps linéaire.
  14 microsecondes pour mon implémentation.

On peut utiliser un Dijkstra classique mais pas sur le graphe classique de la grille.
On peut construire un graphe où les nœuds sont des couples (sommet de la grille, direction) où direction est horizontal ou vertical.

La partie 1 est assez simple. On peut faire une optimisation en remarquant que diviser par 2^n revient à décaler les bits de n donc de faire l'opération a >> n.

Pour la partie 2, j'ai regardé la sortie pour les première valeurs de a.
On remarque la chose suivante.
La dernière valeur de sortie est déterminée par les 3 bits de poids forts.
L'avant-dernière par les 6 bits de poids forts.
L'avant-avant-dernière par les 9 bits de poids forts
etc

Donc on peut chercher les 3 bits de poids forts en simulant le programme avec a variant de 0 à 7 et pour chaque valeur ai dont la sortie correspond au dernier élément du programme chercher les 3 bits suivants en prenant a = ai * 8 + j pour j variant de 0 à 7.
On fait ainsi de suite en faisant des appels récursifs.
Voici le code de cette partie en Rust.
Comme on regarde d'abord les bits de poids forts, on est garanti de trouver sur une solution minimale si elle existe.
J'ai compté qu'il y avait 5 quines possibles pour mon entrée.

fn quine(program: &[u64], a: u64, idx: usize) -> Option<u64> {
    if idx == 0 {
        return Some(a)
    }
    for i in 0..8 {
        let ai = a << 3 | i;
        if let Some(output) = run_first_value(program, ai, 0, 0) {
            if output == program[idx-1] {
                if let Some(q) = quine(program, ai, idx-1) {
                    return Some(q)
                }
            }
        }
    }
    None
}

Oui, facile si on connaît Dijkstra.

Pour la partie 2, on peut lancer un second Dijkstra en partant du sommet final.
J'ai préféré faire un parcours en profondeur (beaucoup plus rapide qu'un Dijkstra) et remonter jusqu'au sommet de départ en suivant les poids données par le Dijkstra de la partie 1.
260 microsecondes pour les 2 parties, la partie 2, utilisant les informations de la partie 1, ne prend que 5 microsecondes.
Je vais voir si je peux optimiser mon Dijkstra mais je ne vois pas trop comment faire pour l'instant.

En consultant d'autres forums, je suis tombé sur une idée que j'ai trouvé astucieuse et élégante.

L'idée est que la position horizontale des robots cycle chaque 101 secondes et celle verticale chaque 103 secondes.
Donc, le nombre de robots par colonne est le même pour deux instants qui ont le même module 101.
De même , le nombre de robots par ligne est le même pour deux instants qui ont le même modulo 103.

Si on peut détecter si un instant t fait apparaître l'image juste en consultant le nombre de robots par ligne ou juste le nombre de robots par colonne alors il suffit de faire ce test seulement pour les instants de 0 à 101 (pour les colonnes) et de 0 à 103 (pour les lignes).
A partir de ça, on est capable d'extrapoler le moment t où l'image apparaît en utilisant le théorème des restes chinois.
Plus précisément, notons t le moment où l'image apparait
si t1 est le moment entre 0 et 101 qui a le même modulo 101 que t
et t2 est le moment entre 0 et 103 qui a le même modulo 103 que t.

Alors t = (t1 * 51 * 103 + t2 * 51 * 101) % (101 * 103)

Pour tester si l'image apparaît en regardant les colonnes, j'ai vu plusieurs approches notamment calculer la variance mais c'est un peu long à calculer.
J'ai essayé de calculer la somme des carrés des nombres de robots qui apparaissent sur chaque colonne mais c'est également un peu long à calculer.
Finalement, j'ai utilisé l'approche suivante.
Je divise mes colonnes en 4 parties Q1 | Q2 | Q3 | Q4 et comme l'image est assez dense et qu'elle fait moins de la moitié des colonnes, j'en déduis que le nombre de robots dans Q1 ou dans Q4 sera assez faible. Donc, je cherche l'instant t entre 0 et 101 qui minimise ce nombre.
Je fais de même pour les lignes.

50 microsecondes pour mon implémentation.

La partie 1 est assez facile car on peut calculer directement la position d'un robot à 100ème seconde sans avoir à calculer les précédentes secondes.

La partie 2 n'est pas très claire et il faut d'abord visualiser l'image.
En discutant un peu, il y a plein de manières différentes de détecter cette image mais pour ma part, j'ai utilisé l'heuristique suivante.
J'ai cherché le premier moment où toutes les positions de robots étaient distinctes.

Pour cela, j'ai utilisé un tableau grid de tailles 101x103 et pour savoir si les positions sont distinctes à la seconde i, je regarde pour chaque position (px, py) de robots, si grid[px*101+py] == i. Si c'est le cas, j'ai deux positions non distinctes.
Sinon, j'affecte grid[px*101+py] = i.

L'avantage de cette méthode est que je peux réutiliser mon tableau à chaque itération sans avoir à le réinitialiser ou en créer un autre.

J'ai également parallélisé le processus avec des threads.
Un thread va travailler sur un segment de 20 secondes. Si il trouve une solution, on s'arrête. Sinon, il va travailler sur le prochain segment de 20 secondes pas encore attribué à un thread.

440 microsecondes pour les deux parties.

Ouh la, vous avez utilisé l'artillerie lourde :)

Comme c'est un système de 2 équations à 2 inconnus, j'ai utilisé la méthode de Kramer.
Désolé pour le nommage des variables.

fn tokens(ax: i64, ay: i64, bx: i64, by: i64, px: i64, py: i64) -> i64 {
    let det1 = bx * py - by * px;
    let det2 = bx * ay - ax * by;
    if det1 % det2 != 0 {
        return 0;
    }
    let x = det1 / det2;
    let p = px - x * ax;
    if p % bx != 0 {
        return 0;
    }
    let y = p / bx;
    if x < 0 || y < 0 {
        return 0;
    }
    3 * x + y
}

200 microsecondes pour la partie 1 + partie 2, je suis assez fier de moi au niveau des optimisations.
L'idée consiste pour chaque lettre non déjà parcourue de faire un parcours en profondeur (plus rapide qu'en largeur) et de calculer en une seule passe l'aire, le périmètre et le nombre de cotés.

• Comme pour la question 10, j'utilise un tableau à une seule dimension avec des symboles # sur les bords. Ce qui me permet de faire grid[index-1], grid[index+1], grid[index+width], grid[index-width] pour accéder aux sommets adjacents tout en garantissant que je ne sorte pas de la grille.
• Pour éviter de créer un nouveau tableau ou autre structure pour noter les sommets déjà visités, j'utilise le bit de poids fort de chaque élément de ma grille. C'est possible car les éléments sont sur 8 bits et seuls 7 bits sont utilisés en ASCII.
• Pour la partie 2, compter le nombre de cotés revient à compter le nombre de coins.

Voici le code

pub fn solve(input: &str) -> Result<(u32, u32)> {
    let grid = Grid::parse_with_padding(input, b'.')?;
    let width = grid.width;
    let mut grid = grid.vec;
    let mut stack = Vec::with_capacity(500);
    let mut p1 = 0;
    let mut p2 = 0;

    for i in 0..grid.len() {
        let start = grid[i];
        if start.is_ascii_uppercase() {
            let mut area = 0;
            let mut perimeter = 0;
            let mut sides = 0;
            stack.push(i);
            while let Some(current) = stack.pop() {
                if grid[current] != start {
                    continue;
                }
                grid[current] |= 128;
                area += 1;
                for (next, side) in [(current-1, width), (current+1, width), (current-width, 1), (current+width, 1)] {
                    stack.push(next);
                    if grid[next] & 127 != start {
                        perimeter += 1;
                        let c1 = grid[current+side];
                        let c2 = grid[next+side];
                        if c1 & 127 != start || c2 & 127 == start {
                            sides += 1;
                        }
                    }
                }
            }
            p1 += area * perimeter;
            p2 += area * sides;
            stack.clear();
        }
    }
    Ok((p1, p2))
}

Oui, u64, c'est unsigned 64.

La plus grande valeur que j'ai obtenue pour une valeur de pierre est 36_024_470_028_800 soit à peut près 3*10¹³ et ma solution est de l'ordre de 10^15.
Donc ça tient sur unsigned 64 et même un signed 64.

Peut être que tu n'as pas eu de chance sur l'input.

Pour le problème du jour, j'ai anticipé la partie 2 et j'ai donc préparé directement un truc efficace pour cette partie.

A chaque itération de blink, je stocke un HashMap qui associe à chaque valeur (pierre) le nombre d’occurrences de cette valeur.

Quelques optimisations:
- j'alloue un hashmap d'une capacité double de la taille du précédent arrangement.
Ca évite de réallouer le hashmap quand celui ci grossit.
- J'utilise la librairie ahash comme fonction de hash à la place de celle par défaut,
ce changement a quasiment divisé le temps d'exécution par 2.
- Pour calculer les deux parties des chiffres d'un nombre, j'utilise la méthode ilog10 ainsi qu'une division et un modulo plutôt que convertir le nombre en string et le reconvertir en entier.

fn split_number(n: u64) -> Option<(u64, u64)> {
    let m = n.ilog10() + 1;
    if m & 1 == 0 {
        let p = 10u64.pow(m >> 1);
        Some((n / p, n % p))
    } else {
        None
    }
}

Je pense que ça aurait été encore plus rapide en faisant plein de if pour chaque puissance de 10 mais ça aurait été très moche.

J'ai essayé d'utiliser des u32 au lieu de u64 comme clé du hashmap mais j'ai des overflows. Par contre, je n'ai pas eu besoin d'utiliser de big integers.

Du coup, un peu moins de 3ms: partie 1 + partie 2.

Je ne sais pas si beaucoup de gens lisent encore ce topic mais je vais quand même continuer.

Quand j'ai vu le problème du jour, je me suis dit "encore un problème avec un parcours en largeur".
Cependant, ce problème a quelques propriétés intéressantes.
- On cherche des chemins avec valeurs croissantes donc pas la peine de se soucier de la détection de cycle.
- Pour une source donnée, le nombre de chemins possibles partant de cette source est très faible.

Du coup, on peut faire un parcours en profondeur (qui est un peu plus rapide qu'un parcours en largeur) sans se soucier des sommets déjà vus. Ce qui économise une table de hash ou autre structure pour les stocker.
On obtient donc un algorithme potentiellement exponentiel alors qu'un parcours en largeur est linéaire mais en pratique, ça va plus vite.

Quelques autres optimisations que j'ai faite.
- pour la partie 1, j'utilise une table de hash pour stocker les sommets finaux (de valeur 9) accessibles depuis la source. Je ne suis pas sûr que ce soit le mieux.
- j'utilise un tableau 1 dimension pour stocker la grille. J'ajoute +1, -1, +width, -width à un index pour obtenir les sommets adjacents.
- pour éviter de tester si un voisin du sommet courant se trouve à l'intérieur de la grille, je rajoute sur les bords de la grille des caractères '#'.

Chose surprenante, la partie 2 se résout plus vite que la partie 1.

65 microsecondes pour la partie 1 + partie 2.

Le neuvième jour n'était pas si simple mais c'est surtout que j'ai cherché à obtenir un algo linéaire pour les deux parties.

Pour la partie 1, j'ai obtenu un algorithme linéaire sans devoir allouer plus de mémoire que l'entrée.
L'idée est de maintenir un indice sur le bloc de fichier qu'on est en train de déplacer et un indice sur l'endroit où on est en train de le déplacer.
On va progressivement décrémenter le premier indice et incrémenter le second jusqu'à ce que le premier soit plus petit que le second.

Pour la partie 2, on va faire un peu la même chose. On va utiliser un indice sur le fichier qu'on est en train de déplacer et 10 indices, le i-ème indice pointant vers le prochain endroit où il y a au moins i blocs disponibles.
De même que pour la partie 1, on va progressivement décrémenter le premier indice et incrémenter les 10 indices ainsi que mettre à jour le nombre de blocs disponibles qu'on a fait un déplacement.
Contrairement à la partie 1, on a besoin de de mémoire supplémentaire pour indiquer à quel point une séquence de blocs vides a été remplie.

50 microsecondes pour la partie 1 and 380 microsecondes for la partie 2.

Je n'ai pas l'impression que l'optimisation d'Obsidian soit la même que la mienne.

Je vais illustrer mon algo par mon exemple pour la partie 2.

Supposons qu'on a la liste [2345, 23, 35, 10] avec 2345 comme valeur cible.

On part de 2345 et on regarde le dernier nombre à savoir 10.
2345 n'est pas divisible par 10 et 10 n'est pas un suffixe du mot 2345.
Donc la seule opération que l'on peut faire est l'addition.
On va donc chercher récursivement si la liste [2345-10=2335, 23, 35] admet une solution.
Regardons de nouveau le dernier nombre 35.
35 est un suffixe de 2335 mais 35 ne divise pas 2335.
Donc on peut faire une addition ou une concaténation.
Si on fait une addition, on va chercher si [2335 - 35, 23] admet une solution et
si on fait une concaténation, on va chercher si [23, 23] admet une solution.
[2335 - 35, 23] n'admet pas de solution mais [23, 23] admet clairement une solution donc la liste [2345, 23, 35, 10] admet une solution.

J'obtiens un gain non pas de x10 mais de x60.

Pour ma part, comme les problèmes des premiers jours sont assez faciles, j'essaie d'optimiser au maximum le temps d'exécution.

Pour le jour 7, j'ai trouvé une petite astuce.

Au lieu d'explorer toutes les combinaisons possibles en allant de gauche à droite, je pars de la valeur cible et j'essaie de remonter jusqu'à la première valeur en allant de droite à gauche et en inversant les opérations si celles-ci sont possibles. Cela réduit énormément l'arbre d'exploration.

Cela me donne 240 microsecondes au lieu de 15 millisecondes avec une approche brute-force.

Comme les années précédentes, j'y participe.

Cette année, ce sera en Rust contrairement aux années précédentes où c'était en Haskell.

Je ne me lèverai pas non plus à 6h. Trop tôt pour moi.

C'est une bonne idée mais je pense que tu as été chanceux sur les données.

En tout cas, trouver des cuts, même de taille 3, de manière efficace est un problème compliqué.
Voir cet article:
https://drops.dagstuhl.de/storage/00lipics/lipics-vol204-esa2021/LIPIcs.ESA.2021.71/LIPIcs.ESA.2021.71.pdf

Tout d'abord, remarquons que ce problème peut être partiellement résolu à la main en repérant les trois arêtes à supprimer à l'aide d'un outil de visualisation comme GraphViz.

C'est ce que j'ai fait pour le résoudre vite mais ce n'est pas très rigolo. Comme je préférais avoir un programme qui résout tout automatiquement, j'ai cherché un algorithme pour ce problème qui s'avère s'appeler un Minimum (Edge) Cut.
J'ai cherché une librairie en Haskell qui faisait ça mais n'en ayant pas trouvé, j'ai décidé d'implémenter moi même un algorithme.

Je suis tombé sur celui de Stoer et Wagner (qui fonctionne aussi sur un graphe pondéré).

https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

Ca n'a pas été facile de l'implémenter car la page wikipedia ne montre que les grandes lignes de l'algorithme mais je suis content de mon résultat.

Ca tourne en 2.5s sur l'input alors que la librairie Python networkx tourne en 6s pour le même problème.
Comme le code est un peu long, je ne le poste pas ici mais vous pouvez le trouver à cette adresse:
https://github.com/gbagan/advent-of-code/blob/master/libraries/aoc/AOC/Graph/MinCut.hs

Je me demande si il existe de meilleurs algorithmes quand on sait que le minimum cut est petit (ici 3).

Pour le code du problème à proprement parler, c'est assez court en utilisant une fonction pour le Minimum Cut et une pour trouver les composantes connexes.

type Network = [(Text, [Text])] 

parser :: Parser Network
parser = row `sepEndBy1` eol where
    row = (,) <$> label <* ": " <*> label `sepEndBy1` hspace
    label = Text.pack <$> some lowerChar 

part1 :: Network -> Int
part1 network = product (map length components) where
    graph = foldl' (\g (u, v) -> addEdge u v g) Map.empty
                [(u, v) | (u, nbor) <- network, v <- nbor]
    cutset = minimumCut graph
    graph' = foldl' (\g (u, v) -> removeEdge u v g) graph cutset
    components = connectedComponents graph'