Advent of Code 2025 - Day 3

Useful Links

Concepts and Packages Demonstrated

Slicing List Comprehensions Greedy Algorithms

Problem Intro

We are in a lobby with offline elevators and a broken escalator. To fix the escalator, we need to power it using banks of batteries. Each bank corresponds to a line of input, and we need to select specific batteries to produce the maximum possible “joltage”.

The input looks like this:

987654321111111
811111111111119
234234234234278
818181911112111

Part 1

Find the largest possible joltage each bank can produce by turning on exactly two batteries.

The joltage is formed by concatenating the digits of the selected batteries. For example, if we pick a battery with 9 and then one with 8, the joltage is 98. We must pick them in the order they appear in the bank.

Solution

The core of the problem is to find the largest number we can form by picking k digits from the string, maintaining their relative order. Since we want to maximize the resulting number, and the number of digits is fixed, we should try to make the most significant digits as large as possible.

This suggests a greedy approach. For the first digit, we want the largest possible number available in the bank, provided that picking it leaves enough remaining digits to satisfy the requirement of picking k-1 more digits.

Greedy Selection

We can iterate through the required number of batteries. For each step, we look at the available slice of the bank string:

Start: Immediately after the index of the previously selected battery (or 0 for the first one).
End: We must stop early enough to leave room for the remaining batteries. If we need r more batteries, we cannot pick a digit from the last r-1 positions.

Here’s how we can implement this logic:

def part1(data: list[str], num_batteries: int = 2):
    max_joltages = []
    for bank in data:
        bank_len = len(bank)
        # Convert to ints for easier numerical comparison
        bank_joltages = [int(joltage) for joltage in bank]
        
        batteries_remaining = num_batteries
        batteries_enabled = []
        
        # Initialise where we start looking for the batteries in the bank.
        bank_index = -1 
        
        while batteries_remaining > 0:
            # Find the max digit in the remaining available slice.
            # The slice starts after the last selected index.
            # The slice ends early enough to leave room for the remaining required batteries.
            search_slice = bank_joltages[bank_index+1 : bank_len - batteries_remaining + 1]
            battery_joltage = max(search_slice)
            
            # Find the position of this max digit in the bank (after the last selected index)
            bank_index = bank_joltages.index(battery_joltage, bank_index+1)
            
            batteries_enabled.append(battery_joltage)
            batteries_remaining -= 1

        # Concatenate the selected digits to form the final joltage number
        max_joltages.append(int("".join(str(battery) for battery in batteries_enabled)))

    return sum(max_joltages)

Key Concepts

List Comprehensions

We convert the input string (e.g., "98765") into a list of integers ([9, 8, 7, 6, 5]) using a list comprehension:

bank_joltages = [int(joltage) for joltage in bank]

This iterates over every character in bank, converts it to an int, and collects the results in a new list. This makes numerical comparisons (like finding max()) straightforward.

Slicing

To find the best next digit, we need to look at a specific subset of the bank. We use Python’s slicing syntax [start:end]:

search_slice = bank_joltages[bank_index+1 : bank_len - batteries_remaining + 1]

Start (bank_index + 1): We must move forward in the bank. We start searching immediately after the position of the last battery we picked.
End (bank_len - batteries_remaining + 1): We cannot pick a digit if it doesn’t leave enough room for the rest of the batteries we need. For example, if we need 2 more batteries, we can’t pick the very last digit in the bank, because there would be nothing left for the final battery.

Finding the Index

Once we know the maximum value in our slice (battery_joltage), we need to know where it is in the original bank so we can update our bank_index for the next iteration.

bank_index = bank_joltages.index(battery_joltage, bank_index+1)

The index(value, start) method searches for value starting from start. This is crucial: the same digit might appear multiple times. We must ensure we find the instance that is after our previous selection.

String Join

After collecting our selected digits (as integers) in batteries_enabled, we need to combine them into a single number.

int("".join(str(battery) for battery in batteries_enabled))

str(battery) converts each integer back to a string.
"".join(...) concatenates them all together with no separator.
int(...) turns the resulting string (e.g., "98") back into the integer 98.

Part 2

Find the largest possible joltage by turning on exactly twelve batteries within each bank.

The logic remains exactly the same! Our greedy approach works for any number of batteries. We simply call our function with num_batteries=12.

Results

The output looks like this:

DEBUG    06:58:26.120 bank=987654321111111                                                                             
DEBUG    06:58:26.121 bank=811111111111119                                                                             
DEBUG    06:58:26.121 bank=234234234234278                                                                             
DEBUG    06:58:26.121 bank=818181911112111                                                                             
DEBUG    06:58:26.122 max_joltages=[98, 89, 78, 92]                                                                    
INFO     06:58:26.122 part1 tests passed                                                                               
INFO     06:58:26.124 Part 1 soln=357                                                                                
INFO     06:58:26.124 Execution time: 0.001 seconds                                                                    
DEBUG    06:58:26.124 bank=987654321111111                                                                             
DEBUG    06:58:26.124 bank=811111111111119                                                                             
DEBUG    06:58:26.125 bank=234234234234278                                                                             
DEBUG    06:58:26.125 bank=818181911112111                                                                             
DEBUG    06:58:26.125 max_joltages=[987654321111, 811111111119, 434234234278, 888911112111]                            
INFO     06:58:26.126 part2 tests passed                                                                               
INFO     06:58:26.128 Part 2 soln=3121910778619                                                                      
INFO     06:58:26.128 Execution time: 0.002 seconds

‹›