Advent of Code is an annual set of daily programming challenges every December.
Read the challenge for 2025, Day 3
Problem
In this problem, we need to find the sum of maximum joltages for many banks of batteries. Each bank is represented as a line of single digits. The joltage for a bank is determined by selecting batteries to activate and concatenating their digits in order—you cannot rearrange them. In part one, we select 2 batteries per bank. In part 2, we must select 12 batteries per bank.
For example, from the bank 4983, selecting the batteries at positions with digits 9 and 8 produces a joltage of 98. The challenge is to find the maximum possible joltage for each bank.
My Solution
The input data represents each bank as a line of digits.
987654321111111
811111111111119
234234234234278
818181911112111 I knew that I’d want to iterate over the batteries in a bank easily and would need to do numeric comparisons often, so I parsed the data into a Vec<Vec<u32>> type.
fn parse_input(input: &str) -> Result<Vec<Vec<u32>>, anyhow::Error> {
input.lines().map(parse_line).collect()
}
fn parse_line(line: &str) -> Result<Vec<u32>, anyhow::Error> {
Ok(line.chars().map(|d| d.to_digit(10).unwrap()).collect())
}For part one, I needed to find the two digits in the list, that when concatenated together in their original order produce the largest number.
When I started trying to solve this problem, the “naive solution” came to mind pretty quickly. I can find every possible joltage in the bank and take the highest one. Even though I knew this wasn’t performant, I thought it was a fine place to start and see if inspiration for a better solution struck.
To find every combination of joltages for selecting 2 batteries in the bank, I can run two “cursors” over the digits. With a bank 4983, I could find all possible joltages (and the max joltage of 98) by following the process below.
4983
^^ 49 Start with both cursors in their leftmost positions.
^ ^ 48 Move the second cursor rightwards...
^ ^ 43 ...until it hits the end of the list.
^^ 98 Then start with both cursors one to the right of their original positions
^ ^ 93 and repeat the process of moving the second cursor rightwards.
^^ 83 Repeat until both cursors are at the end of the list. This extends out to a bank of any size. However it’s not very efficient. What I am doing here is finding all combinations. The number of combinations for a given set, depending on how many items you choose from the set, is called the choose function.
n choose k = (n!)/(k! * (n-k)!) In the above example, we did 4 choose 2 which gave us 6 combinations.
4 choose 2 = (4!)/(2! * (4-2)!) = (24)/(2 * 2) = 24/4 = 6 For the problem, we have 15 batteries and we need to choose 2 of them, so we have to check 15 choose 2 = 105 combinations per bank.
Despite its algorithmic inefficiency, I coded out this solution. Instead of storing every combination, I only store the largest combination I have observed and replace it if I find a larger combination. This serves the purpose of finding the maximum with out having to keep a list of 105 combinations for each bank.
fn part_1(banks: &[Vec<u64>]) -> u64 {
let mut total_joltage = 0;
for bank in banks {
let mut max_joltage = 0;
for lh in 0..bank.len() - 1 {
for rh in lh + 1..bank.len() {
let joltage = bank[lh] * 10 + bank[rh];
if joltage > max_joltage {
max_joltage = joltage;
}
}
}
total_joltage += max_joltage
}
total_joltage
} This very quickly solved part one. It solved the example test. Then it solved the full puzzle input in 242µs. That’s efficient enough for me.
But it’s not efficient enough for part two. In part two I have to choose 12 batteries. With my naive solution, this would require checking 455 combinations per bank.
15 choose 12 = (15!)/(12! * 3!) = (15 * 14 * 13)/(3 * 2 * 1) = 2730/6 = 455 This can be brute forced by creating 12 nested for loops or doing recursive function calls. The nested for loops just reek of inelegance. But with the recursive function calls, to update the max_joltage value, I would have to have shared mutable state between recursive function calls. No thanks.
I did struggle with this second part for awhile. I even wrote the 12 nested for loop solution as a joke. I wrote out choosing the max joltage using pen and paper using whatever way felt most natural to me. What I ended up discovering was that to maximize the resulting number, I should greedily select the highest digit available at each position, working from left to right. The correct battery for the max joltage was always the max digit in a certain sub-set of the list. Using the 4-battery bank example I wrote out in part one, here is how we’d solve it if we were picking 2 batteries again.
4983 We know that the first digit cannot include the final number (3)
498 so we remove it to select the largest digit from the first three values.
^ 9 It's 9. This number is at the second index of the list.
83 | We now know that the second digit must be to the right of the first.
^ 98 As it's the final digit it can include the final number.
We find the highest digit in this remaining list I wrote this solution for the bank choosing 12 batteries.
// Calculates max joltage for a bank of batteries, selecting 12 batteries.
fn calculate_max_joltage(bank: &[u32]) -> u64 {
// The starting index for searching the next battery
let mut index = 0;
// With each highest digit, the max_joltage will be incremented by that digit * 10^place
// where place counts down from 11 to 0.
let mut max_joltage = 0;
// Iterate from 11 to 0, counting down.
for place in (0..12).rev() {
// Get the index of the maximum value and what that value is.
let (idx, m) = max_with_index(&bank[index..bank.len() - place]).unwrap();
// Increment the index by the location of the max digit + 1.
index += idx + 1;
// Increment `max_joltage` by the max digit * 10^place.
max_joltage += m as u64 * 10_u64.pow(place as u32);
}
max_joltage
}
// Returns the index and the value of the maximum number
fn max_with_index(nums: &[u32]) -> Option<(usize, u32)> {
nums.iter()
.enumerate()
.max_by_key(|(_, num)| *num)
.map(|(index, value)| (index, *value))
}Running this on the example case gave me a very funny result.
assertion `left == right` failed
left: 3114910778619
right: 3121910778619This was suspiciously close to the correct answer from the example, but just off by a little.
I wrote another test to check the max joltage for each bank.
const TEST_INPUT: &str = "987654321111111
811111111111119
234234234234278
818181911112111";
#[test]
fn test_calculate_max_joltage() {
let banks = parse_input(TEST_INPUT).unwrap();
let max_js: Vec<u64> = vec![987654321111, 811111111119, 434234234278, 888911112111];
for (bank, max_joltage) in banks.iter().zip(max_js) {
assert_eq!(
max_joltage,
calculate_max_joltage(bank, max_joltage.to_string().len())
);
}
}This gave me the culprit.
assertion `left == right` failed
left: 888911112111
right: 881911112111 For the bank 818181911112111, my solution was giving 881911112111 instead of 888911112111. It was skipping over one of the 8s in the beginning of the bank.
This is a pretty subtle bug, but reading the doc comment for max_by_key explains it.
Returns the element that gives the maximum value from the specified function.
If several elements are equally maximum, the last element is returned. If the iterator is empty, [
None] is returned.# Examples
let a = [-3_i32, 0, 1, 5, -10]; assert_eq!(a.into_iter().max_by_key(|x| x.abs()).unwrap(), -10);
The function is returning the last max element it finds. So when it scanned the first two 8s to find the max between them, it returned the second of the two, skipping the first.
I needed a max function that returns the first max element it finds. It still needs to iterate over the whole list, but it needs to return the first instance of the max that it finds. I had to look this up. This can be accomplished using max_by and comparing the values and their indices. By comparing indices in reverse order when values are equal, we ensure the first occurrence of the maximum is selected.
fn max_with_index(nums: &[u32]) -> Option<(usize, u32)> {
nums.iter()
.enumerate()
.max_by(|(i1, v1), (i2, v2)| v1.cmp(v2).then(i2.cmp(i1)))
.map(|(index, value)| (index, *value))
} With this fix, the solution worked perfectly. I generalized this approach and used it for part one as well. With a release build, my solution ran in 186.38µs on my MacBook Pro M2 Max.
2025-12-05T06:14:23.414Z DEBUG [advent_2025::day_03] Day 3
16854
167526011932478
2025-12-05T06:14:23.414Z DEBUG [advent_2025::day_03] Duration 186.38µsThings I Learned
The subtle difference between max_by_key and max_by in Rust caught me by surprise. When using max_by_key, if multiple elements have the same key value, it returns the last one encountered. This is documented behavior, but easy to overlook.
For this problem, I needed the first maximum element to maintain the correct digit order. The solution was to use max_by instead, comparing both the values and their indices:
.max_by(|(i1, v1), (i2, v2)| v1.cmp(v2).then(i2.cmp(i1))) The key insight here is the .then(i2.cmp(i1)) part. When values are equal (v1.cmp(v2) returns Equal), we compare indices in reverse order (i2.cmp(i1) instead of i1.cmp(i2)). This tells Rust to prefer the element with the smaller index when values tie, effectively selecting the first occurrence.
I also learned to appreciate the value of starting with a naive solution. My brute-force approach for part one solved the problem in microseconds and gave me confidence in my understanding of the problem before optimizing for part two. Sometimes “good enough” really is good enough.