Forum Programmation.autre Advent of Code 2023 : Day 2

Posté par  . Licence CC By‑SA.
Étiquettes :
2
3
déc.
2023

Le deuxiÚme d'une série de 25 forums qui proposeront de partager vos solutions pour l'édition 2023 de l'Advent of Code.

Vous pouvez vous inscrire à un leadboard privé que j'ai créé pour LinuxFR : 2423220-c94050af

Jour 2 (résumé) :

Partie 1

Vous ĂȘtes arrivĂ© sur l'Ăźle de la Neige, et en marchant avec les lutins locaux pour aller inspecter la production, ils vous proposent un petit jeu.

Un lutin a un sac avec des cubes rouges, verts et bleus, et vous montre un certain nombre de fois un certain nombre de cubes tirés du sac.

On note les jeux ainsi :

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

Ici, au premier jeu, le lutin a tiré 3 bleus 4 rouges, puis 2 verts 6 bleus, puis 2 verts (avec remise). S'il n'y a que 12 cubes rouges, 13 cubes vert et 14 cubes bleus dans le sac, quels jeux sont possibles ?

Ici, le 1, 2 et 5 sont possibles, et la somme de ses chiffres qu'il faut trouver fait 8.

Image

Partie 2

Les lutins ne produisent plus de neige, car ils n'ont plus d'eau ! Il vous faut donc monter à la source pour voir ce qu'il s'y passe.

En chemin, le lutin vous propose une autre variante de son jeu : combien faut-il de cubes de chaque couleur au minimum dans le sac pour que le jeu soit possible ?

En reprenant l'exemple précédent :

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

Il faut 4 rouges, 2 verts et 6 bleus pour le premier jeu. Le pouvoir d'un jeu est ces trois nombres multipliés ensemble, soit 48 pour le premier jeu, puis 12, 1560, 630, 36. La somme totale fait 2286. C'est ce qu'il faut trouver.

  • # Commencer Ă  reprĂ©senter le problĂšme pas trop bĂȘtement.

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

Suivre le flux des commentaires

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