Le site arthur.bebou.netlib.re - retour accueil
git clone git://bebou.netlib.re/arthur.bebou
Log | Files | Refs |
3.sh (6530B)
1 #! page
2 title: Advent of code 2024^\(mais c\'est l\'advent of *unix* code\) - jour 3
3 author: Arthur Pons
4 description: L\'advent of code 2024 version Unix
5 publication: 2024-12-04
6
7 sectionmd: main
8
9 ## Jour 3
10
11 [Introduction et jour 1](/aoc2024)\
12 [Jour 2](2.html) - [Jour 4](4.html)
13
14 ### Intitulé résumé
15
16 #### Première partie
17
18 It seems like the goal of the program is just to multiply some numbers. It does
19 that with instructions like mul(X,Y), where X and Y are each 1-3 digit numbers.
20 For instance, mul(44,46) multiplies 44 by 46 to get a result of 2024.
21 Similarly, mul(123,4) would multiply 123 by 4.
22
23 However, because the program's memory has been corrupted, there are also many
24 invalid characters that should be ignored, even if they look like part of a mul
25 instruction. Sequences like mul(4*, mul(6,9!, ?(12,34), or mul ( 2 , 4 ) do
26 nothing.
27
28 #### Deuxième partie
29
30 There are two new instructions you'll need to handle:
31
32 * The do() instruction enables future mul instructions.
33 * The don't() instruction disables future mul instructions.
34
35 Only the most recent do() or don't() instruction applies. At the beginning of the program, mul instructions are enabled.
36
37 ### Commentaire de ma solution
38
39 #### Première partie
40
41 Là on est *typiquement* sur un problème chouette pour du shell. Déjà c'est de
42 la manipulation linéaire de texte. Ensuite c'est des regex. Miam miam on se
43 régale.
44
45 Pour la première partie on va, comme pour le [premier jour](/aoc2024), se
46 contenter de faire travailler `grep` :
47
48 < 3.input grep -Eo 'mul\([0-9]{1,3},[0-9]{1,3}\)' |
49 grep -Eo '[0-9]+,[0-9]+' |
50 tr ',' '*' | paste -s -d'+' |
51 bc
52
53 L'astuce ici est de connaître l'option `-o` de `grep`. Celle-ci permet de
54 demander à `grep` qu'il n'affiche que les match (un par ligne) et non les
55 lignes dans lesquelles il a y un ou plusieurs match. Cela permet de se retrouve
56 avec une sortie toute propre
57
58 mul(1,2)
59 mul(764,2)
60
61 Qu'on peut ensuite modifier à notre guise pour piper dans bc. La transformation
62 suite au premier `grep` peut être faite de mille façons différentes, celle ici
63 est très "logique" pour notre cerveau mais ce n'est certainement pas la plus
64 efficace.
65
66 #### Deuxième partie
67
68 Cette nouvelle version du problème revient à poser la question plus générale
69 de comment filtrer entre deux patterns sur plusieurs lignes, un problème
70 que je trouve étonnamment récurent. Si l'on veut, comme ici, supprimer entre
71 deux patterns, on peut utiliser sed :
72
73 sed "/don't()/,/do()/ d"
74
75 Sauf que cela exclu le pattern de fin de notre intervalle. On aura encore des
76 lignes avec `do()`. On pourrait suivre le `sed` avec `grep -v "do()"` et le tour
77 serait jouer mais il est possible de le faire directement dans `sed` :
78
79 sed "/don't()/,/do()/ d; /do()/ d"
80
81 Il suffit de revérifier si la ligne contient `do()` après la première
82 instruction et, si c'est le cas, la supprimer. Cette commande n'imprime donc
83 que ce qui se trouve *en dehors* de l'intervalle `dont/do`, les patterns exclus.
84
85 J'avais aussi une solution avec `awk` :
86
87 awk 'BEGIN{p=1};/do()/{p=1};/don\047t()/{p=0};p'
88
89 ou plus joliment :
90
91 awk '
92 BEGIN {p=1}
93 /do()/ {p=1}
94 /don\047t()/ {p=0}
95 p
96 '
97
98 Malheureusement pour utiliser une apostrophe dans script awk appelé depuis le
99 shell le plus fiable est d'inscrire son code octal `\047`. Bienvenue dans le
100 quoting hell. A part ça j'aime bien ce bout d'`awk` parce qu'il permet
101 d'évoquer plusieurs mécanismes fondamentaux.
102
103 1. Le bloc `BEGIN`
104
105 `awk` fonctionne, comme la plupart des outils tradi Unix, ligne par ligne. Si
106 l'on veut exécuter quoi que ce soit avant de commencer à manger les lignes on
107 peut utiliser le bloc `BEGIN{}`. Ici on veut que notre état de départ soit
108 d'imprimé, on met donc la variable `p` à 1. On verra ensuite pourquoi.
109
110 2. Le schéma `/pattern/ {action}`
111
112 En son coeur `awk` fonctionne toujours sous forme de `/pattern/ {action}`.
113 `pattern` sera une regex qui tentera d'être matchée sur chaque ligne ou un
114 expression ayant un valeur de vérité. `action` est la séquence d'instructions
115 awk qui doivent être exec si on trouve un match pour `pattern` ou si
116 l'expression est vraie. Ici ce mécanisme se prête très bien à notre problème.
117 On a trois types de lignes, `don't`, `do` et les autres. On veut faire quelque
118 chose de différent sur chacune de ces lignes. Si on est sur une ligne `do`
119 `/do()/` matche et on met `p` à 1, comme pour dire qu'à partir de maintenant
120 on veut imprimer. Quand on rencontre une ligne `don't` on fait l'inverse. Le
121 reste du temps on imprime.
122
123 3. p ?
124
125 On se doute maintenant que la ligne `p` permet d'imprimer. Oui mais pourquoi ?
126 Bienvenue dans le monde des comportements implicites et paramètres par défaut,
127 j'ai nommé les outils Unix. Il n'y a pas d'entourloupe sur ce qu'est `p`. C'est
128 bien simplement une variable qui contient `1` ou `0`. Pas une fonction interne
129 à `awk` qui serait un raccourci pour `print` ou que sais-je encore. La réalité
130 qui se cache derrière cette ligne est la suivante[^1] :
131
132 p==1 {print $0}
133
134 En `awk` il est possible d'omettre l'action auquel cas elle sera par défaut
135 celle d'imprimer la ligne courante. Ici c'est ce que l'on veut, on peut donc
136 retirer l'action :
137
138 p==1
139
140 Il nous reste l'expression qui test si `p` est égale à 1. On peut la raccourcir :
141
142 p
143
144 Et voilà comment on passe de `p==1 {print $0}` à `p`. Ce sont généralement ce
145 genre de choix de design de langage qui expliquent que de nombreuses personnes
146 trouvent le shell, awk et perl difficile à lire. Il est utile de gardez en tête
147 que lorsque quelque chose paraît magique dans l'un de ces langages il y a de
148 très bonnes chance que cela s'explique par un comportement par défaut. L'usage
149 systématique, et possiblement abusif, de ce genre de mécanismes peuvent freiner
150 la lisibilité et maintenabilité du code. Cependant c'est aussi ce qui explique
151 que leurs adeptes les apprécient et se sentent capable d'exprimer rapidement
152 et facilement leurs pensées avec. Maintenant vous devriez avoir toutes les cartes
153 en main pour comprendre la ligne du départ :
154
155 awk 'BEGIN{p=1};/do()/{p=1};/don\047t()/{p=0};p'
156
157 Pas si terrifiant que ça non ? 🙂
158
159 [^1]: une version encore plus longue et moins idiomatique que j'avais
160 initialement écrite était `{if(p==1}{print $0}}`. Ce format est celui-ci où
161 l'on omet `pattern` ce qui permet d'exec `action` quoi qu'il arrive. C'est
162 à l'intérieur de l'action qu'on test la valeur de `p` avec un `if`.