Forum Programmation.autre Advent of Code 2023 : Day 2

• # Commencer à représenter le problème pas trop bêtement.

  Posté par Yth (Mastodon) le 04 décembre 2023 à 17:02. Évalué à 2.

  

  Ce coup-ci, avec une analyse des données, placées dans les bonnes structures, la seconde partie de l'exercice va se faire immédiatement après la première.

  Ici on a encore un truc assez simple, et on va faire un dictionnaire avec en clé le numéro de la partie et en valeur une liste de triplets (rouge, vert, bleu), avec des zéros là où on n'a pas d'infos en entrée.
  -> Normaliser les entrées, avoir une structure assez facile à analyser ensuite.

  import sys
  from functools import reduce
  colors = {"red": 0, "green": 1, "blue": 2}
  
  def read_cubes(cubeset):
      r = [0, 0, 0]
      for cubes in cubeset.strip().split(","):
          nb, color = cubes.strip().split(" ")
          r[colors[color]] = int(nb)
      return r
  
  
  def input():
      for line in sys.stdin:
          game, cubes = line.strip().split(':')
          game = int(game.split(" ")[1])
          cubes = [read_cubes(cubeset) for cubeset in cubes.split(";")]
          yield game, cubes
  
  datas = [x for x in input()]

  Déjà, j'abuse des yields et des générateurs, c'est pas encore utile, mais ça va venir.

  Pour la partie 1 on va avoir une fonction de validation, et après on fait une somme :

  def test_elements(elements, constraint):
      for el in elements:
          for i in range(3):
              if el[i] > constraint[i]:
                  return False
      return True
  
  constraint = [12, 13, 14]
  r = sum(
      game
      for game, elements in datas
      if test_elements(elements, constraint)
  )
  print(f"Possible games : {r}")

  Et là, pour la seconde partie on n'a même plus besoin de fonction de validation, le calcul est immédiat, même si le code est moche. Y'aurait moyen avec des structures de données de numpy de se passer de certaines méthodes peu explicites avec directement des comparaisons de vecteurs, ou un produit vectoriel. Bah, pas encore, on reste en python chocolat, poire… Vanille !

  power = sum(
      reduce(lambda x, y: x * y, [max(i) for i in zip(*elements)])
      for game, elements in datas
  )
  print(f"Sum of Power of games : {power}")

  Le reduce sert à multiplier entre eux tous les éléments de la liste, et le zip va transformer une liste de triplets (r, v, b) en triplet de listes ([r, r, r…], [v, v, v…], [b, b, b…]).

  Jusqu'ici, ya pas grand chose à déclarer, on manipule des données, on n'a même pas vraiment besoin de trop se compliquer à trouver les bonnes structures de données.

  • Yth.

  • [^] # Re: Commencer à représenter le problème pas trop bêtement.

    Posté par 🚲 Tanguy Ortolo (site web personnel) le 04 décembre 2023 à 17:17. Évalué à 4.

    

    Tu n'utilises pas enum.Enum ? Je trouve ça bien pratique pour, eh bien, les cas comme les couleurs, là.

    • [^] # Re: Commencer à représenter le problème pas trop bêtement.

      Posté par Yth (Mastodon) le 04 décembre 2023 à 17:28. Évalué à 2. Dernière modification le 04 décembre 2023 à 17:30.

      

      Le weekend, j'ai moins de cerveau, moins de temps, et je n'ai pas encore trop cherché les bonnes optimisations, mais je devrais commencer, pour reprendre les bonnes habitudes.
      Et me remettre en tête les structures de données moins utilisées, et pourtant tellement utiles.

      J'aurais aussi pu faire une classe cubes avec trois éléments red, green et blue, qui permet des comparaisons immédiates avec <, >, des min, max, sum, multiplications, etc.

      Après les opérations deviennent très simples. Je vais peut-être poster ça demain :)

      • Yth.

      • [^] # Re: Commencer à représenter le problème pas trop bêtement.

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

        

        Alors avec plus d'abstraction, j'ai ça :

        from dataclasses import dataclass
        @dataclass(frozen=True)
        class Bag():
          red: int = 0
          green: int = 0
          blue: int = 0
          def __le__(self, other):
            if self.red > other.red or self.green > other.green or self.blue > other.blue:
              return False
            return True
          def __add__(self, other):
            return Bag(
              red=max(self.red, other.red),
              green=max(self.green, other.green),
              blue=max(self.blue, other.blue),
            )
          @property
          def power(self):
            return self.red * self.green * self.blue

        Une classe pour représenter un sac, avec des cubes rouges, verts et bleus dedans. La dataclass c'est bien pratique, ça s'initialise automatiquement avec les paramètres fournis aux noms des variables, ou alors aux valeurs par défaut.
        Par exemple Bag() c'est 0 de chaque, Bag(red=12, green=5), ça fait ce qui est écrit en laissant blue à 0.
        Il est frozen ce qui signifie qu'on ne peut pas le modifier, donc les opérations retournent une nouvelle instance de Bag, c'est utile en optimisation parce que ça va plus vite. Ici c'est sans importance.

        On définit trois opérations dessus : __le__ permet de comparer bag1 <= bag2, c'est True ssi tous les éléments de bag1 sont inférieurs ou égaux à ceux de bag2.
        __add__ c'est un peu un hack, et ça retourne un Bag avec le maximum pour chaque valeur dans les deux Bag additionnés, ça permet d'utiliser la fonction sum() pour calculer un maximum, parce que la fonction max() fait des comparaisons, et retourne le Bag en entrée le plus grand, ce qui n'a rien à voir avec ce dont on a besoin.
        Et finalement power est un attribut qui sert au calcul du score du second exercice.

        Avec cette classe on va analyser les données, en exploitant les passages d'arguments python par dictionnaire, et les valeurs par défaut de Bag, c'est pas trop abscons à lire, si on n'est pas débutant en Python (et qu'on aime les struct-comprehension) :

        def input():
          for line in sys.stdin:
            game, cubes = line.strip().split(':')
            yield int(game.split(" ")[1]), sum(
              (
                Bag(**{
                  color: int(nb)
                  for cubes in bag.strip().split(",")
                  for nb, color in [cubes.strip().split(" ")]
                })
                for bag in cubes.split(";")
              ), Bag(),
            )

        En réalité on n'a jamais besoin des divers sacs possible, la seule chose qui nous intéresse c'est le maximum pour chaque valeur rouge, vert et bleu, d'où le sum(), et une fois cette optimisation faite, on réalise qu'on s'est furieusement compliqué la vie et qu'au final on avait juste besoin, depuis le tout début de l'exercice, de trouver ce maximum, et de ne s'intéresser qu'à lui.

        Les exercices ensuite sont triviaux, surtout le second, il n'y a vraiment plus rien à faire :

        datas = [x for x in input()]
        constraint = Bag(red=12, green=13, blue=14)
        r = sum(
          game
          for game, biggestbag in datas
          if biggestbag <= constraint
        )
        print(f"Possible games : {r}")
        
        power = sum(
          biggestbag.power
          for game, biggestbag in datas
        )
        print(f"Sum of Power of games : {power}")

        • Yth, qui vient de faire brûler un CPU sur l'exercice 5, parce que parfois c'est plus « rapide » de laisser turbiner que de trouver un meilleur algorithme, mais on en parle jour 5…

• # C'était trop simple... je suspecte un piège !

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

  

  Ma solution en Python :

  #!/bin/python3
  
  maxvalues = {
      "red":12,
      "green":13,
      "blue":14,
  }
  
  def number(game):
      return int(game.split(":")[0][5:])
  
  def possible(game):
      gamelist = game.split(":")[1].split(";")
      for g in gamelist:
          colorlist = g.split(",")
          for c in colorlist:
              n = int(c.split(" ")[1])
              color = c.split(" ")[2]
              if n > maxvalues[color]:
                  return False
      return True
  
  def power(game):
      minimum = {
          "red":0,
          "green":0,
          "blue":0,
      }
      gamelist = game.split(":")[1].split(";")
      for g in gamelist:
          colorlist = g.split(",")
          for c in colorlist:
              n = int(c.split(" ")[1])
              color = c.split(" ")[2]
              if n > minimum[color]:
                  minimum[color] = n
      return minimum["red"]*minimum["blue"]*minimum["green"]
  
  def solve1(testinput,testing=False):
      s = 0
      for line in testinput:
          if line == "" :
              continue
          p = possible(line)
          if testing:
              print(line, "=", p, ";Number=", number(line))
          if p:
              s += number(line)
      if testing:
          print(s)
      return s
  
  def solve2(testinput,testing=False):
      s = 0
      for line in testinput:
          if line == "" :
              continue
          p = power(line)
          if testing:
              print(line, ";Power=", p)
          s += p
      if testing:
          print(s)
      return s
  
  test1 = """Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
  Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
  Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
  Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
  Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green"""
  result1 = 8
  test2 = test1
  result2 = 2286
  
  def solve(short=False):
  
      print("----Part 1----")
      if short == False:
          if solve1(test1.split("\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")
          s1 = solve1(lines)
          print(s1)
  
      print("----Part 2----")
      if short == False:
          if solve2(test2.split("\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")
          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()

  C'était presque simple aujourd'hui, c'est suspect.

  L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

  • [^] # Re: C'était trop simple... je suspecte un piège !

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

    

    Jour 2, c'est simple, on ne se fait pas déjà des noeuds dans le cerveau, c'est normal…

    • Yth.

Suivre le flux des commentaires

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