2025 Day 2 - Finding the biggest numbers

This looks deceptively simple at first glace. We're being given a bank of battery cells, and we want to find the pair that gives us the highest possible number.

My instinct is that we just search from left to right for the biggest number, make that the first, and then from left to right for the second biggest number. In our test data, we have 987654321111111, where we'd find the 9 first, and the 8 second for 98, 811111111111119, which is trickier, we need to know that since the 9 can't have anything higher than it, we need to select the 8 and then the 9 for 89.

But I was thinking about this in my head and thought that we need some test data with some bad cases to ensure our algorithm works, but I can't think of anything that doesn't look a lot like that 89 case.

There's an O(n2) way to do this, in which we search through the list for our first digit and for each potential first digit, we search through all digits to the right to make a pair, and then test the total value. It's actually slightly faster than O(n2) because each sub search is slightly smaller than the one before, but it's defintiely not the most efficient search.

But it's a good start, and should be fairly simple to implement as we don't need to store any other information, so we can just form the numbers, put them into a list and find the biggest.

fn find_largest_pair(line: &Vec<u32>) -> u32 {
    line.iter()
        .enumerate()
        .map(
            |(pivot, first)| match line.split_at(pivot + 1).1.iter().max() {
                Some(value) => first * 10 + value,
                None => 0,
            },
        )
        .max()
        .unwrap()
}

This is a bit ugly, mostly because line.split_at gives us an empty string on the right of the last digit, so we need to handle the fact that max will return a None.

But it works, so lets try it.

We need to just take the lines, turn them into vectors of u32's, and then sum the total

pub fn calculate_part1(input: &str) -> usize {
    input
        .lines()
        .map(|line| find_largest_pair(&line.chars().map(|c| c.to_digit(10).unwrap()).collect()))
        .sum::<u32>() as usize
}