Oui, ça fonctionne parce que le nombre de coupe est faible dans un problème plutôt grand (1 coupe pour 1000 arêtes), et que les coupes sont assez éloignées.
J'ai supposé que ça pouvait être le cas, et j'ai gagné.
Après j'ai eu la chance de prendre un sommet initial assez éloigné de mes coupes. Par hasard en fait parce que si on regarde l'algo, je prend le dernier sommet source défini dans les données.
Et j'ai pris celui là parce que je l'avais sous la main à la fin de l'analyse des données, donc c'était vraiment sans arrière pensée : lui ou un autre, qu'importe ?
Et en fait, ça m'aurait été très difficile de comprendre pourquoi l'algo bloque à un moment, quelle est la topologie du graphe, et pourquoi je ne peux plus avancer, et comment savoir comment avancer.
Parce que sur téléphone c'est pénible, difficile à lire, prise de tête. Si ça avait raté, j'aurais probablement dû partir sur une toute autre idée (une exploration en largeur, en notant la taille des liens possibles ? du brute force trop long probablement. D'autres simplifications, trouver des zones fermées et les réduire ? Récursivement ?), voire attendre d'enfin récupérer un ordinateur.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Oui, ça fonctionne parce que le nombre de coupe est faible dans un problème plutôt grand (1 coupe pour 1000 arêtes), et que les coupes sont assez éloignées.
J'ai supposé que ça pouvait être le cas, et j'ai gagné.
Après j'ai eu la chance de prendre un sommet initial assez éloigné de mes coupes. Par hasard en fait parce que si on regarde l'algo, je prend le dernier sommet source défini dans les données.
Et j'ai pris celui là parce que je l'avais sous la main à la fin de l'analyse des données, donc c'était vraiment sans arrière pensée : lui ou un autre, qu'importe ?
Et en fait, ça m'aurait été très difficile de comprendre pourquoi l'algo bloque à un moment, quelle est la topologie du graphe, et pourquoi je ne peux plus avancer, et comment savoir comment avancer.
Parce que sur téléphone c'est pénible, difficile à lire, prise de tête. Si ça avait raté, j'aurais probablement dû partir sur une toute autre idée (une exploration en largeur, en notant la taille des liens possibles ? du brute force trop long probablement. D'autres simplifications, trouver des zones fermées et les réduire ? Récursivement ?), voire attendre d'enfin récupérer un ordinateur.