AoC 2021 Jour 3: Binary Diagnostic

Grincements étranges et inquiétants dans le sous-marin.

Le défi peut être trouvé ici, et le code lié est sur gitlab.

Consigne du défi

Dans ce défi, on nous apprend que le sous-marin fait des bruits pour le moins étranges. Le fichier d’entrée se compose d’une longue liste de nombres binaires, que nous devons analyser.

Lecture du fichier d’entrée

La lecture du fichier d’entrée se fait de la manière suivante, assez simplement :

fn parse_input(s: &str) -> Vec<Vec<u32>> {
    let mut r: Vec<Vec<u32>> = vec![];
    for e in s.split("\n") {
        if !e.is_empty() {
            r.push(e.chars().filter_map(|e| e.to_digit(2)).collect());
        }
    }
    return r;
}

On va donc transformer chaque ligne (par exemple 101000001100) en un tableau de chiffres, ayant pour valeur 0 ou 1 (dans l’exemple [ 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0 ]). On fait cela pour chaque ligne, pour assembler une matrice de chiffres binaires, faciles à parcourir dans toutes les directions.

Première partie

Pour la première partie, il va falloir créer un nombre binaire à partir des chiffres les plus fréquents dans les colonnes, et un nombre binaire à partir des chiffres les moins fréquents, toujours dans les colonnes. On obtiendra alors deux nombres binaires, qui une fois convertis en base 10 et ensuite multipliés entre eux, donne la réponse à cette première partie.

Une fonction utilitaire permet de convertir les tableaux de nombres binaires en nombre entier non signé :

fn bit_vec_to_u32(v: &Vec<u32>, invert: bool) -> u32 {
    let mut acc = 0;
    for i in 0..v.len() {
        acc += if invert { (v[i] + 1) % 2 } else { v[i] } << (v.len() - 1 - i);
    }
    return acc;
}

On a donc ici un accumulateur qui fait la somme des éléments tout en faisant un décalage binaire, produisant un nombre entier en temps linéaire.

On va donc utiliser une fonction permettant d’obtenir, pour tout le fichier d’entrée, le bit le plus présent dans la colonne c :

fn get_most_in_col(v: &Vec<Vec<u32>>, c: usize) -> u32 {
    let mut a = (0, 0);
    for r in 0..v.len() {
        if v[r][c] == 0 {
            a.0 += 1;
        } else {
            a.1 += 1;
        }
    }
    if a.1 == a.0 { return 1; }
    else { return if a.1 > a.0 { 1 } else { 0 }; }
}

À la fin de la fonction, on peut voir que lors d’une égalité, c’est le 1 qui est considéré comme valeur la plus présente dans la colonne étudiée.

Amélioration possible : il serait potentiellement plus intéressant de faire la somme des entiers stockés dans la colonne, et regarder si cette somme est supérieure au nombre de lignes divisée par deux, car cela nous évite de faire des comparaisons et rend inutiles les conditions if qui sont au milieu de la boucle, ralentissent fortement le calcul et sont donc à proscrire.

On va donc ici calculer en un seul coup la suite de chiffres binaires les plus représentés par colonne dans le fichier d’entrée. La valeur gamma sera donc la conversion directe de ce tableau en nombre entier non signé, et la valeur epsilon sera aussi une conversion, mais inversée.

fn get_gamma_epsilon(v: &Vec<Vec<u32>>) -> (u32, u32) {
    let mut acc: Vec<u32> = vec![];

    for c in 0..v[0].len() {
        acc.push(get_most_in_col(&v, c));
    }
    return (bit_vec_to_u32(&acc, false), bit_vec_to_u32(&acc, true));
}

La multiplication de ces deux valeurs nous donne la réponse à cette première partie.

Deuxième partie

Toujours à partir de ce fichier d’entrée, on doit alors calculer deux nouvelles valeurs : le niveau de génération d’oxygène et le niveau de filtrage de CO2.

Pour obtenir ces deux valeurs, on joue encore sur les bits les plus et les moins communs dans une colonne donnée mais en rajoutant cette fois un concept d’élimination. On va donc faire ceci :

Ici, j’ai utilisé une approche récursive :

fn get_o2(v: &Vec<Vec<u32>>, c: usize) -> u32 {
    if v.len() == 1 { return bit_vec_to_u32(&v[0], false); }

    let a = get_most_in_col(&v, c);
    let f = v.into_iter().filter(|e| e[c] == (a + 1) % 2)
        .fold(vec![], |mut acc, e| { acc.push(e.to_owned()); return acc;});
    return get_o2(&f, c + 1);
}

fn get_co2(v: &Vec<Vec<u32>>, c: usize) -> u32 {
    if v.len() == 1 { return bit_vec_to_u32(&v[0], false); }

    let a = get_most_in_col(&v, c);
    let f = v.into_iter().filter(|e| e[c] == a)
        .fold(vec![], |mut acc, e| { acc.push(e.to_owned()); return acc;});
    return get_co2(&f, c + 1);
}

On va donc récupérer le bit le plus présent dans la colonne c, et conserver les valeurs qui nous intéressent, puis rappeler la méthode sur les valeurs restantes en avançant d’une colonne. Une fois qu’il ne reste qu’une valeur, on sait qu’on a notre résultat, et c’est ce qui est renvoyé.

En relisant ce code, j’ai plusieurs critiques à en faire :

Conclusion

Ce défi fait monter très légèrement la difficulté et le temps de réflexion nécessaire, mais cela reste très accessible. Encore une fois, relire son code et se poser les bonnes questions est très important, surtout se demander si telle ou telle copie ou opération est bien nécessaire. C’est une réflexion que je m’appliquerai à faire plus souvent.

À suivre