Advent of code

◂ 2 décembre 2025 ▸

  Gift Shop : Trouver des nombres qui sont composés exactement d'un pattern qui se répète (ABCABCABCABC par exemple).
17330-35281,9967849351-9967954114, … ,16048379-16225280
La partie 1 se fait facilement.
La partie 2 se fait facilement avec des Regexp et en passant en revue chaque nombre de l'intervalle ; cela prend en revanche 2 secondes pour tout faire.

Il est possible de calculer directement la somme des nombres sans tout passer en revue.
Par exemple, entre 3519 et 8342, il y a 3535, 3636…, 8282. Il suffit donc de compter la somme des nombres de 35 à 82, puis de multiplier par 101.
La difficulté arrive lorsqu'il y a plusieurs divisions du nombre possibles, par exemple pour 6 chiffres: ABABAB et ABCABC, qui va compter à double les AAAAAA. Il faut donc faire une correction avec un principe d'inclusion-exclusion pour supprimer les doublons. Ce code avec formule est beaucoup plus rapide.
  1. code_part1.py
  2. code_regexp.py
  3. code_formule.py
ranges = []
with open("input.txt", 'r', encoding='utf-8') as f:
    for line in f.read().strip().split(','):
        ranges.append(line)

EXCLUSION_INCLUSION = {
   1:(0,),    # ID of length 1 is valid
   2:(0,1),   # ID of length 2 is rejected for repeating pattern of length 1 'A'
   3:(0,1),
   4:(0,0,1,),   # ID of length 4 is rejected for repeating pattern of length 2 'AB', which includes repeating pattern of length 1 'AA'
   5:(0,1),
   6:(0,-1,1,1), # ID of length 6 is rejected for repeating pattern of length 2 'AB', length 3 'ABC', but counts 2 times 'AAAAAA'
   7:(0,1),
   8:(0,0,0,0,1),
   9:(0,0,0,1),
  10:(0,-1,1,0,0,1),
# 30:(0,1,-1,-1,0,-1,1,0,0,0,1,0,0,0,0,1)  # for length 30, add pattern of length 6, 10 and 15, subtract double counted length 2, 3 and 5, add length 1 again.
}

rep1 = 0
rep2 = 0

def sum_range(start, end, rep):
    if start > end:
        return 0
    tot = end*(end+1)//2 - start*(start-1)//2
    m = int(rep*((len(str(start))-1)*'0'+'1'))
    return tot * m

# start and end of same length 
def calc_range(start, end):
    global EXCLUSION_INCLUSION
    L = len(str(start))
    n1 = n2 = 0
    for d,factor in enumerate(EXCLUSION_INCLUSION[L]):
        if factor != 0:
            rep = L // d  
            s = str(start)[:d]
            e = str(end)[:d]
            if int(rep*s) < start:
                s = int(s) + 1
            else:
                s = int(s)
            
            if int(rep*e) > end:
                e = int(e) - 1
            else:
                e = int(e)
            v = sum_range(s, e, rep)
            n2 += factor * v
            if rep == 2:
                n1 += v
    return n1, n2

for r in ranges:
    start, end = r.split('-')
    # split interval in subintervals of numbers of same length:
    # 810-13020 => 810-999 + 1000-9999 + 10000-13020
    for longueur in range(len(start), len(end)+1):
        s = max(int(start), 10**(longueur-1))
        e = min(int(end), 10**longueur-1)
        add1, add2 = calc_range(s,e)
        rep1 += add1
        rep2 += add2
        
print("Réponse partie 1:", rep1)
print("Réponse partie 2:", rep2)




# If needed, compute EXCLUSION_INCLUSION's missing values with this function
import sympy, itertools, math
def get_exclusion_inclusion_factors(n):
    if n == 1:
        return (0,)
    primes = sympy.primefactors(n)   # 6000 => [2,3,5]
    factors = (n//primes[0] + 1)*[0]
    for i in range(1,len(primes)+1):
        for subfactors in itertools.combinations(primes, i):
            factors[n//math.prod(subfactors)] = (-1)**(i+1)
    return tuple(factors)