Forum Programmation.autre Avent du Code, jour 9

Post√©¬†par¬† (site web personnel) . Licence CC¬†By‚ÄĎSA.
√Čtiquettes¬†:
4
9
déc.
2022

Suite de l'Avent du Code, jour 9.

√áa y est, nous sommes vraiment en route dans la for√™t. Il y a un pont de singe √† traverser, mais si les lutins sont bien pass√©s il n'est en revanche pas certain qu'il supporte l'embonpoint du P√®re No√ęl. Ce dernier doit donc calculer des trajectoires de cordes ob√©issant √† la m√©trique associ√©e √† la distance de Tchebychev. Logique.

  • # En Python, mod√©lis√©

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

    #! /usr/bin/python3
    
    # Advent of Code 2022, day 9
    
    from __future__ import annotations
    
    from enum import Enum
    from typing import Iterable, Iterator, Set, Tuple
    
    
    Coords = Tuple[int, int]
    
    
    class Direction(Enum):
        O  = ( 0,  0)
        U  = ( 0,  1)
        D  = ( 0, -1)
        L  = (-1,  0)
        R  = ( 1,  0)
        UL = (-1,  1)
        UR = ( 1,  1)
        DL = (-1, -1)
        DR = ( 1, -1)
    
        def __init__(self, dx, dy):
            self.dx = dx
            self.dy = dy
    
    
    class Knot:
        def __init__(self, x: int, y: int):
            self.x = x
            self.y = y
    
        @property
        def coords(self) -> Coords:
            return (self.x, self.y)
    
        def move(self, direction: Direction) -> None:
            self.x += direction.dx
            self.y += direction.dy
    
        def dist(self, other: Knot) -> int:
            """"Chebyshev distance! (Not really used in my code, actually)"""
            return max(abs(self.x - other.x), abs(self.y - other.y))
    
        def direction_to(self, other: Knot) -> Direction:
            dx = other.x - self.x
            dy = other.y - self.y
            if dx < -1:
                if dy < 0:
                    return Direction.DL
                if dy == 0:
                    return Direction.L
                if dy > 0:
                    return Direction.UL
            if dx == -1:
                if dy < -1:
                    return Direction.DL
                if -1 <= dy <= 1:
                    return Direction.O
                if dy > 1:
                    return Direction.UL
            if dx == 0:
                if dy < -1:
                    return Direction.D
                if -1 <= dy <= 1:
                    return Direction.O
                if dy > 1:
                    return Direction.U
            if dx == 1:
                if dy < -1:
                    return Direction.DR
                if -1 <= dy <= 1:
                    return Direction.O
                if dy > 1:
                    return Direction.UR
            if dx > 1:
                if dy < 0:
                    return Direction.DR
                if dy == 0:
                    return Direction.R
                if dy > 0:
                    return Direction.UR
            assert False  # cannot happen, all cases were covered
    
        def follow(self, other: Knot) -> None:
            self.move(self.direction_to(other))
    
    
    class Rope:
        def __init__(self, n_knots: int) -> None:
            self.knots = [Knot(0, 0) for _ in range(n_knots)]
    
        @property
        def head(self) -> Knot:
            return self.knots[0]
    
        @property
        def tail(self) -> Knot:
            return self.knots[-1]
    
        def move(self, direction: Direction) -> None:
            self.head.move(direction)
            for i in range(1, len(self.knots)):
                leader = self.knots[i - 1]
                follower = self.knots[i]
                follower.follow(leader)
    
    
    def import_lines(lines: Iterable[str]) -> Iterator[Direction]:
        for line in lines:
            word1, word2 = line.split()
            direction = Direction[word1]
            repeat = int(word2)
            for _ in range(repeat):
                yield direction
    
    
    def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
        """Solve both parts of today's puzzle"""
        rope = Rope(10)
        visited1 = set()  # type: Set[Coords]
        visited2 = set()  # type: Set[Coords]
        for direction in import_lines(lines):
            rope.move(direction)
            visited1.add(rope.knots[1].coords)
            visited2.add(rope.tail.coords)
    
        return len(visited1), len(visited2)

    J'aurais bien aimé éviter d'énumérer tous les cas de mouvement de suivi, mais je n'ai rien trouvé d'astucieux pour éviter cela.

    J'espère que dans vos solutions perso, vous aurez pensé à utiliser, en arrivant à la deuxième partie, à utiliser une seule corde pour simuler les deux…

    • [^] # Re: En Python, mod√©lis√©

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†2. Derni√®re modification le 09 d√©cembre 2022 √† 13:56.

      C'est pas tres joli non plus, mais on peut utiliser getattr/setattr pour factoriser la meme operation cote x et y dans la fonction de suivi:

      def get_closer(H: Point, T: Point, axis: str, aligned: bool) -> bool:
          diff = getattr(T, axis) - getattr(H, axis)
          if abs(diff) == 2:
              get_closer_by_1(H, T, axis)
              if not aligned:
                  get_closer_by_1(H, T, "y" if axis == "x" else "x")
              return True
          return False
      
      def get_closer_by_1(H: Point, T: Point, axis):
          setattr(
              T, axis, getattr(T, axis) + (1 if getattr(H, axis) > getattr(T, axis) else -1)
          )
      
      def follow(H: Point, T: Point):
          aligned = T.x == H.x or T.y == H.y
          if not get_closer(H, T, "y", aligned):
              get_closer(H, T, "x", aligned)
      
      for input in inputs:
          for i in range(input[1]):
              match input[0]:
                  case "U":
                      H[0].y += 1
                  case "L":
                      H[0].x -= 1
                  case "R":
                      H[0].x += 1
                  case "D":
                      H[0].y -= 1
              for j in range(1, size_tail + 1):
                  follow(H[j - 1], H[j])
              visited.add((H[size_tail].x, H[size_tail].y))

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: En Python, mod√©lis√©

        Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†3.

        Ce serait sans doute plus joli avec des coordonn√©es index√©es (une liste de coordonn√©es en somme) plut√īt que nomm√©es.

        Mais ce n'est de toute façon pas très compréhensible, de cette façon-là.

    • [^] # Re: En Python, mod√©lis√©

      Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†3. Derni√®re modification le 09 d√©cembre 2022 √† 16:58.

      Bon, en fait, pas besoin d'√©num√©rer de fa√ßon aussi laborieuse bien s√Ľr¬†:

      from __future__ import annotations
      
      from enum import Enum
      from typing import Iterable, Iterator, Set, Tuple
      
      
      Coords = Tuple[int, int]
      
      
      class Direction(Enum):
          O  = ( 0,  0)
          U  = ( 0,  1)
          D  = ( 0, -1)
          L  = (-1,  0)
          R  = ( 1,  0)
      
          def __init__(self, dx, dy):
              self.dx = dx
              self.dy = dy
      
      
      class Knot:
          def __init__(self, x: int, y: int):
              self.x = x
              self.y = y
      
          @property
          def coords(self) -> Coords:
              return (self.x, self.y)
      
          def move(self, direction: Direction) -> None:
              self.x += direction.dx
              self.y += direction.dy
      
          def dist(self, other: Knot) -> int:
              return max(abs(self.x - other.x), abs(self.y - other.y))
      
          def follow(self, other: Knot) -> None:
              if self.dist(other) <= 1:
                  return
              if self.x < other.x:
                  self.x += 1
              if self.x > other.x:
                  self.x -= 1
              if self.y < other.y:
                  self.y += 1
              if self.y > other.y:
                  self.y -= 1
      
      
      class Rope:
          def __init__(self, n_knots: int) -> None:
              self.knots = [Knot(0, 0) for _ in range(n_knots)]
      
          @property
          def head(self) -> Knot:
              return self.knots[0]
      
          @property
          def tail(self) -> Knot:
              return self.knots[-1]
      
          def move(self, direction: Direction) -> None:
              self.head.move(direction)
              for i in range(1, len(self.knots)):
                  leader = self.knots[i - 1]
                  follower = self.knots[i]
                  follower.follow(leader)
      
      
      def import_lines(lines: Iterable[str]) -> Iterator[Direction]:
          for line in lines:
              word1, word2 = line.split()
              direction = Direction[word1]
              repeat = int(word2)
              for _ in range(repeat):
                  yield direction
      
      
      def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
          """Solve both parts of today's puzzle"""
          rope = Rope(10)
          visited1 = set()  # type: Set[Coords]
          visited2 = set()  # type: Set[Coords]
          for direction in import_lines(lines):
              rope.move(direction)
              visited1.add(rope.knots[1].coords)
              visited2.add(rope.tail.coords)
      
          return len(visited1), len(visited2)
      • [^] # Re: En Python, mod√©lis√©

        Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†4.

        J'espère que dans vos solutions perso, vous aurez pensé à utiliser, en arrivant à la deuxième partie, à utiliser une seule corde pour simuler les deux…

        Pas lors de la première résolution, mais après en nettoyant un peu le code oui… Comme d'hab, le problème arrivant en deux fois, on n'optimise pas dès le début pour la seconde partie :)

        Voici mon code :

        import numpy
        input = [(r[0], int(r[2:])) for r in sys.stdin]
        
        move = dict(
            U=(0, 1),
            D=(0, -1),
            L=(-1, 0),
            R=(1, 0),
        )
        def follow(head, tail):
            delta = head - tail
            if max(abs(delta)) <= 1:  # no move
                return
            if delta[0]:
                tail[0] += 1 if delta[0] > 0 else -1
            if delta[1]:
                tail[1] += 1 if delta[1] > 0 else -1
        
        
        knots = [numpy.array((0, 0)) for _ in range(10)]
        tail1_pos = {(0, 0), }
        tail_pos = {(0, 0), }
        for dir, nb in input:
            for _ in range(nb):
                knots[0] += move[dir]
                for n in range(1, 10):
                    follow(knots[n-1], knots[n])
                tail1_pos.add(tuple(knots[1]))
                tail_pos.add(tuple(knots[-1]))
        print(f"Tail positions visited : {len(tail1_pos)}")
        print(f"LongTail positions visited : {len(tail_pos)}")

        Pas trop modélisé, des vecteurs numpy juste pour avoir des simplifications comme l'addition, la soustraction ou la valeur absolue.
        J'aime bien ton import_line qui fait un unique itérateur pour chaque mouvement unitaire, c'est propre !

        Et donc :

        def input():
            move = dict(
                U=(0, 1),
                D=(0, -1),
                L=(-1, 0),
                R=(1, 0),
            )
            for line in sys.stdin:
                direction = move[line[0]]
                for _ in range(int(line[2:])):
                    yield direction
        
        def follow(head, tail):
            delta = head - tail
            if max(abs(delta)) <= 1:  # no move
                return
            if delta[0]:
                tail[0] += 1 if delta[0] > 0 else -1
            if delta[1]:
                tail[1] += 1 if delta[1] > 0 else -1
        
        knots = [numpy.array((0, 0)) for _ in range(10)]
        tail1_pos = {(0, 0), }
        tail_pos = {(0, 0), }
        for direction in input():
            knots[0] += direction
            for n in range(1, 10):
                follow(knots[n-1], knots[n])
            tail1_pos.add(tuple(knots[1]))
            tail_pos.add(tuple(knots[-1]))
        print(f"Tail positions visited : {len(tail1_pos)}")
        print(f"LongTail positions visited : {len(tail_pos)}")
        • Yth.
        • [^] # Re: En Python, mod√©lis√©

          Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4. Derni√®re modification le 09 d√©cembre 2022 √† 18:05.

          Tu peux te passer de la position initiale dans l'ensemble des positions visitées : après le premier mouvement, la queue de la corde y sera toujours.

          • [^] # Re: En Python, mod√©lis√©

            Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†3.

            C'est vrai !

            Bon, comme j'aime bien les trucs rigolos qui bougent, j'ai fait une animation en terminal.
            On ajoute ça :

            import os
            import time
            class display:
                def __init__(self):
                    self.w, self.h = tuple(os.get_terminal_size())
                    self.h -= 1
                    self.delta = numpy.array((self.w//2, self.h//2))
                    self.top = "*" * (self.w)
                    self.line = "*" + " " * (self.w - 2) + "*"
                    self.background = self.top + "".join(
                        self.line for _ in range(self.h - 2)) + self.top
            
                def __call__(self, knots):
                    x, y = self.delta + knots[0]
                    if x <= 0:
                        self.delta[0] += 1
                    if x >= self.w-1:
                        self.delta[0] -= 1
                    if y <= 0:
                        self.delta[1] += 1
                    if y >= self.h-1:
                        self.delta[1] -= 1
                    txt = [c for c in self.background]
                    for knot in knots:
                        x, y = knot + self.delta
                        txt[int(x + y * self.w)] = "#"
                    print("".join(txt))
                    time.sleep(.01)
            
            d = display()

            Et dans la boucle on ajoute à la fin : d(knots)
            J'ai 11460 mouvements dans mon input, à cette vitesse - sleep(.01) - ça prends 2 minutes et quelques.

            √áa commence centr√© sur le d√©marrage, et quand la t√™te d√©borde d'un c√īt√©, on translate tout pour garder dans le champs.

            • Yth, du temps √† perdre on dirait‚Ķ
            • [^] # Re: En Python, mod√©lis√©

              Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

              J'adore l'animation !

              Pour limiter les glitches, j'ai ajouté print("\033[0;0H", end='') au début du __call__.
              Ça replace le curseur la coordonnée (0,0) du terminal ce qui évite le scrolling.

              Dans la même veine, il est bénéfique de cacher le curseur avec tput civis avant de lancer l'animation. À la fin de l'animation, le remettre avec tput cnorm

              • [^] # Re: En Python, mod√©lis√©

                Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†3.

                Bonne idée de remettre le curseur en haut !
                Et encore une petite amélioration inutile donc indispensable :

                        top = "*" * (self.w)
                        lines = [
                            "*" + "‚ĖĎ " * (self.w//2 - 1) + "*",
                            "*" + " ‚ĖĎ" * (self.w//2 - 1) + "*",
                        ]
                        self.backgrounds = [
                            top + "".join(lines[_ % 2] for _ in range(self.h - 2)) + top,
                            top + "".join(lines[1 - _ % 2] for _ in range(self.h - 2)) + top,
                        ]
                [...]
                        txt = [c for c in self.backgrounds[sum(self.delta) % 2]]
                [...]
                            txt[int(x + y * self.w)] = "‚Ėą"

                On a un fond en √©chiquier, qui bascule quand on ¬ę¬†d√©place la cam√©ra¬†¬Ľ, √ßa permet de visuellement voir que √ßa d√©file.
                Ça marche parce qu'on décale toujours de 1, et ça alterne entre les deux fonds quelle que soit la direction du déplacement.
                Et avec des caractères utf-8 de bloc plein, ou gris, c'est plus joli.

                • Yth.
                • [^] # Re: En Python, mod√©lis√©

                  Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

                  Splendide !

                  J'ai réutilisé l'idée de l'utf8 pour le jour 10 aussi. La lecture du LCD est infiniment plus facile, plus besoin de plisser les yeux pour deviner les lettres.

                  Pour l'animation de la corde j'ai choisis d'afficher le numéro du noeud (0 à 9) en noir sur fond jaune ; et de déplacer la caméra de 19 d'un coup. J'aimais pas trop la voir manger le mur :). J'ai aussi géré les largeurs impaires, c'est le cas de mon terminal.

                  class display:
                      def __init__(self):
                          self.w, self.h = tuple(os.get_terminal_size())
                          border = "o"
                          self.delta = numpy.array((self.w//2, self.h//2))
                          top = border * (self.w)
                          wodd = self.w%2
                          lines = [
                              border + "‚ĖĎ " * (self.w//2-1) + "‚ĖĎ"*wodd + border,
                              border + " ‚ĖĎ" * (self.w//2-1) + " "*wodd + border
                          ]
                          self.background = [
                              top + "".join(lines[h%2] for h in range(self.h - 2)) + top,
                              top + "".join(lines[1-h%2] for h in range(self.h - 2)) + top
                          ]
                  
                      def __call__(self, knots):
                          print("\033[0;0H", end='')
                          x, y = self.delta + knots[0]
                          J = 19  # must be odd to see scroll
                          if x <= 0:
                              self.delta[0] += J
                          if x >= self.w-1:
                              self.delta[0] -= J
                          if y <= 0:
                              self.delta[1] += J
                          if y >= self.h-1:
                              self.delta[1] -= J
                          txt = [c for c in self.background[sum(self.delta)%2]]
                          for i,knot in enumerate(reversed(knots)):
                              x, y = knot + self.delta
                              txt[int(x + y * self.w)] = "\033[30;43m" + str(9-i) + "\033[0m"
                          print("".join(txt),end='')
                          time.sleep(.008)
                  • [^] # Re: En Python, mod√©lis√©

                    Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

                    C'est Tanguy qui a pensé à l'utf8 en premier pour le jour 10, je reprends les bonnes idées :)

                    • Yth.
                    • [^] # Re: En Python, mod√©lis√©

                      Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

                      Ah exacte, ligne 1527 et 1529 de son programme ūüėá

                      • [^] # Re: En Python, mod√©lis√©

                        Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

                        Eh oh, je sais que j'écris du code-fleuve, mais pas la peine de se moquer non plus !

                        • [^] # Re: En Python, mod√©lis√©

                          Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

                          Je me moque gentiment. Tu as affiché clairement ton envie de faire du code propre, modélisé, typé. Et c'est louable.
                          Moi je pense avoir affiché mon objectif : peut importe le moyen pourvu qu'on ait la réponse le plus vite possible :)

  • # Coin coin

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

    Le probl√®me parle de corde √† nŇďuds, mais m'√©voquerait plut√īt une canne et ses canetons, pas vous¬†?

  • # Ma solution

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†3.

    Et voici ma solution. Et sans énumérer tous les cas de mouvement de suivi<

    #!/usr/bin/python3
    
    def yield_input():
        import sys
        with open(sys.argv[1]) as f:
            for l in f:
                l = l.strip()
                yield l
    
    class Coord:
        def __init__(self):
            self.x = 0
            self.y = 0
    
        def up(self):
            self.x += 1
    
        def down(self):
            self.x -= 1
    
        def right(self):
            self.y += 1
    
        def left(self):
            self.y -= 1
    
        def follow(self, other):
            x_dist = abs(self.x-other.x)
            y_dist = abs(self.y-other.y)
            if x_dist <= 1 and y_dist <= 1:
                return
            if x_dist == 0:
                self.y += 1 if other.y>self.y else -1
            elif y_dist == 0:
                self.x += 1 if other.x>self.x else -1
            else:
                self.y += 1 if other.y>self.y else -1
                self.x += 1 if other.x>self.x else -1
    
        def as_tuple(self):
            return (self.x, self.y)
    
    class Rope:
        def __init__(self, length):
            self.tails_positions = set()
            self.knots = []
            for _ in range(length):
                self.knots.append(Coord())
            self.tails_positions.add(self.knots[-1].as_tuple())
    
        def up(self):
            self.knots[0].up()
            self.follow()
    
        def down(self):
            self.knots[0].down()
            self.follow()
    
        def right(self):
            self.knots[0].right()
            self.follow()
    
        def left(self):
            self.knots[0].left()
            self.follow()
    
        def follow(self):
            for i, knot in enumerate(self.knots[1:]):
                knot.follow(self.knots[i])
            self.tails_positions.add(self.knots[-1].as_tuple())
    
    command_map = {
        'U': "up",
        'D': "down",
        'R': "right",
        'L': "left",
    }
    
    def main():
        rope1 = Rope(2)
        rope2 = Rope(10)
    
        for command in yield_input():
            direction, number = command.split()
            for _ in range(int(number)):
                getattr(rope1, command_map[direction])()
                getattr(rope2, command_map[direction])()
    
        print("Round 1 :", len(rope1.tails_positions))
        print("Round 2 :", len(rope2.tails_positions))
    
    
    if __name__ == "__main__":
        main()

    Matthieu Gautier|irc:starmad

  • # pfiu

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

    J'ai fait la première partie en AWK en une petite demie heure.
    J'ai eu pas mal de chance car mes calculs étaient approximatifs mais suffisant pour le cas à un noeud.

    En voyant la seconde partie, j'ai tout ré-écrit en python car j'y ai vu un truc récursif.
    J'ai pigé assez vite qu'il fallait mieux faire toutes les étapes, case par case pour tous les neouds.
    Ça donnait toujours le bon résultat pour le premier noeud mais pas pour le dernier.

    J'ai mis vraiment beaucoup de temps à débugger en pas à pas et ajuster mes calculs. Plusieurs heures :(
    Pour au final un code très impératif que j'aurai presque pu laisser en AWK.

    Bref dur ce jour pour moi

    part 1

    BEGIN{P["0_0"]=1; Hx=Hy=Tx=Ty=0}
    function abs(x) { return x>0?x:-x}
    {
      print "==", Hx","Hy, ";", Tx","Ty, "==", $1, $2
      for(i=1;i<=$2;i++){
        if($1=="R") {Hx++}
        if($1=="L") {Hx--}
        if($1=="U") {Hy++}
        if($1=="D") {Hy--}
        dh = abs(Hx-Tx)  # tension horizontale
        dv = abs(Hy-Ty)  # tension vertivale
        if(dh>1 && $1=="R") {Tx++; if (dv>0) {Ty=Hy}}
        if(dh>1 && $1=="L") {Tx--; if (dv>0) {Ty=Hy}}
        if(dv>1 && $1=="U") {Ty++; if (dh>0) {Tx=Hx}}
        if(dv>1 && $1=="D") {Ty--; if (dh>0) {Tx=Hx}}
        P[Ty "_" Tx]=1
        print Hx, Hy, ";", "dh:"dh, "dv:"dv, "=>", Tx, Ty
      }
    }
    END{print length(P)}

    part 2

    import sys
    
    rope = [(0,0) for _ in range(10)]
    P = [{(0,0)} for _ in range(10) ]
    D = {"R":(1,0),"L":(-1,0),"U":(0,1),"D":(0,-1)}
    
    for l in sys.stdin.read().splitlines():
      M, q = l.split(" ")
      q = int(q)
      for k in range(q):
        (x,y) = rope[0]
        (dx,dy) = D[M]
        rope[0] = (x+dx, y+dy)
        for i in range(1,10):
          (Hx,Hy) = rope[i-1]
          (Tx,Ty) = rope[i]
          dh = Hx-Tx  # tension horizontale
          dv = Hy-Ty  # tension vertivale
          if (abs(dh)>1):
            Tx += 1 if dh > 0 else -1
            if (abs(dv)>0):
              Ty += 1 if dv > 0 else -1
          elif (abs(dv)>1):
            Ty += 1 if dv > 0 else -1
            if (abs(dh)>0):
              Tx += 1 if dh > 0 else -1
          P[i].add((Tx,Ty))
          rope[i] = (Tx,Ty)
    
    print(*(len(p) for p in P))

Suivre le flux des commentaires

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