Advent of code 2024^{mais c’est l’advent of unix code} - jour 3

• Jour 3
  • Intitulé résumé
    • Première partie
    • Deuxième partie
  • Commentaire de ma solution
    • Première partie
    • Deuxième partie

Jour 3

Introduction et jour 1
Jour 2 - Jour 4

Intitulé résumé

Première partie

It seems like the goal of the program is just to multiply some numbers. It does that with instructions like mul(X,Y), where X and Y are each 1-3 digit numbers. For instance, mul(44,46) multiplies 44 by 46 to get a result of 2024. Similarly, mul(123,4) would multiply 123 by 4.

However, because the program’s memory has been corrupted, there are also many invalid characters that should be ignored, even if they look like part of a mul instruction. Sequences like mul(4*, mul(6,9!, ?(12,34), or mul ( 2 , 4 ) do nothing.

Deuxième partie

There are two new instructions you’ll need to handle:

• The do() instruction enables future mul instructions.
• The don’t() instruction disables future mul instructions.

Only the most recent do() or don’t() instruction applies. At the beginning of the program, mul instructions are enabled.

Commentaire de ma solution

Première partie

Là on est typiquement sur un problème chouette pour du shell. Déjà c’est de la manipulation linéaire de texte. Ensuite c’est des regex. Miam miam on se régale.

Pour la première partie on va, comme pour le premier jour, se contenter de faire travailler grep :

< 3.input grep -Eo 'mul\([0-9]{1,3},[0-9]{1,3}\)' |
grep -Eo '[0-9]+,[0-9]+' |
tr ',' '*' | paste -s -d'+' |
bc

L’astuce ici est de connaître l’option -o de grep. Celle-ci permet de demander à grep qu’il n’affiche que les match (un par ligne) et non les lignes dans lesquelles il a y un ou plusieurs match. Cela permet de se retrouve avec une sortie toute propre

mul(1,2)
mul(764,2)

Qu’on peut ensuite modifier à notre guise pour piper dans bc. La transformation suite au premier grep peut être faite de mille façons différentes, celle ici est très “logique” pour notre cerveau mais ce n’est certainement pas la plus efficace.

Deuxième partie

Cette nouvelle version du problème revient à poser la question plus générale de comment filtrer entre deux patterns sur plusieurs lignes, un problème que je trouve étonnamment récurent. Si l’on veut, comme ici, supprimer entre deux patterns, on peut utiliser sed :

sed "/don't()/,/do()/ d"

Sauf que cela exclu le pattern de fin de notre intervalle. On aura encore des lignes avec do(). On pourrait suivre le sed avec grep -v "do()" et le tour serait jouer mais il est possible de le faire directement dans sed :

sed "/don't()/,/do()/ d; /do()/ d"

Il suffit de revérifier si la ligne contient do() après la première instruction et, si c’est le cas, la supprimer. Cette commande n’imprime donc que ce qui se trouve en dehors de l’intervalle dont/do, les patterns exclus.

J’avais aussi une solution avec awk :

awk 'BEGIN{p=1};/do()/{p=1};/don\047t()/{p=0};p'

ou plus joliment :

awk '
    BEGIN        {p=1}
    /do()/       {p=1}
    /don\047t()/ {p=0}
    p
    '

Malheureusement pour utiliser une apostrophe dans script awk appelé depuis le shell le plus fiable est d’inscrire son code octal \047. Bienvenue dans le quoting hell. A part ça j’aime bien ce bout d’awk parce qu’il permet d’évoquer plusieurs mécanismes fondamentaux.

1. Le bloc BEGIN

awk fonctionne, comme la plupart des outils tradi Unix, ligne par ligne. Si l’on veut exécuter quoi que ce soit avant de commencer à manger les lignes on peut utiliser le bloc BEGIN{}. Ici on veut que notre état de départ soit d’imprimé, on met donc la variable p à 1. On verra ensuite pourquoi.

2. Le schéma /pattern/ {action}

En son coeur awk fonctionne toujours sous forme de /pattern/ {action}. pattern sera une regex qui tentera d’être matchée sur chaque ligne ou un expression ayant un valeur de vérité. action est la séquence d’instructions awk qui doivent être exec si on trouve un match pour pattern ou si l’expression est vraie. Ici ce mécanisme se prête très bien à notre problème. On a trois types de lignes, don't, do et les autres. On veut faire quelque chose de différent sur chacune de ces lignes. Si on est sur une ligne do /do()/ matche et on met p à 1, comme pour dire qu’à partir de maintenant on veut imprimer. Quand on rencontre une ligne don't on fait l’inverse. Le reste du temps on imprime.

3. p ?

On se doute maintenant que la ligne p permet d’imprimer. Oui mais pourquoi ? Bienvenue dans le monde des comportements implicites et paramètres par défaut, j’ai nommé les outils Unix. Il n’y a pas d’entourloupe sur ce qu’est p. C’est bien simplement une variable qui contient 1 ou 0. Pas une fonction interne à awk qui serait un raccourci pour print ou que sais-je encore. La réalité qui se cache derrière cette ligne est la suivante¹ :

p==1 {print $0}

En awk il est possible d’omettre l’action auquel cas elle sera par défaut celle d’imprimer la ligne courante. Ici c’est ce que l’on veut, on peut donc retirer l’action :

p==1

Il nous reste l’expression qui test si p est égale à 1. On peut la raccourcir :

p

Et voilà comment on passe de p==1 {print $0} à p. Ce sont généralement ce genre de choix de design de langage qui expliquent que de nombreuses personnes trouvent le shell, awk et perl difficile à lire. Il est utile de gardez en tête que lorsque quelque chose paraît magique dans l’un de ces langages il y a de très bonnes chance que cela s’explique par un comportement par défaut. L’usage systématique, et possiblement abusif, de ce genre de mécanismes peuvent freiner la lisibilité et maintenabilité du code. Cependant c’est aussi ce qui explique que leurs adeptes les apprécient et se sentent capable d’exprimer rapidement et facilement leurs pensées avec. Maintenant vous devriez avoir toutes les cartes en main pour comprendre la ligne du départ :

awk 'BEGIN{p=1};/do()/{p=1};/don\047t()/{p=0};p'

Pas si terrifiant que ça non ? 🙂