Forum Programmation.autre Avent du Code, jour 10

Posté par 🚲 Tanguy Ortolo (site web personnel) le 10 décembre 2022 à 13:00. Licence CC By‑SA.

Étiquettes :

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 🚲 Tanguy Ortolo (site web personnel) le 10 décembre 2022 à 13:02. É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 steph1978 le 10 décembre 2022 à 13:35. É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 Yth (Mastodon) le 10 décembre 2022 à 15:14. É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 steph1978 le 10 décembre 2022 à 16:14. É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 Yth (Mastodon) le 10 décembre 2022 à 14:50. É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.

# Où est la partie 2 ?

Posté par gled le 10 décembre 2022 à 15:12. É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 Yth (Mastodon) le 10 décembre 2022 à 15:18. É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 🚲 Tanguy Ortolo (site web personnel) le 10 décembre 2022 à 15:19. É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 gled le 10 décembre 2022 à 15:49. Évalué à 1.
    
    Ah d'accord, merci à vous deux, Yth et 🚲 Tanguy Ortolo de la confirmation, bien dommage alors.

# Plus simple

Posté par GaMa (site web personnel) le 10 décembre 2022 à 16:19. É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 🚲 Tanguy Ortolo (site web personnel) le 10 décembre 2022 à 19:53. É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 Yth (Mastodon) le 10 décembre 2022 à 20:16. É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 steph1978 le 10 décembre 2022 à 21:08. É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 steph1978 le 11 décembre 2022 à 14:27. É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 steph1978 le 01 janvier 2023 à 19:43. É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.