Je suis arrivé à peu près aux mêmes conclusions, avec comme toujours de légères variantes dans l'approche.
Pour la première partie, étant donné que chaque signe était soit « + », soit « ×ばつ », on pouvait utiliser du binaire pour les marquer et j'ai donc utilisé une boucle qui comptait de 0 à 1 << n pour obtenir les combinaisons, et on obtenait donc directement une fonction itérative plutôt que récursive.
En outre, en comptant de deux en deux, on peut forcer le bit0 à être toujours nul et donc à imposer un « + » sur le premier nombre, ce qui permet de l'ajouter directement à un accumulateur vide plutôt que faire une exception rien que pour lui.
Pour la deuxième partie, j'ai effectivement réécrit une fonction récursive mais là encore, étant donné que l'on traite des entiers strictement positifs, le cumul ne peut être que croissant étant donné les opérations à utiliser (ici +, - et ||). Donc, j'ai effectivement passé la cible à la fonction récursive parallèlement aux autres arguments et interrompu la procédure chaque fois qu'une « branche » dépassait la cible. C'est la même chose mais dans l'autre sens.
Cela me donne 240 microsecondes au lieu de 15 millisecondes avec une approche brute-force.
Tu as oublié de remettre les arguments à l'endroit en sortie... :-)
[^] # Re: 7ème jour, un peu de répit
Posté par Obsidian . En réponse au journal Advent of code 2024. Évalué à 2.
Je suis arrivé à peu près aux mêmes conclusions, avec comme toujours de légères variantes dans l'approche.
Pour la première partie, étant donné que chaque signe était soit « + », soit « ×ばつ », on pouvait utiliser du binaire pour les marquer et j'ai donc utilisé une boucle qui comptait de
0à1 << npour obtenir les combinaisons, et on obtenait donc directement une fonction itérative plutôt que récursive.En outre, en comptant de deux en deux, on peut forcer le bit0 à être toujours nul et donc à imposer un « + » sur le premier nombre, ce qui permet de l'ajouter directement à un accumulateur vide plutôt que faire une exception rien que pour lui.
Pour la deuxième partie, j'ai effectivement réécrit une fonction récursive mais là encore, étant donné que l'on traite des entiers strictement positifs, le cumul ne peut être que croissant étant donné les opérations à utiliser (ici
+,-et||). Donc, j'ai effectivement passé la cible à la fonction récursive parallèlement aux autres arguments et interrompu la procédure chaque fois qu'une « branche » dépassait la cible. C'est la même chose mais dans l'autre sens.Tu as oublié de remettre les arguments à l'endroit en sortie... :-)