L'Advent of Code 2020 en Go, jours 1 à 5
- Déserialiser une API variable en Java avec Jackson
- Vous avez tort d’utiliser un mode sombre [~Signet]
Ho, ho, ho ! Connaissez-vous l'Advent of Code ?
Comme son nom l’indique, il s’agit d’un calendrier de l’Avent un petit peu spécial : plutôt que d’ouvrir un chocolat par jour jusqu’à Noël, on résout des énigmes en programmant. Cette année, nous sommes plusieurs sur le serveur Discord de ZdS a avoir décidé d’y participer collectivement, chacun dans son langage de prédilection et selon son niveau en programmation.
En ce qui me concerne, j’y participe bien évidemment en Go, et je me propose de prendre ces exercices comme un prétexte pour illustrer la façon dont on travaille avec. Mon but est donc de résoudre ces exercices non pas le plus rapidement possible, ni même de la façon la plus élégante ou improbable, mais simplement de respecter au mieux la philosophie de Go, à savoir de produire le code final le plus banal et lisible possible sans toutefois faire n’importe quoi du point de vue des performances.
Et pour cela, je me propose d’écrire une série de billets en prenant les exercices 5 par 5. 
- Se construire quelques outils pour la suite
- Jour 1 : Trouver N nombres dont la somme est 2020
- Jour 2 : Valider une politique de mots de passe
- Jour 3 : Parcourir un tableau suivant une pente donnée
- Jour 4 : Valider un JWT... enfin presque
- Jour 5 : Parser des nombres binaires de façon détournée
Se construire quelques outils pour la suite
Bon, clairement, le tout premier jour n’est jamais un challenge : il est plutôt là pour s’assurer que l’on sait lire une consigne et faire manger des entrées à notre programme.
Et ça tombe bien !
En effet, Go est à la fois un langage qui se veut simple1, et qui n’a pas vocation à écrire des scripts. En ce sens, c’est un peu le contraire de Python qui permet de récupérer les entrées des programmes au moyen d’un générateur en intension. Nous allons donc devoir nous munir de fonctions utilitaires, dès le départ, pour mieux nous concentrer sur les problèmes par la suite. Ainsi, dans cette section, je vais surtout me focaliser sur les entrées-sorties.
Conventions
Les exercices de l’Advent of Code suivent tous le même principe :
- Le site vous génère un fichier texte de quelques centaines de lignes,
- Il vous pose deux questions, dont la réponse est systématiquement un nombre entier,
- Vous lui soumettez vos réponses en entrant simplement le nombre entier que vous aurez calculé pour votre fichier d’entrée.
Nous allons donc considérer que, chaque jour, nous allons :
- Télécharger un fichier texte,
- Le faire manger à notre programme…,
- … qui va afficher les deux réponses attendues.
Créons donc un package pour ça, et nommons-le en faisant preuve du moins d’imagination possible : utils. Celui-ci proposera deux fonctions :
utils.ReadLines()va ouvrir, lire, et retourner le contenu du fichier sous la forme d’un[]string: un élément par ligne.utils.ReadInt()va faire la même chose dans le cas où le fichier contient un nombre entier par ligne, et retourner le[]intcorrespondant.
Clairement, cette section va surtout aborder des considérations "système" assez courantes, qui n’ont pas grand chose à voir avec la résolution des problèmes algorithmiques de l’AoC.
Si vous débutez complètement en programmation et n’êtes pas plus curieux que ça sur les conventions du langage Go, vous pouvez sauter cette section, et vous rendre immédiatement à l’énoncé du premier jour.
Ouvrir le fichier passé en ligne de commande
Nos programmes seront lancés en suivant ce modèle :
$ nom_du_programme input.txt
La fonction mustOpen() suivante se charge de lire le nom du fichier qui doit être passé en premier argument de la ligne de commande, et retourner ce fichier ouvert en lecture, ou bien quitte le programme avec un message d’erreur si quelque chose n’est pas normal (l’utilisateur n’a pas passé de fichier, ou bien il y a eu une erreur).
Vous observerez peut-être que la fonction du package os sur laquelle nous reposons s’appelle Open et retourne à la fois un fichier et une possible erreur. C’est ce que font la plupart des fonctions en Go.
Lorsque nous souhaitons écrire une fonction qui ne retourne jamais d’erreur, au risque de quitter le programmer ou de "paniquer" en cas d’erreur, la façon idiomatique de s’y prendre est de préfixer le nom de la fonction par le terme must (ou Must).
La bibliothèque standard de Go regorge de fonctions de ce genre, qui viennent en deux versions : une version normale, et une version Must.
package utils
import (
"fmt"
"os"
)
func mustOpen() *os.File {
if len(os.Args) != 2 {
Fatal("Usage:", os.Args[0], "<input file>")
}
f, err := os.Open(os.Args[1])
if err != nil {
Fatal("Couldn't open file:", err)
}
return f
}
// Fatal exits the program after displaying the arguments on stderr
func Fatal(args ...interface{}) {
fmt.Fprintln(os.Stderr, args...)
os.Exit(1)
}
Si Go vous est étranger, vous tiquerez peut-être sur le formattage des noms : la fonction mustOpen a un nom en lowerCamelCase alors que la fonction Fatal est en CamelCase.
Il faut savoir que le fait d’utiliser l’une ou l’autre de ces conventions veut dire quelquechose en Go. En effet, la fonction mustOpen est privée, et ne pourra être appelée que depuis l’intérieur du package utils, alors que la fonction Fatal et publique, et pourra être appelée par les programmes qui importent notre package. C’est d’ailleurs la raison pour laquelle j’ai documenté cette dernière, mais pas mustOpen.
Lire un flux d’entrée de façon "bufferisée"
Maintenant que nous avons parsé correctement la ligne de commande et ouvert le fichier. Il est temps de le lire et d’implémenter nos fonctions ReadLines et ReadInts.
Dans les deux cas, nous avons besoin de lire le contenu du fichier ligne par ligne. Nous allons pour cela utiliser un objet de la bibliothèque standard qui s’appelle un Scanner, et dont le rôle est de lire un flux en remplissant un buffer. Par défaut, ce buffer sera rempli ligne par ligne. Dans le cas de la seconde fonction, nous utiliserons également la fonction strconv.Atoi2 pour convertir des chaînes de caractères en entier.
Notez l’utilisation de defer, qui permet de nous assurer que le fichier sera fermé dès que nous sortirons du scope de la fonction. C’est un réflexe très courant en Go :
- J’ouvre un
truc, - J’écris immédiatement
defer truc.Close()pour ne pas l’oublier.
package utils
import (
"bufio"
"strconv"
)
// ReadLines opens the input file and reads its lines.
func ReadLines() []string {
f := mustOpen()
defer f.Close()
s := bufio.NewScanner(f)
var input []string
for s.Scan() {
input = append(input, s.Text())
}
if len(input) == 0 {
Fatal("Empty input")
}
return input
}
// ReadInts opens the input file and reads its lines as ints.
func ReadInts() []int {
f := mustOpen()
defer f.Close()
s := bufio.NewScanner(f)
var ints []int
for s.Scan() {
i, err := strconv.Atoi(s.Text())
if err != nil {
Fatal(err)
}
ints = append(ints, i)
}
if len(ints) == 0 {
Fatal("Empty input")
}
return ints
}
Ces deux fonctions vont nous faire gagner pas mal de temps pendant les 25 prochains jours.
- Vous le savez sûrement déjà, mais je le précise une nouvelle fois, juste au cas où : "simple" ne veut pas dire "facile". Typiquement : Go est simple, ce qui le rend plus difficile à utiliser dans certaines situations alors que Python est facile à utiliser, ce qui le rend assez complexe quand on regarde sous le capot.↩
- Ce nom pourra sembler bizarre aux plus jeunes d’entre nous : sachez qu’il est inspiré de la bibliothèque standard du C, et qu’il signifie Array To Integer.↩
Jour 1 : Trouver N nombres dont la somme est 2020
Comme je le disais plus haut, l’énigme du jour 1 est triviale. Cela revient à trouver les deux (ou trois) nombres dans une liste, dont la somme est égale à 2020, et retourner le produit de ces nombres.
Partant de là, ce problème se résout avec deux ou trois boucles for imbriquées, comme ceci :
func partOne(input []int) {
for _, x := range input {
for _, y := range input {
if x+y == 2020 {
fmt.Println("Part 1: ", x*y)
return
}
}
}
}
On pourrait pinailler sur ce code en précisant qu’en toute rigueur, on devrait s’assurer que l’on n’essaye pas d’additionner un nombre à lui-même, même si l’ensemble d’entrée de l’exercice semble prendre bien soin d’éviter ce cas (en tout cas, le nombre 1010 était absent de mon input)…
Allez, faisons-le, juste histoire de préciser que la boucle for de Go, avec cette syntaxe (for ... range), va se comporter sur les slices de la même façon que la fonction enumerate en Python, c’est-à-dire qu’elle va itérer directement sur des paires (indice, valeur). Cela ne nous coûte rien de vérifier que les nombres x et y ont bien des indices différents dans la liste d’entrée :
func partOne(input []int) {
for i, x := range input {
for j, y := range input {
if i != j && x+y == 2020 {
fmt.Println("Part 1: ", x*y)
return
}
}
}
}
Voilà, c’est à peu près tout ce qu’il y a à dire sur cet exercice en Go. Vous pouvez trouver ma solution complète ici.
Jour 2 : Valider une politique de mots de passe
L’énigme du deuxième jour était bien plus rigolotte que celle de la veille.
On nous confie une liste d’entrées ayant la forme suivante:
7-13 f: ftmwxpcsfxzqv
Ces entrées correspondent à des "mots de passe" en clair, chacun stocké avec une contrainte.
Partie 1, parser correctement les entrées
Pour la partie 1, on nous explique que la contrainte de l’exemple plus haut doit être lue comme ceci :
Le mot de passe doit contenir entre 7 et 13 fois la lettre f.
On nous demande donc de retourner le nombre de mots de passe valides dans notre liste d’entrée. À ce stade de l’exercice, je pense qu’il est important de faire une préciser que l'on ne sait pas encore ce que l’on nous demandera dans la partie 2. Ce sera probablement quelque chose lié aux mots de passe, mais là où je voudrais en venir, c’est qu’il est préférable de ne pas essayer de deviner la façon dont notre code devra être factorisé pour le moment.
On va se contenter d’écrire une fonction isValid qui prend une ligne en argument et retourne true si le mot de passe est valide. Cette fonction peut donc se découper en deux parties :
- Extraire les différents paramètres de la ligne,
- Effectuer la vérification elle-même.
Pour extraire les champs de la ligne, la façon la plus simple semble ici d’utiliser une expression régulière.
Quelques remarques à propos des expressions régulières de Go
Le moteur d’expressions régulières présent dans la bibliothèque standard de Go est légèrement différent de celui de la plupart des autres langages (Python, Java, Perl, Ruby, etc.). En effet, celui-ci a le bon goût d’utiliser un algorithme sûr et performant… D’accord, d’accord, dit comme ça, ça peut passer pour un tacle gratuit, mais laissez-moi vous expliquer et vous verrez que c’est à la fois rigoureusement vrai ET intéressant.
Pour évaluer des expressions régulières, on peut considérer grosso-modo qu’il existe deux méthodes populaires.
- La première est le célèbre moteur PCRE, qui date de 1997, et qui nous vient des expressions régulières de Perl 5. C’est ce moteur qui est implémenté dans la plupart des langages de programmation ;
- La seconde de ces deux méthodes est nommée l’algorithme de Thompson, car il a été publié en 1968 par Ken Thompson dans un article sobrement intitulé Regular expression search algorithm. On le retrouve implémenté notamment dans la bibliothèque re2.
Ce qui différencie ces deux moteurs de regexp, c’est principalement que PCRE implémente plus d’opérateurs que re2. On pourrait se dire que cela rend automatiquement PCRE "meilleur", mais en fait, c’est le résultat d’une différence fondamentale de philosophie, et cela se traduit par une différence d’autant plus énorme en termes de simplicité et de stabilité des performances. En effet, les opérateurs que PCRE propose "en plus", ce sont des opérateurs complexes comme celui de lookahead. Comme l’explique très bien Russ Cox dans cet article, cet opérateur impose d’utiliser un algorithme de backtracking pour évaluer les PCRE. Le problème, voyez-vous, c’est que l’algorithme d’évaluation par backtracking est très instable, y compris sur des expressions pourtant "simples" mais pathologiques.
L’algorithme original de Ken Thompson, quant à lui, s’optimise en construisant un cache qui permet d’approcher les performances de l’algorithme optimal, c’est-à-dire un AFD comparable à celui de l’algorithme d’Aho-Corasick1 pour la recherche de mots-clés dans un texte. Partant de ce constat, le moteur re2 fait le compromis de lâcher ces opérateurs de lookahead et lookbehind (qui rendent de toute façon les expressions régulières encore plus difficiles à lire), de manière à garder toutes les propriétés intéressantes de l’algo de Thompson.
Quant à Go, eh bien sachant que Ken Thompson et Russ Cox font tous les deux partie de ses créateurs, je vous laisse deviner quel algorithme il implémente. 
Revenons à nos mots de passe
Bref, tout ça pour dire que le moteur d’expressions régulières de Go a un défaut de moins que la plupart des autres : on peut le considérer comme efficace, et dans un cas comme celui qui nous intéresse ici, il simplifie drôlement les choses.
Le format de nos entrées peut être décrit par la regexp suivante (les parenthèses sont "capturantes") :
^(\d+)-(\d+) ([a-z]): ([a-z]+)$
Nous n’avons plus qu’à l’utiliser pour parser nos lignes, et les valider dans la foulée :
import (
"fmt"
"os"
"regexp"
"strconv"
)
var entryFmt = regexp.MustCompile(`^(\d+)-(\d+) ([a-z]): ([a-z]+)$`)
func isValid(entry string) bool {
// Parsing de l'entrée
res := entryFmt.FindStringSubmatch(entry)
if res == nil {
fmt.Fprintln(os.Stderr, "Malformed input: ", entry)
return false
}
i1, _ := strconv.Atoi(res[1])
i2, _ := strconv.Atoi(res[2])
char := res[3][0]
password := res[4]
// Vérification de la validité du mot de passe
var count int
for _, c := range []byte(password) {
if char == c {
count++
}
}
return i1 <= count && count <= i2
}
Remarquez que ce code utilise la fonction strconv.Atoi que nous avons vu plus haut, ainsi que la fonction regexp.MustCompile qui suit la fameuse convention du préfixe Must sur les fonctions qui paniquent en cas d’erreur.
En dehors de cela, on peut remarquer que l’on convertit notre password en une chaîne d’octets ([]byte) pour itérer dessus. En effet, les chaînes de caractère en Go sont par défaut en UTF-8 (encore un truc inventé par Ken Thompson, tiens !), donc lorsque nous itérons dessus, nous itérons sur des caractères Unicode (rune) et non des octets. Ici, nous savons que le texte est forcément constitué de lettres minuscules ASCII, donc nous pouvons convertir notre chaîne Unicode en une chaîne d’octets sans craindre de casser l’encodage du mot de passe.
Partie 2: Ça y est, on peut factoriser
Sans grande surprise, la partie 2 implémente une politique de validation des mots de passe différente de la première. On va donc devoir factoriser notre code.
Pour cet exercice, il me semble que le plus "sémantique" serait que la fonction isValid prenne deux arguments :
- L’entrée,
- Une "politique de validation", qui va se présenter sous la forme d’une fonction.
type PasswordPolicy func(string, byte, int, int) bool
On pourrait donc découper le code de notre partie 1 comme ceci :
func isValid(entry string, f PasswordPolicy) bool {
res := entryFmt.FindStringSubmatch(entry)
if res == nil {
fmt.Fprintln(os.Stderr, "Malformed input: ", entry)
return false
}
i1, _ := strconv.Atoi(res[1])
i2, _ := strconv.Atoi(res[2])
char := res[3][0]
password := res[4]
return f(password, char, i1, i2)
}
func partOne(password string, char byte, min, max int) bool {
var count int
for _, c := range []byte(password) {
if char == c {
count++
}
}
return min <= count && count <= max
}
Valider un mot de passe se fera donc avec l’appel isValid(entry, partOne). Il ne reste plus qu’à implémenter la fonction partTwo, ce qui ne représente aucune difficulté particulière. Vous trouverez la solution ici.
- Je vous parlais d’ailleurs de l’algorithme d’Aho-Corasick dans ce billet. ↩
Jour 3 : Parcourir un tableau suivant une pente donnée
L’énigme du troisième jour changeait un peu des précédentes. On nous donnait un tableau en deux dimensions avec plusieurs centaines de lignes de 31 caractères ressemblant à ceci :
......##....#...#..#.#....#....
.......#...#..#..#....##.......
#.#...#........###.#.##..#.....
.......#.....##.#..##...##.##..
.#...#.#...##..........#..#....
#.......##.....###.#...#......#
.........#....#.#.......#..#...
... etc., sur plus de 300 lignes ...
Partie 1 : Comprendre le parcours pour une pente donnée
L’énoncé est simple : en partant du premier caractère de la première ligne (input[0][0]), nous allons nous déplacer jusqu’à la dernière ligne en suivant un mouvement de 3 cases vers la droite, et une case vers le bas.
Lorsque l’on arrive au bord d’une ligne, disons à la position 29, le reste du mouvement vers la droite doit être reporté sur le début de la ligne suivante. On se retrouvera donc à la position (29 + 3) % 31 = 1.
Le but de l’exercice est de compter le nombre de caractères # (représentant des sapins) que l’on croise en chemin.
func countTrees(input []string) int {
height, width := len(input), len(input[0])
var count, x int
for y := 0; y < height; y += 1 {
if input[y][x] == '#' {
count++
}
x = (x + 3) % width
}
return count
}
Tout l’intérêt de cette partie est d’aboutir à l’utilisation de l’opérateur modulo (%) pour reporter le mouvement sur le début de la ligne suivante.
Partie 2 : Généraliser à n’importe quelle pente
La partie 2 revient à reproduire la même chose avec des pentes différentes, et donc de généraliser la fonction countTrees à d’autres mouvements que "1 vers le bas, 3 vers la droite". Vous pourrez trouver la solution ici.
Allez, ne perdons pas de temps là-dessus et passons à la suite.
Jour 4 : Valider un JWT... enfin presque
L’exercice du jour 4 a connu un accueil mitigé sur notre serveur Discord.
Nombreux sont ceux qui l’ont trouvé ennuyeux et rébarbatif. En ce qui me concerne, je l’ai bien aimé car c’est celui qui, jusqu’à présent, s’est montré le plus proche d’une problématique courante de la vraie vie.
L’entrée est composée d’un certain nombre de "passeports" séparés par une ligne vide. Voici un exemple avec trois passeports différents :
eyr:2029 byr:1931 hcl:z cid:128
ecl:amb hgt:150cm iyr:2015 pid:148714704
byr:2013 hgt:70cm pid:76982670 ecl:#4f9a1c
hcl:9e724b eyr:1981 iyr:2027
pid:261384974 iyr:2015
hgt:172cm eyr:2020
byr:2001 hcl:#59c2d9 ecl:amb cid:163
Ces passeports sont composés d’un certains nombre de champs :
cid:iddu pays (ce champ est optionnel),pid:iddu passeport,eyr: année d’expiration du passeport,iyr: année d’émission du passeport,byr: année de naissance,hcl: couleur des cheveux,ecl: couleur des yeux,hgt: taille, en centimètres (cm) ou en pouces (in),
Vu que nous sommes face à quelque chose qui commence à ressembler à La Vraie Vie™, il y a une foule de choses que je pourrais vous montrer avec cet exercice, mais je vais me permettre de faire l’impasse sur la plupart d’entre elles (notamment l’écriture de tests), pour me concentrer sur les remarques les plus pertinentes.
Modéliser les données et itérer dessus
Le but de la première partie est évidemment de parser ces passeports, et de commencer à valider ceux-ci. Comme je l’ai dit dans le titre, cet exercice ressemble furieusement à la validation des claims dans un JWT. La première chose qui semble judicieuse à faire, donc, est de modéliser nos passeport de la même façon que les packages JWT de Go modélisent leurs claims, c’est-à-dire via une map :
type Passport map[string]string
Une map en Go, c’est plus ou moins la même chose qu’un dictionnaire en Python. Ici, notre map est contrainte à n’accepter que des string comme clés et comme valeurs.
Maintenant que le type est défini, voici comment je désire résoudre cette première partie :
func main() {
var count int
iterPassports(utils.ReadLines(), func(p Passport) {
if isValid(p) {
count++
}
})
fmt.Println("Part 1:", count)
}
Ce code fait intervenir deux fonctions :
- La fonction
iterPassportsva prendre en entrée deux arguments:- Les lignes de l’entrée,
- Une fonction qui accepte un passeport et qui ne retourne rien1.
- La fonction
isValidprend un passeport en argument et retournetruesi le passeport est valide.
Comme vous le constatez, la fonction que l’on passe à iterPassports est définie sur place. C’est une fonction anonyme. De plus, elle incrémente la variable count qui est définie dans le scope de la fonction main : il s’agit donc d’une closure. Ce faisant, iterPassports se comporte d’une façon qui ressemble énormément à une boucle for qui servirait à itérer sur les passeports au fur et à mesure que ceux-ci sont parsés.
Voici comment je l’ai implémentée :
func iterPassports(input []string, cbk func(Passport)) {
p := make(Passport)
for _, line := range input {
// Parse the passport
for _, field := range strings.Fields(line) {
kv := strings.SplitN(field, ":", 2)
if len(kv) == 2 {
p[kv[0]] = kv[1]
}
}
// On empty lines, process the passport and reset it
if line == "" {
cbk(p)
p = make(Passport)
}
}
// Process the remaining passport
cbk(p)
}
Pour parser un passeport, le principe est simple : on isole d’abord les champs de la ligne, qui sont séparés par une espace (c’est ce que fait la fonction strings.Fields), puis on sépare chaque champ en une clé et une valeur, qui se trouvent de part et d’autre d’un :, avant de rajouter ce couple clé/valeur dans le passeport.
Lorsque l’on tombe sur une ligne vide, on appelle notre fonction de callback sur le passeport avant de le réinitialiser (pour passer au suivant).
Enfin, le fichier ne se termine pas par une ligne vide, donc on va appeler une toute dernière fois le callback avant de retourner.
Valider le passeport
Pour qu’un passeport soit valide dans la première partie, il suffit qu’il possède tous les champs obligatoires. Sautons directement à la seconde partie, dans laquelle il faut que ces champs suivent également le bon format :
- Les années sont contraintes par un intervalle particulier,
- La hauteur également, et les bornes acceptables diffèrent selon l’unité.
- Les autres champs ont un format bien précis à suivre.
Pour que tout cela reste visible, nous allons définir, pour chaque champ obligatoire, une fonction de validation que l’on appellera un Validator :
type Validator func(string) bool
var (
validators = map[string]Validator{
"byr": yearValidator(1920, 2002),
"iyr": yearValidator(2010, 2020),
"eyr": yearValidator(2020, 2030),
"hgt": isValidHeight,
"hcl": regexp.MustCompile(`^#[0-9a-f]{6}$`).MatchString,
"ecl": regexp.MustCompile(`^amb|blu|brn|gry|grn|hzl|oth$`).MatchString,
"pid": regexp.MustCompile(`^\d{9}$`).MatchString,
}
heightFmt = regexp.MustCompile(`^(\d+)(cm|in)$`)
)
Valider un passeport consiste donc à vérifier que ces champs obligatoires sont présents, et validés par la fonction correspondante :
func isValid(p Passport) bool {
for key, valid := range validators {
if s, ok := p[key]; !ok || !valid(s) {
return false
}
}
return true
}
Je vous laisse découvrir l’implémentation des validateurs dans la solution que vous trouverez ici. Ceux-ci n’ont rien d’assez nouveau pour que ça vaille le coup de vous les détailler.
- Bon, pour faire les choses vraiment bien elle devrait retourner une erreur, mais ce n’est pas nécessaire ici : s’il y a une erreur, on appelle
Fatalet le programme est quitté.↩
Jour 5 : Parser des nombres binaires de façon détournée
Ouais, ce titre est un spoiler, mais pas plus que le titre de l’exercice lui-même.
Pour résumer l’énoncé, on peut dire que celui-ci consiste à faire une recherche dichotomique d’une cellule dans un tableau de 128 lignes et 8 colonnes (les sièges d’un avion). Autrement dit, on va vous fournir un code comme celui-ci :
BFFFBBFRRR
Vous pouvez considérer que ce code va jouer au plus ou moins en deux étapes avec vous :
- Les 7 premiers caractères servent à trouver le numéro de rangée de notre siège :
Bnous indique que notre rangée sera entre le numéro 64 et le numéro 127Fnous indique que notre rangée sera entre le numéro 64 et le numéro 93Fnous indique que notre rangée sera entre le numéro 64 et le numéro 79Fnous indique que notre rangée sera entre le numéro 64 et le numéro 71Bnous indique que notre rangée sera entre le numéro 68 et le numéro 71Bnous indique que notre rangée sera entre le numéro 70 et le numéro 71Fnous indique que notre rangée est celle de numéro 70
- Les 3 derniers caractères permettent de trouver le siège dans une rangée de 8 :
Rnous indique que notre siège est entre le numéro 4 et le numéro 7Rnous indique que notre siège est entre le numéro 6 et le numéro 7Rnous indique que notre siège est le numéro 7
Cela se traduit par l’identifiant 70 * 8 + 7 = 567
S’aider de tests unitaires !
Nous allons bien évidemment écrire une fonction seatID qui prend une string en entrée et retourne l’identifiant sous forme d’un int. Avant de nous jeter tête baissée dans son implémentation, ayons le nez creux : on est sur le genre de fonction où il est trop facile de faire des erreurs d'off by one, alors dotons-nous d’un petit test unitaire pour raccourcir notre boucle de feedback.
En Go, pour écrire des tests pour le package main, la façon canonique est de créer un fichier main_test.go qui va ressembler à ceci :
package main
import "testing"
var cases = []struct {
Input string
Expected int
}{
{"BFFFBBFRRR", 567},
{"FFFBBBFRRR", 119},
{"BBFFBBFRLL", 820},
}
func TestSeatID(t *testing.T) {
for _, c := range cases {
id := seatID(c.Input)
if id != c.Expected {
t.Errorf("Input: %q, Expected: %d, Got: %d", c.Input, c.Expected, id)
}
}
}
Remarquez que j’ai écrit une fonction dont le nom est préfixé par Test et qui accepte un *testing.T en argument. Cet objet dispose de fonctions Error, Errorf, Fatal et Fatalf pour, respectivement :
- Indiquer que le test a échoué sans pour autant l’interrompre,
- Indiquer que le test a échoué, sans l’interrompre, en affichant un message formatté,
- Indiquer que le test a écoué et l’interrompre immédiatement,
- Indiquer que le test a écoué, et interrompre celui-ci en affichant un message formatté.
Par défaut, si le test arrive au bout sans qu’aucune de ces méthodes ne soit appelée, celui-ci est considéré comme valide.
Munis de ce fichier (dans ./day_05/main_test.go), il suffit de lancer la commande go test ./day_05 -v pour tester notre code.
Implémentation naïve de l’algorithme
Bien, implémentons l’algorithme que nous avons décrit plus haut. Ce n’est pas forcément très difficile, surtout que maintenant on peut détecter très vite, grâce au test, lorsque nous avons fait une erreur.
func seatID(code string) int {
minRow, maxRow, minSeat, maxSeat := 0, 127, 0, 7
for _, c := range code {
switch c {
case 'F':
maxRow -= (maxRow - minRow + 1) / 2
case 'B':
minRow += (maxRow - minRow + 1) / 2
case 'L':
maxSeat -= (maxSeat - minSeat + 1) / 2
case 'R':
minSeat += (maxSeat - minSeat + 1) / 2
}
}
return minRow*8 + minSeat
}
Testons :
$ go test ./day_05 -v
=== RUN TestSeatID
--- PASS: TestSeatID (0.00s)
PASS
ok gitlab.com/neuware/aoc-2020/day_05 0.001s
Parfait ! Le reste de l’exercice est trivial à coder.
Et s’il y avait une méthode plus maligne ?
Voyons voir. Ce code de 10 chiffres va engendrer un nombre compris entre 0 et… 127 * 8 + 7 = 1023.
Tiens, 1023, c’est assez proche de 210. Et si ce code n’était rien d’autre qu’une représentation binaire un peu bizarre où B et R vaudraient 1, et F et L vaudraient 0 ?
Essayons en convertissant nos trois cas de test :
BFFFBBFRRRdonnerait1000110111en binaire, soit 567,FFFBBBFRRRdonnerait0001110111en binaire, soit 119,BBFFBBFRLLdonnerait1100110100en binaire, soit 820.
Bon sang ! Il suffit de parser ce code comme s’il s’agissait d’une représentation binaire !
Implémentons-le.
func seatID2(code string) int {
var res int
for _, c := range code {
res <<= 1
if c == 'B' || c == 'R' {
res |= 1
}
}
return res
}
Bien sûr, on peut soumettre ce code au même test que seatID pour vérifier qu’il fonctionne…
Quelle méthode est la plus performante ?
Vu le nombre d’opérations élémentaires que l’on réalise à chaque boucle sur des entiers, il ne serait pas surprenant que la seconde implémentation soit plus efficace que la premier. Pour nous en convaincre, réalisons un benchmark !
Pour ce faire, ajoutons les deux fonctions suivantes à notre fichier de test :
func BenchmarkSeatID(b *testing.B) {
for n := 0; n < b.N; n++ {
c := cases[n%3]
if seatID(c.Input) != c.Expected {
b.Errorf("wrong result")
}
}
}
func BenchmarkSeatID2(b *testing.B) {
for n := 0; n < b.N; n++ {
c := cases[n%3]
if seatID2(c.Input) != c.Expected {
b.Errorf("wrong result")
}
}
}
Ces fonctions de benchmark vont itérer autant de fois qu’elles le peuvent. À chaque itération, on s’assure que l’on utilise une valeur d’entrée différente, et que le résultat de la fonction est utilisé, en le comparant à la valeur attendue, pour éviter que l’optimiseur de Go ne dégage purement et simplement la boucle.
On peut lancer le bench comme ceci :
$ go test ./day_05 -bench=. -cpu=1
goos: linux
goarch: amd64
pkg: gitlab.com/neuware/aoc-2020/day_05
BenchmarkSeatID 66955075 17.4 ns/op
BenchmarkSeatID2 88646050 13.1 ns/op
PASS
ok gitlab.com/neuware/aoc-2020/day_05 2.363s
Pour comprendre ce qui est affiché, chaque fonction est ici exécutée en boucle pendant une durée fixe (une seconde). Le nombre qui apparait immédiatement après le nom de la fonction, est le nombre de fois que la boucle a eu le temps de tourner. La colonne à droite nous donne le temps d’exécution moyen par itération.
Bon, ici, je ne suis pas certain que le peu de variété dans les données d’entrées n’introduise un biais dans l’évaluation des performances. Cela dit, on observe quand même que la seconde fonction est un peu plus efficace que la première, mais que cette différence est vraiment de l’ordre d’un pouillème (4 nanosecondes par opération) autant dire que c’est kif-kif.
Mais au moins, vous savez maintenant comment on écrit des tests et des benchmarks en utilisant la toolchain standard de Go.
Comme d’hab, vous pourrez trouver ma solution finale ici.
C’est tout pour cette fois. À dans 5 jours !
