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.