Tu as des sources inconnues.
Et un indice au bout, puisque tu as remplacé récursivement un maximum de sources inconnues en sources actives.
Tu peux décaler ton indice vers la gauche pour chacune des sources inconnues que tu as traversé.
Et à chaque fois tu doubles le nombre de chemin possible après ton indice.
Mais il faut bien vérifier que tu ne prends pas des sources actives pour des sources inconnues rendues actives.
Et puis il y a d'autres cas où en décalant suffisamment vers la gauche, tu libères de la place pour faire plus de chemins à droite parce que l'indice suivant peut « sauter » à gauche au dessus d'un trou de sources actives.
Bon, je ne sais pas si c'est clair, mais j'ai exploré ça en essayant de voir si j'arrivais à trouver les conditions pour savoir quand ça fonctionne ou pas. Le premier problème soulevé est assez simple à résoudre, mais le second pas du tout.
Et ça devient compliqué de savoir quand on doit finalement explorer une nouvelle branche ou pas, mais il suffit de regarder l'indice suivant, puisque tout se fera ensuite de proche en proche.
C'est à ce moment là que j'ai réalisé que mon idée était équivalente à « on se moque de ce qui a été fait à gauche, tout ce qui compte c'est où on en est précisément à la position actuelle », et là l'utilisation du cache était évidente.
Exemple ??.?#? 1,2, tu as .#..##, .#.##., #...## et #..##..
Quand tu es sur le troisième ? en 4è place, ce que tu vas trouver derrière c'est .## ou ##., et ça ne dépend pas du tout de ce qui s'est passé avant, soit .#. ou #...
donc dans ta récursion, quand tu vas explorer .#. et #.., le calcul de ce qui se passe à droite va être strictement le même, tu auras 2 chemins : .## et ##., inutile de recalculer, donc l'utilisation d'un cache devient la bonne façon de faire, puisqu'on sait qu'on va passer notre temps à recalculer la même chose.
[^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 12. Évalué à 3.
Tu as des sources inconnues.
Et un indice au bout, puisque tu as remplacé récursivement un maximum de sources inconnues en sources actives.
Tu peux décaler ton indice vers la gauche pour chacune des sources inconnues que tu as traversé.
Et à chaque fois tu doubles le nombre de chemin possible après ton indice.
Mais il faut bien vérifier que tu ne prends pas des sources actives pour des sources inconnues rendues actives.
Et puis il y a d'autres cas où en décalant suffisamment vers la gauche, tu libères de la place pour faire plus de chemins à droite parce que l'indice suivant peut « sauter » à gauche au dessus d'un trou de sources actives.
Bon, je ne sais pas si c'est clair, mais j'ai exploré ça en essayant de voir si j'arrivais à trouver les conditions pour savoir quand ça fonctionne ou pas. Le premier problème soulevé est assez simple à résoudre, mais le second pas du tout.
Et ça devient compliqué de savoir quand on doit finalement explorer une nouvelle branche ou pas, mais il suffit de regarder l'indice suivant, puisque tout se fera ensuite de proche en proche.
C'est à ce moment là que j'ai réalisé que mon idée était équivalente à « on se moque de ce qui a été fait à gauche, tout ce qui compte c'est où on en est précisément à la position actuelle », et là l'utilisation du cache était évidente.
Exemple
??.?#? 1,2, tu as.#..##,.#.##.,#...##et#..##..Quand tu es sur le troisième
?en 4è place, ce que tu vas trouver derrière c'est.##ou##., et ça ne dépend pas du tout de ce qui s'est passé avant, soit.#.ou#...donc dans ta récursion, quand tu vas explorer
.#.et#.., le calcul de ce qui se passe à droite va être strictement le même, tu auras 2 chemins :.##et##., inutile de recalculer, donc l'utilisation d'un cache devient la bonne façon de faire, puisqu'on sait qu'on va passer notre temps à recalculer la même chose.