• [^] # Re: jour 19 - on souffle

    Posté par . En réponse au journal Advent of code 2024. Évalué à 2.

    Comme d'habitude, j'essaie de trouver le meilleur algorithme pour résoudre le problème même si ce n'est pas nécessaire.

    Aujourd'hui, la structure donnée à utiliser m'a paru naturelle: les prefix trees (également appelés tries).

    https://fr.wikipedia.org/wiki/Trie_(informatique)

    J'ai passé pas mal de temps à bien optimiser mon implémentation.
    Au début, j'avais également fait une fonction récursive avec cache mais de la programmation dynamique s'est avérée plus rapide (3x fois plus rapide pour être précis).

    L'algo en pseudo-code est le suivant

    fonction(trie, design):
 initialiser t un tableau de (len(design)+1) entiers à 0
 t[0] = 1
 pour i de 0 à len(design) - 1:
 pour chaque prefixe p de design[i..] dans trie:
 t[i + len(p)] += t[i]
 renvoyer t[design]

    La structure de données trie permet de très efficacement trouver les préfixes d'un mot appartenant à une liste.
    170 microsecondes partie + partie 2.