Advent of Code 2025 - Day 3: Lobby

multicolored illustration

niels jaspers • december 3, 2025

This is part three 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 3 of Advent of Code 2025 was less about algorithmic breakthroughs and more about squeezing every last millisecond out of Python. Levi had a 1.4ms solution on part 1. I was determined to beat it.

The Problem

We're given lines of digits (like 987654321111111) and need to form the largest possible number by selecting digits, but we can't rearrange them. They must stay in their original order.

Part 1: Select exactly 2 digits to form a two-digit number. Find the maximum.

Part 2: Select exactly 12 digits to form a twelve-digit number. Find the maximum.

Part 1: Finding Two Digits

The naive approach would be to check every pair of positions, but that's O(n²). Instead, we can do it in a single pass.

The insight: we want the largest possible first digit, and then the largest possible second digit that comes after it. As we scan left to right, we track:

When we find a new larger first digit, we reset num2 because any previous second digit candidates are now invalid.

The solution I eventually came up with was: 

def sortDigits(line: str) -> int:
    num1 = line[0]
    num2 = '0'

    for digit in line[1:-1]:
        if num1 == '9' and num2 == '9':
            return 99
        if num1 < digit:
            num1 = digit
            num2 = '0'
        elif num1 == digit or num2 < digit:
            num2 = digit

    digit = line[-1]
    if num1 != '9' or num2 != '9':
        if num2 < digit:
            num2 = digit

    return (ord(num1) - 48) * 10 + (ord(num2) - 48)

But getting here took a journey through failed optimizations and counterintuitive discoveries about Python.

Slow Start

Starting Point: ~3.2ms

My first working solution used a list comprehension to convert the string to integers, then processed the list: 

digits = [int(char) for char in line]
for i, digit in enumerate(digits):
    # ... logic

It worked, but Levi's solution ran in 1.4ms. Challenge accepted.

Failed Optimization #1: Working with Strings Directly

I was suggested to skip the list entirely and use ord(line[i]) - 48 to convert characters to integers on the fly. Surely avoiding list allocation would be faster?

Result: ~4-5ms. Slower than before.

Turns out Python's list comprehensions are highly optimized C code. The overhead of repeated ord() calls and indexing was worse than just building the list once.

Failed Optimization #2: Inlining the Function

Maybe function call overhead was the issue? I inlined everything into the main loop.

Result: ~3-4ms. Also slower...?

Apparently, in Python, function-local variable lookups are actually faster than global lookups because of how the bytecode works. Huh, interesting.

What Actually Worked

Optimization 1: Character Comparison

My speedup mostly came from realizing that in Python, characters compare lexicographically: '0' < '1' < '2' < ... < '9'. So instead of converting to integers, I could compare characters directly and only convert at the very end: 

num1 = line[0]      # Keep as character
num2 = '0'          # Keep as character

if num1 < digit:    # Character comparison works!
    num1 = digit
    num2 = '0'

# Only convert at the end
return (ord(num1) - 48) * 10 + (ord(num2) - 48)

This eliminated ~100 int() calls per line. int() is expensive.

Result: ~1.45ms. Now we're getting somewhere.

Optimization 2: String Slice Iteration

The final trick was changing how I iterated: 

# Before: range + indexing
for i in range(1, n - 1):
    digit = line[i]
    
# After: direct slice iteration
for digit in line[1:-1]:

line[1:-1] creates a new substring. Iterating directly over it avoids:

Result: ~1.3ms. Beat Levi's 1.4ms.

The Winning Micro-Optimizations

The final solution also includes:

Early exit when we hit 99: 

if num1 == '9' and num2 == '9':
    return 99

Can't do better than 99, so stop searching.

Handle last digit separately:

The last digit can only ever be a candidate for num2, never num1 (there's nothing after it). By processing it outside the main loop, we avoid checking i != n - 1 on every single iteration: 

for digit in line[1:-1]:    # Process all except last
    # ... main logic

digit = line[-1]            # Handle last digit separately
if num2 < digit:
    num2 = digit

Combined conditions:

When updating num2, there are two cases that both result in num2 = digit:

Instead of two separate elif branches, we combine them: 

elif num1 == digit or num2 < digit:
    num2 = digit

One branch instead of two.

Part 2: Selecting 12 Digits

Part 2 is a different beast. Now we need to pick 12 digits from a 100-digit string to form the largest possible 12-digit number. With 200 lines of input, efficiency matters.

Instead of trying every possible combination of 12 digits (which would be insane. C(100, 12) is astronomical! (Further down, I'll explain why. For now, just trust me.)), we use a greedy approach: pick the best digit at each step, left to right.

The Greedy Insight

To maximize a number, you want the leftmost digit to be as big as possible. Then the second digit. Then the third. So we just greedily pick the max each time.

But we can't just pick from anywhere:

The Algorithm

  1. For each of the k digits we need to pick, figure out the valid search window. The window is [start, end] where:
    • start = position right after our previous pick (or 0 for the first pick)
    • end = n - (k - i), where i is how many digits we've already picked, and n is the total number of digits.
    Why this formula? We still need (k - i) digits after this pick. So the latest we can pick from is position n - (k - i), leaving exactly enough room for the remaining digits.
  2. Find the maximum digit in that window and lock it in. Move our start position past where we picked.
  3. Repeat until we have k digits.

Worked Example

Here's an example from the test data: "234234234234278" with k=12 (length n=15).

The string has 15 digits, but we only want 12. So we're dropping 3 digits. Which 3 do we drop to get the biggest number? Let's walk through it. 

position:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
digit:     2  3  4  2  3  4  2  3  4  2  3  4  2  7  8

i=0: Picking digit 1 of 12. We still need 12 digits after this. That means we can't pick past position 15 - 12 = 3 (or we'd run out of room). Search window [0, 3]: '2', '3', '4', '2' Best choice: '4' at position 2 Result so far: "4"

i=1: Picking digit 2 of 12. We still need 11 more. Start after position 2, so start = 3. Can't pick past position 15 - 11 = 4. Search window [3, 4]: '2', '3' Best choice: '3' at position 4 Result so far: "43"

i=2: Picking digit 3 of 12. We still need 10 more. start = 5, can't pick past 15 - 10 = 5. Search window [5, 5]: just '4' No choice here, take '4'. Result so far: "434"

From here on, the window is always size 1 (start == end), so we just take each remaining digit in order: '2', '3', '4', '2', '3', '4', '2', '7', '8'.

Final result: "434234234278"

Notice: we skipped the '2' at position 0, '3' at position 1, and '2' at position 3. Those were the "worst" digits we could afford to drop while maximizing the result.

One More Optimization

If we find a '9' in the window, we can stop searching immediately. Can't do better than 9, so why keep looking? 

for j in range(start, end + 1):
    if line[j] > max_char:
        max_char = line[j]
        max_pos = j
        if max_char == '9':
            break

Time Complexity

This picks k digits in O(n × k) worst case, instead of checking all C(n, k) combinations. For n=100 and k=12, that's 1,200 operations vs... a lot. Way faster.

For those who are curious, C(n, k) is the binomial coefficient, which is calculated as n! / (k! × (n - k)!).

In this case, C(100, 12) = 1,731,030,945,644,000,000.

That's a lot of operations.

Lessons Learned

Python's performance intuition is often wrong. Inlining functions made things slower. List comprehensions beat manual loops. Always benchmark.

Character comparison is free. '5' < '7' works in Python, and it's faster than int('5') < int('7'). Only convert when you actually need the numeric value.

Iterate over slices, not indices. for x in line[1:-1] is faster than for i in range(1, n-1) because you avoid range object creation and repeated indexing.

The 99 early exit matters. When you know the answer can't get better, stop computing.

Greedy works when order is constrained. When you can't rearrange, picking the best available option at each step often gives the optimal result.

From 3.2ms to 1.3ms. A 2.5x speedup from micro-optimizations alone. And yes, I did beat Levi's 1.4ms. By 0.1ms, but it counts.

On to Day 4.