Le site arthur.bebou.netlib.re - retour accueil
git clone git://bebou.netlib.re/arthur.bebou
Log | Files | Refs |
commit c681421472a9464ce375811736faf14b214b65a3 parent 5bdae0b620ff42bf899016d0dda2de71542a7360 Auteurice: Arthur Pons <arthur.pons@unistra.fr> Date: Wed, 4 Dec 2024 23:21:09 +0100 Début de l'aoc 2024 Je vais jamais aller jusqu'au bout je le sais Diffstat:
| A | contents/aoc-2024/2.sh | | | 72 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | contents/aoc-2024/3.sh | | | 162 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | contents/aoc-2024/index.sh | | | 205 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 439 insertions(+), 0 deletions(-)
diff --git a/contents/aoc-2024/2.sh b/contents/aoc-2024/2.sh @@ -0,0 +1,72 @@ +#! page +title: Advent of code 2024^\(mais c\'est l\'advent of *unix* code\) - jour 2 +author: Arthur Pons +description: L\'advent of code 2024 version Unix +publication: 2024-12-04 + +sectionmd: main + +## Jour 2 + +[Introduction et jour 1](/aoc2024)\ +[Jour 1](1.html) - [Jour 3](3.html) + +### Intitulé résumé + +#### Première partie + + 7 6 4 2 1 + 1 2 7 8 9 + 9 7 6 2 1 + 1 3 2 4 5 + 8 6 4 4 1 + 1 3 6 7 9 + +This example data contains six reports each containing five levels. + +The engineers are trying to figure out which reports are safe. The Red-Nosed reactor safety systems can only tolerate levels that are either gradually increasing or gradually decreasing. So, a report only counts as safe if both of the following are true: + + * The levels are either all increasing or all decreasing. + * Any two adjacent levels differ by at least one and at most three. + +#### Deuxième partie + +The Problem Dampener is a reactor-mounted module that lets the reactor safety systems tolerate a single bad level in what would otherwise be a safe report. It's like the bad level never happened! + +Now, the same rules apply as before, except if removing a single level from an unsafe report would make it safe, the report instead counts as safe. + +### Commentaire de ma solution + +#### Première partie + +A mon avis nous sommes ici face à un problème qui rempli bien les critères des +problèmes pour lequel le shell est mal adapté. Quand c'est le cas l'unixien·ne +old school vous dira de dégaîner `awk`. Ca tombe bien, je dois le pratiquer +pour m'améliorer. + +La solution n'a rien de bien particulier. On se retrouve avec un algo qui +ressemble beaucoup à ce que l'on ferait en C ou en python pas très idiomatique. +J'imagine que c'est de l'awk vraiment médiocre. Il se peut que je n'ai pas décelé +le pattern caché magique qui permet d'exprimer le problème d'une façon permettant +d'avoir un bel algo. + + < 2.input awk '{ + split($0,a," ") + if (a[2]-a[1] > 0) { upordown="up" } else { upordown="down" } + for(i=1;i<length(a);i++) { + diff=a[i+1]-a[i] + if ( diff > 3 || diff < -3 || diff==0 ) { + print $0" not safe to large of a diff or 0" + next + } + if ( upordown=="up" && a[i+1]-a[i]<0 || upordown=="down" && a[i+1]-a[i]>0 ) { + print $0" not safe wrong way" + next + } + } + print $0" safe" + }' | grep 'safe$' | wc -l + +#### Deuxième partie + +Je n'y suis pas encore arrivé et suis passé à la journée d'après 😀 diff --git a/contents/aoc-2024/3.sh b/contents/aoc-2024/3.sh @@ -0,0 +1,162 @@ +#! page +title: Advent of code 2024^\(mais c\'est l\'advent of *unix* code\) - jour 3 +author: Arthur Pons +description: L\'advent of code 2024 version Unix +publication: 2024-12-04 + +sectionmd: main + +## Jour 3 + +[Introduction et jour 1](/aoc2024)\ +[Jour 2](2.html) - [Jour 4](4.html) + +### 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](/aoc2024), 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[^1] : + + 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 ? 🙂 + +[^1]: une version encore plus longue et moins idiomatique que j'avais + initialement écrite était `{if(p==1}{print $0}}`. Ce format est celui-ci où + l'on omet `pattern` ce qui permet d'exec `action` quoi qu'il arrive. C'est + à l'intérieur de l'action qu'on test la valeur de `p` avec un `if`. diff --git a/contents/aoc-2024/index.sh b/contents/aoc-2024/index.sh @@ -0,0 +1,205 @@ +#! page +title: Advent of code 2024^\(mais c\'est l\'advent of *unix* code\) +author: Arthur Pons +description: L\'advent of code 2024 version Unix +publication: 2024-12-04 + +sectionmd: main + +## Qu'est-ce que c'est ? + +L'[advent of code](https://adeventofcode.com/2024/about) est un évènement +annuel créé par [Eric Wastl](https://was.tl/projects/)[^1] durant lequel +il faut résoudre des exercices algorithmiques. Je documente ici mes +*tentatives* en utilisant les outils traditionnels d'Unix (les commandes +posix, awk, sed, peut-être un peu de GNU coreutils etc). + +Je ne pense pas faire les 25 jours. Premièrement ça demande d'être motivé sur +une longue période ce que j'ai du mal à faire, deuxièmement cette boite à outil +est mal adapté à de nombreux types de problèmes généralement posés. + +Mon but est, pour chaque jour que je vais faire, de mettre en lumière une +fonctionnalité méconnue, problème embêtant, astuce maline etc. + +Malheureusement le jeu nécessite un compte Github, Google, Twitter ou Reddit +pour jouer. Je sacrifie donc mon compte Github pour vous fournir l'intitulé du +problème de chaque journée. L'entrée du problème (et ma solution) sera dans le +[dépôt git aoc2024](http://git.bebou.netlib.re/aoc2024/log.html). Il ce peut +que ce qui se trouve commenté dans les articles ne soit plus synchro avec ce +qui se trouve dans le dépôt. + +## Jour 1 + +[Jour 2](2.html) + +### Intitulé résumé + +#### Première partie + + 3 4 + 4 3 + 2 5 + 1 3 + 3 9 + 3 3 + +Maybe the lists are only off by a small amount! To find out, pair up the +numbers and measure how far apart they are. Pair up the smallest number in the +left list with the smallest number in the right list, then the second-smallest +left number with the second-smallest right number, and so on. + +Within each pair, figure out how far apart the two numbers are; you'll need to +add up all of those distances. For example, if you pair up a 3 from the left +list with a 7 from the right list, the distance apart is 4; if you pair up a 9 +with a 3, the distance apart is 6. + +To find the total distance between the left list and the right list, add up the +distances between all of the pairs you found. In the example above, this is 2 + +1 + 0 + 1 + 2 + 5, a total distance of 11! + +#### Deuxième partie + +This time, you'll need to figure out exactly how often each number from the +left list appears in the right list. Calculate a total similarity score by +adding up each number in the left list after multiplying it by the number of +times that number appears in the right list. + +So, for these example lists, the similarity score at the end of this process is +31 (9 + 4 + 0 + 0 + 9 + 9). + +### Commentaire de ma solution + +#### Première partie + +On veut tout de suite séparer les deux colonnes pour les trier. Il est +étrangement "compliqué" de faire ça sur un fichier dont les colonnes son +séparées par trois espaces sans dégainer `awk`. En effet, `cut` ne prend qu'un +seul caractère comme argument et si on lui donne un espace le fichier sera en +réalité séparé en cinq colonnes et non deux comme on voudrait. On peut faire +avec mais ce n'est pas agréable. Pour utiliser `cut` on peut masser le fichier +en "squeezant" les espaces successifs avec `tr -s ' '` puis un cut. + +Personnellement plutôt que de multiplier les pipes j'ai tendance à dégaîner `awk` +dès que je rencontre un fichier dont les champs sont séparés de manière un peu +arbitraire avec du blanc. `awk` se charge tout seul de faire le taf et on +peut simplement écrire : + + < 1.input awk '{print $1}' | sort + < 1.input awk '{print $2}' | sort + +Sinon pour le coeur de la réponse j'ai eu naturellement recours à la technique +"utiliser sed,paste,tr pour écrire des maths et piper tout ça dans `bc`". C'est +une illustration de se dont parle [Florian Cramer](http://floriancramer.nl/) +dans son super article [$(echo echo) echo +$(echo)](http://reader.lgru.net/texts/echo-echo-echo-echo-command-line-poetics/). + +> Command lines can be constructed that wrangle input data, text, into new +> commands to be executed. Unlike in GUIs, there is recursion in user interfaces: +> commands can process themselves. + +J'utilise également un fifo pour éviter de créer un fichier temporaire qui +risquerait de rester ici et de prendre de la place sur mon disque. Si l'on ne +prend pas le temps de supprimer le fifo il restera également mais au moins il +est vide. + +Au final ça donne : + + mkfifo left 2> /dev/null + < 1.input awk '{print $1}' | sort > left& + < 1.input awk '{print $2}' | sort | + paste -d '-' left - | grep -Ev '^-$' | + bc | + tr -d '-' | paste -s -d'+' | + bc + +Avec cette idée de manipuler du texte pour créer des formules mathématiques +l'équivalent de `abs(x)` devient `tr -d '-'`. + +#### Deuxième partie + +Ce problème est une bonne opportunité pour évoquer le shell et ses performances. +Récemment on m'a demandé s'il était possible d'implémenter des algos de machine +learning (spécifiquement avec des réseaux de neurones) en shell. La réponse est +techniquement oui mais il serait vain de tenter de le faire, le shell n'est pas +fait pour faire de l'algèbre. Cela a ouvert une discussion plus générale sur +la performance du shell. + +On admet ici qu'il n'est pas question des performances du shell "pure" qui +n'appellerait aucun programme externe. Bien qu'il soit possible de programmer +en shell "pure" il n'existe pas vraiment de bonne raison de le faire. +peut s'installer sur un unix". A l'inverse on ne compterait pas comme "du +shell" un script qui se contenterait d'appeler un autre programme bien que ce +soit un usage légitime. Dans presque tous les cas quand on parle du shell on +entend "un programme shell unixien pouvant appeler à minima les outils posix et +au maxima n'importe quel outil qui peut s'installer sur un Unix et dont le +fonctionnement et le temps d'exécution dépend pour une partie non négligeable +des méchanismes du shell lui même (pipes, boucles, redirections etc)." + +Aujourd'hui je répond à cette question de cette manière : + + 1. Le shell "pure" n'est pas un langage très performant + 2. *mais* il permet d'orchestrer efficacement des programmes qui peuvent être + très performants + 3. la performance d'un programme en shell dépend donc, peut-être plus que + pour n'importe quel autre langage, des outils utilisés **et** de la manière + de les agencer. + +La nature des shell unix fait qu'il est très facile de d'utiliser des +mécanismes assez avancés permettant d'accélérer l'exécution (parallélisme avec +le pipe) et tout aussi facile de faire de grosses bêtises (forker +exponentiellement en fonction de la taille de notre problème). L'étendu des +performances possibles en shell pour un problème donné est très grande. + +Illustrons cet exemple avec notre deuxième partie. Une solution qui pourrait +paraître naturelle, notamment pour une personne ayant l'habitude d'un langage +comme le C, serait : + + < 1.input awk '{print $2}' | sort | uniq -c > rightcount + for e in $(< 1.input tr -s ' ' | cut -f1 -d' ');do + echo "$e * $(grep -E "$e$" rightcount | awk '{print $1}')" + done | sed 's/* $/*0/' | bc | paste -s -d'+' | bc + +Dans `rightcount` le nombre d'occurences des chiffres dans la seconde colonnes +du type :`3 1234` si `1234` y apparaît 3 fois. Pour chaque élément de la +première colonne on va récupérer ses occurrences dans `rightcount` qu'on multiplie +à sa propre valeur. A la fin de la boucle on fait la somme et hop dans bc. + +C'est rapide à écrire mais c'est leeent. Pourquoi ? Parce que pour chaque +nombre (et y'en a pas mal) on fork pour exécuter notre `grep` et aller chercher +la bonne ligne dans `rightcount`. De manière générale quand on fork beaucoup +(par exemple pleins de captures de commandes) dans une boucle en shell c'est +mauvais signe pour les perfs. Bien sûr si votre problème est petit ce n'est pas +un souci. A vous de voir si la relative lisibilité du code vaut le coup de perf[^2]. + +Une solution plus "unixienne", beaucoup plus performante mais aussi plus obscure quand on y est pas habitué serait : + + < 1.input awk '{print $2}' | sort | uniq -c > rightcount + < 1.input awk '{print $1}' | sort > leftc + < rightcount grep -f leftc | awk '{print $1"*"$2}' | paste -s -d'+' | bc + +Toujours nos occurences dans `rightcount`, Dans `leftc` la première colonne +triée. Ici l'astuce est de laisser `grep` faire le travail en utilisant son +option `-f` qui permet d'utiliser comme pattern à matcher les lignes successives +d'un fichier. Il se trouve que c'est exactement ce que l'on veut faire ! Plus +qu'à créer les formules et hop dans `bc`. + +C'est performant parce que le très gros du travail est fait dans un seul +processus `grep`. Et `grep`[^3], c'est trèèèès rapide. + +Dans l'ensemble le shell est très bon quand : + + 1. le gros du travail peut être sous traité à un coreutils + 2. il est possible de paralléliser le problème par ligne (le pipe est alors + un gain de perf "gratuit") + 3. le problème n'est pas complexe algorithmiquement parlant, il y a peu ou + pas d'exceptions, peu de finesse dans le traitement à faire, peu + d'embranchements logiques, peu de maths + +Pour plus de contenu sur le shell, son monde et ses perfs voir [un article sur +sed](/substitutions/) ou [cet article assez connu qui compare le shell avec un +cluster +hadoop](https://adamdrake.com/command-line-tools-can-be-235x-faster-than-your-hadoop-cluster.html). + +[^1]: également créateur de vanilla-js.com donc une personne particulièrement drôle. +[^2]: au passage il y a une autre bêtise ici qui est que la formule peut être construite uniquement avec les données qui sortent du `grep` en faisant `awk '{print $1*$2}'\ mais peu importe, ça ne changerait presque rien en terme de perf. De manière générale le fait que beaucoup de choses peuvent être mises dans awk et possiblement pour le meilleur sera, je le prédis, un thème récurrent de l'aoc. +[^3]: en particulier GNU grep