Skip to main content

Advent of Code 2021 Day 16

Le problème

Parties 1 et 2

Le titre de l’exercice d’aujourd’hui est “Packet Decoder”, et on va vite se rendre compte de la nature du travail qui nous attend.

Premièrement, on reçoit en input un paquet arbitrairement long écrit en hexadécimal. La tâche va être de convertir ce paquet en binaire, et d’en déterminer le contenu. Là où les choses se compliquent, c’est qu’un paquet peut en contenir un ou plusieurs autres, et que ces paquets ont des formats différents.

Il faut donc être capable de reconstruire le paquet initial récursivement, tout en respectant les règles données dans l’énoncé (et il y en a BEAUCOUP). Pour le coup, et puisque les parties 1 et 2 sont assez complémentaires, j’ai fusionné les deux parties et j’ai commenté de façon assez extensive les fonctions implémentées.

from math import prod


def parse_input_data():
    with open('input-large.txt', 'r') as data:
        # This fills with preceding 0s in case of leading zeros when converting
        # from hexadecimal to binary representation
        return ''.join(f"{int(hexa, 16):04b}" for hexa in data)


def parse_literal(binary_data):
    """
    Parses a string of binary numbers to obtain a list of literals. These
    literals are then joined to be converted into decimal values.
    :param binary_data: A string of binary numbers
    :return: A shift value to continue parsing, and the literal value
    """
    index = 0
    literals = []
    while True:
        literals.append(binary_data[index+1:index+5])
        header = binary_data[index]
        index += 5
        if header == '0':
            break
    return 5*len(literals), int(''.join(literals), 2)


def parse_data(binary_data):
    """
    Parses the string of binary numbers.
    If encounters a literal, then calls `parse_literal()` and shifts the current
    index to continue the parsing.
    If encounters a 0-length operation, then processes the following 15 bits to
    compute the number of bits that need to be parsed before this operation
    packet can be closed. Then, recursively calls this function to get either a
    literal or the result of the operation until the shift grows larger than the
    number of bits to consider.
    if encounters a 1-length operation, then processes the following 11 bits to
    computer the number of subpackets contained in this packet. Then,
    recursively calls this function as many times as needed to create the
    necessary subpackets.
    :param binary_data: A string of binary numbers
    :return: Sum of version, result of the operations, and a shift value
    """
    v = int(binary_data[:3], 2)
    t = int(binary_data[3: 6], 2)
    index = 6
    if t == 4:
        shift, packets = parse_literal(binary_data[index:])
        return v, packets, index+shift
    sum_v = v
    packets = []

    if binary_data[index] == '0':
        length_bits = int(binary_data[index+1:index+16], 2)
        index += 16
        stop_index = index + length_bits
        while index < stop_index:
            version, sub_packets, shift = parse_data(binary_data[index:])
            index += shift
            sum_v += version
            packets.append(sub_packets)
    else:
        nb_packets = int(binary_data[index+1:index+12], 2)
        index += 12
        for i in range(nb_packets):
            version, sub_packets, shift = parse_data(binary_data[index:])
            index += shift
            sum_v += version
            packets.append(sub_packets)

    # After all packets are parsed, we can apply the appropriate operator 
    # and produce the corresponding output
    output = 0
    if t == 0:
        output = sum(packets)
    elif t == 1:
        output = prod(packets)
    elif t == 2:
        output = min(packets)
    elif t == 3:
        output = max(packets)
    elif t == 5:
        output = int(packets[0] > packets[1])
    elif t == 6:
        output = int(packets[0] < packets[1])
    elif t == 7:
        output = int(packets[0] == packets[1])
    return sum_v, output, index


def solve_part_one():
    binary_data = parse_input_data()
    sum_v, packets, index = parse_data(binary_data)
    print(sum_v, packets)

Les difficultés

Cet exercice met en avant pleins de difficultés différentes.

Difficultés pratiques tout d’abord, puisque Python va supprimer les bits de poids forts lors de la conversion si ceux-ci sont égaux à 0. Lors du parsing, on pourrait se retrouver avec un décalage qui fausserait complètement notre résultat final.

Difficultés algorithmiques ensuite, avec un appel récursif de fonction devant gérer tout un tas de règles de parsing, dont la réalisation de l’opération correspondante au type de paquet. Cette journée aura l’une de celle qui m’aura donné le plus de fil à retordre jusqu’à présent, en grande partie due à la longueur de l’énoncé que je ne voulais apparemment pas lire attentivement…

comments powered by Disqus