These are observations and methods from the more interesting problems in this year's Advent of Code

To keep this day as efficient as possible, we want numeric operations to operate on a number's digits. Although it is still perfectly possible to just treat each digit of a number as a character of a string, its better to think of every number as a sum of powers of ten.

So to take half of a number's digits, let us think about e.g. 456456 as 456000 + 456. And for Part 2, to think about repeating combinations of digits, we can think of 456456456456 as 456 + 456000 + 456000000 + 456000000000 = 456 + 456 * 10^3 + 456 * 10^6 + 456 * 10^9.

As an extra trick, we notice that we are making a geometric series, so we can invoke a known formula to immeditaely calculate the whole sum.

Also, while this puzzle is framed as a search problem, it is much more efficient to construct the solutions than traverse the search space. It is hard to numerically check whether some number is a repeated set of digits, but it's easy to find every 9 digit number made of repeating digit sets -- 3 is the only non-trivial divisor, and we can easily use 3-digit numbers as the basis of the relevant geometric series.

Once we've realised all this, we just have to be careful not to count e.g. 222222 multiple times (because it is 222 222 but also 22 22 22). I get around this with a set capturing solutions, but maybe there is a way to guarantee uniqueness in construction.

This construction, of making a decision about an element of a matrix by considering a small window around that element has many practical uses. One is image manipulation: we can blur an image by "mixing" every pixel somehow with the pixels around it.

Because it has a technical mathematical definition, we can use pre-written methods in the SciPy library, we just have to write the right kernel.

My solution itself describes the process, but the lesson here is that if we set up a solution structure in the right order, we can continually depend on previous results.

The idea behind this solution is from a Reddit thread but the proof of correctness is mine.

We are trying to find a sequence of button pressed so that the counters reach certain levels (in the problem these are called joltages). Remembering that button presses are just incrementing some indexed counters, we know it doesn't matter the order they were pressed in. So we can imagine pressing one button however-many times, then the next button however-many times, etc. Or, if we press a button an odd number of times, we save one press for later.

So if button 1 is pressed 5 times, we press it 4 times to start, continue with the others, and then we pause. Because every number has been pressed an even number of times, every counter must be an even number. Now, when we do our leftover presses, we are pressing each button at most once. The resulting odd- and evenness (parity) of the resulting counters would have been the same if we had never done the double presses.

Our trick is that beforehand we consider every combination of unique button presses, and remember the parity pattern, the actual pattern of counters that those presses would yield, and how many presses are involved in that combo.

Then we find the possible button combinations that give the same parity as our pattern and subtract their effects. But what we're left with, according to our grouping of presses, is a series of duplicated presses. So we can divide this new pattern by two, and continue our search again.

We quit any path on our search tree that gives us an impossible pattern (any counter being negative), and when we do reach home (an all-zero pattern), we count all the presses it took us to get here.

My breadth-first-search counting method used in part 1 is not correct in general --- it assumes that every node belongs to a single generation.

The correct matrix generalisation in part 2 is equivalent to iteratively checking that the total number of paths to every node is the sum of the paths to all its predecessors. If you kicked this process off with a single node having path count 1, you'd be following the exact same process (albeit less efficiently).

The trick for counting all paths passing through dac and fft is counting the three portions separately and multiplying together the counts. Because the problem only makes sense if the graph has no cycles, we also note for curiosity's sake that either dac must come before fft in every valid path, or the other way around.