Advent of Code 2025 - Day 2

Useful Links

Concepts and Packages Demonstrated

Problem Intro

In the Gift Shop at the North Pole, an Elf has accidentally entered invalid product IDs into the database. Our job is to filter through a list of ID ranges and identify which IDs are invalid based on specific patterns.

The input is a comma-separated list of ranges, like 11-22,95-115.

Part 1

Which IDs are invalid because they consist of a sequence of digits repeated exactly twice?

For example, 123123 is invalid because it’s 123 repeated twice. 11 is 1 repeated twice.

This is a straightforward string manipulation task. For each number in the given ranges, we convert it to a string. If the length is odd, it can’t be a “repeated twice” pattern. If it’s even, we split it in half and check if the two halves are identical.

def part1(data: str) -> int:
    ranges = parse_input(data)
    invalid_ids = []
    for prod_id_range in ranges:
        for prod_id in range(prod_id_range[0], prod_id_range[1] + 1):
            prod_id_str = str(prod_id)
            id_len = len(prod_id_str)
            if id_len % 2 != 0: # odd numbers of digits can't contain invalid IDs
                continue
            if prod_id_str[0:id_len//2] == prod_id_str[id_len//2:id_len]:
                invalid_ids.append(prod_id)

    return sum(invalid_ids)

Part 2

Which IDs are invalid because they consist of a sequence of digits repeated at least twice?

Now the rule is broader. 123123123 is invalid (repeated 3 times). 1111111 is invalid (repeated 7 times).

To solve this efficiently, we need to find all possible “chunk lengths” that could form the string. If a string has length L, then any repeating chunk must have a length f that is a factor of L.

For example, if the ID has length 10, the factors are 1, 2, 5, 10.

Length 1: repeated 10 times?
Length 2: repeated 5 times?
Length 5: repeated 2 times?

We can iterate through all factor pairs of the string length.

Factor Pairs

I implemented a helper function get_factor_pairs(n) that returns a list of tuples (small_factor, large_factor).

@cache # We'll run this many times, so let's cache the results
def get_factor_pairs(n):
    """
    Returns a list of factor pairs of n. Always (smaller, larger).
    E.g. 8 -> [(1, 8), (2, 4)]
    """
    factors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            factors.append((i, n // i))
    
    return sorted(factors)

Caching for Performance

Since we are checking millions of IDs, many of them will have the same lengths (e.g., 6, 7, 8, 9, 10 digits). Calculating factors for 8 or 10 repeatedly is wasteful. By using functools.cache, we store the results of get_factor_pairs and reuse them.

[!TIP] Adding @cache reduced the execution time from 1.2s to 0.5s!

The Solution Logic

For each ID, we get the factor pairs of its length. For each pair (f1, f2), we check two possibilities:

Is the string made of a chunk of length f1 repeated f2 times?
Is the string made of a chunk of length f2 repeated f1 times?

We add a break to ensure we don’t double-count an ID if it matches multiple patterns (e.g., 1111 matches both length 1 repeated 4 times and length 2 repeated 2 times).

def part2(data: str) -> int:
    ranges = parse_input(data)
    invalid_ids = []
    for prod_id_range in ranges:
        for prod_id in range(prod_id_range[0], prod_id_range[1] + 1):
            prod_id_str = str(prod_id)
            id_len = len(prod_id_str)
            factor_pairs = get_factor_pairs(id_len)
            is_invalid = False
            for f1, f2 in factor_pairs:
                # Check using f1 as length (repeated f2 times)
                if f2 > 1 and f2 * prod_id_str[0:f1] == prod_id_str:
                    is_invalid = True
                # Check using f2 as length (repeated f1 times)
                elif f1 > 1 and f1 * prod_id_str[0:f2] == prod_id_str:
                    is_invalid = True
                
                if is_invalid:
                    invalid_ids.append(prod_id)
                    break

    return sum(invalid_ids)

Results

The final solution runs in about 0.5 seconds.

The output looks something like this…

Part 1 soln=1227775554
Part 2 soln=4174379265

‹