aoc/year2025/
day03.rs

1//! # Lobby
2//!
3//! The highest possible joltage is made by choosing the maximum value for the most
4//! significant digit (leaving enough batteries over to make the rest of the bank),
5//! then the maximum value for the second most significant digit and so on.
6//!
7//! One approach is to scan from left to right checking for the maximum. While the complexity is
8//! technically `O(n)` we do have to scan the same digits multiple times (up to twelve in part two).
9//!
10//! Instead, starting with enough batteries to make the bank, we scan from right to left. If we
11//! encounter a battery greater than or equal to the leading battery in the bank then we replace it.
12//! The replaced battery is then checked against the next battery, "bubbling" up from right to left
13//! just like the [infamous sorting algorithm](https://en.wikipedia.org/wiki/Bubble_sort).
14//!
15//! While the worst case complexity of bubble sort is `O(n²)`, in practice this approach is much
16//! faster due to the randomized nature of the inputs.
17use std::mem::replace;
18
19pub fn parse(input: &str) -> Vec<&str> {
20    input.lines().collect()
21}
22
23pub fn part1(input: &[&str]) -> u64 {
24    solve::<2>(input)
25}
26
27pub fn part2(input: &[&str]) -> u64 {
28    solve::<12>(input)
29}
30
31fn solve<const N: usize>(input: &[&str]) -> u64 {
32    let mut batteries = [0; N];
33
34    input
35        .iter()
36        .map(|&bank| {
37            // Start with enough batteries to make the bank, taken from the right of the input.
38            let end = bank.len() - N;
39            batteries.copy_from_slice(&bank.as_bytes()[end..]);
40
41            // Scan from right to left, bubbling up any battery greater than the start of the bank.
42            for mut next in bank[..end].bytes().rev() {
43                for battery in &mut batteries {
44                    if next < *battery {
45                        break;
46                    }
47                    next = replace(battery, next);
48                }
49            }
50
51            batteries.iter().fold(0, |joltage, &b| 10 * joltage + u64::from(b - b'0'))
52        })
53        .sum()
54}
aoc/year2025/day03.rs

aoc/year2025/
day03.rs
