Advent of Code 2024: Day 07

Code for solutions available on GitHub.

Bridge Repair

What would an Advent of Code be without some dynamic programming at some point? For today’s input, we have a bunch of numbers like this:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

The first number in each line is the target. The remaining numbers on the line are numbers we have to use to create the target number by using the addition (+) and multiplication (*) operators. Each line is known as an equation. The task is to figure out which equations are possible to create using the two operators. They are always evaluated left-to-right, so we don’t have to worry about precedence rules.

First, a simple struct:

struct Equation {
    target: u64,
    numbers: Vec<u64>,
}

And now to figure out whether an equation is valid or not. You could do this by considering the gap between each number as a bit in a binary number, mapping e.g. 0 to + and 1 to * and simply trying all 2^n possible solutions. However, this would do a lot of repeated work and a lot of unnecessary work. Consider if the result is already too large halfway through the list of numbers. Then the equation is invalid and there’s no point in continuing. And changing operators in the later part of the list of numbers repeats all the work from the start of the list.

Instead, we can approach this in a dynamic programming-inspired way, and going backwards through the list of numbers. So instead of adding and multiplying to get to the target value, we subtract or divide to get the target number down to 0 or 1, depending on operation. We save all – and I mean all – valid intermediate solutions in a table to avoid duplicate work. If the subtraction would underflow, or the target number is not divisible by the current number in the iteration, we don’t save that result. This cuts down on a lot of unnecessary work.

For each iteration, we subtract the current number from all valid intermediate solutions from the previous iteration (where possible), and divide all valid intermediates by the current number (where possible). Repeating this until we reach the last iteration (the first number), we can then figure out whether the equation is possible by looking at the second to last iteration’s results. If the first element of self.numbers appears anywhere there, it’s possible! And which row of the table it appears in tells us what the first operation is!

That’s a lot of words, and this concept can be a bit difficult to explain with words, so instead I’ll explain with code:

impl Equation {
    fn is_valid(&self) -> bool {
        // Our table. 2 rows: one for each kind of operation.
        let mut dp = [const { Vec::new() }; 2];

        // Each column of the table rows is a Vec
        // containing intermediate results.
        dp[0].resize(self.numbers.len(), Vec::<u64>::new());
        dp[1].resize(self.numbers.len(), Vec::<u64>::new());

        // Iterate backwards, keep track of indices.
        for (i, number) in self.numbers.iter().enumerate().rev() {

            // Next intermediate results
            let next = if i == self.numbers().len() - 1 {
                // The first result should be `self.target`.
                vec![self.target]
            } else {
                // Otherwise, the next result should
                // be a Vec of all intermediate results
                // from the previous iteration
                // (from both rows).
                let mut next = dp[0][i + 1].clone();
                next.extend_from_slice(&dp[1][i + 1]);
                next
            }

            // Check all subtractions, save intermediate.
            dp[0][i] = next
                .iter()
                .filter_map(|n| n.checked_sub(*number))
                .collect();
            // Check all divisions, save intermediate.
            dp[1][i] = next
                .iter()
                .filter(|n| *n % number == 0)
                .map(|n| n / *number)
                .collect();
        }

        // There's a path where the first operation is
        // addition.
        dp[0][1].contains(&self.numbers[0]) ||

        // There's a path where the first operation is
        // multiplication.
        dp[1][1].contains(&self.numbers[0])
    }
}

An alternative return code is to check whether the first column of the first row contains a 0, or the first element of the second row contains a 1. If one is true, the other is as well. But I’m being explicit here with which operation is found first.

For the sake of completeness, here’s a visualization of what happens in this code:

Consider the equation line "292: 11 6 16 20".
Iterating backwards

i = 3:
numbers = [11, 6, 16, 20];  292 >= 20
                       ↑    292 % 20 != 0
dp = [
  + [ [], [], [], [272] ],  272 (292 - 20) inserted
  * [ [], [], [],    [] ],  nothing inserted, not divisible
                     ↑
]

i = 2:
numbers = [11, 6, 16, 20];  272 >= 16
                   ↑        272 % 16 == 0
dp = [
  + [ [], [], [256], [272] ],   256 (272 - 16) inserted
  * [ [], [],  [17],    [] ],   17 (272 / 16) inserted
                 ↑
]

For i = 1, we have to consider both Vecs at i = 2:

i = 1:
numbers = [11, 6, 16, 20];  256 >= 6
               ↑            17 >= 6
                            256 % 6 != 0
                            17 % 6 != 0
dp = [
  + [ [], [250, 11], [256], [272] ],    250 (256 - 6),
                                        11 (17 - 6) inserted
  * [ [],        [],  [17],    [] ],    nothing inserted
                 ↑
]

i = 0:
numbers = [11, 6, 16, 20];  250 >= 11
            ↑               11 >= 11
                            250 % 11 != 0
                            11 % 11 == 0
dp = [
  + [ [239, 0], [250, 11], ... ],   239 (250 - 11),
                                    0 (11 - 11) inserted
  * [ [1], [], ... ],               1 (11 / 11) inserted
       ↑
]

A bit convoluted still, but because the table row for + has a Vec that contains our first number (11) in the second column, there’s a way to realize the equation with the first operation being +. Staring long enough at the final table, you can come to the conclusion that the way to make 292 from 11 6 16 20 is as follows:

• 292 = (((11 + 6) * 16) + 20)

I added parentheses to clarify that the equations are evaluated left-to-right.

Here’s how to stare at the final table:

Looking at the second column (heading 1), we have the first number in the sequence 11 at the first row. Because we’re in the first row, the next operation is addition. Adding the next number (6); we get 17. Going to the next column, we find 17 in the second (multiplication) row. So the next operation is multiplication. Multiplying what we have so far (17), with the next number (16), we get 272. This is found in the first row, so the next operation is addition. Finally, adding the next and final number (20) to 272, we end up at 292, which was the target number! And thus the sequence is 11+6*16+20.

Here’s a visualization of the path (first column included, even though it’s actually superfluous) with all irrelevant entries removed.

      11        +6          *16  +20    = 292

    (+11)                       (+20)
0 --------> 11           272------------> 292
      |      |           ^
 (*11)|      | (+6)      | (*16)
      |      |           |
1 ----´       `--> 17 ---´

Phew! That’s a lot of typing and diagrams. And I’m still not quite happy with any explanation. It’s a difficult thing both to explain and to visualize. This final excursion into recreating the path is completely irrelevant to the task. It just wanted to know which equations are possible, disregarding the details.

Oh, right! The task!

Once we have a Vec<Equation>, and the Equation::is_valid method from waaay before, actually getting the result is easy:

let result = equations
    .into_iter()
    .filter(Equation::is_valid)
    .map(|equation| equation.target)
    .sum();

Part 2

Of course, part 2 predictably adds another operation into the mix: concatenation. It’s exactly what you’d expect, 15 || 6 would create 156. Everything is still left-to-right, so this is just a matter of adding another row to the table in a new method:

impl Equation {
    fn is_valid_with_concatenation(&self) -> bool {
        // ---<snip>---
        for (i, number) in self.numbers.iter().enumerate().rev() {
            // ---<snip>---
            dp[2][i] = next
                .iter()
                .filter(|n| {
                    let num_digits = number.ilog10() + 1;
                    let modulus = 10u64.pow(num_digits);
                    if *n % modulus == *number {
                        Some(*n / modulus)
                    } else {
                        None
                    }
                })
                .collect();
            // ---<snip>---
        }
        dp[0][1].contains(&self.numbers[0]) ||
        dp[1][1].contains(&self.numbers[0]) ||
        dp[2][1].contains(&self.numbers[0])
    }
}

This code just checks whether the target number of the intermediate solution ends with the same digits as the current number in the list. If so, it shifts those digits off and stores the result as a new intermediate result. Getting the full result is then just a matter of changing .filter(Equation::is_valid) from part 1 to .filter(Equation::is_valid_with_concatenation).

Visualizing the path works in the exact same way as before, except there’s a third row which represents that the next operation is concatenation.

A quick excursion into the table for the equation 192: 17 8 14:

In the second column, we have the first number (17) in the third row. So concatenation is the first operation. We concatenate our second number (8) to get 178. This is in the third column of the first row, so our next operation is addition. We add the final number (14) to 178 and wouldn’t you know, it’s 192! The target number! So the equation is 192 = ((17 || 8) + 14).

Full code on GitHub, if you prefer to read code with much fewer explaining comments. :)