Day 3 had a nice change of pace between the two parts. Part 1 was solvable by brute force, and it was immediately apparent that part 2 would not be.

Part 1

For the first part, you have to pick two digits from a list (in order) to make the largest two-digit number you can. That's small enough for brute force, being O(n2) in the number of digits given. You walk down the list, taking each digit in turn, then forming a two digit number with each digit in the remainder of the list.

This is almost a fold operation, except that you need access to the rest of the list at each stage, rather than just looking at one element in isolation.

maxPower2 :: [Int] -> Int
maxPower2 [] = 0
maxPower2 (tens:batteries) 
  | null batteries = 0
  | otherwise = max this other
  where this = tens * 10 + (maximum batteries)
        other = maxPower2 batteries

Part 2

This is where a change in approach is needed. The challenge now is to pick 12 digits from the list (of one hundred digits), in order, to make the largest 12-digit number. That means there are something like 100-choose-12 possible solutions to consider, which is something like \( \frac{100!}{88! 12!} \). It's less than that, as elements have to be chosen in order, but it's still a very large number.

The different approach is to use dynamic programming. I maintain a table of partial results as I walk down the list. The table maps the number of batteries used so far to the largest "joltage" found using that number of batteries.

For instance, consider the input sequence "234234234234278". When I start, the table contains the single entry mapping zero batteries to zero joltage. When I look at the first value, "2", I add the entry of "one battery, joltage = 2" to the table.

Things get more interesting when I look at he second battery, with value 3. I take each entry in the existing table and see what would happen if I add that battery to the partial results. That would take the table {0 → 0, 1 → 2} and convert it into the table {1 → 3, 2 → 23}. I combine that with the original table, keeping the highest joltage in cases where there are the same number of batteries. That results in the table {0 → 0, 1 → 3, 2 → 23}. The process continues, as below.

  1. Used: 2. Table: {0 → 0, 1 → 2}
  2. Used: 23. Table: {0 → 0, 1 → 3, 2 → 23}
  3. Used: 234. Table: {0 → 0, 1 → 4, 2→ 34, 3 → 234}
  4. Used: 2342. Table {0 → 0, 1 → 4, 2 → 42, 3 → 342, 4 → 2342}

The table is limited to have only 12 entries, as I have to pick only 12 batteries. At the end, I look up the value of the key "12" in the table.

The overall shape of the solution becomes a foldl over the list of batteries, updating the table at each step. Each step updates the table following the process above.

batteriesPower :: [Int] -> Table
batteriesPower batteries = foldl' batteriesPowerOne (M.singleton 0 0) batteries

batteriesPowerOne :: Table -> Int -> Table
batteriesPowerOne table battery = M.unionWith max table useThisBattery
  where incompleteBatteries = M.filterWithKey (\n _ -> n < batteriesToUse) table
        useThisBattery = M.foldlWithKey' incorporate M.empty incompleteBatteries
        incorporate p n b = M.insert (n + 1) (b * 10 + battery) p

Code

You can get the code from Codeberg.