Forum Programmation.autre Avent du Code jour 16

• # C'est trop pour moi

  Posté par alkino le 16 décembre 2022 à 13:33. Évalué à 4.

  

  Et arrive ce jour comme chaque année dans Advent Of Code… Je veux bien y passer un peu de temps mais j'ai un boulot et des occupations hors écrans.

  • [^] # Re: C'est trop pour moi

    Posté par Yth (Mastodon) le 16 décembre 2022 à 13:45. Évalué à 3.

    

    Ça prend du temps là, je vais avoir du mal ce week-end.
    Et faut que je rattrape le temps perdu au boulot…
    À un moment ça va craquer aussi.

    • Yth.

• # Ça chauffe, ça chauffe !

  Posté par Yth (Mastodon) le 16 décembre 2022 à 13:43. Évalué à 3.

  

  Et 6h30 après la publication du problème, il n'y avait que 2500 personnes à avoir eu une solution complète.
  Pour ma part j'ai mis 25 minutes à coder la seconde partie à partir de la première, et la valider sur les données de test, en pleine visio boulot.
  Puis 5 minutes à installer pypy et vérifier comment ça marche (réponse : bien).
  Et 15 minutes de calculs pour avoir une solution… (J'ai killé la version cpython au bout de 20 minutes)
  J'ai laissé tourner en espérant que ça allait marcher.

  À noter que je stocke tous les chemins, puis je trie et je pond le dernier.
  C'est utile pour le débuggage, mais complètement crétin : on peut toujours comparer au fur et à mesure et ne conserver que le dernier !

  Fallait s'en douter déjà : sur les données de test, j'explore toujours les 720 possibilités, donc il y a sûrement une optimisation possible, pourtant aujourd'hui j'ai suivi mon conseil : réfléchir avant d'agir.
  Pas assez…

  J'ai recodé pour ne garder en mémoire que le meilleur chemin, et pas tous les chemins triés après coup.
  Données de test, avec python3, plus rapide que pypy3 sur un délais aussi court :
  Ex1 en 0.05s : Score 1651, 720 chemins explorés
  AA->DD->BB->JJ->HH->EE->CC
  Ex2 en 0,07s : Score 1707, 720 chemins explorés
  AA->JJ->BB->CC AA->DD->HH->EE

  Données réelles, avec pypy :
  Ex1 en 0,5s : Score 1871, 106 839 chemins explorés
  Ex2 en 2min21 : Score 2416, 37 306 254 chemins explorés

  Et là, je réalise que les 15 minutes c'était 13 minutes pour afficher 37 millions de foutues lignes dans mon terminal débile, et peut-être un peu de temps pour gérer la RAM explosive de la liste de 37 millions d'entrées, et la trier à la fin…

  Non mais sérieux…

  Au passage cpython prends 2,1 secondes pour l'exo 1 réel contre 0,5 secondes pour pypy3.
  Mais pour l'exo 2, pypy prend 2min21 quand cpython monte à plus de 20 minutes (il a pas terminé là).
  pypy3 prend 108Mo de RAM, fixe quand on fait pas le crétin.
  cpython3 reste à 12Mo de RAM, là aussi quand on ne fait pas l'idiot.
  Et j'ai découvert que quand la RAM se réduit, Firefox décharge naturellement les onglets ouverts, pour rétrécir plutôt que de mourir !

  Donc merci à Steph pour l'idée d'utiliser pypy :)

  • Yth.

  • [^] # Re: Ça chauffe, ça chauffe !

    Posté par Yth (Mastodon) le 16 décembre 2022 à 14:03. Évalué à 4.

    

    Côté algo :
    * on crée nos valves (ou vannes, osef) ;
    * on lie les objets les uns aux autres pour les liaisons directes ;
    * on explore de proche en proche pour enregistrer la liste des autres valves avec la distance pour y aller depuis chaque valve ;
    * on n'optimise pas en stockant la distance retour dans la valve distante, vu mon algo ça pouvait empêcher la valve distante de calculer certaines distances, modélisation fausse, résultat faux, et les données de test ne sont pas affectées ;
    * on parcours à nouveau nos valves et on supprime les chemins vers les valves à flux nul, on réduit le problème aux seules valves utiles (15 en situation réelle, 6 en test), mais avec des distances complètes.

    Là on ne cherche plus à se déplacer, juste à mesurer le temps qui passe à partir d'ici ou de là.
    Et donc pour chaque situation :
    * valve où on se trouve
    * temps restant
    * score final actuel (dès qu'on ouvre une valve on calcule directement toute la vapeur dégagée jusqu'au bout du temps imparti)
    * liste des valves ouvertes

    On calcule le score final en allant ouvrir chaque vanne accessible.

    On récurse à partir de chaque destination possible (vannes encore ouvertes), et une fois au bout, soit du temps disponible (données réelles), soit de vannes à ouvrir (données de test), on a un chemin avec un score.

    On ne retourne que le meilleur score, et pas tous les chemins trouvés, sinon on explose la RAM et la durée.
    Et à la fin on a notre résultat.

    class Valve:
        def __init__(self, name, flow, links):
            self.name = name
            self.flow = int(flow)
            self.locallinks = links.strip().split(", ")
            self.links = dict()
            # considering valve with no flow as already opened
            self.open = self.flow == 0
    
        def __repr__(self):
            return f"{self.name}@{self.flow}: {' '.join(f'{n.name}:{d}' for n, d in sorted(self.links.items()))}"
    
        def __lt__(self, other):
            return self.name < other.name
    
        def linkvalves(self, valves):
            self.valves = valves
            self.locallinks = [valves[link] for link in self.locallinks]
            # self.links = {link: 1 for link in self.locallinks}
            self.links[self] = 0
    
        def graph(self):
            explore = {self, }
            distance = 0
            while explore:
                distance += 1
                step = set(
                    link
                    for valve in explore
                    for link in valve.locallinks
                    if link not in self.links
                )
                for valve in step:
                    self.links[valve] = distance
                explore = step
    
        def reducegraph(self):
            self.links = {
                link: score
                for link, score in self.links.items()
                if link.flow
            }
    
        def getscores(self, timeleft, currentscore, opened):
            self.scores = dict()
            for link, distance in self.links.items():
                timeafter = timeleft - distance - 1
                # valve already opened or too far to be useful
                if link in opened or timeafter <= 0:
                    continue
                self.scores[link] = currentscore + timeafter * link.flow, timeafter
            return self.scores
    
    regex = re.compile(
        r"Valve ([A-Z]+) has flow rate=(\d+); "
        r"tunnels? leads? to valves? ([A-Z, ]+)")
    valves = {
        v.name: v
        for v in (
            Valve(*regex.match(line).groups())
            for line in sys.stdin
        )
    }
    for valve in valves.values():
        valve.linkvalves(valves)
    for valve in valves.values():
        valve.graph()
    for valve in valves.values():
        valve.reducegraph()
    
    def nextscores(valve, currentscore, timeleft, opened, currentpath):
        path = valve.getscores(timeleft, currentscore, opened)
        if not path:  # end of the line !
            return currentscore, timeleft, currentpath, 1
        explored = 0
        r = (0, 0, "", 0)
        for link, (score, time) in path.items():
            x = nextscores(
                link,
                score,
                time,
                opened + [link],
                currentpath + "->" + link.name
            )
            explored += x[-1]
            r = x if x > r else r
        return r[0], r[1], r[2], explored
    
    score, time, path, explored = nextscores(valves['AA'], 0, 30, [], 'AA')
    print(f"Score {score}, explored {explored} paths : {path}")

    Pour l'exercice 2 on conserve la même modélisation, aucun changement.
    La fonction d'exploration change : on lui fourni deux explorateurs, chacun avec son chemin parcouru, et son temps restant.
    Et on travaille sur l'explorateur qui a le plus de temps disponible à chaque itération.

    class explorer:  # pour se simplifier la vie
        def __init__(self, valve, timeleft, path=None):
            self.valve = valve
            self.timeleft = timeleft
            self.path = path or valve.name
    
        def __call__(self, s):
            return f"{self.path}->{s}"
    
        def __repr__(self):
            return f"time remaining {self.timeleft} {self.path}"
    
        def __lt__(self, other):
            return self.timeleft < other.timeleft
    
    def doublescores(e1, e2, currentscore, opened):
        if e1 < e2:  # look using the explorer with the most time remaining
            e2, e1 = e1, e2
        path = e1.valve.getscores(e1.timeleft, currentscore, opened)
        if not path:  # end of the line !
            return (currentscore, e1, e2, 1)
        explored = 0
        r = (0, 0, "", 0)
        for link, (score, time) in path.items():
            x = doublescores(
                explorer(link, time, e1(link.name)),
                e2,
                score,
                opened + [link],
            )
            explored += x[-1]
            r = x if x > r else r
        return r[0], r[1], r[2], explored
    
    score, p1, p2, explored = doublescores(
        explorer(valves['AA'], 26),
        explorer(valves['AA'], 26),
        0,
        [],
    )
    print(f"Score {score}, explored {explored} paths, {p1} {p2}")

    Et voilà, on a bien perdu du temps et fait chauffer la machine.

    • Yth.

    • [^] # Re: Ça chauffe, ça chauffe !

      Posté par syj le 16 décembre 2022 à 19:11. Évalué à 1.

      

      Gg.
      Je n'ai pas pensé à simplifier les chemin.
      Résultat, j'ai fait un AG. il met 1h pour trouver l'optimum de la 2ème réponse :o)

      • [^] # Re: Ça chauffe, ça chauffe !

        Posté par alkino le 16 décembre 2022 à 20:24. Évalué à 2. Dernière modification le 16 décembre 2022 à 20:27.

        

        Au final j'ai simplifié à l'extrême.

        Je résous la première solution en 26 secondes, puis je prends les nœuds restants et je résous de nouveau en 26 secondes.
        Je fais la somme des deux et … ça a marché !
        Sinon mon objectif était de tester avec le deuxième puis le troisième puis …
        Au final : 11 secondes

        La première solution j'exécute sur une permutation de tout l'ensemble en limitant le nombre d'éléments.

        for l in permutations(useful_nodes, r=7)

        • [^] # Re: Ça chauffe, ça chauffe !

          Posté par Yth (Mastodon) le 16 décembre 2022 à 23:07. Évalué à 2. Dernière modification le 16 décembre 2022 à 23:09.

          

          Pour le second tu dis qu'en prenant la solution du premier et en envoyant l'éléphant jouer avec les vannes non ouvertes par le premier, ça marche ?

          Dingue ça…
          Bon, 2min20 ça va au final, mais bigre… 37 millions de chemins testés !!!

          • Yth.

• # python caché

  Posté par steph1978 le 18 décembre 2022 à 08:14. Évalué à 2.

  

  Un parcours de graph avec la complication que l'état du graph change pendant le parcours.

  J'ai procédé en brute force et n'ai pas trouvé vraiment de moyen de couper des branches, si ce n'est marquer dès le départ les vannes à 0 comme étant déjà ouverte. Ça marchait bien jusqu'à 20 de profondeur mais passé ça, ça ramait trop (je timeout à 10 min). J'ai donc ajouté du cache et bim, 0.37s et 91MB de cache.

  Cependant cette solution ne passe pas à l'échelle pour le parcours à 2 qui multiplie les branches.

  J'ai ouïe dire des solutions où on pré-calcul des distances ou des scores mais je crois que je vais en rester là, j'ai déjà un retard de deux jours. J'ai atteint ma limite.

  part 1

  import sys
  import re
  
  pat = re.compile('Valve ([A-Z]{2}) has flow rate=([0-9]+); tunnels? leads? to valves? ([ ,A-Z]+)')
  P = dict()
  for i,l in enumerate(sys.stdin.read().splitlines()):
      g = pat.search(l)
      p = int(g[2])
      P[g[1]] = (i, p, g[3].split(", "))
  
  STEPS = int(sys.argv[1])
  ALLO = 0
  for _,(i,p,_) in P.items():
      if p == 0:
          ALLO = ALLO | (1<<i) 
  
  cache = {}
  def step(pos="AA", left=STEPS, opens=ALLO):
      if left <= 0:
          return 0
      key = (pos, left, opens)
      r = cache.get(key, -1)
      if r >= 0:
          return r
      (i, p, nh) = P[pos]
      is_open = opens & (1 << i)
      a = 0
      if not is_open:  # also means 0 - worth opening valve ?
          left -= 1 # cost to open
          opens = opens | (1<<i)
          a = p*(left+30-STEPS) + max(step(n, left-1, opens) for n in nh)
      b = max(step(n, left-1, opens) for n in nh)
      r = max(a,b)
      cache[key] = r
      return r
  
  print(step())

Suivre le flux des commentaires

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