Le problème

Partie 1

Notre ballade en sous-marin se poursuit, et l’on continue même de descendre en profondeur. L’énoncé nous dit alors que l’on rencontre un énorme banc de poissons-lanternes, tellement que l’on cherche à modéliser leur reproduction. Notre perspicacité nous fait deviner qu’un poisson-lanterne engendre un autre poisson-lanterne au bout de 7 jours.

Notre sous-marin nous produit alors notre jeu de données : une liste d’entiers compris entre 0 et 7 et qui correspondent aux “horloges” (ou timers) pour chaque poisson-lanterne initial. À chaque jour qui passe, ces horloges diminuent de 1 jusqu’à arriver à 0 où un nouveau poisson-lanterne est créé.

3,4,3,1,2

L’objectif de cet exercice est de calculer, à partir de notre liste initiale, le nombre de poissons-lanternes après 80 jours de reproduction.

Pour cette première partie, on va assez simplement reproduire les événements qui se passent chaque jour pour calculer le nombre de poissons-lanternes à la fin des 80 jours. Ainsi, après chaque jour :

1. L’horloge interne de tous les poissons diminue de 1.
2. Si des horloges internes sont égales à -1, c’est que le poisson-lanterne en a engendré un autre.
3. On compte alors le nombre de -1 dans la liste, pour ajouter autant de 8 à la fin de celle-ci (synonyme de nouveaux poissons-lanternes engendrés).
4. Pour tous les poissons-lanternes ayant comme valeur -1, on change désormais leurs horloges internes pour prendre la valeur 6, comme expliqué par l’énoncé.

Lorsque les 80 jours sont passés, il n’y a plus qu’à calculer la longueur de la liste des horloges internes, qui correspond également au nombre final de poissons-lanternes.

def parse_input_data(is_first_part):
    with open('input-small', 'r') as data:
        lines = [int(x) for x in data.read().splitlines()[0].split(',')]
       return lines
       
       
       
def solve_part_one():
    """
    This function retrieves the list of timers of all the initial fish. 
    We then implement the following algorithm:
    Repeat 80 times:
        - We decrease by 1 the timer for each element in the list of timers.
        - We count the number of timers that reached the value of -1, which means 
          that they have "hatched", or gave birth to a new fish.
        - As we are told, these fish get their timer values set to 6.
        - And we add as many 8's to the initial list as there are fish that are 
          just born.
    Finally, we simply return the length of this list to produce the final result.
    :return: The length of the list `timers`, which represents the number of fish 
             after 80 reps.
    """
    timers = parse_input_data()
    for i in range(80):
        timers = [timer - 1 for timer in timers]
        hatched = timers.count(-1)
        timers = [timer if timer != -1 else 6 for timer in timers]
        timers += [8] * hatched
    print(len(timers))

Partie 2

Pour la deuxième partie, et pour la première fois en 6 jours, l’énoncé est exactement le même au détail suivant près : il faut désormais compter le nombre de poissons-lanternes après 256 jours de reproduction.

Les énoncés des deux parties peuvent laisser présager de ce qu’il va se passer si l’on change naïvement la valeur de 80 à 256 dans notre boucle for : la taille des données devient trop grande et l’algorithme prend trop de temps avant de donner une réponse.

Si on y réfléchit un peu, un poisson engendre un autre poisson au bout de 7 jours, qui engendre un autre poisson au bout de 7 jours, et ainsi de suite. Après 256 jours, si on compte grossièrement 36 cycles de reproduction (36 * 7 = 252), un poisson-lanterne initial aura engendré 2^36 - 1 autres poissons, soit environ 68 milliards de poissons. Cela peut être expliqué par la petite illustration ci-après, où on a représenté :

• En noir, le poisson initial ;
• En bleu, les poissons engendrés après un cycle de 7 jours ;
• En vert, les poissons engendrés après un second cycle de 7 jours ;
• En rouge, les poissons engendrés après un troisième cycle de 7 jours.

Et on comprend donc l’explosion de la taille de la liste si l’on reste sur un algorithme naïf. Il faut donc changer son fusil d’épaule, et j’ai décidé de représenter le problème encore une fois avec un dictionnaire. Hier, on m’a même introduit les Counter qui sont assez bien adaptés au problème d’aujourd’hui. En effet, les clés de ce Counter seront les valeurs d’horloge des poissons-lanternes, et les valeurs associées à ces clés seront le nombre de poissons ayant cette valeur d’horloge. Ainsi, à chaque jour qui passe, on va faire basculer la valeur de counter[0] vers counter[-1], celle de counter[1] vers counter[0], celle de counter[2] vers counter[1], etc.

Une fois ces bascules faites, il n’y a plus qu’à gérer la valeur de counter[-1] qui correspond au nombre de poissons-lanternes ayant engendrés de nouveaux poissons. Pour ceux-là :

1. On initialise à counter[8] la valeur de counter[-1] ;
2. On ajoute à counter[6] la valeur de counter[-1] ;
3. On ajoute à length le nombre de poissons-lanternes engendrés en ce jour.

Et au bout des 256 jours, on n’a plus qu’à retourner la valeur de length.

from collections import Counter


def parse_input_data(is_first_part):
    with open('input-small', 'r') as data:
        lines = [int(x) for x in data.read().splitlines()[0].split(',')]
        if is_first_part:
            return lines
        length = len(lines)
        counter = Counter({k: 0 for k in range(9)})
        counter.update(lines)
        return length, counter


def solve_part_two():
    """
    Although the exercise is exactly identical to the first part 1, we are 
    reaching a problem if we reuse the same algorithm due to the exponential 
    growth of the number of fish. So I've changed the data structure used to 
    represent the problem to a Counter.
    :return: The number of fish after 256 reps.
    """
    length, counter = parse_input_data(False)
    for i in range(256):
        counter = {k - 1: counter[k] for k in counter.keys()}
        hatched = counter[-1]
        length += hatched
        counter[-1] = 0
        counter[6] += hatched
        counter[8] = hatched
    print(length)


if __name__ == '__main__':
    solve_part_one()
    solve_part_two()

Les difficultés

Si l’on compare les deux parties, on constate très rapidement que la taille de la structure de données utilisées en partie 2 n’augmente pas malgré le nombre de nouveaux poissons-lanternes engendrés.

Pour information, les valeurs que j’ai obtenues pour la partie 1 et 2 sont respectivement 343441 et 1,569,108,373,832 (plus de mille milliards de poissons) !

On s’imagine bien que de devoir gérer chacun des mille milliards de poissons dans une boucle for n’est pas du tout optimisé, et la solution proposée ici me semble assez simple et élégante pour contourner ce problème. Un bel exemple des différences de performances en fonction de la modélisation choisie pour un même problème !