Jour 3 - Maxima récursifs

Raison numéro un pour rater un exercice, dans Advent of Code comme à l’école: mal lire l’énoncé.

Et l’objectif est de trouver pour chaque ligne le plus grand nombre à deux chiffres que l’on peut faire avec, sans modifier l’ordre. Donc par exemple pour la dernière ligne 818181911112111, on aura 92. Je n’avais initialement pas bien saisi le “ne pas changer l’ordre”, et donc j’avais fait un joli code qui me sortait 98. Mais après un café et un trajet en tram pour me réveiller, j’ai pu rapidement faire une solution.

Mais d’abord, comme toujours, transformer l’input en quelque chose d’utilisable:

def prepare_data(data: str) -> list[list[int]]:
    lines = data.split('\n')
    values = [[int(v) for v in line] for line in lines if line != '']
    return values

D’abord on sépare par ligne avec split('\n'), puis on convertit chaque caractère en entier, pour faire donc une liste de listes d’entiers. Ensuite, il faut trouver des maxima.

Première partie - maxima

Reformulons le problème: pour faire un nombre à deux chiffres le plus haut possible, je sais que le premier chiffre ne peut forcément pas être le dernier de ma liste, puisque je ne peux pas modifier l’ordre. Donc je commence par chercher le maximum parmi les n-1 premiers chiffres:

def part1(data: list[list[int]]) -> int:
    maxdigit = [max(d[:-1]) for d in data]
    # ...

def part1(data: list[list[int]]) -> int:
    # ...
    posmax = [d.index(m) for m,d in zip(maxdigit, data)]
    # ...

Pour le second chiffre, ce sera le maximum parmi les chiffres suivants le maximum. On peut ensuite former le nombre à deux chiffres en faisant 10*m+s, où m est le premier chiffre et s le second:

def part1(data: list[list[int]]) -> int:
    # ...
    secondigit = [max(d[p+1:]) for p,d in zip(posmax, data)]
    numbers = [m*10+s for m, s in zip(maxdigit, secondigit)]
    # ...

def part1(data: list[list[int]]) -> int:
    # ...
    return sum(numbers)

Deuxième partie - récursion

La deuxième partie est un “twist” assez classique dans les Advent of Code, qui nous force à généraliser la solution trouvée au premier. Au lieu d’avoir un nombre à deux chiffres par ligne, il faut maintenant trouver un nombre à 12 chiffres.

Pour moins risquer de me tromper, je vais commencer par faire une nouvelle méthode qui généralise celle de la première partie, mais en l’utilisant pour recalculer la version “deux chiffres”, pour voir que je n’introduit pas de nouvelle erreur.

Je vais donc commencer par créer une fonction qui trouve, pour une ligne, le plus grand nombre à n_digits chiffres. Si on a une liste de m chiffres, le premier choix doit garder au minimum n_digits-1 chiffres disponibles derrière lui. On va ensuite restreindre l’espace des chiffres disponibles pour qu’il commence après la première occurrence de ce maximum, et recommencer en diminuant le nombre de chiffres restant à trouver.

Je suis dans les exercices de récursivité dans le cours de Math que je donne pour l’instant, donc codons la solution récursive. Le cas de base sera si je demande un nombre à 1 chiffre: renvoyer le maximum. Sinon, on cherche le maximum parmi row[:-(n_digits-1)], on trouve la position, et on fait l’appel récursif. Pour être propre, je rajoute un test si n_digits < 1, où je renvoie 0. Ce ne sera pas vraiment nécessaire ici, mais je n’aime pas laisser la possibilité d’une récursion infinie!

def largest_number_in_row(row: list[int], n_digits: int) -> int:
    if n_digits < 1:
        return 0
    if n_digits == 1:
        return max(row)

    d = n_digits-1
    maxdigit = max(row[:-d])
    posmax = row.index(maxdigit)

    return maxdigit*(10**d) + largest_number_in_row(row[posmax+1:], d)

On pourrait aussi alternativement tout à fait utiliser une forme itérative, qui nécessite juste un petit peu de chipotage pour le cas où n_digits==0, car row[:-0] renvoie une liste vide…

def largest_number_in_row(row: list[int], n_digits: int) -> int:
    n = 0
    available = row[:]
    for d in range(n_digits-1, -1, -1):
        maxdigit = max(available[:-d] if d > 0 else available)
        posmax = available.index(maxdigit)
        available = available[posmax+1:]
        n += maxdigit*(10**d)
    return n

def part1bis(data: list[list[int]]) -> int:
    s = 0
    ns = [largest_number_in_row(row, 2) for row in data]
    return sum(ns)

def part2(data: list[list[int]]) -> int:
    s = 0
    ns = [largest_number_in_row(row, 12) for row in data]
    return sum(ns)