• # jour 19 - on souffle

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

    Cela faisait longtemps que la solution ne tenait plus en quelques lignes, et que la partie 2 ne pétait pas complètement la partie 1.

    Aujourd'hui, avec du récursif et du cache, ça tient en 4 lignes.

    import sys
from functools import cache
f = cache(lambda s: 1 if len(s)==0 else sum(f(s[len(r):]) for r in R if s.find(r) == 0))
R, I = sys.stdin.read().strip().split("\n\n")
R = R.split(", ")
print(sum(f(i)>0 for i in I.split("\n")))
print(sum(f(i) for i in I.split("\n")))

    Il n'y a qu'une seule ligne intéressante : la fonction récursive.
    En gros : pour une chaîne, si on trouve un préfixe valide, on refait un appel avec la chaîne amputée du préfixe. Si on arrive à une chaîne vide, on a pu faire le pattern demandé, sinon, non (la somme d'un générateur vide vaut 0).

    Pour s'en convaincre, il faut regarder les différents cas.

    • si la chaîne est vide, elle peut trivialement être réalisée avec n’importe quelle règle (retourne Vrai ou 1)
    • si la chaîne ne commence par aucune des règles, elle ne peut pas être réalisé (retour Faux ou 0)
    • si plusieurs règles constituent un préfixe de la chaîne, il faut examiner toutes les pistes pour construire la sous-chaîne et sommer ces possibilités.

    La combinatoire explosant très vite, on met les résultats en cache pour pouvoir les réutiliser. Plus la chaîne est petite, plus le cache fera effet, c'est à dire en bout de chaîne ; dans l'exemple "gbr" est réalisé de trois façons différente ("g-b-r","gb-r", "g-br") ; on met en cache "bgbr" -> 3 et on a plus à le recalculer.

    Pour "rrbgbr", on sait qu'on peut faire "rrb" de deux façons ("r-rb" ou "r-r-b"), on a donc 3+3=6 façons de faire la chaîne complete. Plus on avance dans l'exercice, plus on a des bouts réutilisables.

    Dans mon cas, il y a 841E12 branches valides ce qui serait impossible à explorer ; mais avec le cache, seulement 53E3 appels à f et 18E3 entrées dans le cache.