Advent of code 2021 jour 1: Sonar sweep - proposition de solution

Cet article a pour but de donner une solution possible à la résolution du premier jour du calendrier de l'avent du code. Il y a évidemment plusieurs solutions possibles dans tous les langages souhaités. Je donnerai la solution en Rust avec les explications qui vont bien. J'essaierai de mettre des liens vers la documentation des différentes méthodes utilisées, lorsque nécessaire.

Le problème posé

Les clefs du traîneau du Père Noël sont parties à l'eau ! Heureusement qu'il y a un sous-marin orné de guirlandes de Noël (parce qu'un sous-marin est orné de tout cela, forcément !). Le premier puzzle proposé nous propose en entrée une liste de profondeurs relevés par un sonar à bord. L'exemple donné sur le site est le suivant:

199
200
208
210
200
207
240
269
260
263

Dans la partie 1, le but est de déterminer le nombre de mesures qui sont supérieures à la précédente. Pour ce faire, rien de très compliqué.

Partie 1

Lecture du fichier

Dans cette partie, nous allons mettre en place la "structure" du programme qui nous permettra de résoudre ce puzzle. Cette partie ne parlera pas de créer les fichiers minimaux à un binaire écrit en Rust; nous allons droit dans le sujet.

Tout d'abord, en partant du principe que l'entrée du programme a été mis dans un fichier, nous allons commencer par le lire avec un nom donné comme argument en ligne de commandes:

use std::env::args;
use std::fs::File;
use std::io::{BufRead, BufReader};
use std::str::FromStr;

fn main() {
    let input_filename = args().nth(1).expect("USAGE: day1 <input file>");
    let file = File::open(&input_filename).unwrap_or_else(|_| panic!("Can't open file {}", input_filename));
    let file = BufReader::new(file);

    // La suite du programme viendra ici
}

La fonction std::env::args retourne un itérateur sur les arguments passés en ligne de commande. La méthode nth permet de récupérer le n-ième élément de cet itérateur. Comme une ligne de commande se structure communément comme programme argument1 argument2 argumentN, la position de l'argument qui nous intéresse, le premier argument, est en position 1, le programme étant en position 0. Ensuite, avec std::fs::File, on ouvre le fichier. S'il n'est pas présent, on provoque une erreur. Enfin, on ouvre un buffer.

Note: il est tout à fait possible de faire la même chose en lisant le fichier en entier directement dans une variable de type String.

Ensuite, depuis le fichier, on va récupérer les lignes et les mettre dans un Vecteur, à l'aide des itérateurs.

let lines = file
    .lines()
    .map(Result::unwrap)
    .map(|l| i32::from_str(&l))
    .map(Result::unwrap)
    .collect::<Vec<i32>>();

Petites explications. .lines() renvoie un itérateur qui parcourera les lignes de notre fichier. Puisque la lecture et l'interprétation du contenu peut échouer (fichier binaire avec caractères Unicode invalides par exemple) ─ comprendre "renvoyer Result::Err" ─, nous avons un Result<String, std::io::Error>. Comme on est sûr que le fichier ne contiendra que des caractères Unicodes valables (et parce que la gestion d'erreurs n'est pas une priorité), nous allons tout simplement enlever la couche Result<T, E> avec unwrap à chaque ligne de l'itérateur avec .map(Result::unwrap).

La façon d'écrire .map(Result::unwrap) est équivalente à écrire .map(|line| line.unwrap()).

Jusqu'à maintenant, dans notre itérateur, nous avons des String, or, nous souhaitons avoir des entiers afin de travailler plus facilement sur les nombres. Pour ce faire, nous allons passer chaque ligne du fichier en cours de lecture dans i32::from_str. Il est important de noter que i32::from_str prend une référence (un emprunt) de la chaîne de caractères; il ne prend pas la propriété de cette dernière. Par conséquent, une closure comme |line| i32::from_str(&line) est nécessaire.

Comme on peut l'imaginer, caster une chaîne de caractères en nombre entier est faillible; nous avons encore un Result<i32, ParseIntError> qui en ressort. Comme nous savons qu'il n'y a réellement que des entiers dans le fichier, on déballe l'entier de son résultat avec .map(Result::unwrap).

Enfin, nous avons un itérateur qui nous sort que des nombres entiers. Il nous manque à les mettre dans un tableau avec la ligne .collect::<Vec<i32>>.

La variable lines contient désormais un tableau avec des entiers.

Résolution du problème

Maintenant que nous avons les ingrédients nécessaires pour résoudre ce puzzle. Allons réaliser la première partie !

La question posée est la suivante:

Combien de mesures sont plus grandes que la précédente mesure ?

Parce que le code que je mets dans cet article est le même qui est dans un dépôt de code source, j'ai mis un peu de bonne volonté et j'ai séparé les deux parties comme suit:


fn main(){
    // Ouverture du fichier
    // Lecture des lignes du fichier et cast des lignes en
    // nombre entier

    part1(&lines);
    part2(&lines);
}

fn part1(lines: &[i32]) {
    // La résolution de cette partie
}

fn part2(lines: &[i32]) {
    // La résolution de la prochaine partie
}

Commençons à remplir le corps de fonction de la première partie.

La question posée nous demande de comparer la mesure courante avec la mesure précédente. Pour ce faire, nous avons deux moyens:

  • la boucle for
  • utiliser la fonction fold sur un itérateur

Je commence par l'utitilisation de la méthode fold, ensuite je donnerai l'équivalent avec une boucle for.

La méthode .fold de Iterator

Tout d'abord, nous devons obtenir un itérateur sur le tableau (en réalité une slice ─ une tranche ─ de celui-ci). La méthode iter est là pour cela.

lines
    .iter()

Ensuite, puisque l'on veut déterminer le nombre de mesures supérieures à leur précédentes, utiliser la méthode fold (la méthode peut être appelée reduce dans d'autres langages) me semble une excellente option. Il s'agit de plier/réduire le tableau d'entiers à une seule valeur.

Cette méthode prend deux paramètres: une valeur initiale et une closure qui prend deux paramètres. La closure prend en paramètre un "accumulateur" et la valeur suivante à traîter.

Je propose que la valeur intiale soit (None, 0). None parce que nous ne connaissons initialement pas de profondeur précédente et zéro parce que nous avons détecté aucune profondeur supérieure à la précédente. Étant donné que nous avons deux valeurs à passer, un tuple est parfait pour cela.

lines
    .iter()
    .fold((None, 0), |(previous_depth, nb_increased), depth| {
        (Some(depth), nb_increased)
    });

Pour satisfaire le vérificateur de types, je renvoie d'ores et déjà un tuple qui sera utilisé dans l'itération suivante. Dans ce tuple, puisque je connais la profondeur qui servira à l'itération suivante, je mets Some(depth). Le nombre de mesures qui sont supérieures à la précédente reste intouché.

Si on se réfère à la question, nous savons que nous voulons comparer les deux profondeurs uniquement si la précédente est connue. Pour ce faire, la construction if let en Rust sera utile:

if let Some(previous_depth) = previous_depth {
    unimplemented!()
}

Ensuite, nous pouvons comparer les deux valeurs et, si la profondeur actuelle est plus grande que la précédente, retourner un tuple qui servira pour l'itération suivante:

if depth > previous_depth {
    return (Some(depth), nb_increased + 1);
}

Comme avant, nous renvoyons la profondeur actuelle qui sera la nouvelle profondeur précédente au prochain tour d'itérateur. Le nombre de profondeurs détectés, par contre, est augmenté de un.

Autrement, si la profondeur précédente n'est pas connue ou que la profondeur précédente connue est plus grande que la profondeur actuelle, "on ne fait rien".

Au final, ce qui précède nous donne la chaîne d'itérateurs qui suit:

lines
    .iter()
    .fold((None, 0), |(previous_depth, nb_increased), depth|{
        if let Some(previous_depth) = previous_depth {
            if depth > previous_depth {
                return (Some(depth), nb_increased + 1);
            }
        }

        (Some(depth), nb_increased)
    });

fold nous renverra l'accumulateur qui est "le tableau réduit en une valeur". Comme on s'en moque d'une profondeur précédente à ce stade, on peut se débarasser de cela:

let (_, nb_increased_readings) = // la chaîne d'itérateurs

On affiche tout cela et bingo !

println!("Nb of increasing depth: {}", nb_increased_readings);

La boucle for

Comme promis, la même chose mais avec une boucle for. Il faut d'abord déclarer les variables qui seront ensuite modifiées dans la boucle:

let mut previous_depth = None;
let mut nb_increased = 0;

for depth in lines {
    // ...
}

Le corps de boucle est le même que ce qui est dans la méthode fold de notre itérateur, à quelques détails près:

let mut previous_depth = None;
let mut nb_increased = 0;

for depth in lines {
    if let Some(previous_depth) = previous_depth {
        if depth > previous_depth {
            nb_increased += 1;
        }
    }

    previous_depth = Some(depth);
}

Dans le corps de la boucle, les mêmes vérifications sont faites. Si ces vérifications passent, alors on incrémente nb_increased de 1.

Dans tous les cas, la profondeur courante devient la profondeur précédente pour le tour de boucle suivante.

Partie 2

La deuxième partie est un poil plus tordue, mais avec ce qu'on a en place, elle n'est pas si compliquée. Cette partie demande de prendre une profondeur, puis les deux suivantes et d'en faire une somme glissante sur les profondeurs enregistrées.

Je pourrais certainement donner un équivalent avec une boucle for, mais je pense qu'utiliser les itérateurs dans ce cas est tellement plus simple.

Ceci étant dit, je reprends le corps de la fonction part2 qui reste ~~désespérément~~ vide et je vais ajouter les appels aux fonctions nécessaires afin d'obtenir un itérateur.

fn part2(lines: &[i32]) {
    lines
        .iter();
}

On se retrouve un peu "coincé". Comment faire en sorte d'avoir l'entrée suivante du tableau tout en l'ayant à côté de nous ? Deux méthodes sur les itérateurs nous seront utiles pour réaliser cela: zip et skip. La façon utilisée de mettre tout cela ensemble s'inspire de l'expansion de la macro izip! disponible dans la crate itertools.

Tout d'abord, on définit un itérateur basé sur le même tableau d'entiers avec lines.iter().skip(1). Cela aura pour effet de créer un itérateur qui sautera le premier élément du tableau. Ensuite, on met ce nouvel iterateur à côté de l'itérateur intialement créé avec la méthode zip. La fonction zip retourne un tuple contenant les éléments des deux itérateurs mis ensembles. Elle s'arrête quand un des itérateurs est à court d'éléments à itérer.

Résultat de l'application de ce qui précède:

lines
    .iter()
    .zip(lines.iter().skip(1))
    // On refait exactement la même chose pour le deuxième
    // élément à avoir en avance
    .zip(lines.iter().skip(2))

Avec cela, on a maintenant un élément de l'itérateur qui est un tuple de tuple: ((i32, i32), i32). Afin de ranger tout cela, on va utiliser la méthode map:

lines
    .iter()
    .zip(lines.iter().skip(1))
    .zip(lines.iter().skip(2))
    .map(|((x, y), z)| (*x, *y, *z))

Certaines personnes vont demander pourquoi je mets une étoile devant x, y et z. L'itérateur travaille avec des références et non pas des valeurs directement. Cela pose quelques problèmes si on s'amuse à faire des calculs, donc on déréférence tout cela. De plus, copier un entier est tellement "bon marché" que... c'est négligeable.

Le reste de la chaîne d'itérateurs est semblable à la première partie.

lines
    .iter()
    .zip(lines.iter().skip(1))
    .zip(lines.iter().skip(2))
    .map(|((x, y), z)| (*x, *y, *z))
    .fold((None, 0), |(prev_sum, nb_increased), (line, follow1, follow2)| {
        let current_sum = line + follow1 + follow2;

        if let Some(prev_sum) = prev_sum {
            if current_sum > prev_sum {
                return (Some(current_sum), nb_increased + 1);
            }
        }

        (Some(current_sum), nb_increased)
    });

La différence entre cette partie et la précédente est l'addition de la mesure que l'on a sous la main, la suivante et cette d'après. Le reste, c'est-à-dire la vérification de l'existance d'une somme précédente, la comparaison avec la mesure précédente, l'incrémentation d'un compteur.

La conclusion

C'est le premier jour d'un calendrier de l'avent. Certes, il n'y a rien d'exceptionnel, mais ce puzzle permet d'entrer dans le bain et de commencer en douceur.