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…