Advent of Code 2021 Day 8

Le problème

Partie 1

Aujourd’hui, le problème repose sur les afficheurs sept segments. Chaque segment est représenté par une lettre allant de a à g.

  0:      1:      2:      3:      4:
 aaaa    ....    aaaa    aaaa    ....
b    c  .    c  .    c  .    c  b    c
b    c  .    c  .    c  .    c  b    c
 ....    ....    dddd    dddd    dddd
e    f  .    f  e    .  .    f  .    f
e    f  .    f  e    .  .    f  .    f
 gggg    ....    gggg    gggg    ....

  5:      6:      7:      8:      9:
 aaaa    aaaa    aaaa    aaaa    aaaa
b    .  b    .  .    c  b    c  b    c
b    .  b    .  .    c  b    c  b    c
 dddd    dddd    ....    dddd    dddd
.    f  e    f  .    f  e    f  .    f
.    f  e    f  .    f  e    f  .    f
 gggg    gggg    ....    gggg    gggg

Dans notre jeu de données, chaque ligne contient deux parties séparées par une barre verticale | :

Une première partie avec les 10 chiffres représentés par les lettres, mais où celles-ci ne correspondent plus à celles illustrées plus haut.
Une seconde partie avec uniquement 4 chiffres, qui représentent le résultat de la ligne.

Voici un exemple pour une ligne :

bgafcde gfcd agc ebdgac adfceb bafeg efgca cgdfae cg ecadf | fabgced gc agc cdfg

Dans la première partie, notre travail est de déterminer le nombre de 1, 4, 7, et 8 présents dans les secondes parties du jeu de données. L’énoncé nous aide beaucoup pour cette partie, puisqu’il nous dit que :

Le chiffre 1 est le seul qui n’utilise que 2 segments ;
Le chiffre 7 est le seul qui n’utilise que 3 segments ;
Le chiffre 4 est le seul qui n’utilise que 4 segments ;
Le chiffre 8 est le seul à utiliser les 7 segments.

Il suffit donc de parcourir toutes les lignes, en ne récupérant que les parties à droite de la barre verticale, et de compter le nombre d’éléments de taille 2, 3, 4, ou 7.

def parse_input_data():
    with open('input-large', 'r') as data:
        lines = [line.split(' | ')[1] for line in data.read().splitlines()]
        return lines


def solve_part_one():
    """
    We first need to get a single list of all digit representations before we
    can calculate the number of 1s, 4s, 7s, and 8s.
    """
    lines = parse_input_data()
    digits = []
    for line in lines:
        digits += line.split(' ')
    count = sum([1 for digit in digits if len(digit) in (2, 3, 4, 7)])
    print(count)

Partie 2

L’énoncé de la partie 2 laissait présager qu’il fallait déterminer comment chaque nombre serait représenté sur l’afficheur sept segments.

Pour cette partie, j’avoue ne pas avoir cherché à faire du code propre. On peut en fait identifier tous les chiffres en faisant preuve d’un peu de logique et en utilisant les ensembles pour profiter de leurs fonctions permettant de calculer des intersections :

On est déjà en mesure de détermine les chiffres 1, 4, 7, et 8.
J’ai ensuite procéder en regroupant les autres chiffres par nombre de segments nécessaires pour les afficher :
- 2, 3, et 5 nécessitent tous 5 segments :
  - 3 est le seul à afficher les segments du 1, on peut retirer 3 de la liste des nombres nécessitant 5 segments ;
  - 5 est le seul à partager trois segments avec 4. En déterminant 5, on a également déterminer 2 par élimination.
- 0, 6, et 9 nécessitent tous 6 segments :
  - 9 est le seul chiffre à inclure tous les segments du 3, on peut le retirer de la liste des nombres nécessitant 6 segments ;
  - 0 est le seul chiffre à inclure tous les segments du 1. En déterminant 0, on a également déterminer 6 par élimination, et cela met un terme à notre algorithme.

Une fois que tous les nombres sont déterminés, j’ai simplement mis leurs représentations dans une liste [zero, one, two, ..., nine]. Puis, je prends la partie droite du jeu de données pour identifier le nombre à quatre chiffre en sortie en comparant les représentations avec les éléments dans la liste (en pensant à bien tout transformer en ensembles).

def parse_input_data():
    with open('input-large', 'r') as data:
        return [line.split(' | ') for line in data.read().splitlines()]


def map_digits(digits):
    """
    Not the best looking function, but it simply works out which number is
    which by proceeding by elimination.
    :param digits: A string that contains all 10 digits
    :return: An ordered list of all representations
    """
    digits = digits.split(' ')
    one = {c for segments in digits for c in segments if len(segments) == 2}
    seven = {c for segments in digits for c in segments if len(segments) == 3}
    four = {c for segments in digits for c in segments if len(segments) == 4}
    # Five-segment digits
    five_segments = [{c for c in segments}
                     for segments in digits if len(segments) == 5]
    three = {c for segments in five_segments for c in segments
             if len({c for c in segments}.intersection(one)) == 2}
    five_segments.remove(three)
    five = {c for segments in five_segments for c in segments
            if len({c for c in segments}.intersection(four)) == 3}
    five_segments.remove(five)
    two = five_segments.pop()
    # Six-segment digits
    six_segments = [{c for c in segments}
                    for segments in digits if len(segments) == 6]
    nine = {c for segments in six_segments for c in segments
            if len({c for c in segments}.intersection(three)) == 5}
    six_segments.remove(nine)
    zero = {c for segments in six_segments for c in segments
            if len({c for c in segments}.intersection(one)) == 2}
    six_segments.remove(zero)
    six = six_segments.pop()
    eight = {c for segments in digits for c in segments if len(segments) == 7}
    return [zero, one, two, three, four, five, six, seven, eight, nine]


def compute_output(line):
    """
    The first part of this method is to identify which digit is which.
    Then, we transform the digits of the output into its actual number
    representation and return it.
    :param line: A line composed of both the left and right hand side of the
                 pipe
    :return: The output
    """
    digits, output = line
    digit_map = map_digits(digits)
    output = output.split(' ')
    result = ''
    for number in output:
        number = {c for c in number}
        for digit, representation in enumerate(digit_map):
            if representation == number:
                result += str(digit)
    return int(result)


def solve_part_two():
    lines = parse_input_data(True)
    result = 0
    for line in lines:
        result += compute_output(line)
    print(result)

Les difficultés

Les problèmes d’aujourd’hui ont introduit les ensembles, qui nous sont bien utiles pour déterminer quels segments se retrouvent dans l’un ou l’autre des chiffres. Ensuite, on a vu qu’en procédant avec précaution, il était finalement assez simple d’identifier tous les chiffres.

J’imagine qu’il existe une méthode un peu plus élégante pour identifier les chiffres, mais j’avoue avoir été un peu pris par le temps pour chercher une telle solution.

2021-12-08

https://patrickwang.fr/posts/advent-of-code-2021-day-8/