Cet article a pour but de donner une solution possible à la résolution du troisième 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.

Note: je m'en fiche un peu que cet article paraisse en février 2022. Les cours existent.

Le problème posé

Le sous-marin fait des bruits de craquement étranges. Il nous émet un rapport de diagnostic qui nous permettra de savoir ce qui se passe. Par contre, ce diagnostic contient des nombres binaires.

L'exemple de départ donné est le suivant:

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

Je ne vais pas traduire tout l'énoncé non plus; ça prendrait un peu trop de temps et ce n'est pas le but de cet article.

Dans la première partie, on va mettre en place la structure du programme et quelques trucs utiles, en plus de résoudre le puzzle. Ensuite, dans la seconde partie, beh on résout la seconde partie. Rien de sorcier.

Préparation du programme

En partant du principe que les fichiers de base d'un binaire en Rust sont créés, on va d'abord faire la structure du programme.

use std::cmp::Ordering;
use std::env::args;
use std::fs::File;
use std::io::{BufRead, BufReader};

type CountOnesAndZeroesClosure = dyn FnMut((i32, i32), &Vec<String>) -> (i32, i32);

fn main(){

}

fn part1(){

}

fn part2(){

}

J'expliquerai plus bas, lors du parcours de la première partie, à quoi servira la déclaration du type CountOnesAndZeroesClosure.

Lecture du fichier

Avant d'attaquer la première partie, à proprement parler, il serait pas mal de lire l'entrée du programme qui se trouve dans un fichier.

fn main() {
    // Lire le fichier passé en argument
    let input_filename = args().nth(1).expect("USAGE: day3 <input file>");
    let file = File::open(&input_filename).unwrap_or_else(|_| panic!("Can't open file {}", input_filename));
    let file = BufReader::new(file);

    // Transformer chaque ligne en tableau
    // de tableau
    let lines = file
        .lines()
        .map(Result::unwrap)
        .map(|l: String| l
            .split("")
            .filter(|part| !part.is_empty())
            .map(ToString::to_string)
            .collect::<Vec<_>>()
        )
        .collect::<Vec<_>>();

    // Résoudre les parties du puzzle
    part1(&lines);
    part2(&lines);
  }

Comme lors du puzzle précédent présenté, BufReader::lines renvoie un itérateur de résultats parce que la lecture d'un fichier est une opération qui peut poser problème.

Comme on sait qu'on aura que des caractères unicode valables, on ne fait pas de gestion d'erreurs. On va plutôt se concentrer sur la séparation des caractères avec String::split, retirer les chaînes vides puis mettre tout ça dans un tableau de tableau. Au final, on a un Vec<Vec<String>> que l'on pourra utiliser.

Première partie

La première partie demande de former deux nombres à partir de l'entrée donnée puis de multiplier ces nombres pour obtenir la consommation énergétique du sous-marin.

Le premier nombre, le gamma rate, est formé en prenant le bit le plus commun dans la colonne de nombres binaires. L'epsilon rate est formé en prenant le bit le moins commun dans cette même colonne.

Ainsi, dans l'exemple raccourci suivant...

00100
11110
10110
10111

le gamma rate formé par la première colonne est 1, l'epsilon rate de cette même colonne est 0. Pour la seconde colonne, il s'agit de, respectivement 0 et 1, et ainsi de suite.

C'est parti !

fn part1(lines: &[Vec<String>]) {
    let columns_count = lines[0].len();
    let mut gamma_number = 0u32;
    let mut epsilon_number = 0u32;

    for column in 0..columns_count {
        let (one_count, zero_count) = lines
            .iter()
            .fold((0, 0), count_ones_and_zeroes(column));
    }
}

Dans ce bout de code, on commence par définir le nombre de colonnes qu'une ligne contient. Cette opération suppose que toutes les lignes sont de même longueur. Ensuite, on boucle depuis la première colonne (la colonne zéro) jusqu'à la dernière (la colonne columns_count non incluse). Dans la boucle, on compte combien il y a de chaque bit dans la colonne que l'on désire.

Il nous manque une pièce du puzzle: la fonction count_onces_and_zeroes. La closure prise par Iterator::fold a été déplacée dans cette fonction puisqu'elle est utilisée à plusieurs endroits. Remarquez que j'appelle cette fonction, alors qu'il s'agit de quelque chose à ne pas faire quand on passe des références de fonctions. En effet, la fonction appelée retourne une autre fonction qui sera celle utilisée par Iterator::fold !

// Rappel du type dont CountOnesAndZeroesClosure est un alias
type CountOnesAndZeroesClosure = dyn FnMut((i32, i32), &Vec<String>) -> (i32, i32);

fn count_ones_and_zeroes(column: usize) -> Box<CountOnesAndZeroesClosure> {
    Box::new(move |(one_count, zero_count), bits| {
        let bit = bits[column].as_str();
        match bit {
            "0" => (one_count, zero_count + 1),
            "1" => (one_count + 1, zero_count),
            _ => unreachable!("The numbers should only be ones or zeroes, not anything else in {:?}", bits)
        }
    })
}

Ça fait un petit bloc. Décortiquons tout cela.

CountOnesAndZeroesClosure est un type qui définit une closure (dyn FnMut¹) qui prend en paramètre un tuple d'entiers et une référence vers un tableau de String ((i32, i32), &Vec<String>) et retourne un tuple d'entiers (-> (i32, i32)). Surprise, il s'agit de la signature de la fonction de rappel attendue par Iterator::fold !

fn fold<B, F>(self, init: B, f: F) -> B
where
    // La définition de notre closure qui colle à ce que la méthode fold attend ! ↓
    F: FnMut(B, Self::Item) -> B

Le tout est Boxé parce qu'une implémentation de trait n'a pas de taille. À la place, on place l'adresse de la closure sur le tas (le heap) et le pointeur vers cette closure sur la pile (la stack).

Dans le corps de la fonction count_ones_and_zeroes, on définit une closure qui prend les paramètres décrits. Dans cette closure, on prend le bit à la colonne qui nous intéresse, puis on regarde qu'est-ce qui se trouve à cet endroit. Selon ce qui est présent, on retourne un tuple avec l'un des deux compteurs incrémenté.

Une fois que l'on a obtenu nos compteurs de uns et zéros, on va les comparer comme expliqué dans la donnée. Le bit le plus fréquent entre dans la composition du gamma rate, le bit le moins fréquent va dans l'epsilon rate.

if one_count > zero_count {
    gamma_number = (gamma_number << 1) | 1;
    epsilon_number <<= 1;
} else {
    gamma_number <<= 1;
    epsilon_number = (epsilon_number << 1) | 1;
}

Ohhh yeah ! Un peu de bit shifting parce que c'est bien ! On peut tout à fait composer le nombre binaire avec des strings, puis caster tout ça en entier avec i32::from_str_radix. Comme ce n'est pas drôle, on joue avec les bits. Pas de panique, explications.

gamma_number = (gamma_number << 1) | 1;
epsilon_number <<= 1;

L'opération sur la première ligne est la suivante: déplacer les bits d'une place à gauche, puis mettre le dernier bit (si on lit les bits de gauche à droite) à un.

Si j'illustre un peu sur un petit nombre:

Décalage à gauche:
00000001 << 1 = 00000010

OU binaire avec 1:
  00000010
| 00000001
----------
= 00000011

L'opération sur la deuxième ligne se content de décaler les bits à gauche d'un cran, ce qui a pour effet de juste ajouter un zéro.

Avec tout ça, on comprend rapidement qu'on peut former notre nombre sans passer par la composition d'une chaîne de caractères.

À la fin de la boucle, on affiche les résultats:

println!(
    "Gamma number: {}, Epsilon number: {}, Power consumption rate: {}",
    gamma_number,
    epsilon_number,
    gamma_number * epsilon_number
);

Deuxième partie

La deuxième partie demande un peu plus de travail, mais c'est surtout de l'élimination. Il s'agit de compter le nombre de bits dans une colonne, puis éliminer les lignes selon un certain critère jusqu'à ce qu'il ne reste plus qu'une.

L'oxygen generator rating se détermine en gardant les lignes dont la colonne est le bit le plus fréquent. Le CO2 scrubber rating est déterminé de la même façon mais en gardant les lignes avec le bit le moins fréquent. L'exemple est donné sur la page du puzzle, en anglais.

Pour ce faire, on va créer une fonction qui se chargera de faire la partie élimination et recherche de la ligne qui nous intéresse. Ensuite, on utilisera cette fonction pour résoudre notre puzzle. Pourquoi je sens que y'aura du code qui ressemble légèrement à de la programmation fonctionnelle ?²

fn bit_criteria_filtering<F>(lines: &[Vec<String>], comparison_function: F) -> i32
    where F: Fn(i32, i32) -> &'static str
{
    todo!();
}

Cette fonction prend un vecteur de vecteur de String et une variable de type F. Cette variable comparison_function est en réalité une closure qui prend deux entiers et retourne une référence à un str³. Cette closure s'occupera de faire la comparaison et de retourner ce qu'il faut garder. Le tout retourne un entier qui correspond à la ligne qui reste dans notre tableau de lignes.

Je ne vais pas vous faire attendre pour donner le code complet et l'expliquer.

fn bit_criteria_filtering<F>(lines: &[Vec<String>], comparison_function: F) -> i32
    where F: Fn(i32, i32) -> &'static str
{
    // Cloner les éléments du tableau pour ne pas toucher l'argument initial
    // qui est "en lecture seule"
    let mut lines = lines.iter().collect::<Vec<_>>();

    let mut current_column = 0;
    while lines.len() > 1 {
        // Voir partie 1 pour l'explication de cette ligne
        // et d'où sort `count_ones_and_zeroes`
        let (one_count, zero_count) = lines
            .iter()
            .copied()
            .fold((0, 0), count_ones_and_zeroes(current_column));


        let keep = comparison_function(one_count, zero_count);

        // Conserver les lignes dont le n-ième bit correspond
        // à ce qui a été retourné par la fonction de comparaison
        lines = lines
            .iter()
            .filter(|line| line[current_column] == keep)
            // On peut copier des références, un &&str devient un &str
            .copied()
            .collect::<Vec<_>>();

        current_column += 1;
    }

    i32::from_str_radix(&lines[0].join(""), 2).unwrap()
}

Les brèves explications sont insérées dans le code donné.

On a notre fonction qui fera la détermination de la ligne qui reste. Reste à l'utiliser pour résoudre la seconde partie de notre puzzle:

fn part2(lines: &[Vec<String>]) {
    let o2_generator_rating = bit_criteria_filtering(
        lines,
        |one_count, zero_count| {
            match one_count.cmp(&zero_count) {
                Ordering::Less => "0",
                Ordering::Equal => "1",
                Ordering::Greater => "1"
            }
        }
    );

    let co2_scrubber_rating = bit_criteria_filtering(
        lines,
        |one_count, zero_count| {
            match one_count.cmp(&zero_count) {
                Ordering::Less => "1",
                Ordering::Equal => "0",
                Ordering::Greater => "0"
            }
        }
    );

    println!(
        "O2 rating: {}, CO2 rating: {}, Life support rating: {}",
        o2_generator_rating,
        co2_scrubber_rating,
        o2_generator_rating * co2_scrubber_rating
    );
}

Oui, "c'est tout". En passant des fonctions, on peut réutiliser une partie "commune" ─ dans ce cas compter des bits et enlever des lignes ─ tout en gardant cette flexibilité de glisser des spécificités à l'aide d'une closure qui sera appelée au bon endroit.

J'aimerais me pencher sur les closures qui sont passées à bit_criteria_filtering. Je choisirai l'une d'entre elles puisqu'elles font exactement la même chose:

|one_count, zero_count| {
    match one_count.cmp(&zero_count) {
        Ordering::Less => "0",
        Ordering::Equal => "1",
        Ordering::Greater => "1"
    }
}

Comme discuté au préalable, la closure prend deux arguments de type entier. Le code d'origine consistait en conditions qui comparaient les deux entiers avec des if et sortaient le bon nombre. Il s'avère que cargo clippy parvenait à détecter ce genre de façon de faire et a suggéré d'appeler i32::cmp. J'étais un peu surpris.

Selon l'ordre renvoyé par i32::cmp (plus petit que, égal à ou plus grand que), je renvoie zéro ou un. Ce chiffre sous forme de chaîne de caractères sera ensuite utilisé dans la fonction de filtrage pour enlever les nombres dont le n-ième bit ne correspond pas à ce qui doit être conservé.

Le code

Le code complet de la solution présentée se trouve sur mon dépôt GitHub de l'avent du code.