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:
- Only consider the first L-N digits, where N is the remaining digits besides the current one (so 11 initially)
- Find the biggest digits, D, starting with 9
- Recurse with the remaining digits and N-1
- 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.