Pour le problème du jour, ma première approche a consisté à énumérer chaque id de chaque intervalle et tester s'il est invalide ou non.
Ca prend 100ms, c'est raisonnable mais j'ai cherché une solution plus efficace.
Je fais 2 suppositions sur l'input:
Tous les intervalles sont deux à deux disjoints
Chaque nombre contient au plus 10 chiffres
Pour la partie 1:
Pour l'exemple, on considère un intervalle [start, end] où start et end sont tous les deux des entiers à 6 chiffres.
Alors, les ids invalides pour cet intervalle sont les entiers multiples de 1001 dans cet intervalle.
Il faut donc faire la somme d'une suite arithmétique et ça peut se faire de manière efficace (en temps constant) sans avoir à itérer sur les valeurs de l'intervalle.
Pour la partie 2, c'est un peu plus compliqué.
Gardons le même exemple. La somme des ids invalides est la somme des multiples de 1001 (comme dans la partie 1) et des multiples de 10101 (si on coupe l'entier en 3).
Le problème, c'est qu'on a pu compter des ids en double (ceux à la fois multiples de 1001 et de 10101, ce qui correspond aux multiples de 111111).
Il faut donc retirer la somme de ces ids du total.
Les entiers posant ce problème sont ceux à 6 chiffres et ceux à 10 chiffres.
Je ne vais pas poster mon code car il est peu long et très moche.
Ca prend moins d'une microseconde soit 100_000 fois plus rapide que la première approche.
[^] # Re: Jour 2
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 3.
Pour le problème du jour, ma première approche a consisté à énumérer chaque id de chaque intervalle et tester s'il est invalide ou non.
Ca prend 100ms, c'est raisonnable mais j'ai cherché une solution plus efficace.
Je fais 2 suppositions sur l'input:
Pour la partie 1:
Pour l'exemple, on considère un intervalle
[start, end]oùstartetendsont tous les deux des entiers à 6 chiffres.Alors, les ids invalides pour cet intervalle sont les entiers multiples de 1001 dans cet intervalle.
Il faut donc faire la somme d'une suite arithmétique et ça peut se faire de manière efficace (en temps constant) sans avoir à itérer sur les valeurs de l'intervalle.
Pour la partie 2, c'est un peu plus compliqué.
Gardons le même exemple. La somme des ids invalides est la somme des multiples de 1001 (comme dans la partie 1) et des multiples de 10101 (si on coupe l'entier en 3).
Le problème, c'est qu'on a pu compter des ids en double (ceux à la fois multiples de 1001 et de 10101, ce qui correspond aux multiples de 111111).
Il faut donc retirer la somme de ces ids du total.
Les entiers posant ce problème sont ceux à 6 chiffres et ceux à 10 chiffres.
Je ne vais pas poster mon code car il est peu long et très moche.
Ca prend moins d'une microseconde soit 100_000 fois plus rapide que la première approche.