Forum Programmation.autre [Doublon] Advent of Code 2023 : Day 5

• # Python sans brûlage de CPU ni explosion de RAM

  Posté par alberic89 🐧 le 05 décembre 2023 à 16:01. Évalué à 1. Dernière modification le 05 décembre 2023 à 16:01.

  

  Une solution dont je ne suis pas peux fier, puisqu’elle est économe en ressource et prend moins d'une seconde à terminer. Et j'ai enfin commencé à utiliser la POO :

  #!/bin/python3
  
  class Range:
  
      def __init__(self,start,end,pas=0):
          if end <= start:
              raise ValueError
          self.start = start
          self.end = end
          self.pas = pas
  
      def contain(self, n):
          if type(n) == Range:
              if self.start <= n.start and self.end >= n.end:
                  return True
              return False
          if self.start <= n and n < self.end:
              return True
          return False
  
      def ins(self, thisrange):
          if thisrange.contain(self.start) and thisrange.contain(self.end-1):
              return True
          return False
  
      def before(self, thisrange):
          if thisrange.contain(self.start) == False and thisrange.contain(self.end-1):
              return True
          return False
  
      def after(self, thisrange):
          if thisrange.contain(self.start) and thisrange.contain(self.end-1) == False:
              return True
          return False
  
      def not_ins(self, thisrange):
          if thisrange.contain(self.start) == False and thisrange.contain(self.end-1) == False and thisrange.contain(self) == False:
              return True
          return False
  
      def apply(self, thisrange):
          if self.pas == 0:
              return ValueError
          thisrange.start = thisrange.start + self.pas
          thisrange.end = thisrange.end + self.pas
          return thisrange
  
  
  
  def get_seeds(seeds):
      seeds = seeds.split(":")[1].split()
      for s in range(len(seeds)):
          seeds[s] = int(seeds[s])
      return seeds
  
  def get_seeds_range(seeds):
      seeds_range = []
      seeds = get_seeds(seeds)
      for i in range(0,len(seeds),2):
          seeds_range.append(Range(seeds[i],seeds[i]+seeds[i+1]))
      return seeds_range
  
  def mapping(almanac,seedlist):
      changed = [False for i in range(len(seedlist))]
      almanac = almanac.split(":")[1].split("\n")[1:]
      for c in almanac:
          if c == "" :
              continue
          c = c.split()
          c = [int(i) for i in c]
          for i, s in enumerate(seedlist):
              if s >= c[1] and s < c[1]+c[2] and changed[i] == False:
                  newvalue = c[0]+s-c[1]
                  seedlist[i] = newvalue
                  changed[i] = True
  
      return seedlist
  
  def mapping_range(almanac, seedrange):
      almanac = almanac.split(":")[1].split("\n")[1:]
      ranges = []
      for c in almanac:
          if c == "" :
              continue
          c = c.split()
          c = [int(i) for i in c]
          ranges.append(Range(c[1],c[1]+c[2],c[0]-c[1]))
      iterations = 0
      while iterations < len(seedrange):
          changed = [False for i in range(len(seedrange))]
          for i in range(iterations,len(seedrange)):
              s = seedrange[i]
              for r in ranges:
                  if changed[i]:
                      continue
                  if s.ins(r):
                      seedrange[i] = r.apply(s)
                      changed[i] = True
  
                  elif s.before(r):
                      seedrange.append(Range(s.start,r.start))
                      seedrange[i] = r.apply(Range(r.start, s.end))
                      changed[i] = True
  
                  elif s.after(r):
                      seedrange.append(Range(r.end,s.end))
                      seedrange[i] = r.apply(Range(s.start, r.end))
                      changed[i] = True
  
                  elif s.contain(r):
                      seedrange.append(Range(s.start,r.start))
                      seedrange.append(Range(r.end, s.end))
                      seedrange[i] = r.apply(Range(r.start, r.end))
                      changed[i] = True
  
  
                  elif s.not_ins(r):
                      pass
                  else:
                      print("Maybe Error with range",r.start,r.end,r.pas,"and seedrange",s.start,s.end)
              iterations += 1
  
      return seedrange
  
  def solve1(puzzle,testing=False):
      s=0
      seeds = get_seeds(puzzle[0])
  
      for changes in puzzle[1:]:
          seeds = mapping(changes, seeds)
      s = min(seeds)
      if testing:
          print(s)
      return s
  
  def solve2(puzzle,testing=False):
      s = 0
      seeds = get_seeds_range(puzzle[0])
  
      for changes in puzzle[1:]:
          seeds = mapping_range(changes, seeds)
      s = seeds[0].start
      for r in seeds:
          if r.start < s:
              s = r.start
      if testing:
          print(s)
      return s
  
  test1 = """seeds: 79 14 55 13
  
  seed-to-soil map:
  50 98 2
  52 50 48
  
  soil-to-fertilizer map:
  0 15 37
  37 52 2
  39 0 15
  
  fertilizer-to-water map:
  49 53 8
  0 11 42
  42 0 7
  57 7 4
  
  water-to-light map:
  88 18 7
  18 25 70
  
  light-to-temperature map:
  45 77 23
  81 45 19
  68 64 13
  
  temperature-to-humidity map:
  0 69 1
  1 0 69
  
  humidity-to-location map:
  60 56 37
  56 93 4
  """
  result1 = 35
  test2 = test1
  result2 = 46
  
  def solve(short=False):
  
      print("----Part 1----")
      if short == False:
          if solve1(test1.split("\n\n"),testing=True) != result1:
              print("Not working.")
              return False
          else :
              print("Maybe working?")
      with open("input.txt",'r') as file:
          lines = file.read().split("\n\n")
          s1 = solve1(lines)
          print(s1)
  
      print("----Part 2----")
      if short == False:
          if solve2(test2.split("\n\n"),testing=True) != result2:
              print("Not working.")
              return False
          else :
              print("Maybe working?")
      with open("input.txt",'r') as file:
          lines = file.read().split("\n\n")
          s2 = solve2(lines)
          print(s2)
  
      return s1, s2
  
  if __name__ == "__main__":
  
      from sys import argv
  
      try:
          if argv[1] == "--summary" or argv[1] == "-s":
              solve(short=True)
      except IndexError:
          solve()

  Il y a 10 sortes de gens dans le monde – ceux qui comprennent le ternaire, ceux qui ne le comprennent pas et ceux qui le confondent avec le binaire.

  • [^] # Re: Python sans brûlage de CPU ni explosion de RAM

    Posté par alberic89 🐧 le 05 décembre 2023 à 20:36. Évalué à 1.

    

    Au début, je m'étais dit naïvement :

    Faisons un dictionnaire qui indiquera toutes les valeurs à modifier pour passer du début à la fin, en lui appliquant toutes les étapes, pour toutes les valeurs qui peuvent être modifiée. !

    Après m'être fait rappeler à l'ordre par mon OOM Killer, j'ai mis en place une solution plus simple qui applique directement les modifications aux numéros de graine et se souvenant s'il a déjà modifié cette valeur (pour éviter de changer 3 fois par étape les numéros).

    La partie 2 m'a donnée beaucoup plus de fil à retordre, car ce n'est pas simplement :

    Bon bah je génère une liste avec tous les numéros des graines et hop ! je les passe à la même fonction que la partie 1 !

    Mais l'OOM Killer proteste encore une fois, m'obligeant à finalement essayer de gérer des intervalles plutôt que des valeurs. Après beaucoup de débuggage et d'arrachage de cheveux, j'ai fini par trouver la recette qui s'exécute instantanément.

    Il y a 10 sortes de gens dans le monde – ceux qui comprennent le ternaire, ceux qui ne le comprennent pas et ceux qui le confondent avec le binaire.

• # Le code que j'aurais aimé faire du premier coup.

  Posté par Yth (Mastodon) le 05 décembre 2023 à 16:21. Évalué à 2.

  

  Mon premier algo a fait fondre deux CPU en même temps, sur deux machines différentes, avec partage du travail à faire, pour pondre le résultat en pas loin de 40 minutes, avec PyPy.
  Voici le second, celui qui fonctionne, qui prends moins d'un dixième de seconde pour résoudre tout le problème, et de façon assez élégante en plus, juste en exploitant le range() de Python.
  C'est pour ça que dans l'algo présenté, j'utilise la même méthode pour les deux exercices, avec des range de un élément pour l'exercice 1, je n'ai pas codé ça dès le début.
  Et non, je ne posterai pas mon premier algo, très bien pour l'exo 1, mais très crado pour le 2 ^{^}

  Les données d'abord, je distingue les graines et le reste :

  def seedranges(seeds):
    def __iter():
      while seeds:
        src = seeds.pop(0)
        dst = seeds.pop(0)
        yield range(src, src + dst)
    return __iter()
  
  datas = [x.strip().split(" ") for x in sys.stdin]
  seeds = [int(x) for x in datas.pop(0)[1:]]
  # Exercice 1
  values = [range(seed, seed + 1) for seed in seeds]
  # Exercice 2
  values = list(seedranges(seeds))

  Les graines sont donc une liste de range().

  Ensuite les transformations pour trouver les correspondances, on va avoir une classe avec deux listes : les range() source, et les opérations à appliquer sur chaque range, qui sont simplement un entier relatif à ajouter. Et puis les noms des éléments depuis et vers lesquels on transforme :

  class Map():
    ranges = None
    operations = None
    def __init__(self, *ranges):
      self.ranges = []
      self.operations = []
      for dst, src, size in ranges:
        self.ranges.append(range(src, src + size))
        self.operations.append(dst - src)
  
  def readmap(lines):
    ranges = None
    mapname = None
    for line in lines:
      if not line[0]:
        if mapname:
          yield mapname[0], mapname[2], Map(*ranges)
        ranges = None
      elif ranges is None:
        mapname = line[0].split("-")  # ['seed', 'to', 'soil']
        ranges = []
      else:
        ranges.append(int(x) for x in line)
    yield mapname[0], mapname[2], Map(*ranges)
  
  converters = {
    src: (dst, mapping)
    for src, dst, mapping in readmap(datas)
  }

  Pour les calculs en eux-même, la méthode qui fait le travail est ajoutée à Map(), et la résolution est assez simple au bout du compte.
  On calcule tout simplement les superpositions de deux range() : on va avoir un range d'éléments non traité avant un range de transformation, un range d'éléments non traités après un range de transformation, et enfin un range transformé. On boucle sur toutes les opérations disponibles, en remettant dans le pot les range non traités (avant et après) et en retournant (yield est ton ami) les range traités.
  On n'oublie pas à la fin de retourner tous les range ayant échappés aux transformations, car ils restent identiques selon l'énoncé.
  Le code est vraiment simple grâce aux itérateurs, avec yield, on ne se fatigue pas à construire une liste, à tester des trucs : on a une donnée finale ? yield, et on continue, elle est envoyée, et on ne s'en occupe plus.
  Et on utilise les propriétés des range(), au début je voulais faire des if élément in range_operation qui est immédiat, mais en fait on n'en a pas besoin. La seule subtilité c'est qu'un range est Vrai s'il contient en pratique des éléments, et Faux sinon, donc range(20, 10) c'est faux.
  if before signifie donc simplement : si on a des éléments non traités avant.

  class Map():
    [...]
    def __call__(self, sources):
      for i, r in enumerate(self.ranges):
        op = self.operations[i]
        new_sources = []
        while sources:
          src = sources.pop()
          before = range(src.start, min(src.stop, r.start))
          after = range(max(src.start, r.stop), src.stop)
          transformed = range(max(src.start, r.start) + op, min(src.stop, r.stop) + op)
          if before:
            new_sources.append(before)
          if after:
            new_sources.append(after)
          if transformed:
            yield transformed
        sources = new_sources
      for src in sources:
        yield src

  Enfin le résolution se fait à l'identique pour les deux parties, avec la bonne valeur initiale pour values :

  while src in converters:
    dst, converter = converters[src]
    # print(f"Converting from {src} to {dst}")
    values = list(converter(values))
    src = dst
  print("Closest location is {}".format(
    min(v.start for v in values)
  ))

  Pour info, faire les 7 moulinettes sur une liste de 850 millions d'éléments, même avec PyPy, ça prend dans les dix/quinze minutes, et je parle pas de la RAM.
  Comme quoi ça peut valoir le coup de regarder les données à traiter pour savoir où on va se planter, avant de coder…
  Cela dit, un algo non optimisé, même à 45 minutes de calcul réparti sur deux machines (j'aurais pu aller plus vite en parallélélisant sur les multiples proc des machines, un range initial par exécution, en moins de 15 minutes c'était plié), c'est plus rapide que de réinventer un algorithme, le coder, le valider.

  • Yth.

Suivre le flux des commentaires

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