arthur.bebou

git clone git://bebou.netlib.re/arthur.bebou
Log | Files | Refs |

index.sh (9962B)

 #! 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