Licence CC BY-NC

L'Advent of Code 2020 en Go, jours 1 à 5

Apprenons chaque jour un truc nouveau !

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

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 []int correspondant.

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

Convention de nommage

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. :)


  1. 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.
  2. 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. :D

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.


  1. 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: id du pays (ce champ est optionnel),
  • pid: id du 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 iterPassports va 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 isValid prend un passeport en argument et retourne true si 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. :)


  1. 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 Fatal et 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 :
    • B nous indique que notre rangée sera entre le numéro 64 et le numéro 127
    • F nous indique que notre rangée sera entre le numéro 64 et le numéro 93
    • F nous indique que notre rangée sera entre le numéro 64 et le numéro 79
    • F nous indique que notre rangée sera entre le numéro 64 et le numéro 71
    • B nous indique que notre rangée sera entre le numéro 68 et le numéro 71
    • B nous indique que notre rangée sera entre le numéro 70 et le numéro 71
    • F nous 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 :
    • R nous indique que notre siège est entre le numéro 4 et le numéro 7
    • R nous indique que notre siège est entre le numéro 6 et le numéro 7
    • R nous 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 :

  • BFFFBBFRRR donnerait 1000110111 en binaire, soit 567,
  • FFFBBBFRRR donnerait 0001110111 en binaire, soit 119,
  • BBFFBBFRLL donnerait 1100110100 en 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 ! :D

10 commentaires

Désolé je n’ai même pas encore fini de lire ton article, mais sérieux là je peux pas m’empêcher de pousser un énième coup de gueule contre Go.

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.

Sérieux ? … C’est complètement con. Encore une fois on préfère l’idiome à une factorisation standard, toutes les fonctions doivent être dupliquées pour supporter ça, il faut reproduire la logique à chaque fois, et rien ne garantit qu’une fonction qu’on utilise l’implémente. La façon de faire de Rust est beaucoup plus élégante : les fonctions renvoient toujours un Result<T,E>, et le Result implémente la méthode standard unwrap. Ici c’est le bordel, sans aucun gain de performance, c’est juste dans la philosophie de Go de ne rien factoriser, de ne rien standardiser (ou plutôt de standardiser aléatoirement), et de tout dupliquer. Bon retour dans le C des années 70, la généricité c’est pour les hipsters et les standards pour les réactionnaires. Tant qu’on y est on peut aussi retourner à l’assembleur, les performances seront encore meilleures.

+0 -9

Sérieux ? … C’est complètement con.

Ce message est tellement agressif et rempli de préjugés que je n’ai vraiment pas envie d’y répondre.

Si cette convention existe, dans un langage imaginé par des mecs qui ont créé Unix, puis Go après 50 ans de C, c’est peut-être qu’il y a un raisonnement fort d’une expérience de 50 ans de pratique de la programmation derrière, non ?

En fait sur Discord, quelqu’un a réagi à ce passage en posant la question : "je comprends pas à quoi ça sert d’avoir ces fonctions préfixées en Must : dans quel cas voudrait-on paniquer plutôt que retourner une erreur ?".

Et il y en a au moins un évident que l’on rencontre plus bas dans le billet… Mais le ton odieux et condescendant de ton message me laisse penser que je suis en train de perdre mon temps à essayer de te l’expliquer.

+2 -0

Ça suffit, @Society. Tu peux être en total désaccord avec la philosophie de Go mais ça ne t’octroie pas le droit d’être condescendant.

Et pour information, avant de pousser un coup de gueule, faut lire le reste de l’article (au risque de rater des explications ultérieures…).

+2 -0

Bon retour dans le C des années 70, la généricité c’est pour les hipsters et les standards pour les réactionnaires. Tant qu’on y est on peut aussi retourner à l’assembleur, les performances seront encore meilleures.

Society

Je pense que tu devrais te renseigner sur l’histoire des langages de programmation. Les systèmes de types complexes qu’on retrouve de manière édulcorée dans Rust existaient déjà au début des années 70 (dans SML notamment). Tout comme la création du C qui date du début des années 70, en fait.

Lors de la création d’un langage, il y a d’autres considérations que l’élégance. Notamment les temps de compilation (avantage important de Go) et la complexité du compilateur par rapport à la performance visée. Les langages fonctionnels comme OCaml ne sont pas triviaux du tout à compiler avec un objectif de performance. Je ne pense pas non plus qu’on puisse dire de Rust ou C++ qu’ils sont faciles à compiler.

Sérieux ? … C’est complètement con.

Bah, tu sais, dans l’info, il y a des comportements nettement plus cons que ça. Si tu appelle une fonction en C avec des arguments non initialisés, tu rentres dans un comportement indéfini. Donc d’après la norme, ça peut faire n’importe quoi, c’est valide. Et bah j’ai rencontré un cas où ça faisait une boucle infini.

Si les must sont « complètement con », comment définis-tu mon petit cas à moi ? :D Je vois (trop) souvent des cas en C où il serait largement préférable qu’une fonction appelée n’importe comment fasse tout planter plutôt que de faire ce qu’elle fait.

+0 -0

OK, j’ai bondi de ma chaise et réagi un peu trop à chaud. J’ai été expressif, mais ni agressif ni condescendant, que ce soit clair @nohar je n’attaque pas l’excellente suite d’articles que tu écris sur Go, ils exposent des cas concrets et de bonnes pratiques dans la façon de les aborder, c’est une documentation précieuse et de qualité, et très agréable à lire. Je n’attaque pas non plus l’intérêt de la vulgarisation que tu fais du langage, qui a malgré tout des qualités évidentes et surtout aucun concurrent sérieux.

Je suis très critique envers ce langage, et plus encore envers la hype excessive dont il bénéficie. Il faudrait que je prenne le temps d’approfondir le sujet et d’écrire un billet complet pour exposer mes idées de façon structurée, je reconnais que pousser un coup de gueule ici ne présente pas d’intérêt. Mais selon moi, même si je n’ai pas atteint une confiance suffisante dans un jugement tranché, je me dois d’exprimer ce genre de critiques car le net est rempli de centaines d’articles de blog de développeurs sans recul qui vantent tous les mérites de ce langage comme s’il avait tout révolutionné, ce qui n’est à mon avis pas le cas, et qui se contentent d’effleurer médiocrement les cas d’usages les plus basiques sans étayer plus sérieusement leur éloge par de pertinentes comparaisons, la mise en lumière ou s’il y en a l’explication des défauts du langage, ou des retours d’expérience sur la maintenabilité de bases de code de taille et complexité pertinentes.

J’ai l’impression qu’on est dans le même genre d’effets de mode que Node.js il y a quelques années, pour ne donner qu’un exemple récent. On a poussé le developer-friendly et l’élégance jusqu’à son extrême, notamment avec Python, aujourd’hui volte-face toute, on redécouvre un souci extrême de performance et la notion d’analyse statique comme si ça n’avait jamais existé, tout en régressant de manière effrayante sur de nombreux autres aspects. Une bonne technologie, et notamment un bon langage, c’est un bon compromis entre plusieurs facteurs, adapté à un problème précis, et qui tire parti des expériences passées. Force est de constater que Go est vanté par une armée de prosélytes qui manquent cruellement de recul, et de maîtrise des concepts qu’ils manipulent, et c’est assez inquiétant car Go est en réalité, de ce que j’en connais jusque là, très critiquable, et commence cependant à s’imposer dans les entreprises sans jamais être remis en question.

Si cette convention existe, dans un langage imaginé par des mecs qui ont créé Unix, puis Go après 50 ans de C, c’est peut-être qu’il y a un raisonnement fort d’une expérience de 50 ans de pratique de la programmation derrière, non ?

nohar

Certes ça pèse dans le jugement, mais ça ne reste qu’un hasardeux argument d’autorité. Déjà, ce n’est pas parce que tu es à la pointe et produis d’excellentes choses en début de carrière que c’est toujours le cas en fin de carrière, les exemples ne manquent pas en recrutement de vieux développeurs qui se sont laissés dépasser et ne sont plus à la page malgré leur expérience. Ensuite, les mecs dont tu parles ne sont qu’une partie des équipes qui travaillent sur Go, et n’ont pas forcément complètement la main sur les choix de conception, l’orientation ou les priorités que Google souhaite donner au langage. D’ailleurs, Google n’est pas non plus spécialement connu pour sortir et pérenniser des produits de qualité constante.

En fait sur Discord, quelqu’un a réagi à ce passage en posant la question : "je comprends pas à quoi ça sert d’avoir ces fonctions préfixées en Must : dans quel cas voudrait-on paniquer plutôt que retourner une erreur ?".

Et il y en a au moins un évident que l’on rencontre plus bas dans le billet… Mais le ton odieux et condescendant de ton message me laisse penser que je suis en train de perdre mon temps à essayer de te l’expliquer.

nohar

Ma question n’est pas à quoi ça sert de paniquer, j’ai bien compris que cela permet d’intégrer les tests (encore que d’ailleurs cela aussi pourrait être critiqué), ma question c’est pourquoi Go a choisi cette horrible convention de dupliquer toutes les fonctions selon le traitement qu’on désire faire de leurs erreurs. Sérieusement, je suis le seul que ça choque ? Ca m’apparaît comme une extraordinaire régression en termes d’architecture et de maintenabilité, sans aucun intérêt du point de vue des performances.

Ton billet ne donne pas d’information sur ce point, contrairement à ce que vous dites. Ce n’est pas un reproche envers le billet, cette explication n’aurait rien à y faire, je veux juste indiquer que non je n’ai pas poussé une gueulante sur un point expliqué par la suite.

Je pense que tu devrais te renseigner sur l’histoire des langages de programmation. Les systèmes de types complexes qu’on retrouve de manière édulcorée dans Rust existaient déjà au début des années 70 (dans SML notamment). Tout comme la création du C qui date du début des années 70, en fait.

Lors de la création d’un langage, il y a d’autres considérations que l’élégance. Notamment les temps de compilation (avantage important de Go) et la complexité du compilateur par rapport à la performance visée. Les langages fonctionnels comme OCaml ne sont pas triviaux du tout à compiler avec un objectif de performance. Je ne pense pas non plus qu’on puisse dire de Rust ou C++ qu’ils sont faciles à compiler.

Aabu

J’ai évoqué l’approche de Rust qui repose en effet sur la généricité par paramétrage de type, mais on pourrait très bien adresser le point précis dont je parle sans aller jusque là, et même sans modifier le langage. Il suffit par exemple de remonter l’erreur et de faire un simple panic(err.Error()). Cela dit, tu évoques la vitesse de compilation, mais ça ne semble pas être la raison derrière ce choix précis puisque Russ Cox a reconnu que la généricité est le principal manque du langage et qu’elle y sera bientôt intégrée. Dommage que ça arrive dix ans après la sortie du langage, pour au final être implémenté de façon très classique, et alors que tout l’écosystème s’est constitué sans et commence à devenir stable. Introduire la généricité est un changement de paradigme plus important qu’il peut n’en avoir l’air pourtant, sauf s’il n’est ajouté qu’en tant que gadget. Dans le même style, on pourrait évoquer les modules, qui ne sont apparus qu’en 1.12…

Qu’est-ce que tu désignes exactement par "systèmes de types complexes qu’on retrouve de manière édulcorée dans Rust" ?

Par ailleurs, pas de souci avec Rust, je suis aussi critique avec lui qu’avec Go, pour d’autres raisons. Je travaille depuis cinq ans sur mon propre langage, je sais pertinemment qu’un langage n’est qu’un compromis entre de nombreux facteurs, extrêmement difficile à réaliser, que tout n’est pas possible, et que certains choix sont liés entre eux malgré leur apparente orthogonalité. Mais tout comme pour les autres types de logiciels, les mauvais choix restent possibles, et selon moi Go en fait plusieurs, et une bonne partie de sa communauté encore bien plus.

Go reste très intéressant sur de nombreux aspects, et représente un choix très pertinent à l’heure actuelle pour certains types d’applications. Tout ce que je voulais dire c’est qu’il ne faut pas l’idéaliser, il est aussi bourré de défauts et certains d’entre eux sont vraiment horripilants, et effrayants.

+0 -0

ma question c’est pourquoi Go a choisi cette horrible convention de dupliquer toutes les fonctions selon le traitement qu’on désire faire de leurs erreurs.

Ok, en fait je pense que tu as mal compris le propos, probablement à cause de la façon dont je l’ai exprimé.

Go ne "duplique pas toutes les fonctions". Il y a une façon et une seule, idiomatique, de gérer les erreurs et c’est de retourner une paire (value, error), cette seconde devant implémenter l’interface error. Par contre, il arrive que certaines fonctions doivent paniquer. Tout comme on en trouve en Rust (mais je vais revenir là-dessus juste après).

On pourrait se dire que c’est quand même dingue de ne pas utiliser un type Result<...> comme en Rust, mais là c’est une question de philosophie : un langage qui demande de manipuler des types algébriques à coups de pattern matching dès la première fonction non-triviale que l’on écrit avec n’aurait aucun droit de se revendiquer d’être simple. D’autant que le bénéfice d’un type algébrique, à l’usage, est quasi-nul dans ce cas : une simple vérification statique que la variable d’erreur est bel et bien utilisée (ce que fait le compilo Go par défaut) suffit à s’assurer qu’on ne laisse pas traîner d’erreur (sauf à l’ignorer explicitement), sans introduire le moindre type complexe.

Maintenant arrivons-en aux fonctions qui paniquent. Tu sembles t’offusquer du fait qu’il y ait une convention pour les nommer en Go (les préfixer par Must), mais c’est pas si différent de ce que l’on trouve en Rust. J’en veux pour preuve que le seul moyen de savoir si une fonction panique en Rust, c’est d’aller lire sa documentation et d’espérer que celle-ci respecte la convention qui veut que l’on ajoute un paragraphe intitulé Panics: dans sa documentation pour expliquer les cas dans lesquels ça peut arriver, s’il y en a.

Ici, ça apparaît dès le nom de la fonction. Je ne vois donc pas en quoi la convention de Go serait plus débile que celle de Rust pour gérer ce cas de figure : au contraire, on a un moyen direct d’identifier une fonction qui panique, sans avoir besoin d’aller se taper sa documentation !

Enfin, tu sembles dire que rajouter une version Must va dupliquer toutes les fonctions. Ce n’est juste pas vrai. À l’usage, on n’ajoute une version Must qui panique à une fonction que si l’on voit un intérêt (et des cas légitimes d’utilisation) à ce raccourcis. Et il y en a pas mal, mais ça représente une portion très petite de la lib standard ! Typiquement, la fonction MustCompile du module regexp permet de compiler une expression régulière et l’assigner à une variable globale en une seule ligne : si la regexp échoue à compiler, on veut que ça fasse crasher bruyamment le programme (en l’occurrence, ça fera crasher la CI avant toute chose), et pré-compiler des expressions régulières à l’initialisation du programme est un cas d’usage d’une banalité sans nom…

Du coup je ne vois vraiment pas du tout ce qu’il y a de con à dire "attention, cette fonction préfère quitter abruptement le programme plutôt que retourner une erreur", simplement en lui donnant un préfixe de 4 lettres.

+0 -0

ma question c’est pourquoi Go a choisi cette horrible convention de dupliquer toutes les fonctions selon le traitement qu’on désire faire de leurs erreurs.

Ok, en fait je pense que tu as mal compris le propos, probablement à cause de la façon dont je l’ai exprimé.

Je vois, suite à ton explication, OK effectivement ta formulation m’a laissé penser à tort que cette duplication était massive et idiomatique, au temps pour moi.

Go ne "duplique pas toutes les fonctions". Il y a une façon et une seule, idiomatique, de gérer les erreurs et c’est de retourner une paire (value, error), cette seconde devant implémenter l’interface error. Par contre, il arrive que certaines fonctions doivent paniquer. Tout comme on en trouve en Rust (mais je vais revenir là-dessus juste après).

Que certaines fonctions doivent paniquer, c’est à mon avis un parti pris. Distinguer les erreurs contextuelles des erreurs internes, et éventuellement détecter les secondes le plus tôt possible, c’est une très bonne idée, mais le faire via un panic n’est qu’une façon de faire parmi d’autres. On pourrait même aller jusqu’à dire qu’il peut être pertinent dans certains cas de faire ce choix au niveau de l’application et non du langage.

On pourrait se dire que c’est quand même dingue de ne pas utiliser un type Result<...> comme en Rust, mais là c’est une question de philosophie : un langage qui demande de manipuler des types algébriques à coups de pattern matching dès la première fonction non-triviale que l’on écrit avec n’aurait aucun droit de se revendiquer d’être simple.

Dit comme ça c’est sûr, mais en pratique ça reste très simple aussi. Et même conceptuellement ce n’est pas spécialement plus compliqué qu’un tuple. :P

D’autant que le bénéfice d’un type algébrique, à l’usage, est quasi-nul dans ce cas : une simple vérification statique que la variable d’erreur est bel et bien utilisée (ce que fait le compilo Go par défaut) suffit à s’assurer qu’on ne laisse pas traîner d’erreur (sauf à l’ignorer explicitement), sans introduire le moindre type complexe.

Mais là on parle d’autre chose, Rust pourrait très bien utiliser Result sans forcer à matcher toutes les variantes. Ce sont deux sujets décorrélés. Je ne critiquais pas ici l’idiome du tuple versus l’union, les deux sont très proches (en soi, et également en comparaison à l’autre grand paradigme de traitement d’erreur qu’est la propagation d’exception).

Maintenant arrivons-en aux fonctions qui paniquent. Tu sembles t’offusquer du fait qu’il y ait une convention pour les nommer en Go (les préfixer par Must), mais c’est pas si différent de ce que l’on trouve en Rust. J’en veux pour preuve que le seul moyen de savoir si une fonction panique en Rust, c’est d’aller lire sa documentation et d’espérer que celle-ci respecte la convention qui veut que l’on ajoute un paragraphe intitulé Panics: dans sa documentation pour expliquer les cas dans lesquels ça peut arriver, s’il y en a.

Ici, ça apparaît dès le nom de la fonction. Je ne vois donc pas en quoi la convention de Go serait plus débile que celle de Rust pour gérer ce cas de figure : au contraire, on a un moyen direct d’identifier une fonction qui panique, sans avoir besoin d’aller se taper sa documentation !

Mais de ce que tu dis par la suite, le préfixe Must n’indique pas que la fonction peut paniquer, elle indique simplement que la fonction est un raccourci qui panique directement pour un cas d’usage donné. Donc ça ne remplace pas dans le cas général le fait d’aller voir la documentation d’une fonction pour voir dans quels cas elle peut paniquer. J’ai mal compris ?

Enfin, tu sembles dire que rajouter une version Must va dupliquer toutes les fonctions. Ce n’est juste pas vrai. À l’usage, on n’ajoute une version Must qui panique à une fonction que si l’on voit un intérêt (et des cas légitimes d’utilisation) à ce raccourcis. Et il y en a pas mal, mais ça représente une portion très petite de la lib standard ! Typiquement, la fonction MustCompile du module regexp permet de compiler une expression régulière et l’assigner à une variable globale en une seule ligne : si la regexp échoue à compiler, on veut que ça fasse crasher bruyamment le programme (en l’occurrence, ça fera crasher la CI avant toute chose), et pré-compiler des expressions régulières à l’initialisation du programme est un cas d’usage d’une banalité sans nom…

Du coup je ne vois vraiment pas du tout ce qu’il y a de con à dire "attention, cette fonction préfère quitter abruptement le programme plutôt que retourner une erreur", simplement en lui donnant un préfixe de 4 lettres.

nohar

J’ai l’impression que ça va un peu à l’encontre de la philosophie de simplicité en fait. Si ça reste marginalisé à des cas typiques pourquoi pas, mais c’est justement le genre de raccourcis peu cohérents qui me repoussent en Go. Pour reprendre ton exemple, pré-compiler les expressions régulières en début d’exécution ne me semble pas courant au point de mériter ce raccourci, et peut être également fait avec de l’analyse statique par exemple.

+0 -0

Que certaines fonctions doivent paniquer, c’est à mon avis un parti pris. Distinguer les erreurs contextuelles des erreurs internes, et éventuellement détecter les secondes le plus tôt possible, c’est une très bonne idée, mais le faire via un panic n’est qu’une façon de faire parmi d’autres. On pourrait même aller jusqu’à dire qu’il peut être pertinent dans certains cas de faire ce choix au niveau de l’application et non du langage.

Ah mais on est d’accord, c’est un choix, et d’ailleurs le fait de proposer une version qui remonte un tuple permet de laisser la décision au niveau de l’application, entre les mains des développeurs.

Mais de ce que tu dis par la suite, le préfixe Must n’indique pas que la fonction peut paniquer, elle indique simplement que la fonction est un raccourci qui panique directement pour un cas d’usage donné. Donc ça ne remplace pas dans le cas général le fait d’aller voir la documentation d’une fonction pour voir dans quels cas elle peut paniquer. J’ai mal compris ?

Non non, on est bien d’accord. On a juste une convention qui fait que quand on voit une fonction préfixée par Must, on sait qu’elle peut paniquer (et ça nous indique aussi dans quel cas on peut vouloir l’utiliser, par extension), mais ce n’est pas une relation d’équivalence. Typiquement, ce n’est pas parce qu’une fonction peut paniquer qu’elle sera forcément préfixée par Must, et donc ça ne dispense pas d’aller lire la doc. C’est juste une convention pratique.

En Rust, le pattern que j’ai vu le plus souvent appliqué, c’était, plutôt que de préfixer les fonctions qui paniquent par must, suffixer les fonction qui ne paniquent pas par _safe. Je trouve ça un poil moins pratique (ça donne moins d’informations vraiment utiles en fait).

Dans les deux cas, de toute façon, il faut lire la doc des fonctions qu’on utilise. Mon argument se bornait simplement à dire que Rust aussi repose sur des idiomes et des conventions comparables à ceux de Go, comme celle de préciser un paragraphe "panics" dans la doc.

Pour reprendre ton exemple, pré-compiler les expressions régulières en début d’exécution ne me semble pas courant au point de mériter ce raccourci, et peut être également fait avec de l’analyse statique par exemple.

Pour le coup, je ne suis pas d’accord. Analyser statiquement les expressions régulières, cela demanderait de les considérer comme une partie de la syntaxe du langage, et donc d’avoir un module dédié dans le compilateur, ce qui :

  • le complexifierait en rajoutant un gros morceau à sa grammaire,
  • interdirait d’utiliser d’autres moteurs d’expressions régulières, qui ne supportent pas forcément la même syntaxe, ou alors ce serait de la "concurrence déloyale" : "tu peux utiliser le moteur de regexp que tu veux, mais seul l’officiel est supporté par les analyses du compilateur".

Ou alors il faudrait imaginer quelque chose comme le langage Zig, qui permet d’exécuter du code arbitraire à la compilation et de garder le résultat dans le segment .data de l’exécutable, ce qui permettrait d’avoir à la fois une vérification à la compilation (donc "statique", d’une certaine façon), et de charger très vite le programme. Dans les cas des expressions régulières en particulier, ça me semble overkill. Ça pourrait avoir du sens si l’expression que l’on cherche à compiler se traduisait en un AFD (parce que c’est beaucoup plus long à générer que les AFN classiques des regexps), mais ça représenterait un surcoût prohibitif en termes de taille de l’exécutable (c’est la raison première pour laquelle on ne compile pas de regexps en AFD dans le cas général, et c’est d’ailleurs un domaine de recherche encore actif de nos jours).

Si on met toutes les données de cette problématique particulière bout à bout, pour moi, le plus simple, c’est encore que la compilation de la regexp se fasse dès l’initialisation du package, par un bête appel à la bibliothèque qui va bien, comme ça se fait assez classiquement dans beaucoup de programmes qui ont besoin de valider des regexps fixes. Ça n’implique rien d’autre que les mécanismes de base de n’importe quel langage de programmation, pour au final apporter une garantie suffisante (il suffit de lancer les tests ou de charger le package pour être sur que la regexp constante compile correctement à l’initialisation).

+0 -0

Erratum à la fin du billet :

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.

C’est un détail alors j’ai la flemme d’éditer le billet, mais concrètement, ici, le bench est faussé par le fait que l’ensemble des données passées en entrée tient dans le cache L1 de mon CPU, mais qu’il lui faut le temps d’être mis en cache au début du premier test.

Si je relance un bench mais cette fois sur la totalité du fichier d’input du problème, j’obtiens :

$ INPUT_FILE=$(pwd)/day_05/input.txt go test -bench=. -cpu=1 ./day_05  
goos: linux
goarch: amd64
pkg: gitlab.com/neuware/aoc-2020/day_05
BenchmarkSeatID         21280707                54.4 ns/op
BenchmarkSeatID2        21298512                54.3 ns/op
PASS
ok      gitlab.com/neuware/aoc-2020/day_05      2.431s

Autant dire qu’il n’y a aucune différence significative, donc à choisir, j’aurais tendance à préférer la première solution qui a le mérite de traduire l’énoncé le plus fidèlement possible.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte