Problem

Read it here tl;dr — You have banks of batteries, each represented as a line of digits (1-9). Pick a specific number of batteries to turn on. The joltage produced is the number formed by those digits (in left-to-right order). Maximize the joltage from each bank and sum them.

Part 1: Pick exactly 2 batteries per bank.

Bank	Best Pick	Joltage
987654321111111	positions 1,2	98
811111111111119	positions 1,15	89
234234234234278	positions 14,15	78
818181911112111	positions 7,12	92

Part 1 Total: 98 + 89 + 78 + 92 = 357

Part 2: Pick exactly 12 batteries per bank.

Bank	Strategy	Joltage
987654321111111	drop some 1s at the end	987654321111
811111111111119	drop some 1s in the middle	811111111119
234234234234278	drop a 2, a 3, and another 2	434234234278
818181911112111	drop some 1s near the front	888911112111

Part 2 Total: 987654321111 + 811111111119 + 434234234278 + 888911112111 = 3121910778619

Key insight: You can’t rearrange — digits stay in order. To maximize, greedily pick the largest available digit for each position from left to right, ensuring you leave enough digits remaining to fill the rest.

---

My Solution (Handcrafted)

Part 1: Single Pass from the Back

Initially I thought about using a simple nested loop, but that would be O(n²). I wanted to challenge myself to solve it in O(n).

The trick is to iterate from the back while tracking three things:

pub fn solve_1(filename: &str) -> u32 {
    let input = Self::read_input(filename);

    let mut joltages = Vec::new();
    for line in input {
        let sequence = line
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .collect::<Vec<u32>>();

        // loop from the back and find the largest two digits
        let mut first_digit = sequence[sequence.len() - 2];
        let mut second_digit = sequence[sequence.len() - 1];
        let mut second_digit_candidate = second_digit;

        for &c in sequence.iter().rev().skip(2) {
            if c >= first_digit {
                second_digit_candidate = max(second_digit_candidate, first_digit);
                second_digit = max(second_digit_candidate, second_digit);
                first_digit = c;
                continue;
            }

            if c >= second_digit_candidate {
                second_digit_candidate = c;
            }
        }

        let joltage = first_digit * 10 + second_digit;
        joltages.push(joltage);
    }

    return joltages.iter().sum();
}

The logic:

• first_digit — the best candidate for the tens place so far
• second_digit — the best candidate for the ones place (must come after first_digit)
• second_digit_candidate — digits we’ve seen that could become second_digit if we find a better first_digit

When we find a digit >= first_digit, the old first_digit becomes a candidate for second_digit. We propagate the best candidates forward as we scan.

Part 2: Tracking 12 Digits with Insertion

For Part 2, I couldn’t use the same three-variable trick — tracking 12 positions would be a nightmare. I tried a shifting approach but inserting at the head of a vector was awkward.

My final approach: start with the last 12 digits, then scan backwards and try to improve:

pub fn solve_2(filename: &str) -> u64 {
    let input = Self::read_input(filename);

    let mut joltages: Vec<u64> = Vec::new();
    for line in input {
        let sequence = line
            .chars()
            .map(|c| c.to_digit(10).unwrap() as u64)
            .collect::<Vec<u64>>();

        let mut digits: Vec<u64> = sequence
            .iter()
            .skip(sequence.len() - 12)
            .map(|x| *x)
            .collect();

        // start from the back and keep iterating
        for (i, &c) in sequence.iter().enumerate().rev().skip(12) {
            if c >= digits[0] {
                digits.insert(0, c);
                // shifting the digits - remove first occurrence of a "bad" digit
                for i in 1..digits.len() {
                    if digits[i] > digits[i - 1] {
                        digits.remove(i - 1);
                        break;
                    }
                }
            }
        }

        let joltage = digits.iter().take(12).fold(0, |acc, x| acc * 10 + x);
        joltages.push(joltage);
    }

    return joltages.iter().map(|x| *x).sum();
}

The idea: If I find a digit larger than my current first digit, insert it at the front. Then scan through and remove the first digit that breaks the “should be as large as possible” property — specifically, when a digit is larger than the one before it, the one before it is the weak link.

This works, but it’s a bit convoluted and the nested loop makes it harder to reason about correctness.

---

Gemini’s Solution

Part 1: Brute Force (O(n²))

Gemini went with the straightforward nested loop:

pub fn solve_1(filename: &str) -> i32 {
    // ... file reading ...

    for line in content.lines() {
        let digits: Vec<u32> = line.chars().filter_map(|c| c.to_digit(10)).collect();

        let mut max_bank_joltage = 0;

        // Iterate through all pairs to find the maximum
        for i in 0..digits.len() {
            for j in (i + 1)..digits.len() {
                let joltage = digits[i] * 10 + digits[j];
                if joltage > max_bank_joltage {
                    max_bank_joltage = joltage;
                }
            }
        }

        total_output_joltage += max_bank_joltage as i32;
    }

    total_output_joltage
}

Simple and correct. For Part 1 where we only pick 2 digits, the O(n²) complexity is totally fine — the input isn’t that large.

Part 2: The Monotonic Stack

This is where Gemini’s solution really shines. It recognized this as a classic “remove k digits to maximize number” problem and used a monotonic stack:

pub fn solve_2(filename: &str) -> i64 {
    // ... file reading ...

    for line in content.lines() {
        let digits: Vec<u32> = line.chars().filter_map(|c| c.to_digit(10)).collect();

        let to_remove = digits.len() - 12;
        let mut drops_remaining = to_remove;
        let mut stack: Vec<u32> = Vec::new();

        for &digit in &digits {
            // While we can still drop digits, and the current digit is larger
            // than the last one we picked, discard the smaller one
            while drops_remaining > 0 && !stack.is_empty() && *stack.last().unwrap() < digit {
                stack.pop();
                drops_remaining -= 1;
            }
            stack.push(digit);
        }

        // Truncate if we haven't dropped enough
        stack.truncate(12);

        let mut max_bank_joltage: i64 = 0;
        for d in stack {
            max_bank_joltage = max_bank_joltage * 10 + d as i64;
        }

        total_output_joltage += max_bank_joltage;
    }

    total_output_joltage
}

How it works:

1. Frame the problem as “remove (len - 12) digits to maximize the result”
2. Iterate through each digit from left to right
3. Before adding a new digit to the stack, pop any smaller digits from the top (if we still have drops remaining)
4. This ensures we always keep the largest possible prefix
5. If the sequence was already descending (nothing got popped), truncate at the end

This is O(n) and much cleaner than my approach. The stack naturally handles the “which digit to remove” logic that I was doing manually with nested loops.

---

Comparison

Aspect	My Solution	Gemini’s Solution
Part 1	O(n) single pass — clear win	O(n²) nested loop — lazy
Part 2	O(n) backwards scan with tracking	O(n) monotonic stack
Approach	Custom logic, thinks from scratch	Applies known pattern
Result	Both correct, both fast	Both correct, both fast

---

Reflection

Part 1: I won this one. Gemini went with the brute force O(n²) approach while I took the time to figure out a proper O(n) solution. Yes, O(n²) would have worked fine for this input size, but if you’re going to solve a problem, why not solve it well?

Part 2: Two different approaches, both O(n), both correct. Gemini used a monotonic stack which is a known pattern for “remove k digits” problems. I came up with my own approach — iterate backwards, insert at front when beneficial, then clean up the sequence. Different mental models, same result.

The stack approach is more “textbook” but my approach worked just fine. Sometimes rolling your own logic is satisfying even when a standard pattern exists.

Time spent: ~45 minutes