Day 3: Lobby

use std::io;

fn main() {
  let mut part1 = 0;
  let mut part2 = 0;
  for line in io::stdin().lines().map(|l| l.unwrap()) {
    // The index is the number of batteries used for the given max. Index 0
    // will never be modified, but is still usefull to avoid the corner case
    // when updating index 1.
    let mut max_vals = [0; 13];
    for c in line.as_bytes() {
      let n = (c - b'0') as u64;
      // Updating in reverse, otherwise max_vals[i] would use the already updated value of
      // max_vals[i-1].
      for i in (1..13).rev() {
        max_vals[i] = max_vals[i].max(max_vals[i - 1] * 10 + n);
      }
    }
    part1 += max_vals[2];
    part2 += max_vals[12];
  }
  println!("Part 1: {}", part1);
  println!("Part 2: {}", part2);
}

Note: ?<unicode codepoint> is a funky bit of built-in syntax that gives the integer value of a unicode codepoint. For basic ascii characters, it's equivalent to C's '<character>' syntax. For example, ?a == 97.

When the puzzle input string is a bunch of digit characters that need to be parsed into a list of integers, digit_char - ?0 is a little shortcut for parsing each one.

use AdventOfCode.Solution.SharedParse

@impl true
@spec parse(String.t()) :: [[0..9]]
def parse(input) do
  input
  |> String.split()
  |> Enum.map(&for(d <- String.to_charlist(&1), do: d - ?0))
end

def part1(battery_banks) do
  Enum.sum_by(battery_banks, &max_joltage_p1/1)
end

defp max_joltage_p1(batteries, acc \\ {0, 0})

defp max_joltage_p1([], {tens, ones}), do: Integer.undigits([tens, ones])
defp max_joltage_p1([b], {tens, ones}) when b > ones, do: max_joltage_p1([], {tens, b})
defp max_joltage_p1([_b], acc), do: max_joltage_p1([], acc)
defp max_joltage_p1([b | bs], {tens, _ones}) when b > tens, do: max_joltage_p1(bs, {b, 0})
defp max_joltage_p1([b | bs], {tens, ones}) when b > ones, do: max_joltage_p1(bs, {tens, b})
defp max_joltage_p1([_b | bs], acc), do: max_joltage_p1(bs, acc)

def part1(battery_banks), do: Enum.sum_by(battery_banks, &max_joltage(&1, 2))
def part2(battery_banks), do: Enum.sum_by(battery_banks, &max_joltage(&1, 12))

defp max_joltage(batteries, num_to_activate) do
  bank_size = length(batteries)
  init_active_group = List.duplicate(0, num_to_activate)

  batteries
  # Annotate batteries with the earliest index they can occupy in the activated group
  |> Enum.with_index(fn b, i -> {b, max(num_to_activate + i - bank_size, 0)} end)
  |> Enum.reduce(init_active_group, &update_active_group/2)
  |> Integer.undigits()
end

defp update_active_group({b, min_i}, active_group) do
  {ineligible, eligible} = Enum.split(active_group, min_i)
  update_active_group(b, eligible, Enum.reverse(ineligible))
end

defp update_active_group(_b, [], acc), do: Enum.reverse(acc)

defp update_active_group(b, [active | actives], acc) when b > active,
  do: update_active_group(b, [], List.duplicate(0, length(actives)) ++ [b | acc])

defp update_active_group(b, [active | actives], acc),
  do: update_active_group(b, actives, [active | acc])

(Using the general solution--which for part 1 is a few hundred μs slower than the bespoke solution)

Name             ips        average  deviation         median         99th %
Parse         4.18 K      239.18 μs     ±3.65%      235.08 μs      261.13 μs
Part 1        2.68 K      373.56 μs    ±14.17%      370.92 μs      408.97 μs
Part 2        0.84 K     1188.87 μs     ±1.98%     1190.63 μs     1230.33 μs

Another relatively straightforward problem today. For part 1, with only 2 digits, it's a simple check to find the biggest digit (as long as it's not the last one) and pair it with the biggest digit to its right.

For part 2, it's simply a matter of expanding that to a more general solution. I chose to write it recursively—to find the biggest 12-digit number, find the biggest digit (as long as it's not in the 11-rightmost ones); then take the rest of the digits and find the biggest 11-digit number. Repeat until you're down to finding the biggest one-digit number.

There are a couple micro-optimizations I found that probably didn't change much (my solution already ran in under 1ms):

• Don't bother to parse strings as their respective numerical values. The character `'9'` still has a bigger underlying value than the character `'8'`, so comparing them will give you the same result as comparing `9` to `8`.
• There's no need to actually build your number as you go. I originally did some math to multiply the resulting digit by a power of 10 and then add the rest of the value to it, but that's not necessary. It's more efficient to just build an array of the desired characters (`['4', '3', '4', ...]`). Then only when it's finished, you parse it to a `long` for the final summation.

C# code

I eventually realized that caring about combinations at all was the wrong approach. As an example, let's say we're trying to find the maximum joltage with three batteries from the bank 482651:

1. First, find the largest battery excluding the last two, since we need two more batteries after this one. The largest battery out of 4826 is 8.
2. Next, find the largest battery that comes after our first one, but before the last in the bank, since we need one more battery after this one. The largest battery out of 2651 is 6.
3. Finally, find the largest battery that comes after our second one. The largest battery out of 51 is 5.

So, the maximum joltage is 865. I'm not sure what the time complexity of this is, but it seems pretty efficient.

Probably others arrived at something like this too, though I haven't looked at many other solutions yet.

define find_maximum_joltage(
    line: String, size: Integer, batteries: Integer
): Integer {
    var index = 0
    var joltage = 0

    do: {
        var largest = 0
        for i in index...size - batteries: {
            var battery = line[i] - '0'
            if battery > largest: {
                largest = battery
                index = i
            }
        }

        index += 1
        joltage = joltage * 10 + largest

        batteries -= 1
    } while batteries > 0

    return joltage
}

var output_joltage_two_batteries = 0
var output_joltage_twelve_batteries = 0

for line in File.read_to_string("inputs/day_03.txt").split("\n"): {
    var size = line.size()
    output_joltage_two_batteries += find_maximum_joltage(line, size, 2)
    output_joltage_twelve_batteries += find_maximum_joltage(line, size, 12)
}

print("Part 1: {}\nPart 2: {}".format(
    output_joltage_two_batteries, output_joltage_twelve_batteries
))

The first simple enough solution I could come up with was to maintain an array that keeps track of the largest K-digit number that can be formed from the given digits, from 0 to 12 digits (yes, the 0th element is always 0 but I will eat a few bytes of wasted memory to avoid weird off-by-one situations). This array starts with all 0s, but we go left to right and analyzing each new digit of the digit string to update our array, ending with an array with the true answer in the 12th element.

When we look at each new digit, we can update our array by seeing that each largest K-digit number either doesn't use the rightmost digit or it does use this rightmost digit.

If it doesn't, then the answer is unchanged, since we already knew the largest K-digit number without the rightmost digit.

If it does, then we consider what the first K-1 digits would look like, and realize that this itself is a number, in fact that it's the largest K-1 digit number that could be formed without the rightmost digit (what planning luck! We already have that in our array!)

To cover both options, we can simply take the max over these (and take care for the order of operations, since an in-place array update might destroy that "K-1 digit number" information) and repeat for all K and all the way from left to right to get the full answer.

(I will note that the kids call this algorithm strategy Dynamic Programming, and given that it has a fancy name I'm not convinced it's the simplest algorithm.)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(const vector<ll>& arr, ll len) {
	vector<ll> best(len+1,0);
	for(const auto& u: arr) {
		for(int i=len;i>0;i--) {
			best[i] = max(best[i],best[i-1]*10+u);
		}
	}
	return best[len];
}
int main() {
	string input;
	ll ans = 0;
	ll ans1 = 0;
	while(cin >> input) {
		vector<ll> digit_input;
		for(const auto& c: input) {
			digit_input.push_back(c-'0');
		}
		ans1 += solve(digit_input,2);
		ans += solve(digit_input,12);
	}
	cout << ans1 << '\n';
	cout << ans << '\n';
}

We instead observe that, for numbers with the same digit, numbers with larger first digits are larger, no matter what digits follow (for example 20000 > 19999, despite 199 having lots more 9s).

This gives us a different solution: If we just seek out the biggest leftmost digits and merely ensure that we can fill out the remaining digits, we get another solution that may be even faster:

Starting from the very left of the digit string, move forwards to the first 9 and see if there are enough remaining digits to build out the rest of the number (this is actually just an string index check, since you can always fill out a number by just taking all the digits after it). If it works, take it and continue building the number after the 9. If the 9 doesn't work (or there are no 9s in the string), try the next 8, then the next 7, etc. (you're not going to exhaust all the digits unless you're trying to build a number with more than N digits, which is easy to check).
Repeating this enough times, we will eventually end up with enough digits for a number.

But is it faster?

At first it doesn't look like it's faster, because we have to seek out the next digit each time, and that would make it O(NK) like before. But we can make an optimization that saves a ton of time on those seeks: just pre-compute for each position where the next occurrence of each digit is, and those seeks become O(1) array lookups.

Well that's a new problem: how do we pre-compute at each position where the next occurrence of each digit is?

The secret is to build this pre-computed array from right-to-left. Now the next occurrence of each digit (left-to-right) is just the most recently seen occurrence of each digit (right-to-left), and we can just update each value right-to-left as we see it.

This precomputation takes O(10 N) = O(N) time, and now that we only need to do an array lookup to build our number of K digits, the full solution takes O(10 N+10 K) = O(N+K) = O(N) time (remembering that K <= N in any reasonable version of this problem), which is definitely the fastest we can go.

Bonus problem: What if the base isn't 10? Given a N-digit string in base M, this solution will take O(NM) time. Can you find an even faster solution that covers this case? (I think there is one, but the solution that comes to me is exponentially more horrible and contains some super weird ideas).

:- ['src/util.pl'].

max_batteries(N, Batteries, Joltage):- max_batteries(N, Batteries, 0, Joltage).
max_batteries(0, _, Acc, Acc).
max_batteries(N, Batteries, Acc, Joltage):-
    length(Batteries, L),
    FrontLength is L - N + 1,
    take(FrontLength, Batteries, Front),
    max_list(Front, MaxDigit),
    nth1(MaxIndex, Front, MaxDigit),
    drop(MaxIndex, Batteries, Rest),
    succ(N1, N),
    Acc1 is Acc + 10 ^ N1 * MaxDigit,
    max_batteries(N1, Rest, Acc1, Joltage).

string_to_digits(String, Digits):-
    string_chars(String, DigitChars),
    maplist(char_code, DigitChars, Codes),
    maplist(plus(-48), Codes, Digits).

main:-
    Filename = 'inputs/day03.txt',
    read_file_to_strings(Filename, BankStrings),
    maplist(string_to_digits, BankStrings, Banks),

    maplist(max_batteries(2), Banks, Joltages),
    sum_list(Joltages, Result1),
    write("Part 1: "), write(Result1), nl,

    maplist(max_batteries(12), Banks, Joltages2),
    sum_list(Joltages2, Result2),
    write("Part 2: "), write(Result2), nl,

    halt.

:- initialization(main).

def max_jolt(bank : String, num_digits : Int32 = 12) : Int64
    digits = [] of Int32
    raise "error" if bank.size < num_digits
    i = 0
    num_digits.times do
        max = 0
        bank[0..bank.size - num_digits].each_char_with_index do |char, index|
            if char.to_i > max
                i = index 
                max = char.to_i 
            end 
        end
        digits << max
        num_digits -= 1
        bank = bank[i+1..-1] unless i>=bank.size
    end
    digits.map { |c| c.to_i }.join("").to_i64
end

sum : Int64 = 0
File.read("input.txt").split("\n").each do |bank|
    sum += max_jolt(bank)
end
puts sum

total = 0
with open("03-joltage.txt", "r") as file:
    for bank_line in file:
        tens_digit: str = "0"
        ones_digit: str = "0"

        for pos, digit in enumerate(bank_line):
            if digit > tens_digit and pos < len(bank_line) - 2:
                tens_digit = digit
                ones_digit = "0"
            elif digit > ones_digit:
                ones_digit = digit

        total += int(tens_digit + ones_digit)
print(total)

def process_line(total: int, line: str, out_size: int = 12):
    line = line.rstrip("\n")
    cur_str: str = line[:out_size]
    for i in range(out_size, len(line)):
        temp_str: str = cur_str + line[i]
        for j in range(1, out_size + 1):  # compare suffix
            cur_suf = cur_str[-j:]
            temp_suf = temp_str[-j:]
            if temp_suf > cur_suf:
                cur_str = cur_str[:-j] + temp_suf
    total += int(cur_str)
    print(cur_str)
    return total

with open("03-joltage.txt", "r") as file:
    total = 0
    for bank_line in file:
        total = process_line(total, bank_line)

print(total)

def part_one(lines):
  total = 0
  for line in lines:
    firstDigit = secondDigit = 0
    digits = [int(num) for num in line]

    firstDigit = max(digits[:-1])
    index = digits.index(firstDigit)
    secondDigit = max(digits[index+1:])

    total += 10*firstDigit + secondDigit
  return total


def part_two(lines):
  total = 0
  for line in lines:
    digits = [int(num) for num in line]
    index = 0
      
    for n in range(12):
      joltage = max(digits[index:len(digits)-(11-n)])
      index += digits[index:].index(joltage) + 1
      total += joltage * 10**(11-n)

  return total


with open('20250103.in') as file:
  lines = [line.rstrip() for line in file]

print("Part 1:", part_one(lines))
print("Part 2:", part_two(lines))

I did have a working solution with the test numbers provided but when we went from 15 digits to 100, well... exponential growth hurts and brute forcing it was not cutting it.

use std::fs::read_to_string;

const TEST_FILE: &str = "example_input.txt";
const PUZZLE_INPUT: &str = "puzzle_input.txt";

// Reads in the puzzle input text file which contains the D##
fn read_puzzle_input(file_name: &str) -> Vec<String> {
    return read_to_string(file_name)
        .unwrap()
        .lines()
        .map(String::from)
        .collect();
}

fn main() {
    // Part 1
    let part_one_answer = part_one(read_puzzle_input(PUZZLE_INPUT));
    println!("The total output voltage is: {}", part_one_answer);
    // Part 2
    let part_two_answer = part_two(read_puzzle_input(PUZZLE_INPUT));
    println!("The total combined output voltage is: {}", part_two_answer);
}

fn part_one(battery_banks: Vec<String>) -> u32 {
    let mut total_output_joltage = 0;

    for bank in battery_banks.iter() {
        // Create our array of chars
        let bank_array: Vec<char> = bank.chars().collect();
        // Setup some vars as we iterate
        let mut skip_item: usize = 0;
        let mut first_item = 0;
        let mut last_item = 0;

        // Iterate to find our first number
        for (position, battery) in bank_array.iter().enumerate() {
            let num = battery.to_digit(10).unwrap();
            // This will grab the first item that is the highest number that isn't the last item in the vector
            if num > first_item && position < bank_array.len() - 1 {
                first_item = num;
                skip_item = position
            }
        }
        // Iterate to find our second number; ignore the items LESS than the position in the array.
        for (position, battery) in bank_array.iter().enumerate() {
            let num = battery.to_digit(10).unwrap();
            if num > last_item && position > skip_item {
                last_item = num
            }
        }
        // Combine our first and last numbers
        let producing_jolts = format!("{}{}", first_item, last_item)
            .parse::<u32>()
            .unwrap();
        total_output_joltage += producing_jolts
    }
    return total_output_joltage;
}

fn part_two(battery_banks: Vec<String>) -> u64 {
    let mut total_output_joltage: u64 = 0;

    for bank in battery_banks.iter() {
        let mut max_values = [0; 13];
        let bank_array: Vec<u32> = bank.chars().map(|c| c.to_digit(10).unwrap()).collect();
        for number in bank_array {
            for i in (1..13).rev() {
                max_values[i] = max_values[i].max(max_values[i - 1] * 10 + number as u64)
            }
        }
        total_output_joltage += max_values[12];
    }
    return total_output_joltage;
}

#[test]
fn part_one_example() {
    let battery_banks = read_puzzle_input(TEST_FILE);
    let total_output_joltage = part_one(battery_banks);
    assert_eq!(total_output_joltage, 357);
}

#[test]
fn part_two_example() {
    let battery_banks = read_puzzle_input(TEST_FILE);
    let total_output_joltage = part_two(battery_banks);
    assert_eq!(total_output_joltage, 3121910778619);
}

type InputData = number[][];

function formatInput(input: string): InputData {
  const inputArr = input.trim().split('\n');
  return inputArr.map(line => line.split('').map(joltageString => parseInt(joltageString, 10)));
}

export function run(input: string): string[] {
  const data = formatInput(input);

  const totalJoltage = (batteryBanks: InputData, batteryCount: number): number => {
    let total = 0;
    for (const batteryBank of batteryBanks) {
      const selectedBatteryIndices: number[] = [];
      for (let resultDigitIndex = 0; resultDigitIndex < batteryCount; resultDigitIndex++) {
        selectedBatteryIndices[resultDigitIndex] =
          resultDigitIndex === 0 ? 0 : selectedBatteryIndices[resultDigitIndex - 1] + 1;
        for (
          let batteryIndex = selectedBatteryIndices[resultDigitIndex];
          batteryIndex < batteryBank.length - batteryCount + resultDigitIndex + 1;
          batteryIndex++
        ) {
          if (batteryBank[batteryIndex] > batteryBank[selectedBatteryIndices[resultDigitIndex]]) {
            selectedBatteryIndices[resultDigitIndex] = batteryIndex;
          }
        }
      }
      total += Number(selectedBatteryIndices.map(index => batteryBank[index]).join(''));
    }
    return total;
  };

  const totalNormalJoltage = (batteryBanks: InputData): number => {
    return totalJoltage(batteryBanks, 2);
  };

  const totalOverrideJoltage = (batteryBanks: InputData): number => {
    return totalJoltage(batteryBanks, 12);
  };

  return [`${totalNormalJoltage(data)}`, `${totalOverrideJoltage(data)}`];
}

from common import load_input
input = load_input()

def find_largest(batteries: [int], start_index: int, chop: int) -> int:
    largest = -1
    largest_index = -1
    for i in range(start_index, len(batteries) - chop):
        if batteries[i] > largest:
            largest = batteries[i]
            largest_index = i
    return largest_index

total = 0
banks = input.split('\n')
for bank in banks:
    batteries = list(map(int, list(bank)))
    a = find_largest(batteries, 0, 1)
    b = find_largest(batteries, a + 1, 0)
    total += (batteries[a] * 10) + batteries[b]

print(total)

from common import load_input
input = load_input()

def find_largest(batteries: [int], start_index: int, chop: int) -> int:
    largest = -1
    largest_index = -1
    for i in range(start_index, len(batteries) - chop):
        if batteries[i] > largest:
            largest = batteries[i]
            largest_index = i
    return largest_index

total = 0
banks = input.split('\n')
for bank in banks:
    batteries = list(map(int, list(bank)))

    allowed = 12
    last_index = 0
    for i in range(allowed):
        n = find_largest(batteries, last_index, (allowed - i - 1))
        power = pow(10, (allowed - i - 1))
        total += batteries[n] * (1 if power == 0 else power)
        last_index = n + 1

print(total)

use std::{
    env,
    fs::File,
    io::{self, BufRead},
    path::Path,
    time::Instant,
};

fn main() {
    let now = Instant::now();
    let mut sum: i64 = 0;

    let args: Vec<String> = env::args().collect();

    if let Ok(lines) = read_lines(&args[1]) {
        for line in lines {
            let temp_line = line.expect("");
            let mut chars = vec![];
            let mut used_index = 0;
            let mut index = 12;
            while index > 0 {
                let last_index = temp_line.len() - index;
                let result = get_highest_char(&temp_line[used_index..last_index]);
                chars.push(result.1);
                used_index += result.0;
                index -= 1;
            }
            println!("{:?}", chars);
            sum = sum
                + chars
                    .into_iter()
                    .collect::<String>()
                    .parse::<i64>()
                    .expect("");
        }
        println!("{sum}");
    }
    let elapsed = now.elapsed();
    println!("Elapsed: {:.2?}", elapsed);
}

fn get_highest_char(available: &str) -> (usize, char) {
    let mut best_index = 0;
    let mut best_char = '0';
    let mut index = 0;
    for n in available.chars() {
        if n > best_char {
            best_char = n;
            best_index = index;
        }
        index += 1;
        if best_char == '9' {
            break;
        }
    }
    return (best_index, best_char);
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<File>>>
where
    P: AsRef<Path>,
{
    let file = File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

def solve(input: str) -> int:
    return sum(max_joltages(input, batteries=12))


def max_joltages(input: str, batteries: int) -> Iterator[int]:
    for bank in input.split():
        yield int("".join(max_batteries(bank, batteries)))


def max_batteries(bank: str, batteries: int) -> Iterator[str]:
    start_index = 0
    end_index = len(bank) - batteries

    for _ in range(batteries):
        end_index += 1
        digit = max(bank[start_index:end_index])
        start_index = bank.index(digit, start_index) + 1
        yield digit