Advent of Code 2025 - Day 3: Lobby

Day 3 was about powering an escalator using batteries. Each battery bank is a string of digits, and the goal is to select specific digits to form the largest possible number. Part 1 was straightforward. Part 2… took some work.

Part 1: Two Batteries

The task: from each string of digits, pick exactly two to form the largest possible two-digit number. For example, from 811111111111119, you’d pick the 8 and 9 to get 89.

My first instinct was to find the largest digit, split the string at that index, then find the largest digit in what remained. But this broke immediately on 811111111111119 - it would find 9, split to 81111111111111 and 9, then find 9 again, giving 99 instead of 89.

Then I thought: regex! Maybe I could use \b\d{2}\b to find two-digit numbers and pick the largest. But that’s not how the problem works - you’re picking individual batteries, not consecutive pairs.

Back to basics. Find the largest digit, but skip the last one (since we need a second digit after it). Then find the largest digit in everything after the first one’s position. Special case: if the first digit is second-to-last, the next digit must be the last one.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def part1():
    score = 0
    nums = loadFile(input_f)
    
    for n in nums:
        max_nums = 0
        max_idx = 0
        for i in range(0, len(n)-1):  # Skip last digit
            if int(n[i]) > max_nums:
                max_nums = int(n[i])
                max_idx = i
        
        max2_nums = 0
        
        if max_idx+2 == len(n):  # Special case: first digit is second-to-last
            score += int(str(max_nums) + str(n[max_idx+1]))
        else:
            for i in range(max_idx+1, len(n)):
                if int(n[i]) > max2_nums:
                    max2_nums = int(n[i])
            
            score += int(str(max_nums) + str(max2_nums))
    
    return score

First try. Done.

Part 2: Twelve Batteries - The Long Road

Now we need to pick 12 digits instead of 2. This is where things got complicated.

Attempt 1: Loop the Part 1 Logic

Just do the Part 1 approach 12 times instead of 2. Didn’t work - the greedy approach of always taking the largest available digit doesn’t account for what comes later.

Attempt 2: Find Largest, Skip Used Indices

Find the largest digit, mark its index as used, then find the next largest (skipping used indices). Repeat 12 times. The problem: for 234234234234278, this finds digits from left to right, giving you 234... at the start instead of 434....

Attempt 3: Reverse the Search

Same as attempt 2, but scan from right to left. For 234234234234278, this gave 343434234278 instead of 434234234278. Still wrong - you need to select digits in their original order, just skip certain ones.

Attempt 4: Pop from List

Find the largest, pop it from the list, repeat. Gave 342234434478 for the test case. The fundamental issue remained: greedy selection doesn’t work when later digits matter.

Attempt 5: Track Indices with Reversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

n = list2int(list(n))
index = []
for i in range(0,12):
    max_num = 0
    max_index = 0
    for jdx, j in reversed(list(enumerate(n))):
        if j > max_num:
            if jdx not in index:
                max_num = j
                max_index = jdx
    index.append(max_index)

Still gave 343434234278. The problem persisted.

Attempt 6: Remove Smallest Instead

Maybe work backwards - find the smallest digits and remove them until 12 remain? Nope.

Attempt 7: Window-Based Lookahead

1
2
3
4
5
6
7
8
9

number = ''
left = 12
for i in range(0, len(n)):
    window = n[i+1:13]
    
    if n[i] > max(window) and left > 0:
        number += str(n[i]) 
        left -= 1
    # ... more conditions

Got closer, but couldn’t get the exit conditions right. The logic was getting messy.

The Breakthrough: Skip Budget

The key insight: think in terms of a “skip budget.”

• You have len(n) - 12 digits you can afford to skip
• At each position, look at a “window” of the next can_skip + 1 digits
• If the current digit is >= the max in the window, take it
• Otherwise, skip it (decrement your skip budget)

This works because it’s greedy with lookahead. You take a digit if it’s at least as good as anything you could get by skipping it.

The Final Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def part2(): 
    score = 0
    nums = loadFile(input_f)
    
    for n in nums:
        n = list2int(list(n))
        
        pos = 0
        filled = 0
        left = len(n)
        can_skip = left - 12
        number = ''
        
        while filled < 12:
            current = n[pos]
            window = n[pos:pos+can_skip+1]
            
            if current >= max(window):
                number += str(current)
                pos += 1
                filled += 1
            else:
                pos += 1
                can_skip -= 1
        
        score += int(number)
    return score

The window is n[pos:pos+can_skip+1] - it includes the current position plus the next can_skip positions. If the current digit is >= anything in that window, it’s safe to take it. Otherwise, skip it and reduce the budget.

This worked on the example. Then it worked on the input on the third submission (had a couple of condition adjustments).

The Lesson

Part 2 was a reminder that greedy algorithms are subtle. “Always pick the biggest available” doesn’t work when order matters and you can’t rearrange. The solution needed lookahead - specifically, knowing whether skipping now would give you something better later.

The skip budget framing made the algorithm click. Instead of thinking “which 12 to keep,” think “which 3 to skip” (for a 15-digit string). That shifts the perspective from selection to optimization: use your skips wisely to avoid taking digits that would block better ones later.

Six stars total. Part 2 took some iteration, but that’s what makes it satisfying when it finally works.