Jour 2 - Intervalles

Nous avons face à nous une série d’intervalles, encodés de la façon suivante:

Dans chaque intervalle se cache des nombres “invalides”, selon une certaine règle. Pour la première partie, un nombre est invalide s’il est formé d’une séquence répétée deux fois: par exemple, 11, 22, 99, 1010 sont des nombres invalides. L’objectif est de trouver les nombres invalides dans les intervalles donnés, et de les sommer.

La première chose qui m’est venue à l’esprit est une règle simple: seuls les nombres ayant un nombre pair de chiffres peuvent être invalides. La longueur (en terme de “nombre de caractères”) du nombre sera déterminante pour pouvoir trouver les “bons” (mauvais) nombres. Je vais donc en récupérant les intervalles les garder en string pour l’instant. Comme hier, j’ai une première fonction qui vient récupérer les données brutes sous forme d’une chaîne de caractère, que je peux maintenant parser pour obtenir le résultat désiré, ici une liste de tuples (str, str) avec le début et la fin de chaque intervalle:

def prepare_data(data: str) -> list[tuple[str, str]]:
    intervals = data.split(',')
    intervals = [i.split('-') for i in intervals]
    return [(i[0], i[1]) for i in intervals]

Première partie: solution moche

On va ensuite, à l’intérieur de chaque intervalle, chercher les potentiels invalides. On va appliquer la règle suivante:

Dans les deux cas, on peut avec ce système avoir un “premier candidat” qui est inférieur au début de l’intervalle, mais ça nous permet de déjà bien contraindre le problème. Après, on va itérer les candidats possibles en incrémentant la “première moitié” à répéter, jusqu’à ce qu’on soit sorti de l’intervalle (et en ne gardant évidemment que ceux qui sont plus grands que le début).

def invalid_numbers(intervals: list[tuple[str, str]]) -> list[int]:
    invalid: list[int] = []
    for start, end in intervals:        # pour tous les intervalles
        nb_digits_start = len(start)
        nb_digits_end = len(end)
        if nb_digits_start%2 == 1:  # début de l'intervalle a un nb de chiffres impair
            if nb_digits_end == nb_digits_start: # et la fin a le même nb de chiffres
                continue
            half_digits = str(10**((nb_digits_start+1)//2 - 1)) # première possibilité avec nb de chiffre supérieur
        else:
            half_digits = start[:math.ceil(nb_digits_start/2)] # sinon on prend simplement la moitié
        min_candidate = half_digits*2   # * pour les strings = répétition: '123'*2 = '123123'
        start_ = int(start)
        end_ = int(end)
        while (min_ := int(min_candidate)) <= end_: # tant qu'on est pas sorti de l'intervalle
            if min_ >= start_:  # et si on y est bien rentré
                invalid.append(min_) # alors on a trouvé un invalide
            half_digits = str(int(half_digits)+1)   # incrémentation de la "moitié à répéter"
            min_candidate = half_digits*2   # et répétition
    return invalid

Dans le main, on peut maintenant récupérer la liste des nombres invalides et faire la somme:

def main():
    data = load_input(2, '', prepare_data)
    invalid = invalid_numbers(data)
    print(f"Part 1: {sum(invalid)}")

Ce qui me donne le bon résultat, même si c’est un peu dégueulasse. Je m’attend à devoir fortement modifier l’approche pour la seconde partie.

Seconde partie: un peu plus propre

C’est très souvent le cas dans Advent of Code: la seconde partie oblige à trouver une solution un peu plus élégante avec une toute petite modification de l’énoncé. Ici, on change la règle d’invalidité: tout nombre formé d’un nombre répété est maintenant proscris. Donc 111, 121212, 33333 sont maintenant aussi invalides.

Cela change assez fort la donne. On peut maintenant avoir un nombre de chiffres impair et être invalide. Et si on a par exemple 8 chiffres, on peut avoir différents types de répétition: 8*1 chiffre, 4*2, 2*4. La façon dont j’aborde le problème jusqu’à présent ne va pas faciliter la résolution sans rendre la fonction très complexe. Je vais donc plutôt changer d’approche. Plutôt que de partir des intervalles, on va partir des nombres invalides.

Reformulons donc la question: quels sont tous les nombres invalides, en allant jusqu’à un nombre de caractère correspondant au maximum présent dans nos intervalles ?

Partons du nombre de chiffres “à répéter”. Si j’ai n chiffres au maximum, j’aurai entre 1 et n//2 chiffres à répéter. Et pour m chiffres à répéter, je vais pouvoir les répéter entre 2 et n//m fois (avec // la division entière, soit a//b = floor(a/b)).

Je vais coder ça en Python, en mettant tout dans un set pour éviter de compter deux fois les mêmes candidats (1111 par exemple, comme '1'*4 et '11'*2). Pour chaque nombre de chiffres répétés, on passera donc sur toutes les valeurs possibles, qui vont de 10**(m-1) à 10**m exclus (ex. 3 chiffres, de 100 à 999).

def get_all_candidates(max_digits: int) -> set[int]:
    all_candidates = set()
    repeated_digits = 1
    while repeated_digits <= max_digits//2:
        max_repeat = max_digits//repeated_digits
        if max_repeat < 2:
            continue

        digits = range(10**(repeated_digits-1), 10**repeated_digits)
        for d in digits:
            for n in range(2, max_repeat+1):
                all_candidates.add(int(str(d)*n))

        repeated_digits += 1

    return all_candidates

Maintenant qu’on a tous les candidats, il suffit de vérifier lesquels se retrouvent dans au moins un des intervalles:

def invalid_numbers_2(intervals: list[tuple[str, str]]) -> list[int]:
    invalid: list[int] = []

    # récupération du nombre de chiffres maximum présent dans un intervalle
    max_digits_all = max(len(e) for _, e in intervals)

    # récupération de tous les candidats
    all_candidates = get_all_candidates(max_digits_all)

    for c in all_candidates:
        # si le candidat est dans au moins un intervalle
        if any(int(s) <= c <= int(e) for s, e in intervals):
            invalid.append(c)

    return invalid

invalid = invalid_numbers_2(data)
print(f"Part 2: {sum(invalid)}")

4 étoiles sur 4 pour l’instant, pourvu que ça dure ! Je préfère largement ma solution deuxième partie que la première, qui pourrait sans doute être refactorisée pour aussi d’abord chercher à lister les candidats possibles. Mais j’aime bien laisser la solution “brouillonne” pour avoir le contraste entre les deux.

Addendum

Une grande tradition du Advent of Code est d’aller voir, après avoir résolu le problème, les solutions des autres. Ce qui peut avoir deux effets: soit on se dit “ah, chouette, ils ont eu les mêmes difficultés que moi”, soit on se dit “ah oui en fait on pouvait faire ça, c’est plus simple.”

J’étais clairement dans le second camp en voyant la solution de Juha-Matti Santala, qui utilise une “bête” Regex pour reconnaître les cas invalides. La beauté de la solution, c’est qu’on peut reconnaître la première partie avec:

INVALID_ID_PATTERN = r'^(\d+)\1$'

Qui va récupérer tout ensemble de chiffres (\d+) répété (\1 indique “le même élément que dans la parenthèse précédente”). Et pour la deuxième partie, il peut simplement faire:

INVALID_ID_PATTERN_2 = r'^(\d+)(\1)+$'

Où l’on signale cette fois-ci que la chaîne répétée \1 peut elle-même être répétée plusieurs fois ((\1)+). Joli!