Forum Programmation.autre Avent du Code, jour 10

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

Suite de l'Avent du Code, jour 10.

Le P√®re No√ęl est tomb√© dans un torrent et n'a pas bien entendu ce que les lutins ont voulu lui dire avant de continuer leur chemin. Pour trouver un moyen de communiquer avec eux, il faut r√©impl√©menter le processeur de son communicateur, qui a un peu souffert de l'humidit√©.

  • # En Python, mod√©lis√©

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†5. Derni√®re modification le 10 d√©cembre 2022 √† 13:03.

    Sans surprise, j'ai implémenté un CPU selon les spécifications fournies. Mais pour ce qui est de faire quelque chose à partir des états qu'il atteint à des cycles donnés, je me suis amusé à y introduire ce que j'ai appelé un débogueur, je vous laisse découvrir ça.

    import io
    
    from enum import Enum
    from typing import Callable, Iterable, Iterator, List, Optional, Tuple
    
    
    class Operation(Enum):
        addx = ('addx', 1, 2)
        noop = ('noop', 0, 1)
    
        def __init__(self, word: str, nargs: int, cycles: int) -> None:
            self.word = word
            self.nargs = nargs
            self.cycles = cycles
    
    
    class Instruction:
        def __init__(self, op: Operation, *args: int) -> None:
            self.op = op
            if len(args) != op.nargs:
                raise ValueError(
                        "operator {} expect {} arguments".format(op, op.nargs))
            self.args = args
    
    
    class CPU:
        def __init__(self, program: Iterable[Instruction],
                     debug: Optional[Callable[[int, int], None]] = None) -> None:
            self.X = 1
            self.cycle = 1
            self.program = program
            self.debug = debug
    
        def _apply(self, instruction: Instruction) -> None:
            if instruction.op is Operation.addx:
                self.X += instruction.args[0]
            elif instruction.op is Operation.noop:
                pass
    
        def _cycle(self) -> None:
            if self.debug is not None:
                self.debug(self.cycle, self.X)
            self.cycle += 1
    
        def run(self) -> None:
            last_instruction = None
            for instruction in self.program:
                for _ in range(instruction.op.cycles):
                    self._cycle()
                self._apply(instruction)
    
    
    def import_program(lines: Iterable[str]) -> Iterator[Instruction]:
        for line in lines:
            words = line.split()
            op = Operation[words[0]]
            args = [int(word) for word in words[1:]]
            yield Instruction(op, *args)
    
    
    class StrengthSum:
        def __init__(self) -> None:
            self.strength = 0
    
        def __call__(self, cycle: int, value: int) -> None:
            if cycle in (20, 60, 100, 140, 180, 220):
                self.strength += cycle * value
    
    
    class CRTDrawer:
        def __init__(self) -> None:
            self.crt = io.StringIO()
    
        @staticmethod
        def position(cycle: int) -> int:
            return (cycle - 1) % 40
    
        def __call__(self, cycle: int, value: int) -> None:
            position = self.position(cycle)
            if position == 0:
                self.crt.write('\n')
            if value - 1 <= position <= value + 1:
                self.crt.write('‚Ėą')
            else:
                self.crt.write(' ')
    
    
    class MultiDebug:
        def __init__(self, *debugs: Callable[[int, int], None]) -> None:
            self.debugs = debugs
    
        def __call__(self, cycle: int, value: int) -> None:
            for debug in self.debugs:
                debug(cycle, value)
    
    
    def solve_both(lines: Iterable[str]) -> Tuple[int, str]:
        """Solve part 1 of today's puzzle"""
        program = import_program(lines)
        strength_report = StrengthSum()
        crt_drawer = CRTDrawer()
        cpu = CPU(program, debug=MultiDebug(strength_report, crt_drawer))
        cpu.run()
        return strength_report.strength, crt_drawer.crt.getvalue()
  • # quick python

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

    Rien à voir avec hier, les deux parties en une grosse demie heure.

    part 1

    import sys
    
    X = 1
    C = 0
    S = []
    I = {20, 60, 100, 140, 180, 220}
    
    def inc():
      global C
      C += 1
      if C in I:
        S.append(C*X)
    
    for l in sys.stdin.read().splitlines():
      m, q = (l+" _").split(" ")[:2]
      if m == "noop":
        inc()
      else: # add
        inc()
        inc()
        X += int(q)
    
    print(sum(S))

    part 2

    import sys
    
    X = 1
    C = 0
    LCD = [["."]*40 for _ in range(6)]
    
    def inc():
      global C
      (r,c) = divmod(C, 40)
      C+=1
      if c in [X, X-1, X+1]:
        LCD[r][c]="#"
    
    for l in sys.stdin.read().splitlines():
      m, q = (l+" _").split(" ")[:2]
      if m == "noop":
        inc()
      else: # add
        inc()
        inc()
        X += int(q)
    
    print("\n".join("".join(r) for r in LCD))
    • [^] # Re: quick python

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†4. Derni√®re modification le 10 d√©cembre 2022 √† 15:14.

      Tu peux simplifier un peu ta gestion des input en faisant ça :

      for l in sys.stdin:
        m, *q = l.split()
        if m == "noop":
          inc()
        else: # add
          inc()
          inc()
          X += int(*q)

      Le premier point, d'utiliser for l in sys.stdin permet de ne pas lire tout l'input, mais simplement d'itérer sur les lignes, on reste plus bas en RAM, on traite un flux.

      Le second point, c'est d'utiliser *q pour prendre ¬ę¬†ce qui reste¬†¬Ľ.
      Dans le cas d'une ligne "noop" on a m="noop" et q=[].
      Dans le cas de "addx XX" on a m="addx" et q=[XX], une list avec la valeur en premier (et unique) élément.
      Mais en refilant *q √† int, il ¬ę¬†unpack¬†¬Ľ et int(*q) devient √©quivalent √† int(XX).

      Avec √ßa tu g√®res des instructions diff√©rentes, avec autant de param√®tres que tu veux, tu t'en fous au niveau du parsing, tu veux juste conna√ģtre l'instruction et passer le reste √† la gestion de l'instruction.

      Ça évite de rajouter un argument factice, et de splitter en ne prenant que les deux premiers.

      • Yth.

      PS: et aussi, chapeau pour la ma√ģtrise d'awk, j'en suis pas l√†¬†!

      • [^] # Re: quick python

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

        Ah ça c'est vu que j'ai bidouillé pour gérer un ou deux arguments par lignes :)
        Merci pour l'astuce, ça me resservira.

  • # Entre deux.

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

    Moins modélisé que Tanguy, mais plus que steph.

    import sys
    def input():
        for line in sys.stdin:
            yield tuple(line.split())
    
    class cpu:
        def __init__(self):
            self.X = 1
            self.history = []
        def noop(self):
            self.history.append(self.X)
        def addx(self, n):
            self.history.append(self.X)
            self.history.append(self.X)
            self.X += int(n)
        def __getitem__(self, n):  # Cycle 1 is history 0
            return self.history[n-1]
        def __call__(self, row, col):
            return "#" if abs(self.history[row * 40 + col] - col) <= 1 else " "
    
    
    mycpu = cpu()
    for action, *values in input():
        getattr(mycpu, action)(*values)
    
    signal_strength = sum(mycpu[n]*n for n in range(20, 221, 40))
    print(f"Signal Strength : {signal_strength}")
    screen = "\n".join(
        "".join(mycpu(row, col) for col in range(40))
        for row in range(6)
    )
    print(screen)

    Là je conserve tout l'historique des valeurs de X à chaque cycle, ça n'est évidemment pas viable sur un long programme.
    Il faudrait optimiser pour la demande, c'est à dire écrire instruction après instruction l'état de l'écran pour le cycle qui passe, et faire un hook sur les valeurs de la première question, pour additionner/stocker par ailleurs.

    Au début j'avais mis un compteur de cycle dans ma classe cpu mais à la fin je ne l'utilisais pas, alors je l'ai viré…
    C'est assez facile d' ¬ę¬†optimiser¬†¬Ľ la classe cpu pour qu'elle dessine l'√©cran au fur et √† mesure, on fait une m√©thode comme √ßa :

        def cycle(self):
            self.screen.append("#" if abs(self.X-self.col) <= 1 else " ")
            self.col = (self.col + 1) % 40
            if not self.col:
                self.screen.append("\n")
            self.history.append(self.X)

    Et définir self.col = 0; self.screen = [] dans l'init.
    On remplace les appels à self.history.append(self.X) par self.cycle().
    On réalise que cpu.noop ne fait plus qu'exécuter cpu.cycle, donc on garde noop et addx devient :

        def addx(self, n):
            self.noop()
            self.noop()
            self.X += int(n)

    On vire le cpu.call puisqu'on dessine l'écran à la volée dans mycpu.screen et on affiche print("".join(mycpu.screen)) à la fin. On n'a plus qu'à rajouter un history à 0 pour le cycle 0 inexistant, et on n'a plus besoin de faire return self.history[n-1] dans cpu.__getitem__()

    Avec tout ça mis en place on a un code plus concis, plus clair, mais on conserve toujours l'historique pour la question 1, et s'en débarrasser oblige a faire un hook un peu crados dans cpu.noop(), conserver le numéro du cycle courant, et si cycle%40==20 ajouter à self.signal_strength self.X * self.cycle.
    On se débarrasse de l'historique.

    Plus propre ?
    Moins propre ?
    Difficile à dire…
    Mais il s'agit de débuggage, donc on peut introduire un hook cpu.debug à chaque cycle, qui servirait à ça.

    Bilan :

    import sys
    def input():
        for line in sys.stdin:
            yield tuple(line.split())
    
    class cpu:
        def __init__(self):
            self.X = 1
            self.history = [0]
            self.col = 0
            self.screen = []
            self.cycle = 0
            self.strength = 0
        def debug(self):
            self.cycle += 1
            if self.cycle % 40 == 20:
                self.strength += self.cycle * self.X
        def noop(self):
            self.screen.append("#" if abs(self.X-self.col) <= 1 else " ")
            self.col = (self.col + 1) % 40
            if not self.col:
                self.screen.append("\n")
            self.debug()
        def addx(self, n):
            self.noop()
            self.noop()
            self.X += int(n)
    
    mycpu = cpu()
    for action, *values in input():
        getattr(mycpu, action)(*values)
    
    print(f"Signal Strength : {mycpu.strength}")
    print("".join(mycpu.screen))

    Bilan ?
    8 octets de différence dans le fichier final, temps d'exécution rigoureusement similaire.
    En pratique si on bourrine sur les entrées, le second code est plus lent puisqu'il maintient à jour un écran.
    On peut utiliser un deque pour cpu.screen et avoir un scroll automatique, ça restreint la RAM utilisée, qui reste stable quelles que soient les données en entrées.
    Alors que le premier fait juste un history.append(), ça pompe de la RAM (à l'infini d'ailleurs) mais pas du CPU.

    • Yth
  • # O√Ļ est la partie 2 ?

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

    Pour la somme des intensités, pas trop de difficultés, ma solution sans fioritures (en trichant un peu).

    cycles = {}
    x = 1
    cycle = 1
    for line in program.strip().split("\n"):
        cycle += 1
        cycles[cycle] = x
        try:
            x += int(line.split(" ")[1])
            cycle += 1
            cycles[cycle] = x
        except IndexError:
            # noop
            pass
    
    signals = [x * cycles[x] for x in range(20, 221, 40)]
    print(signals, sum(signals))

    Mais que faut-il faire ensuite¬†? O√Ļ est la seconde partie de l'exercice sur la page d'adventofcode¬†? La derni√®re phrase que je vois sur la page est :

    Find the signal strength during the 20th, 60th, 100th, 140th, 180th, and 220th cycles. What is the sum of these six signal strengths?

    Faut-il avoir un compte susnommé en bas de page pour le voir ?

    • [^] # Re: O√Ļ est la partie 2 ?

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

      Il faut te connecter, d'une façon ou d'une autre, j'utilise mon compte github perso.
      Et là tu as un jeu de donnée personnalisées en entrée, et tu peux fournir le résultat dans un champs spécifique en bas de page.
      Ça te donne accès au second exercice.

      • Yth.
    • [^] # Re: O√Ļ est la partie 2 ?

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

      Oui, la seconde partie appara√ģt alors avoir rentr√© la bonne r√©ponse √† la premi√®re partie. Et les donn√©es d'entr√©e et donc les bonnes r√©ponses sont associ√©es √† une identit√© en effet.

      • [^] # Re: O√Ļ est la partie 2 ?

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

        Ah d'accord, merci √† vous deux, Yth et ūüö≤ Tanguy Ortolo de la confirmation, bien dommage alors.

  • # Plus simple

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

    J'ai trouvé ce jour assez facile.
    J'ai pas modélisé un CPU complet comme Tanguy, c'est un peu l'enclume pour écraser la mouche.
    L'astuce pour rester simple, c'est de remplacer une instruction add (sur deux cycles) par une instruction noop et une instruction add (sur un cycle). Après ça roule tout seul.

    #!/usr/bin/python3
    
    def yield_input():
        import sys
        with open(sys.argv[1]) as f:
            for l in f:
                l = l.strip()
                yield l
    
    def yield_command():
        for line in yield_input():
            if line == "noop":
                yield None
            if line.startswith("addx"):
                v = int(line[5:])
                yield None
                yield v
    
    def round_1():
        X = 1
        result = 0
        for cycle, command in enumerate(yield_command(), 1):
            if cycle in (20, 60, 100, 140, 180, 220):
                result += cycle*X
            if command is not None:
                X += command
    
        print("Round 1 :", result)
    
    def round_2():
        X = 1
        result = 0
        for cycle, command in enumerate(yield_command()):
            current_pos = cycle%40
            char = "#" if abs(current_pos-X) <= 1 else " "
            end = "\n" if current_pos == 39 else ""
            print(char, end=end)
            if command is not None:
                X += command
    
    round_1()
    round_2()

    Matthieu Gautier|irc:starmad

    • [^] # Re: Plus simple

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

      J'ai pas modélisé un CPU complet comme Tanguy, c'est un peu l'enclume pour écraser la mouche.

      √áa reste √† voir, √ßa. Il y a eu un AoC o√Ļ on n'arr√™tait pas de ressortir un processeur bizarro√Įde pour l'enrichir de nouvelles instructions et variantes d'instructions existantes.

      Il y a un risque pour que ce ne soit pas la dernière fois que nous aurons à bidouiller avec du code machine de communicateur elfique…

      • [^] # Re: Plus simple

        Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2. Derni√®re modification le 10 d√©cembre 2022 √† 20:17.

        C'est un peu l'idée derrière mon propre code.
        Et si on l'enrichissait ?

        Par exemple si on veut ajouter une commande affxy a b - qui fait la fonction affine a*x+b - à deux arguments et trois cycles par exemple, dans mon code il suffit d'ajouter cette méthode :

            def affxy(self, a, b):
                self.noop()  # ou :
                self.noop()  # self.history.append(self.X)
                self.noop()  # pour la première version
                self.X = int(a) * self.X + int(b)

        Voilà, c'est géré.

        • Yth.
      • [^] # Re: Plus simple

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

        C'est l'AoC 2019 au moins un jour sur deux il fallait ressortir son processeur "intcode".

  • # un bout de AWK

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

    Je me suis laissé emporté par le python du jour 9.
    Le problème du jour passe très bien en AWK.

    part 1, 11 lines

    BEGIN { x=1 }
    function inc() {
        c+=1
        S += index("20,60,100,140,180,220,", c ",")>0 ? x*c : 0
    }
    { inc() }
    $1 == "addx" {
        inc()
        x+=$2
    }
    END { print S }

    part 2, 20 lines

    BEGIN { x=1 }
    function inc() {
        i = (c%40)
        A[c+1] = (i==x-1||i==x||i==x+1) ? "‚Ėą" : "‚ĖĎ"
        c+=1
    }
    { inc() }
    $1 == "addx" {
        inc()
        x+=$2
    }
    END {
        for (i=0;i<=5;i++) {
            r = ""
            for (j=1;j<=40;j++) {
                r = r A[i*40+j]
            }
            print r
        }
    }
    • [^] # Re: un bout de AWK

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

      Pour la partie deux, aucun intérêt à bufferiser avant d'afficher :

      awk, 14 loc

      function inc() {
          i = (c%40)
          r = r ((i==x||i==x+1||i==x+2) ? "‚Ėą" : " ")
          if (i == 39) {
              print r
              r = ""
          }
          c++
      }
      { inc() }
      $1 == "addx" {
          inc()
          x+=$2
      }

Suivre le flux des commentaires

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