AoC '25, day 2 part 2

solve.py

# AoC '25, day 2 part 2
import math

# naive implementation, iterates and checks every number in the range
def pn(l, r):
    for n in range(l,r+1):
        digits = int(math.log10(n))+1
        for period in [p for p in range(1,digits//2+1) if not digits % p]:
            base = n // 10**(digits-period)
            periodic = base
            for i in range(1,digits//period):
                periodic = periodic * 10**period + base

            if periodic == n:
                yield n
                break

# faster approach that constructs periodic numbers within the range
def pnf(l, r):
    # avoids the situations like 3333 having a period of both 1 and 2 being
    # double counted.
    seen = set()

    # unfortunate ugliness: the approach here only works when not crossing a
    # power of 10. If our range does so, split the range into orders of
    # magnitude and do our thing
    ldigits = int(math.log10(l))+1
    rdigits = int(math.log10(r))+1

    if ldigits != rdigits:
        for e10 in range(ldigits, rdigits+1):
            yield from pnf(max(10**(e10-1), l), min(10**e10-1, r))

        return

    # Consider the following range: 1200 - 1300
    # The period of a repeating number must evenly divide the number of digits
    # in the number, so the only possible periods here are 1 and 2.
    # For a given period take the first p digits of each end of the range and
    # iterate between them, repeating those p digits, enumerating all possible
    # repeating numbers of that period, so in this case iterate over [12,13]
    # repeating each to discover 1212 and 1313 are the period 2 cabdidates,
    # then just bounds check to pick out 1313
    #
    # Asymptotic analysis? IDK mang. O(log10(n)) periods (where n is the width of
    # the range) need be considered. Now actually that's smaller, only p
    # evenly dibisible by #digits, but what's the bound on the number of factors
    # a number might have? I actually don't know, linear in the limit?
    # Anyway let's say log10(n) periods, then the upper bound on number of
    # patterns we need to consider _within a given period_ is constant, e.g. there
    # are always at most 99 p=2 values to consider, but 999 p=3, etc so O(10^p),
    # let's assume only the largest period dominates (which I think is correct),
    # then what's the bound on the size of the period? log10(n)/2 again. So I think
    # this gives us a O(log10(n)^2) (with caveat about n being range _width_)
    # which I think is still O(log10(n))? IDK, that didn't seem super rigerous
    # but hey, if I'm not smoking crack a genuine lg(n) algo! How about that?
    # All you losers who used backreferences: behold!
    for period in [p for p in range(1,ldigits//2+1) if not ldigits % p]:
        lbase = l // 10**(ldigits-period)
        rbase = r // 10**(ldigits-period)

        for base in range(lbase, rbase+1):
            periodic = base
            for i in range(1,ldigits//period):
                periodic = periodic * 10**period + base

            if periodic >= l and periodic <= r and periodic not in seen:
                seen.add(periodic)
                yield periodic

# from timeit import timeit
# raw = open("input.txt", "r").read()
# input = [(int(l), int(r)) for (l,r) in [s.split('-') for s in raw.strip().split(',')]]
# timeit(lambda: sum([sum(solve.pn(l,r)) for l,r in input]), number=10)
# timeit(lambda: sum([sum(solve.pnf(l,r)) for l,r in input]), number=10)