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.
17pub fn parse(input: &str) -> Vec<&str> {
18 input.lines().collect()
19}
20
21pub fn part1(input: &[&str]) -> u64 {
22 solve::<2>(input)
23}
24
25pub fn part2(input: &[&str]) -> u64 {
26 solve::<12>(input)
27}
28
29fn solve<const N: usize>(input: &[&str]) -> u64 {
30 let mut batteries = [0; N];
31
32 input
33 .iter()
34 .map(|&bank| {
35 // Start with enough batteries to make the bank, taken from the right of the input.
36 let end = bank.len() - N;
37 batteries.copy_from_slice(&bank.as_bytes()[end..]);
38
39 // Scan from right to left, bubbling up any battery greater than the start of the bank.
40 for mut next in bank[..end].bytes().rev() {
41 for battery in &mut batteries {
42 if next < *battery {
43 break;
44 }
45 (*battery, next) = (next, *battery);
46 }
47 }
48
49 batteries.iter().fold(0, |joltage, &b| 10 * joltage + u64::from(b - b'0'))
50 })
51 .sum()
52}