Day 3: Lobby

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).

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);
}