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

• Qu’est-ce que c’est ?
• Jour 1
  • Intitulé résumé
    • Première partie
    • Deuxième partie
  • Commentaire de ma solution
    • Première partie
    • Deuxième partie

Qu’est-ce que c’est ?

L’advent of code est un évènement annuel créé par Eric Wastl¹ 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. 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

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 dans son super article $(echo echo) echo $(echo).

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².

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³, 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 ou cet article assez connu qui compare le shell avec un cluster hadoop.