--- Day 3: Batteries ---

December 3

Listening to: NEON PALM MALL (Vaporwave Mix)


This year feels chill actually. No global leaderboard, half the number of puzzles. I don't feel the pressure to do it as much as I've made myself feel in previous years.

Anyway, easy and quick enough to brute force it for part 1.

int sum = 0;
foreach (var bank in batteries)
{
    int maxJoltage = 0;
    for (int i = 0; i < bank.Count - 1; i++)
    {
        for (int j = i + 1; j < bank.Count; j++)
        {
            int joltage = (bank[i] * 10) + bank[j];
            maxJoltage = Math.Max(maxJoltage, joltage);
        }
    }

    sum += maxJoltage;
}

Ha. Here's the first real tricky bit. I don't think this one can easily be brute forced, not with how many permutations there could be. I think some cleverer thinking might be necessary. My first thought:

  1. Only consider the first L-N digits, where N is the remaining digits besides the current one (so 11 initially)
  2. Find the biggest digits, D, starting with 9
  3. Recurse with the remaining digits and N-1
  4. If there's no valid joltage with D, D-- and try again
private static long FindLargest(int[] bank, int start, int remaining)
{
    if (remaining == 1)
    {
        return bank.Skip(start).Max();
    }

    long largest = 0;
    int digit = 10;

    while (largest == 0 && --digit > 0)
    {
        for (int i = start; i < bank.Length - remaining + 1; i++)
        {
            if (bank[i] == digit)
            {
                largest = Math.Max(FindLargest(bank, i + 1, remaining - 1), largest);
            }
        }
    }

    return largest + (digit * (long)Math.Pow(10, remaining - 1));
}

Despite how recursive it get, it goes surprisingly fast because it's limited to only a few to look at in the first place, and specifically targetting the larger digits, essentially pruning a lot of dead branches.

It did take me a while to figure out an off-by-one errrr in the main for loop though.


Time taken: 1 hour

My solutions for today's puzzles