Comment réparer un pont, Advent of Code ay 7

Après ce qui semblait être une éternité (cinq heures, pour être précis), Day 20 part 2 a finalement décidé de coopérer. Je suis encore un peu étourdi par l’attente, mais le devoir m’appelle ! Aujourd'hui, nous abordons le jour 7 de l'Avent du Code, reprenant là où nous nous étions arrêtés avec le jour 6 la semaine dernière. Notre tâche aujourd'hui est de réparer un pont afin de pouvoir le traverser et de poursuivre notre recherche de l'historien en chef.

Une jolie illustration générée par Microsoft Copilot

Le défi d’aujourd’hui nous présente un autre type de problème : on nous donne des listes de nombres disposés dans un format spécifique (heureusement, pas un puzzle 2D aujourd’hui…). Chaque ligne est conçue pour former une équation, mais les opérateurs sont absents. Notre tâche est de tester divers opérateurs pour déterminer si l'équation résultante est vraie.

Nous utilisons deux fonctions d'analyse pour traiter l'entrée. La fonction d'analyse divise d'abord chaque ligne par le caractère deux-points (:) :

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

parse_line convertit la chaîne attendue et la chaîne d'opérandes en entiers, renvoyant un tuple contenant l'entier attendu et un tuple d'opérandes entiers

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

Je préfère un style de programmation fonctionnel, et malgré la nature impérative de Python, les bibliothèques comme toolz/cytoolz sont incroyablement utiles. Aujourd'hui, nous utilisons thread_first de toolz.functoolz. Voici comment fonctionne thread_first : il prend une valeur initiale, puis applique une séquence de paires fonction-argument, en enfilant le résultat à chaque étape.

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

Dans cet exemple, thread_first commence par 1, puis applique add avec 2 (ce qui donne 3) et enfin applique mul avec 2 (ce qui donne 6). Cela équivaut à mul(add(1, 2), 2).

Nous définissons maintenant la fonction calculer pour appliquer les opérations. Il prend un tuple de fonctions (funcs) et un tuple d'opérandes (opérandes) en entrée :

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

L'assertion garantit un opérande de plus que les fonctions. operands[1:] fournit les opérandes des fonctions. zip et * créent les paires fonction-opérande pour thread_first, qui effectue les calculs enchaînés.

Exemple :

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Nous pouvons maintenant vérifier chaque ligne de l'entrée à l'aide de la fonction check_can_calibrate. Cette fonction prend en entrée le résultat attendu, les opérandes et un tuple de fonctions possibles, et renvoie True si une combinaison de fonctions produit le résultat attendu, et False sinon :

def check_can_calibrate(
    expected: int,
    operands: tuple[int, ...],
    funcs: tuple[Callable[[int, int], int], ...],
) -> bool:
    return next(
        filter(
            None,
            (
                calculate(funcs, operands) == expected
                for funcs in product(funcs, repeat=len(operands) - 1)
            ),
        ),
        False,
    )

itertools.product génère toutes les combinaisons de fonctions. Une expression génératrice vérifie si une combinaison correspond au résultat attendu. filter(None, ...) et next(..., False) trouvent efficacement le premier résultat True ou renvoient False si aucun n'est trouvé.

Pour la première partie, nous ne disposons que d’opérateurs de multiplication et d’addition. Le puzzle demande la somme des valeurs attendues, où une équation valide peut être formée à l'aide de ces opérateurs. Nous implémentons la fonction d'évaluation pour calculer cette somme :

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

Il parcourt l'entrée analysée et additionne les valeurs attendues pour lesquelles check_can_calibrate renvoie True.

Enfin, nous assemblons la partie 1 à partir de ce que nous avons déjà construit jusqu'à présent

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

Cette fonction analyse l'entrée à l'aide de parse, puis appelle évaluer avec les données analysées et le tuple de fonctions (operator.mul, Operator.add), représentant respectivement la multiplication et l'addition.

Dans la partie 2, nous rencontrons un opérateur de concaténation qui joint deux nombres ensemble. En Python, cela équivaut à utiliser une f-string :

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

Cela crée effectivement un nouveau numéro en ajoutant les chiffres du deuxième numéro à la fin du premier numéro.

Alternativement, nous pouvons effectuer la concaténation en utilisant une formule mathématique. Le nombre de chiffres dans un entier positif x peut être calculé à l'aide de la formule :

Cela fonctionne car log₁₀(x) donne la puissance à laquelle 10 doit être élevé pour obtenir x. La fonction floor arrondit ce résultat à l'entier le plus proche, et l'ajout de 1 donne le nombre de chiffres. Prenons 123 comme exemple :

Implémentation de ceci en tant que fonction int_concat :

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

L'exécution d'une concaténation d'entiers évite mathématiquement la surcharge liée aux conversions de chaînes. La concaténation de chaînes implique une allocation et une manipulation de mémoire, ce qui est moins efficace que l'arithmétique directe des nombres entiers, en particulier pour les grands nombres ou les nombreuses concaténations. Cette approche mathématique est donc généralement plus rapide et plus économe en mémoire.

Enfin, nous implémentons la partie 2. La seule différence par rapport à la partie 1 est l'ajout de l'opérateur int_concat :

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Ta-da ! Nous avons réussi le Jour 7. C'était un défi relativement simple, surtout par rapport aux jours suivants (l'optimisation du Jour 20 me donne toujours mal à la tête ?). Même si ce n'est peut-être pas le plus performant, j'ai donné la priorité à la lisibilité.

C’est tout pour aujourd’hui. Bonnes vacances et bonne année ?! On croise les doigts pour une meilleure situation professionnelle l'année prochaine (toujours #OpenToWork, envoyez-moi un ping pour des collaborations !), et j'écrirai à nouveau la semaine prochaine.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!