Advent of Code 2025 - Day 2: Gift Shop

multicolored illustration

niels jaspers • december 2, 2025

This is part two of an ongoing series of posts about my experiences solving the Advent of Code 2025 puzzles. This year, I'm doing a showdown with my good friend Levi. Since AoC is twelve days long this year, we'll be solving the puzzles in twelve different languages.

Day 2 of Advent of Code 2025 had me learning Lua from scratch while discovering that sometimes the best optimization isn't faster code. Sometimes it's just realizing you're solving the wrong problem entirely.

The Problem

We're given ranges of "ID numbers" and need to find all "invalid IDs" within them. An invalid ID is one that consists of a repeating pattern.

Part 1: Numbers where the left half equals the right half. Think 1212, 100100, 77777777.

Part 2: Numbers where any pattern repeats two or more times. Now 111, 565656, and 824824824 all count too.

The catch? Some ranges span millions of numbers. Checking each one individually would take forever, especially in Lua.

Starting Simple

My first approach was the obvious one: iterate through every number, convert to string, split in half, compare. 

for i = s, e do
    local str = tostring(i)
    if #str % 2 == 0 then
        local mid = #str / 2
        local left = string.sub(str, 1, mid)
        local right = string.sub(str, mid + 1)
        if left == right then
            table.insert(numbers, i)
        end
    end
end

This worked fine for small ranges. Then I hit a range like 7777742220-7777814718 and watched my terminal hang.

Runtime: ~850ms for the test data. Not great.

Learning Lua's Quirks Along the Way

Before I could optimize anything, I had to wrestle with Lua itself. Some highlights:

The Insight: Generate, Don't Check

The turning point came when I stopped trying to speed up the checking and started asking: can I generate only the numbers that match the pattern?

Numbers like 11, 1212, 100100 follow a pattern. For a number with an even number of digits (say, 2k digits where k is half), if the left half equals the right half, it can be expressed as: 

n × (10^k + 1)

Where n is any k-digit number.

Why does this formula work?

The expression 10^k + 1 creates a "repeater" multiplier. When you multiply n by this:

So n × (10^k + 1) = n × 10^k + n, which concatenates n with itself.

Concrete example: For n = 12 and k = 2: 

12 × (10² + 1) = 12 × 101 = 12 × 100 + 12 × 1 = 1200 + 12 = 1212

The pattern for different digit counts

Instead of checking millions of numbers, I only need to generate all k-digit patterns and multiply. For 4-digit results, that's just 90 multiplications (10-99). For 10-digit results, still only 90,000 multiplications. That's way better than checking millions.

Tight bounds: only generate what's in range

There's another optimization hiding here. Instead of generating all possible patterns and filtering to our range, we can compute exactly which patterns will produce results in range [s, e] (where s and e are the start and end of the range).

Since candidate = n × multiplier, we need s ≤ n × multiplier ≤ e.

Rearranging: s/multiplier ≤ n ≤ e/multiplier

We clamp this to the valid n range to avoid generating out-of-range numbers: 

local start_n = math.max(min_n, math.ceil(s / multiplier))
local end_n = math.min(max_n, math.floor(e / multiplier))

for n = start_n, end_n do
    total = total + (n * multiplier)
end

No conditional checks needed inside the loop - every generated number is guaranteed to be in range.

Part 2: Any Repeating Pattern

Part 2 expanded the definition: any repeating pattern counts, not just "left half equals right half". Now 111 (1 repeated 3 times), 565656 (56 repeated 3 times), and 824824824 (824 repeated 3 times) are all invalid.

The approach is similar, but we need to consider all valid chunk sizes, not just half.

The algorithm

Step 1: Figure out which digit counts could appear in the range [s, e].

Example: range 95-115 contains 2-digit numbers (95-99) and 3-digit numbers (100-115), so we check d = 2 and d = 3.

Step 2: For each digit count d, find all ways to split it into repeating chunks.

A chunk size k is valid if:

Example for d=6:

Step 3: For each valid chunk size k, generate all possible k-digit patterns.

Example for k=2: generate all 2-digit numbers from 10 to 99. These are the "chunks" we'll repeat.

Step 4: For each pattern p, use the formula to create the full repeating number.

The generalized formula: 

p × (10^d - 1) / (10^k - 1)

Why does this formula work?

Let's break down (10^d - 1) / (10^k - 1) for d=6, k=2: 

(10⁶ - 1) / (10² - 1) = 999999 / 99 = 10101

What is 10101? It's 10000 + 100 + 1, or equivalently 10^4 + 10^2 + 10^0.

When you multiply a 2-digit pattern by 10101: 

56 × 10101 = 56 × (10000 + 100 + 1)
           = 560000 + 5600 + 56
           = 565656

The multiplier places the pattern at each "slot" position. For 3 repetitions of a 2-digit chunk, those slots are at positions 0, 2, and 4.

Step 5: Check if the generated number is in range and hasn't been added yet.

The Duplicate Bug

My Part 2 solution initially gave the wrong answer: 4174823709 instead of 4174379265.

The problem? Numbers like 222222 match multiple patterns:

I was counting it three times. The fix was simple though, just track what we've already added: 

local seen = {}

for p = start_p, end_p do
    local candidate = p * multiplier
    if not seen[candidate] then
        seen[candidate] = true
        total = total + candidate
    end
end

The Final Optimized Solution

After all the iterations, the final code is clean and fast: 

local pow10_cache = {}
local function pow10(n)
    if not pow10_cache[n] then
        pow10_cache[n] = math.pow(10, n)
    end
    return pow10_cache[n]
end

local total = 0
local seen = {}

for s_str, e_str in line:gmatch("(%d+)-(%d+)") do
    local s = tonumber(s_str)
    local e = tonumber(e_str)
    
    local min_digits = #s_str
    local max_digits = #e_str
    
    for d = min_digits, max_digits do
        for k = 1, math.floor(d / 2) do
            if d % k == 0 then
                local multiplier = (pow10(d) - 1) / (pow10(k) - 1)
                
                local start_p = math.max(pow10(k-1), math.ceil(s / multiplier))
                local end_p = math.min(pow10(k)-1, math.floor(e / multiplier))
                
                for p = start_p, end_p do
                    local candidate = p * multiplier
                    if not seen[candidate] then
                        seen[candidate] = true
                        total = total + candidate
                    end
                end
            end
        end
    end
end

Runtime: sub-millisecond. From 850ms to essentially instant.

Optimizations That Mattered

In order of impact:

  1. Generate instead of check. The algorithmic change from O(M) to O(D × 10^(D/2)) where M is the range size and D is digit count.
  2. Tight bounds calculation. Instead of generating all patterns and filtering, compute exactly which patterns produce in-range results.
  3. Sum as you go. No intermediate storage, no second loop. Just accumulate directly.
  4. Inline parsing. Replaced a custom split function with a single gmatch pattern: "(%d+)-(%d+)" captures both numbers directly.
  5. Cache pow10. Minor but measurable. Avoids redundant math.pow calls.

Lessons Learned

The best optimization is often algorithmic. All the micro-optimizations in the world (caching, inlining, avoiding string operations) wouldn't have saved my 850ms solution. The biggest speedup came from recognizing that the numbers I wanted had a mathematical structure I could exploit.

Constraints are features. Using "slow" Lua forced me to think about efficiency in a way that Python might not have. The discomfort was productive.

Duplicates will get you. Any time you're generating candidates from multiple sources (different chunk sizes, different ranges), think about whether the same result can appear twice.

Math is your friend. Once I understood why n × (10^k + 1) produces repeating numbers, extending it to arbitrary repetitions was straightforward. It's not magic, it's just place value arithmetic.

On to Day 3.