Le problème

Les deux parties

Une fois n’est pas coutume, je vais décrire tout de suite les deux parties du problème puisqu’elles sont en réalité quasi-identiques.

Aujourd’hui, on nous propose un problème où il faudra gérer des chaînes de caractères, et plus particulièrement des insertions de caractères en suivant des règles bien précises.

Dans le dataset, on a :

• Une chaîne de caractères (par exemple NNCB) ;
• Des règles d’insertion du type CH -> B, qui signifie que l’on va insérer une lettre B entre les deux lettres C et H.

Avec cette chaîne de caractères initiale et ces règles, l’exercice nous demande d’effectuer ces insertions 10 fois de suite pour la première partie, ou 40 fois de suite pour la seconde. Le point d’attention concerne le résultat attendu : il s’agit de calculer la différence entre le nombre d’apparitions de la lettre la plus fréquente et le nombre d’apparitions de la lettre la moins fréquente.

Une version brute force permet de résoudre la première partie assez simplement et rapidement, en créant la chaîne au fur et à mesure des 10 itérations. Mais avec une complexité exponentielle (la taille de cette chaîne quasi-double à chaque itération), on est vite coincé lorsqu’il s’agit d’attaquer la seconde partie.

J’avoue avoir été pas mal décontenancé par cette seconde partie, parce que je cherchais désespérément à construire la chaîne complète avant de calculer la fréquence de chaque lettre. Mais grâce à l’aide de mes collègues JP et JC, j’ai finalement compris l’astuce : peu importe de construire la chaîne, celle-ci reposera toujours sur des couples de lettres qui vont engendrer deux autres couples de lettres. En effet, l’énoncé nous informe des constructions après chaque étape :

NNCB    # {'NN':1, 'NC': 1, 'CB': 1}

NN -> C ==> ('NC', 'CN')
NC -> B ==> ('NB', 'BC')
CB -> H ==> ('CH', 'HB')

NCNBCHB ---> {'NC': 1, 'CN': 1, 'NB':1, 'BC': 1, 'CH': 1, 'HB': 1}

Et on constate donc que le résultat NCNBCHB est en fait équivalent aux couples nouvellement générés. Ce qui est encore plus intéressant, c’est que l’ordre des couples ne nous importe peu, puisque la chaîne résultante sera toujours constitué de la même façon. J’ai ensuite choisi de représenter la chaîne cela sous la forme d’un dictionnaire pour pouvoir compter le nombre de fois que ces couples apparaissent avant chaque itération.

Voici donc la solution pour les deux parties :

from collections import Counter, defaultdict


def parse_input_data():
    with open('input-large.txt', 'r') as data:
        lines = data.read().splitlines()
        template = lines[0]
        rules = {line.split(' -> ')[0]:line.split(' -> ')[1] for line in lines[2:]}
        return template, rules


def create_dict_of_pairs(template):
    pairs = defaultdict(int)
    for i in range(len(template) - 1):
        pairs[template[i:i + 2]] += 1
    return pairs


def update_count(pairs, rules, count):
    pairs_created = defaultdict(int)
    for key, value in pairs.items():
        letter = rules[key]     # La lettre à ajouter
        count[letter] += value  # Le nombre de fois qu'il faut ajouter la lettre
        head = key[0] + letter  # Le couple nouvellement généré
        tail = letter + key[1]  # L'autre couple nouvellement généré
        pairs_created[head] += value    # Mise à jour du dictionnaire de paires
        pairs_created[tail] += value
    return pairs_created        # Dictionnaire réutilisé pour l'itération suivante


def solve(iterations):
    template, rules = parse_input_data()
    pairs = create_dict_of_pairs(template)
    count = Counter(template)
    for _ in range(iterations):
        pairs = update_count(pairs, rules, count)
    print(max(count.values()) - min(count.values()))


if __name__ == '__main__':
    solve(10)
    solve(40)

Les difficultés

Le problème d’aujourd’hui m’a pris pas mal de temps parce que je cherchais absolument à construire la chaîne de caractères. Et pour le coup, avec une complexité exponentielle, j’aurais pu attendre longtemps…

L’astuce pour cette journée provient du fait que, encore une fois, il n’est pas nécessaire de construire toute la chaîne puisqu’on peut compter les éléments au fur et à mesure. Merci encore une fois à JP et JC pour m’avoir soufflé l’astuce !