Advent of Code 2025 - Day 3

Problem description

We are given an array of digits. For each line, we have to find the highest possible m-digit number, taking m digits from a list of n digits, without modifying digits order.

Part 1

In this part, we are asked to find a 2-digit number.

I used an iterative algorithm, with dynamic programming. First, in a list of length n, I search the highest element between indexes 0 and n-2, then I pick its index (firstIdx), and I search the highest digit between indexes firstIdx + 1 and n-1.

private def maxJoltage(bank: Array[Int]): Int =
  val firstBattery = bank.init.max
  val firstIdx = bank.indexOf(firstBattery)
  val secondBattery = bank.slice(firstIdx + 1, bank.length).max
  10 * firstBattery + secondBattery

Part 2

Now, we have to find a 12-digit number. This part cannot seriously be brute-forced.

My algorithm for Part 2 is a generalization of my Part 1 algorithm.

private def maxJoltage(bank: Array[Int], batteries: Int): Long =
  var batteryIdx = -1
  var joltage = 0L

  for i <- 1 to batteries do
    val subBank = bank.slice(batteryIdx + 1, bank.length - batteries + i)
    val battery = subBank.max
    joltage = 10 * joltage + battery
    batteryIdx += subBank.indexOf(battery) + 1

  joltage

Complexity

The code executes in linear time (O(n), n being the line length). A brute-force approach would have a complexity of O(n^d), d being the length of the requested number.