Advent of Code 2025 - Day 3: Maximizing Battery Joltage

I recently tackled Day 3 of Advent of Code 2025, and it turned out to be an interesting optimization problem disguised as a battery puzzle. The premise was simple: help restore power to an offline escalator by maximizing the joltage output from battery banks. But the solution required some clever thinking about greedy algorithms and optimization strategies.

Understanding the Problem

We're given multiple banks of batteries, where each battery is labeled with a joltage rating from 1 to 9. The puzzle input looks something like this:

987654321111111
811111111111119
234234234234278
818181911112111

Each line represents a battery bank, and we need to select specific batteries to form numbers that maximize joltage output.

Part 1: Select exactly 2 batteries from each bank to create the largest possible two-digit number. The batteries must maintain their original order (no rearranging).

Part 2: Crank it up to 12 batteries per bank to create twelve-digit numbers.

The final answer is the sum of maximum joltages across all banks.

Part 1: The Two-Battery Problem

Initial Thoughts

My first reaction was straightforward: iterate through all possible pairs of batteries and pick the maximum. But with potentially long battery banks, this O(n²) approach felt inefficient. There had to be a better way.

The Key Insight

Then it hit me: for a two-digit number, we want the largest digit as far left as possible. The tens place contributes 10x more than the ones place, so maximizing the left digit is crucial.

This led me to think about the problem differently. For any split point in the battery bank, I could form a two-digit number using:

• The maximum digit from the left section (tens place)
• The maximum digit from the right section (ones place)

The Solution

fn compute_joltage_1(battery_banks: &Vec<Vec<u32>>) -> u64 {
    let mut total_joltage = 0;

    for battery_bank in battery_banks {
        let n = battery_bank.len();
        let mut pre_max = vec![0; n];
        let mut post_max = vec![0; n];

        // Precompute maximum from left
        pre_max[0] = battery_bank[0];
        for i in 1..n {
            pre_max[i] = max(pre_max[i-1], battery_bank[i]);
        }

        // Precompute maximum from right
        post_max[n-1] = battery_bank[n-1];
        for i in 1..n {
            post_max[n-i-1] = max(post_max[n-i], battery_bank[n-i-1]);
        }

        // Find the best split point
        let mut joltage = 0;
        for i in 0..n-1 {
            joltage = max(joltage, 10 * pre_max[i] as u64 + post_max[i+1] as u64);
        }

        total_joltage += joltage;
    }

    total_joltage
}

The strategy:

1. Build a pre_max array where pre_max[i] stores the maximum battery value from index 0 to i
2. Build a post_max array where post_max[i] stores the maximum battery value from index i to the end
3. For each possible split point, compute the two-digit number and track the maximum

This reduces the complexity to O(n) with a single pass to build the arrays and another to find the optimal split. Much better!

Example Walkthrough

For the bank 987654321111111:

• pre_max = [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
• post_max = [9,8,7,6,5,4,3,2,1,1,1,1,1,1,1]
• Best split: position 0, giving us 9 * 10 + 8 = 98

Part 2: The Twelve-Battery Problem

The Challenge Escalates

Now we need to select 12 batteries instead of 2. The search space explodes exponentially, making brute force completely impractical. I needed a different approach.

Greedy Strategy

The solution came from recognizing that positional value matters enormously. A 9 in the leftmost position contributes 9 × 10¹¹, while a 9 in the rightmost position only contributes 9 × 10⁰. This massive difference means we should greedily select the largest digit possible for each position, working left to right.

But there's a constraint: we need to ensure we can still select enough batteries for the remaining positions.

The Solution

fn compute_joltage_2(battery_banks: &Vec<Vec<u32>>) -> u64 {
    let mut total_joltage: u64 = 0;

    for battery_bank in battery_banks {
        let n: usize = battery_bank.len();
        let mut dist: usize = n - 11;  // Initial search window end
        let mut pos: usize = 0;         // Current search start
        let mut joltage: u64 = 0;

        // Select 12 digits from most to least significant
        for i in (1..=12).rev() {
            let mut digit: u32 = 0;
            let end = dist;
            let start = pos;

            // Find the largest digit in the valid range
            for j in start..end {
                if battery_bank[j] > digit {
                    pos = j;
                    digit = battery_bank[j];
                }
            }

            // Add this digit's contribution
            joltage += digit as u64 * 10u64.pow((i as u32) - 1);
            pos += 1;  // Next search starts after this position
            dist += 1; // Expand search window
        }

        total_joltage += joltage;
    }

    total_joltage
}

How the Search Window Works

The clever part is managing the sliding search window:

1. First digit (position 12): Search from index 0 to n-11. This ensures we leave at least 11 batteries for the remaining positions.

2. After selecting a digit at position pos:

   • Next search starts at pos + 1 (can't reuse batteries)
   • Search window expands by 1 (we need one fewer remaining battery)

3. Continue until all 12 digits are selected

Example Walkthrough

For the bank 987654321111111:

• Position 12: Search [0, 4], pick 9 at index 0
• Position 11: Search [1, 5], pick 8 at index 1
• Position 10: Search [2, 6], pick 7 at index 2
• ...and so on

Result: 987654321111 (skipping the last few 1s)

Why This Greedy Approach Works

The greedy algorithm is optimal because of the exponential positional value difference. Consider this:

• Moving from 8 to 9 in position 12: gains 1 × 10¹¹ = 100,000,000,000
• Maximizing ALL remaining 11 positions with 9s: gains at most 9 × (10¹⁰ + ... + 10⁰) ≈ 10¹¹

The leftmost position always dominates! This means locally optimal choices (picking the largest digit available for each position) lead to the globally optimal solution.

Performance

Both solutions run in O(n × m) time, where n is the number of battery banks and m is the average bank length. The precomputation in Part 1 and the constrained greedy search in Part 2 keep everything efficient even for large inputs.

Key Takeaways

1. Precomputation saves time: Building auxiliary arrays can turn O(n²) problems into O(n) solutions
2. Greedy works when position matters: Problems with exponential positional value often yield to greedy strategies
3. Constraints guide the solution: The "must leave enough batteries" constraint was the key to implementing the greedy approach correctly

This puzzle reminded me that recognizing problem structure often beats brute force. Sometimes the best optimization is changing your perspective on the problem itself.

Full Solution

You can find my complete solution, including input parsing and testing, on GitHub:

View Full Solution on GitHub

---

Have you solved this puzzle differently? I'd love to hear about alternative approaches in the comments!