202412070000 Advent of Code 2024 Day 07

Bridge Repair

Today we're visiting the rope bridge from 2022 day 9 and need to help the elves repair it by sorting out there test calculations.

The Puzzle

Today we're visiting the rope bridge from 2022 day 9 and need to help the elves repair it by sorting out their test calculations.

We’re given a list with lines containing a value and some numbers. We’re tasked with figuring out whether the numbers can be put together using a set of operators to obtain the value. For example,

190: 10 19
156: 15 6

The first part starts with the + and * operators and the second adds the || (concatenation) operator. We’re also told that precedence for all these is equal and we should just evaluate them from left to right.

Solution

The only real complexity today is figuring out how to test all the possible combinations of operators. As you'll see, there are different ways to do this and some are more efficient than others.

I started by using a Cartesian Product of the set of operators per slot. For example, in part two the line 7290: 6 8 6 15 would need to test all three operators ([*, +, ||]) on the three slots between numbers (6 8 6 15). The list of possibilities would look like

[*, *, * ]
[*, *, + ]
[*, *, ||]
[*, +, * ]
[*, +, + ]
[*, +, ||]
... and so on

In order to dynamically test these operations I created a string with the numbers and operators and then used JS's eval function to run the string as code.

export const solutionOne = (input) => {
  const equations = parse(input);
  let possible = [];
  for (const [answer, numbers] of equations) {
    const opts = cartesian(...[['*', '+']].repeat(numbers.length - 1));
    for (const seq of opts) {
      let sval = numbers[0];
      for (let i = 0; i < seq.length; i++) {
        sval = eval(`${sval} ${seq[i]} ${numbers[i + 1]}`);
      }
      if (answer === sval) {
        possible.push(answer);
        break;
      }
    }
  }
  return possible.sum();
};

Note that the answer we need for the puzzle is the sum of the left-hand numbers of the lines that are valid. Looking back to the top of the post to the example with two lines, if both of those were valid lines, we'd get puzzle_answer = 190 + 156. This explains the possible.push(answer) bit.

This worked but was very slow. I got the answers for the day and then started thinking about other ways to do it.

Pretty quickly, a recursive version popped out. I honestly don't know why I didn't think to do it like this to begin with. Maybe other people would have felt this was much more natural than my first caveman approach.

const valid = (eq, v, i, ops) => {
  if (i === eq.length) return eq[0] === v;
  if (v > eq[0]) return false;
  return ops.some((op) => valid(eq, op(v, eq[i]), i + 1, ops));
};

const solve = (input, ops) =>
  input
    .map((l) => l.match(/\d+/g).nums())
    .filter((eq) => valid(eq, eq[1], 2, ops))
    .reduce((s, c) => s + c[0], 0);

const OPS = [(a, v) => a + v, (a, v) => a * v];
export const solutionOne = (input) => solve(input, OPS);
export const solutionTwo = (input) =>
  solve(input, [...OPS, (a, v) => +`${a}${v}`]);

This solution works by actually exploring each path speculatively, like a tree instead of just trying one iteration per whole path. The valid function is called with the value we're trying to find and the next value in the list of numbers on the right. Then we apply each operator in the map and see if they've bottomed-out in the recursion. We bottom-out when we're on the last value in the list or if we have already exceeded our target value (since all our operations cause the values to increase). We get a small assist from the short-circuiting of the some function too. By exploring the paths like this, we prune a huge portion of the problem space.

Consider the following line with a series of operations.

10: 5 3 2

[ *, * ]
[ *, + ]
[ *, ||]
[ +, * ]
[ +, + ]
[ +, ||]
[||, * ]
[||, + ]
[||, ||]

We can see just by the first two values (5 and 3) that all the paths starting with * or || will be invalid. The first approach would run these anyway, while the second does not.

Not only is this significantly faster, but the whole solution is much less code and much more understandable. The first solution had the code I showed, an equally large block of code for the second part (since we had to special-case the concat instead of using eval, though maybe it could have been refactored a bit), a line or two for the parse function, and the mutually recursive cartesian method that I stuck in my array helper library.

I'm pretty happy with this refactor. It really took an ugly slow solution and turned it into a fast and elegant one.

Update

I looked online at other people's solutions after writing this up and see that some people needed to use BigInts for their code. Maybe I just got lucky that my input didn't need this, but then again, my answer was one (nearly two) orders of magnitude below JS's MAX_SAFE_INTEGER. Perhaps the inputs did really vary that much, but typically they don't. If for some reason, you're using this code as a guide and aren't getting the right answers, consider trying BigInts instead of regular Numbers.

Got somewhere nice with this one in the end. I feel the longer nights coming though, and with a newborn at home, I'm not sure how many more days I'll be able to do at midnight. See you tomorrow.

You can find the full solutions to today's AoC puzzles in my AoC GitHub repo.