Forum Programmation.autre Advent of Code 2023, jour 25

Posté par  . Licence CC By‑SA.
Étiquettes :
4
25
déc.
2023

Hello et joyeux Noël à tous.

Ce jour ci comme les années précédentes, il n'y a qu'une seule partie pour le challenge de l'AOC.

On se donne un réseau de câbles comme celui donné en exemple.

jqt: rhn xhk nvd
rsh: frs pzl lsr
xhk: hfx
cmg: qnr nvd lhk bvb
rhn: xhk bvb hfx
bvb: xhk hfx
pzl: lsr hfx nvd
qnr: nvd
ntq: jqt hfx bvb xhk
nvd: lhk
lsr: lhk
rzs: qnr cmg lsr rsh
frs: qnr lhk lsr

Chaque ligne indique pour chaque nœud la liste de ces nœuds voisins.
Cela forme un graphe non orienté (c'est à dire que si x est un voisin de y alors y est voisin de x) mais les voisins ne sont indiqués que dans un sens. Par exemple, rsh est voisin de frs mais n'est pas indiqué dans la liste des voisins de frs.

Le but du problème est de retirer 3 arêtes (câbles) de telle manière à ce que le graphe soit déconnecté.
Ensuite, on calcule la taille de chaque composante connexe et on fait le produit de tout ça.

  • # Solution en Haskell

    Posté par  . Évalué à 4.

    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'

    • [^] # Re: Solution en Haskell

      Posté par  (Mastodon) . Évalué à 2.

      Ma solution est beaucoup plus rapide : 0,07s, donc assez négligeable devant le temps de démarrage de python.
      Mais…
      Je ne sais pas qu'elle fonctionne, je le constate.
      Et ça exploite très fortement le fait qu'on ait trois liens à couper, sans cette information je ne sais pas quand m'arrêter, l'algo n'est plus du tout le même.

      En gros je fais l'hypothèse que deux liens à couper ne sont pas proches (partageant un même sommet), et que je vais avoir un peu de chance.

      Je pars d'un sommet, au pif, mais ça rate s'il s'agit d'un sommet d'une des arêtes à supprimer. Là je me dis que si je ne trouve pas de solution, je peux prendre un autre sommet au pif, normalement, au bout du 7è je suis certain d'avoir au moins essayé avec un sommet qui n'est pas dans une des arêtes à supprimer.
      Là ça a fonctionné directement.

      Je considère comme « exploré » toutes ses arêtes, et les sommets directement connectés.

      Et j'itère :
      * Je considère l'ensemble des arêtes liées à tous mes sommets, et pas déjà explorées.
      * Je considère l'ensemble des nouveaux sommets accessibles via ces arêtes.
      * Pour chacun de ces nouveaux sommets, si il est accédé par au moins deux des nouvelles arêtes, je l'ajoute.
      * Et je reconstruit l'ensemble des arêtes explorées à partir des liens possibles entre mes sommets explorés.
      * Il me reste un ensemble d'arêtes considérées, mais rejetées, et qui seront à nouveau considérées le coup d'après.
      * Si je n'ajoute aucun nouveau sommet, j'ai a priori fini.

      Normalement, si il n'y a pas deux arêtes à couper qui partagent un même sommet, je ne peux pas « traverser » ces arêtes avec mon algorithme.
      Il se trouve que ça s'arrête très très vite sans donner de résultat, donc j'ai juste essayé un truc :
      * Si l'ensemble des arêtes que je peux atteindre mais que je n'ai pas considérées n'est pas de taille 3, alors j'ajoute unilatéralement toutes les arêtes possibles : je ne suis pas allé assez loin, il faut que j'avance, et c'est la méthode la plus naïve pour avancer.
      À noter que ça peut foirer si l'un de ces nouvelles arêtes et une des arêtes à couper.
      Je n'ai pas regardé dans le détail, mais je pense que ce problème n'existe qu'au démarrage, il faudrait peut-être partir directement à deux arêtes de distance de mon sommet d'origine (la suite me prouvera que j'ai raison pour le démarrage, mais tort globalement).

      Bref, ça a fonctionné puisqu'après mon algorithme s'est arrêté à trois arêtes accessibles mais mises de côté, et là on sait que c'est le bon résultat, pif paf, terminé.

      L'algorithme mériterait bien plus de vérifications, et éventuellement une boucle sur un sommet de démarrage différent, jusqu'à tomber sur une solution.
      Il faudrait au minimum identifier quand est-ce que j'ai besoin de mon hack pour avancer un peu plus loin dans le noir, peut-être faire une exploration en branches pour ajouter un sous-ensemble et tester, histoire de s'assurer qu'on va trouver un truc viable, ou tout explorer sans trouver.

      Mais ça a fonctionné du premier coup.
      On peut noter qu'il y a 1502 sommets et 3363 arêtes dans mes données, donc au final démarrer depuis un des sommets à éviter, ça serait surtout beaucoup de malchance, c'est la taille du problème qui m'a incité à tester cette approche, en me disant que j'avais plus de chance de tomber dans le « gras » du problème que pile là où il ne fallait pas.

      J'ai cherché des simplifications, un peu, avant, comme de simplifier les triangles (A<->B<->C<->A), mais autant ça donne un peu quelque chose sur les données de test (on peut brute-forcer la recherche sans soucis : prendre trois arêtes et voir si on a coupé en deux), c'est inutile sur les données réelles, on simplifie de 42 arêtes, sur 3363 ça change rien.

      Par contre, en nettoyant mon code, je vois que le « hack » sert trois fois : à 15 sommets à explorer (1ère itération, donc dès le début), à 54 sommets à explorer (3ème itération), puis à 217 sommets à explorer (345 déjà validés, 13ème itération !), et là on est quand même assez loin, on aurait très facilement pu mal tomber, sachant que le résultat arrive à 18 itérations.
      Bilan, je dirais que j'ai plutôt eu de la chance avec mon sommet de départ…

      Voilà le code nettoyé :

      from sys import stdin
test = stdin.isatty()
r1, r2 = (54, 0) if test else (562912, 0)
t1, t2 = "Étape 1", "Étape 2"
ok, nok = "\033[38;5;118m✓\033[0m", "\033[38;5;196m✗\033[0m"
data = (__doc__ if test else stdin.read()).strip().splitlines()
ex1 = ex2 = 0

nodes = set()
flinks = set()
for d in data:
  a = d.replace(":", "").split(" ")
  nodes.update(a)
  s = a.pop(0)
  for b in a:
    flinks.add(frozenset((s, b)))
S = s  # Soit S un sommet quelconque

def explore(s, links):
  explinks = {i for i in links if s in i}
  expnodes = {a for i in explinks for a in i}
  newnodes = expnodes.difference([s])
  print(expnodes, explinks, newnodes)
  i = 0
  while newnodes:
    i += 1
    newlinks = {
      i for i in links
      if i.intersection(expnodes)
    }.difference(explinks)
    exploring = [
      _ for i in newlinks
      for _ in i
      if _ not in expnodes
    ]
    newnodes = {i for i in exploring if exploring.count(i) > 1}
    expnodes.update(newnodes)
    explinks.update(
      i for i in links
      if i.issubset(expnodes)
    )
    # Hack when stopping too early: adding everything linked
    if not newnodes and len(newlinks.difference(explinks)) > 3:
      newnodes = set(exploring).difference(expnodes)
      expnodes.update(newnodes)
      print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")
  print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")
  return expnodes, newlinks.difference(explinks)

a, b = explore(S, flinks)
if len(b) != 3:
    print("ERROR, wrong result ahead")
ex1 = len(a) * (len(nodes) - len(a))

      Pour une fois, mes expérimentations téléphoniques pour coder moins et avoir de la chance rapidement, ont portées leurs fruits, j'étais le premier surpris :)
      Mais c'est rude de faire du code aussi approximatif, et de s'en contenter au bout du compte, ça heurte vraiment ma façon de penser.
      Enfin, c'est pour ça que j'ai validé cette étoile avant la seconde du jour précédent.

      • Yth.

      • [^] # Re: Solution en Haskell

        Posté par  (Mastodon) . Évalué à 2.

        Après vérification, mon hack, au lieu de tout ajouter, pourrait ajouter 1 seul sommet au hasard parmi les sommets possibles.
        Je tombe sur la solution, mais pas toujours pour le coup, en y allant au pif, je tombe parfois sur un mauvais chemin.

        Je sais déjà que ça peut fonctionner, parce que ça fonctionne en les ajoutant tous, mais ça veut surtout dire qu'on peut brancher sur une exploration 1 par 1 de tous les sommets possibles, quand on coince avec l'algo de base, et faire une exploration.

        On doit pouvoir avoir un algo capable de nous assurer qu'on trouve une solution.
        Encore une fois, tout ça fonctionne parce qu'on sait qu'on a trois sommets à couper hein.

        C'est un brin moche mais voilà, on peut retomber sur nos pieds.

        • Yth.

      • [^] # Re: Solution en Haskell

        Posté par  . Évalué à 1.

        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

        • [^] # Re: Solution en Haskell

          Posté par  (Mastodon) . É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.

          • Yth.

  • # Algorithme de Karger

    Posté par  . Évalué à 2.

    Pour le dernier jour, j'ai tenté plusieurs solutions naïve avant de chercher un algorithme qui pouvait répondre à mon problème.

    Je suis tombé sur l'algorithme de Karger qui me semblait relativement simple à implémenter.

    https://fr.wikipedia.org/wiki/Algorithme_de_Karger

    Je trouve que ma condition de sortie est un peu moisie mais dans l'ensemble.
    En gros, j'arrête le programme quand j'arrive à une contraction à 2 noeud avec 3 lien qui sont les 3 liens à couper.
    C'était la solution attendu. Je n'ai pas cherché plus loin.

    package aoc2023;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Aoc2023s25 {
    final static Random random = new Random(0);

    public static class Link {

        String srcName;
        String dstName;

        public Link(String srcName, String dstName) {
            this.srcName = srcName;
            this.dstName = dstName;
        }

        @Override
        public String toString() {
            return dstName + "/" + srcName;
        }

        public boolean match(String name) {
            return name.equals(srcName) || name.equals(dstName);
        }

        public String otherName(String name) {
            return srcName.equals(name) ? dstName : srcName;
        }

        public Link replace(String left, String right, String b) {
            String nsrc = srcName;
            if (nsrc.equals(left) || nsrc.equals(right)) {
                nsrc = b;
            }

            String ndst = dstName;
            if (ndst.equals(left) || ndst.equals(right)) {
                ndst = b;
            }

            return new Link(nsrc, ndst);
        }

    }

    public static class Node {
        String name;

        public Node(String s) {
            this.name = s;

        }

        @Override
        public String toString() {
            return "Node [name=" + name + "]";
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Node other = (Node) obj;
            return Objects.equals(name, other.name);
        }
    }

    public static void main(String[] args) {
        try (Scanner in = new Scanner(Aoc2023s25.class.getResourceAsStream("res/t25.txt"))) {

            Map<String, Node> nodeByName = new HashMap<>();
            List<Link> links = new ArrayList<>();
            while (in.hasNext()) {
                String row = in.nextLine();

                String[] fields = row.split(":");
                Node n = new Node(fields[0].trim());
                nodeByName.put(n.name, n);

                links.addAll(Arrays.stream(fields[1].trim().split(" ")).map(String::trim)
                        .map(d -> new Link(n.name, d)).toList());
            }

            for (Link a : links) {
                nodeByName.computeIfAbsent(a.dstName, k -> new Node(k + ": "));
            }

            while (true) {
                Map<String, Node> clone = new HashMap<>(nodeByName);
                algorithmKarger(clone, new ArrayList<>(links));
            }
        }

    }

    private static void algorithmKarger(Map<String, Node> nodeByName, List<Link> links) {

        while(nodeByName.size() > 2) {
            Link link = links.get(random.nextInt(links.size()));

            String leftName  = link.srcName;
            String rightName = link.dstName;
            String contractName = leftName + "," + rightName;

            nodeByName.remove(leftName);
            nodeByName.remove(rightName);
            nodeByName.put(contractName,new Node(contractName));

            List<Link> intLinks = links.stream()
                .filter(l -> !(l.match(leftName) && l.match(rightName)))
                .map(l->l.replace(leftName, rightName, contractName))
                .toList();

            links =intLinks;


        }

        System.out.println(nodeByName.size());
        System.out.println(links.size());
        for(Node n : nodeByName.values()) {
            System.out.println(n.name + " => " + n);
        }
        if(links.size() == 3) {
            int prod = 1;
            for(String n :  nodeByName.keySet()) {
                String[] keys = n.split(",");
                System.out.println(keys.length);
                prod *= keys.length;
            }
            System.out.println(prod);
            System.out.println(links);
            System.exit(0);
        }

    }
}

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.