Recently I was introduced to Advent of Code, and for the last couple of days I’ve been working through the various Advent of Code problems to have something to do and to help challenge my personal coding ‘skill’ with some crazier problems then I would normally encounter. It helps that these problems are bite sized and allow you to get sucked into a problem for 30 minutes to an hour, find a solution, and then move onto the next thing. Honestly I encourage anyone with an interest in programming, computer science, or computer engineering to work through these as they are a lot of fun and allow for some very fun personal challenges (solve them under a certain computation time, solve them in a certain language, solve them, but with only single board computers, etc). Today I solved Day 7 of the 2024 Advent of Code riddle, and the solution ended up involving a pretty novel algorithm. It was so novel that I felt the need to do a quick right up about it.

In Day 7s problem you are given a list of ‘calibrations’, and are tasked with determining which calibrations are accurate and which ones are not. A calibration consists of an integer value, followed by a colon, and then followed by a series of other integer values. For example:

190: 10 19
3267: 81 40 27
83: 17 5

Each calibration here is an equation, with the elements after the colon being the operands and the value before the colon being the result. The issue is that the operators are missing from all of these equations. Now some of these calibrations are accurate, where a possible combination of the operands with certain operators between each element would indeed generate the given result. Some of the calibrations are not accurate, and no combination of operators works. A couple of caveats to the rules, the operators are always determined from left to right, not following standard figure order of merit, and the operands cannot be moved around the equation. They are strictly read left to right as given.

The first puzzle is to determine which calibrations are accurate provided that the only possible operations are addition and multiplication. With those two possible operators, determine which calibrations are accurate and provide a sum of all valid calibration results.

Note that the calibrations given above are just a sample, the actual puzzle input is 850 calibrations long, and has calibrations with up to 10-12 operands. That said, even with 12 operands, it wouldn’t be too tricky to just check all possible combinations of operators for all calibrations. Since there are two possible operators there are 2^n-1 possible operator combinations, so time complexity for brute forcing this problem is exponential. But with our highest n being only 10-12 that shouldn’t be a big deal.

So my thought with solving the first problem basically worked out as so:

1. For each calibration, see how many operands there are and subtract one to get the number of operators
2. Check every possible operator permutation to see if it results in the given calibration value
3. If a match is ever found, break out of our check and add the calibration value to our ultimate answer

A very simple algorithm, but in this came the trick that this post is about. The challenge is with step 2 of the above algorithm. This means that we need a way of:

• Determining every possible permutation of operators
• Tracking what permutation should be checked, and getting the correct placement of addition and multiplication operations
• Ensuring that we don’t check any permutation more than once and
• Ensuring that we do check every permutation at least once

Since we only have two possible operators we can go ahead and represent each operation with a one bit value (in my case I said a 0 meant addition, and a 1 meant multiplication). Now the cool part, since we know how many operators are present in a given calibration, we can actually determine all of the possible permutations for a given calibration by creating a binary integer of (in my case) all multiplication operations, and counting from zero to that number. For example:

0000 0000 - 8 operator equation where all operators are addition
0000 0001
0000 0010
---------
1111 1101
1111 1110
1111 1111 - 8 operator equation where all operators are multiplication

This is cool, because by simply counting from zero to whatever number our ‘all multiplication’ permutation is we’ve already determined all possible permutations, we can easily ensure that we check all permutations and none more than once, and we can track what permutation is currently being checked and how the operators should be positioned by just inspecting the iteration that we are currently on! The permutation’s specific positioning is encoded in our iteration, we just have to for loop through each bit of that integer to get our addition or multiplication values.

In my actual code, checking one calibration for whether or not it was valid ended up looking like this:

Now every Advent of Code problem comes with a ‘part two’ that is only revealed when you are able to correctly answer the first problem. It always involves the same puzzle input data and is related to the first problem, but with a slight twist. In the part two for this problem you have to calculate a very similar result to that of part one, but instead of only addition and multiplication operators there is now a third operator called ‘concat’, that concatenates the integer on the left with the integer on the right.

123 || 456 = 123456

Outside of the straight forward challenge of making a method for this new operation (involving string converting the param integers, concatenating the strings, and parsing a long out as a result), this poses a challenge with our first solution. Since we can no longer define each operator as either a 0 or a 1, we can no longer encode our operations in an integer in the same way that we were earlier. However, we can modify our solution by shifting two bits in to our range for every operator instead of one, and making a truth table.

0 0 | Addition
0 1 | Multiplication
1 0 | Concatenation
1 1 | Not used (invalid)

This solution proceeds exactly as the solution for part one did, except as stated earlier our ’top level’ permutation now has two 1s for every operator instead of 1, and when checking each operator we have to shift out two bits per operator. Here’s how my code ended up looking:

Importantly (and this was a bug when I first coded this up), any permutation in which there is any 0b11 operator at all would be invalid. 0b11 in this case is not simply a NOP, it’s a completely invalid permutation as that operator doesn’t exist.

Another important thing, with this solution we’re doing quite a bit more work then we need to. Since 0b11 is not a valid permutation, we don’t actually need to be checking that at all, and we end up checking 25% more permutations then we need to. Also, where the time complexity of our original problem was 2^n-1, the complexity of this solution is 4^n-1. Still exponential, but clearly takes quite a bit more time. When I ran this (single threaded) on my Ryzen 9 it took 25 ms to solve part 1, but it took almost a MINUTE to solve part 2!

Lots of talk for one small algorithm, but it was such a cool idea that I wanted to post about it. The idea of using your iterator as a bitmask to check all possible permutations of an array is a problem that I could see myself running into even outside of fun riddles like this, and this is a pretty novel way to solve it.