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.