Rust

Seeing some of the other solutions in this thread, there are definitely simpler (and probably still faster) solutions possible, but I first sorted the bank by the highest batteries (keeping the index information) and then used a recursive greedy algorithm to find the largest battery that still follows the index order.

View on github

fn part1(input: String) {
    let mut sum = 0;
    'banks: for l in input.lines() {
        let mut sorted: Vec<(usize, u32)> = l
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .enumerate()
            .collect();
        sorted.sort_by(|(_, a), (_, b)| a.cmp(b).reverse());
        for (idx, first) in &sorted {
            for (id2, second) in &sorted {
                if id2 > idx {
                    sum += first * 10 + second;
                    continue 'banks;
                }
            }
        }
    }
    println!("{sum}");
}

// Recursive implementation of greedy algorithm.
// Returns Vec of length 12 if a result was found, guaranteed to be optimal.
// If there is no solution with the input, a shorter Vec is returned.
fn recursive(bank: &[(usize, u32)], mut cur: Vec<(usize, u32)>) -> Vec<(usize, u32)> {
    let pos = cur.last().unwrap().0;
    for &(idx, e) in bank.iter().filter(|(idx, _)| *idx > pos) {
        cur.push((idx, e));
        if cur.len() == 12 {
            // Recursion anchor: We have filled all 12 spots and therefore found
            // the best solution
            return cur;
        }
        // Recurse
        cur = recursive(bank, cur);
        if cur.len() == 12 {
            // Result found
            return cur;
        }
        // Nothing found, try next in this position
        cur.pop();
    }
    // Unsuccessful search with given inputs
    cur
}

fn part2(input: String) {
    let mut sum = 0;
    'banks: for l in input.lines() {
        let mut sorted: Vec<(usize, u32)> = l
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .enumerate()
            .collect();
        sorted.sort_by(|(_, a), (_, b)| a.cmp(b).reverse());
        let mut cur: Vec<(usize, u32)> = Vec::with_capacity(12);
        for &(idx, first) in &sorted {
            cur.push((idx, first));
            cur = recursive(&sorted, cur);
            if cur.len() == 12 {
                let num = cur.iter().fold(0u64, |acc, e| acc * 10 + e.1 as u64);
                sum += num;
                continue 'banks;
            }
            cur.pop();
        }
    }
    println!("{sum}");
}

util::aoc_main!();