Jour 5 - Problèmes de mémoire

Malade ce matin, mais j’avais quand même envie de tester le puzzle du jour. Tout semblait aller bien, jusqu’à ce que je crashe mon ordinateur.

Première partie - le retour des intervalles

La première partie était très proche de ce qu’on avait déjà fait au jour 2: gérer des intervalles et vérifier si certains nombres s’y trouve. Cette fois-ci, on a une entrée en deux parties. L’exemple fourni est:

Le premier bloc correspond à une série d’intervalles, qui peuvent se superposer. La seconde donne une série de nombres. On nous demande de compter les nombres dans cette liste qui se trouve dans au moins un des intervalles. On commence donc par récupérer les données sous forme d’une liste d’entiers (les nombres à tester) et d’une liste de tuples de deux entiers (début et fin de l’intervalle).

Je stocke les intervalles avec un +1 sur la fin, parce que Python utilise la convention “borne supérieure exclue”, alors que la définition ici est “borne supérieure inclue”, et que je voulais me faciliter la vie si j’utilisais le range Python.

def prepare_data(data: str) -> tuple[list[int], list[tuple[int, int]]]:
    raw_ranges, raw_ids = data.split('\n\n')
    ranges = raw_ranges.split('\n')
    ranges = [r.split('-') for r in ranges]
    ranges = [(int(r[0]), int(r[1])+1) for r in ranges]

    ids = [int(d) for d in raw_ids.split('\n')]
    return ids, ranges

Une fois qu’on a les données, on va les filtrer. Pas besoin de faire des choses très compliquées ici: on parcourt les nombres, et s’ils se trouvent dans n’importe lequel des intervalles, on les garde.

def filter_in_range(ids: list[int], ranges: list[tuple[int, int]]) -> list[int]:
    good_ids = []
    for idx in ids:
        if any(idx in range(*r) for r in ranges):
            good_ids.append(idx)
    return good_ids

La ligne “clé” est if any(idx in range(*r) for r in ranges). any(x) renvoie True si au moins un des éléments de x est True (ou plutôt “truth-y”). range(*r) est équivalent à faire range(r[0], r[1]), le * étant ici l’opérateur d’unpacking, qui découpe un tuple en ses éléments.

On peut maintenant utiliser tout ça dans le main pour obtenir la réponse de la première partie, qui est le nombre d’identifiants “valides”, c’est-à-dire appartenant à au moins un des intervalles:

def main():
    ids, ranges = load_input(5, '', prepare_data)
    good_ids = filter_in_range(ids, ranges)
    print(f"Part 1: {len(good_ids)}")

Deuxième partie: facile?

Dans la deuxième partie, on ne s’intéresse plus aux nombres fournis, mais juste aux intervalles. On voudrait savoir la longueur de tous les intervalles combinés. Évidemment, on ne veut pas compter de doublons dans les intervalles superposés, donc 10-15 et 12-18 doivent se rassembler en 10-18 pour former un intervalle de taille 9. Ma première tentative était la suivante. Ne faites pas tourner ce code sur un input réel du puzzle (sauf si vous aimez bien redémarrer votre ordinateur!):

def expand_ranges(ranges: list[tuple[int, int]]) -> set[int]:
    all_ids = set()
    for r in ranges:
        all_ids = all_ids.union(set(range(*r)))
    return all_ids

def main():
    ids, ranges = load_input(5, '', prepare_data)
    # ...
    all_ids = expand_ranges(ranges)
    print(f"Part 2: {len(all_ids)}")

L’idée était la suivante: on parcours les intervalles, et on garde une liste de tous les ids dans un set. Le set s’occupe tout seul de détecter les doublons, donc on fait juste une “union” de tous les ensembles définis par les intervalles. Boum, puzzle fini en 2 minutes, trop fastoche.

Ah. Contrairement au jour 2, les intervalles fournis ici sont grands. Très grands. Si on essaie d’énumérer tous les nombres contenus à l’intérieur, l’ordinateur n’apprécie pas. Je suis tombé dans le panneau.

Deuxième partie: facile, en fait.

La solution n’est pas compliquée une fois qu’on relit correctement l’énoncé et qu’on se rend compte qu’on ne doit jamais lister explicitement les nombres valides. On doit juste les compter. On va donc adopter la procédure suivante:

def total_range(ranges: list[tuple[int, int]]) -> int:
    n = 0
    ranges.sort(key = lambda x: x[0])
    min_r, max_r = ranges[0]
    for new_min, new_max in ranges[1:]:
        if new_min < max_r: # overlap
            max_r = max(max_r, new_max)
        else:
            n += (max_r-min_r)
            min_r, max_r = new_min, new_max
    return n+(max_r-min_r)

Comme je récupère mes intervalles avec n+1 sur la borne supérieure, je peux juste faire max_r-min_r pour la taille de l’intervalle. Sinon j’aurais du faire +1.

Le code tourne et fournit immédiatement la réponse, sans inquiéter la mémoire. Tout va bien. Enfin, moi pas trop, je vais me recoucher…

Addendum

if any(idx in range(*r) for r in ranges):

Complexifie un peu inutilement les choses. Ca me paraissait naturel d’écrire ça comme ça, mais je suis même un peu surpris que ça marche. Typiquement, quand on écrit x in range(...), c’est pour itérer sur un range. Ici, on teste si le nombre en fait partie. C’est une opération tout à fait permise sur les range en Python, mais ça me semble surtout utile si on a un range un peu complexe, avec un pas différent de 1, où le test d’appartenance n’est pas évident. Ici, il nous suffit en réalité de faire:

if any(r[0] <= idx < r[1] for r in ranges):