Le problème

Partie 1

Aujourd’hui, on nous dit désormais que notre sous-marin fait de drôles de bruits, et qu’il faut maintenant analyser un rapport diagnostique qui consiste en une liste de nombres binaires.

On nous explique qu’il faut analyser la consommation d’énergie du sous-marin,qui se calcule en multipliant deux valeurs : la valeur gamma et la valeur epsilon.

À partir de notre liste de nombres binaires, on peut déterminer les valeurs en binaire de gamma et de epsilon de la façon suivante :

• Chaque bit de gamma est déterminé en récupérant la valeur la plus fréquemment trouvée pour cette position pour chaque ligne du rapport diagnostique.
• Chaque bit de epsilon est déterminé en récupérant la valeur la moins fréquemment trouvées pour cette position pour chaque ligne du rapport diagnostique.

D’ores et déjà, on peut constater que epsilon est le complément à un de gamma. Cela signifie gamma + epsilon = 2^n - 1, où n est le nombre de bits.

Il faut donc être en mesure de déterminer la valeur de bit la plus fréquente à chaque position. Pour ça, j’applique l’algorithme suivant :

Pour i allant de 0 à taille_message:
    Détermine la valeur de bit la plus fréquente
    Ajoute cette valeur à la variable gamma
Convertit gamma en entier
Calcule epsilon

Voici donc les deux fonctions que j’ai implémentées (une pour déterminer la valeur de bit la plus fréquente, une autre pour résoudre l’exercice) :

def most_recurrent_digit(lines, index):
    values = [int(line[index]) for line in lines]
    # Puisqu'il n'y a que des '0' et '1', on peut simplement compter le nombre de 1
    # et le comparer à la moitié de la taille du message.
    return '1' if sum(values) >= len(lines)/2 else '0'
    
    
def solve_part_one():
    with open('input-small', 'r') as data:
        lines = data.read().splitlines()
        size_message = len(lines[0])
        gamma = ''
        for char_index in range(size_message):
            gamma += most_recurrent_digit(lines, char_index)
        gamma = int(gamma, 2)
        epsilon = (2**size_message - 1) - gamma
        print(gamma * epsilon)

Partie 2

La seconde partie du problème reprend à peu près le même principe, sauf qu’au lieu de déterminer la valeur du bit la plus fréquente dans l’ensemble des données, on procède d’abord à un filtre pour ne garder que les lignes où cette valeur est effectivement présente. Il y a également une petite subtilité quand à la valeur à garder lorsqu’il y a un nombre égal de 0 et de 1, selon que l’on cherche à déterminer la valeur en oxygène ou en CO2.

Pour cela, l’algorithme est quasiment identique, il faut simplement faire attention à bien filtrer les bonnes lignes, et à rappliquer l’algorithme sur les lignes filtrées. Cela donne les deux fonctions suivantes :

# On note l'ajout du paramètre pour distinguer les valeurs d'oxygène ou de CO2
def most_recurrent_digit(lines, index, is_oxygen):
    values = [int(line[index]) for line in lines]
    if is_oxygen: 
        return '1' if sum(values) >= len(lines)/2 else '0'
    return '0' if sum(values) >= len(lines)/2 else '1'
    
    
def solve_part_two():
    with open('input-large', 'r') as data:
        lines = data.read().splitlines()
        size_message = len(lines[0])
        # On crée les listes de lignes qui serviront au filtrage
        oxygen_lines, co2_lines = lines, lines
        for char_index in range(size_message):
            # Ici, on fait bien attention à chercher le bit le plus fréquent 
            # dans les listes filtrées
            oxygen_digit = most_recurrent_digit(oxygen_lines, char_index, True)
            co2_digit = most_recurrent_digit(co2_lines, char_index, False)
            if len(oxygen_lines) > 1:
                oxygen_lines = [line for line in oxygen_lines
                                     if line[char_index] == oxygen_digit]
            if len(co2_lines) > 1:
                co2_lines = [line for line in co2_lines 
                                  if line[char_index] == co2_digit]
        ox_rating, co2_rating = int(oxygen_lines[0], 2), int(co2_lines[0], 2)
        print(ox_rating * co2_rating)

Pour le coup, on pourrait refactoriser le tout pour n’avoir qu’une seule fonction most_recurrent_digit() qui aurait toujours 3 paramètres, mais dont la valeur par défaut de is_oxygen serait True pour ne pas avoir à s’en préoccuper pour la partie 1.

Les difficultés

Pour les deux problèmes d’aujourd’hui, le problème principal est que le format des données que l’on reçoit n’est pas idéal pour les opérations que l’on doit faire dessus.

En effet, on reçoit une liste de nombres binaires mais on nous demande plutôt de travailler sur chaque colonne. Pour le coup, les compréhensions de listes sont assez pratiques ici pour créer rapidement la structure de données utile pour résoudre ensuite rapidement le problème.

Pour le reste, reconnaître le complément à un permet de simplifier un peu les calculs en partie 1. Et ensuite, la partie 2 nécessite une manipulation assez précise des listes que l’on filtre au fur et à mesure. Pour ne pas m’embêter avec des modifications de listes intempestives (dues au fait que les listes sont mutables), je redéfinis à chaque fois oxygen_lines et co2_lines par compréhension.