Advent of Code 2025, Day 10, Part 2
My personal approach to Advent of Code is to do things from scratch. Using a regex library might be okay to use but a sledgehammer like z3 is not. Any manual steps is certainly forbidden. I'd rather look up hints for a problem online than solving it in the "wrong" way.
This years day 10 part 2 was a problem, because I couldn't find a solution that wasn't horribly slow. It seems I was not alone in this, because the Advent of Code subreddit was filled with people having used z3, written an ILP solver, or implemented matrix reduction followed by a brute force solve. This discouraged me from trying to solve it at all, but after some browsing I found an interesting solution.
Their description was confusing. It's the type of argument that kind-of sounds like it's correct, but at the same time not quite making sense. I sat down trying to prove it, but couldn't do so. Instead I found another solution which turned out to be exactly the same solution, but looking at the problem from a different view.
Here it is.
Problem
I'll quickly recap the problem. We're given lines of the form:
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
We can ignore the [.##.] part, those were for part 1.
The (3) (1,3) ... part is a list of buttons, where each button contains indices 0..n-1 into
the last part {3,5,4,7}, which is the target.
We start at {0,0,0,0}, and pressing a button increments the indices of that button by 1;
pressing the (3) button would take us to {0,0,0,1}, since the 3rd index is incremented.
The goal is to find the smallest number of button presses to reach the target {3,5,4,7}.
Let's name and render the buttons in a few different forms, for convenience:
name input vector graphic
------------------------------------
a (3) {0,0,0,1} . . . o
b (1,3) {0,1,0,1} . o . o
c (2) {0,0,1,0} . . o .
d (2,3) {0,0,1,1} . . o o
e (0,2) {1,0,1,0} o . o .
f (0,1) {1,1,0,0} o o . .
I'll write $abc$ for pressing $a$ and $b$ and $c$, and $a^2$ for pressing $a$ twice. Note that ordering doesn't matter, so $ab$ is the same as $ba$. This means that when looking for solutions we're really looking for the number of button presses for each button.
Brute Force
Straight-forward brute force is too slow.
The larger instances in the real input have ~13 buttons and target coefficients over 250.
We cannot attempt to click each of the 13 buttons [0,250] times.
We could try to do smarter things, like observing that in the example input only two buttons have 0 in them ($e$ and $f$)
and so their sum (the number of times we press $e$ plus the number of times we press $f$) must be 3,
but this leads down the linear algebra path, which I already had decided was not for me.
A Bit of Fun
Instead, let's write out the target in binary. Our goal will be to efficiently enumerate all possible combinations of buttons that sum to the target, and then select the shortest one. That is, we don't really care about the length of the solutions quite yet, we only want to list out all button sequences.
Here's the target in binary:
3 = 0011
5 = 0101
4 = 0100
7 = 0111
Let's focus on the least significant bit of the 3, the bit in the top right corner.
Since only buttons $e$ and $f$ increment this number,
all solutions must press $e$ an odd number of times or $f$ an odd number of times, and not both.
This is the same as saying that the total number of $e$s and $f$s must be odd because 3 is odd,
and the sum of two numbers is odd iff exactly one of the terms is odd.
This is great, because we've only looked at one bit of the target, and we've already split the total search space in half: for any pair of $e$ and $f$ we can discard exactly half of them, namely the ones that have the same parity (even/odd-ness). Splitting the search space in half by a "local" observation such as this shows great promise, because if we can do this repeatedly the space will shrink really fast.
The Column
Now, we were only looking at the first bit in the first column, but this observation holds for the entire column. Instead of only looking at $e$ and $f$ we look at all buttons at once and try to figure out which of them we need to press an odd number of times. The rightmost column of the bit pattern of the target tells us this because only an odd number of presses of a button will be able to affect those bits.
The bits are 1101; if we can press a button at most once,
which subsets of buttons give us the pattern 1101?
Turns out, it's not too many!
Each row in this table lists a subset of the buttons, the increments when they're all pressed once, as well as the parity of that increment.
buttons vector parity
3 = 001[1] -------------------------
5 = 010[1] af {1,1,0,1} 1101
4 = 010[0] bce {1,1,2,1} 1101
7 = 011[1] cdf {1,1,2,1} 1101
abde {1,1,2,3} 1101
We are looking at many bits at once here, but we are doing exactly the same as before:
instead of saying that only buttons $e$ and $f$ will give us the upper-right bit 1,
we generalize and say that these four subsets of buttons are the only subsets that
give us the entire column 1101.
This gives us four alternatives for buttons to press an odd number of times, and so we also know that for each alternative, the other buttons are pressed an even number of times: if $af$ is pressed an odd number of times, then they're at least pressed once, and $b$, $c$, $d$, and $e$ are pressed an even number of times (considering 0 as even).
The Table
Now comes the trick.
"Odd" implies "at least once" so we can subtract $af$ {1,1,0,1} from the target {3,5,4,7} and get a lower target {2,4,4,6}.
Now we also know that all buttons must be pressed an even number of times.
The odd buttons $af$ were pressed once, so the remaining presses for $af$ must be even (still counting 0 as even).
We now have a smaller instance of the problem and we can recurse.
This might not seem like much because we only reduced the target by {1,1,0,1}, but the real
improvement is that we now know each button is pressed an even number of times.
This means instead of matching the lowest bits of the target
we can consider the second-lowest bits and ask what needs to be there.
Here are the old and new targets written out in binary:
level 0 level 1
-------- --------
3 = 0011 2 = 00[1]0
5 = 0101 4 = 01[0]0
4 = 0100 4 = 01[0]0
7 = 0111 6 = 01[1]0
Which sets of buttons will produce the pattern at the second column 1001?
buttons vector lsb
-------------------------
bf {1,2,0,1} 1001
de {1,0,2,1} 1001
ace {1,0,2,1} 1001
abcdf {1,2,2,3} 1001
We're not pressing each button once, but twice. However, this only moves the bit pattern one position to the left:
bf = {1,2,0,1} bbff = {2,4,0,2}
1 = 0001 2 = 0010
2 = 0010 4 = 0100
0 = 0000 0 = 0000
1 = 0001 2 = 0010
so subtracting $b^2f^2$ from the target clears out this column too, and
{2,4,4,6} becomes {0,0,4,4}:
level 0 level 1 level 2
-------- -------- --------
3 = 0011 2 = 0010 0 = 0[0]00
5 = 0101 4 = 0100 0 = 0[0]00
4 = 0100 4 = 0100 4 = 0[1]00
7 = 0111 6 = 0110 4 = 0[1]00
The pattern in the third column is 0011, and the subsets that give us this pattern are
buttons vector lsb
-------------------------
d {0,0,1,1} 0011
ac {0,0,1,1} 0011
bef {2,2,1,1} 0011
abcdef {2,2,3,3} 0011
Just like before, pressing each button in the set four times moves it to the third column,
but otherwise keeps it unchanged.
Looking at alternative $d$, we can press it four times.
This makes {0,0,4,4} which reduces the target to {0,0,0,0}. We're done!
Coming back up from the recursion, we pressed $d$ four times, $bf$ two times, and $af$ once, which makes this solution $d^4(bf)^2af = ab^2d^4f^3$. We can double check that this is correct:
(a) {0,0,0,1} * 1
(b) + {0,1,0,1} * 2
(d) + {0,0,1,1} * 4
(f) + {1,1,0,0} * 3
= {3,5,4,7}
Okay!
Recap
We're building up a solution for our target by looking at how many times we're pressing each button.
On level one we looked at the lowest bit of the target number, which constrained which buttons we could press an odd number of times. Pressing a button an even number of times wouldn't affect the parity of the number, since all indices would be incremented by a multiple of 2. For each alternative we recurse, knowing that from now on all buttons are pressed an even number of times.
On level two we do exactly the same, but we're looking at the second-lowest column of bits. This doesn't affect the "which subset gives us the pattern" logic, because pressing buttons twice shifts the bit-pattern by one position to the left, but doesn't change it otherwise. Again we got four alternatives, and for each alterantive we subtract and recurse. Now button presses must come in groups of four.
Now, this was only one path through the search tree, so we don't know if this is a shortest path,
but it is a valid path.
Not all choices lead to valid paths:
at the last level we could have chosen $bef$ instead of $d$,
but this would have reduced our target from {0,0,4,4} to {-8,-8,0,0} which is clearly not good.
It also doesn't have to occur at the last level.
The recursion can take us into a state that we cannot make progress from
if not every bit-pattern is possible to make from some subset of the buttons,
and if there is a way to require this bit-pattern from the target.
In our example, all bit-patterns are possible.
Here's some pseudo-rust that implements the search process:
fn solve_binary(target: &Vector, level: u32) -> Option<Moves> {
if target.has_negatives() {
return None; // went too far
}
if target.is_zero() { // if we're at zero we're done.
return Some(Moves::empty());
}
let mut solutions = Vec::new();
let mask = mask_at_level(target, level); // required pattern
for button_set in button_subsets_with_mask(mask) { // consider each subset
let next = target.subtract_at_level(button_set, level);
if let Some(mut moves) = solve_binary(&next, level + 1) {
moves.add_at_level(button_set, level); // add the pressed buttons
solutions.push(moves); // save candidate
}
}
solutions.sort_by_key(|moves| moves.len());
solutions.first().cloned() // shortest subsolution is best (if any).
}
level is passed around since we need to know how many times to press each button,
namely 2.pow(level).
Alternative: Building Bits
Another way of looking at this process is that we're looking at the bits in the target
while trying to figure out the bits in the number of button presses.
On the first level we're figuring out which buttons we press an odd number of times,
which corresponds to the ? bits in the "button table" on the left.
This is constrained by the corresponding column (the rightmost) in the "target table" in the middle.
The pattern there, 1101, gives us alternatives for the pattern we can put on the left.
a = ...[?]
b = ...[?] 3 = 001[1] 100001 (af) {1,1,0,1}
c = ...[?] 5 = 010[1] 1101 => 011010 (bce) {1,1,2,1}
d = ...[?] 4 = 010[0] 001101 (cdf) {1,1,2,1}
e = ...[?] 7 = 011[1] 110110 (abde) {1,1,2,3}
f = ...[?]
Each of those patterns again give us a vector to subtract from the target with the property
that it zeroes out the current column, and maybe touch the upper bits, but leave the bottom
bits zero. $af$ (100001), is one such pattern, and its corresponding vector is {1,1,0,1},
so on this branch the next level looks liks this:
a = ..[?]1
b = ..[?]0 2 = 00[1]0 010001 (bf) {1,2,0,1}
c = ..[?]0 4 = 01[0]0 1001 => 000110 (de) {1,0,2,1}
d = ..[?]0 4 = 01[0]0 101010 (ace) {1,0,2,1}
e = ..[?]0 6 = 01[1]0 111101 (abcdf) {1,2,2,3}
f = ..[?]1
This time we choose $bf$ (010001), bringing the target down to {0,0,4,4}.
Note that this also cleared the bit in the third column of the first 4; this is fine.
a = .[?]01
b = .[?]10 0 = 0[0]00 000100 (d) {0,0,1,1}
c = .[?]00 0 = 0[0]00 0011 => 101000 (ac) {0,0,1,1}
d = .[?]00 4 = 0[1]00 010011 (bef) {2,2,1,1}
e = .[?]00 4 = 0[1]00 111111 (abcdef) {2,2,3,3}
f = .[?]11
Lastly we choose alternative $d$ which brings the target to zero:
a = 0001 = 1
b = 0010 = 2 0 = 0000
c = 0000 0 = 0000
d = 0100 = 4 0 = 0000
e = 0000 0 = 0000
f = 0011 = 3
Now we simply read out the number in the "button table" that we built. The final button counts correspond to our solution $ab^2d^4f^3$.
To summarize: For each column in the button press counts we choose one alternative from a set given by the bit-pattern of the target in the matching column. The chosen alternative gives us a vector to subtract from the target. Repeat for each column, and in the end we've built the counts for the buttons that make up the target number. Magical!
Analysis
I think the table-building point-of-view is nice because it makes it easy to reason about
the complexity of our solution, and see why this works so much better than the brute-force method.
Each recursion level consideres one column of the bit pattern of the target, so the recursion
depth is bounded by the bit-length of the largest number in the target, i.e. its log2 rounded up.
The largest inputs has numbers around 250, so the depth is at most 9.
How many choices can we expect at each level? This depends on the button set and the target, since it depends on which pattern we're looking for as well as how well the buttons cover the possible patterns. If $D$ is the dimension of the target (4 in the example) and $B$ is the number of buttons (6 in our example) we have $2^B=64$ possible button subsets and $2^D=16$ possible bit-patterns that the subsets cover, so on average a pattern will have $64/16=4$ subsets covering it (this is indeed what we had at each level, but it didn't have to be that way). This makes for $4^9=262,144$ leaf nodes in the search tree, assuming no early exits or other pruning. Still, this is a small number of states to visit.
The Full Tree
So far we've only taken one path through the search tree.
In this figure the nodes are button press counts, and edges are the alternatives we choose.
Edges are labelled with their depth and buttons, and the format 2be means $b^2e^2$.
Rounded boxes are states that hit the target {3,5,4,7}.
By construction our states here are unique, so this is a proper tree.
The sequence we followed in the example was
$af$, $b^2f^2$, $d^4$, ending at [1 2 0 4 0 3], and this
was only one out of 14 possible valid paths.
We can also show things in a slightly different way by having the targets make up the nodes. There are multiple button combinations to reach the same target, so this graph is more tangled up. It is also smaller, because many nodes have multiple paths to it. You can imagine using memoization to compute the path from a node to the end once, and then have the parents of that node reuse the memoized result instead of computing it every time the node is visited in the search.
Pretty neat!
The Dividing Method
This is the method I read on reddit which explanation kind-of made sense, but also not really. They have updated the explanation, but I still don't think it is that convincing. The method is exactly the same as mine, but somehow I find it much harder to understand why it is correct.
It goes like this: at every step we find all button subsets that bring the parity of the target to 0. We try every subset. Subtract it from the taret to get a target consisting of only even numbers. Then we divide it in half recurse.
For our example numbers, this means starting with {3,5,4,7}, pressing e.g. $af$ to get {2,4,4,6}, dividing this
to be {1,2,2,3}, and solve this sub-problem using the same procedure.
How can we know that the best solution to solve {2,4,4,6} is to solve {1,2,2,3} and press those buttons twice?
Could it not happen that the best button counts for {2,4,4,6} contain some odd number of presses?
We can construct a set of buttons that when pressed an odd number of times will give us a target that is all even,
so it feels like the dividing by two isn't okay.
It is, though.
Instead of showing why it's correct, we can say that by assuming this structure we aren't missing out on any solutions. Let $x$ be a target vector and $B=\{b_i\}_n$ the set of buttons. The shortest number of presses to get $x$ is some number of each button, so we can write $$x = b_1^{k_1} b_2^{k_2} \dots b_n^{k_n}$$ to fix some notation. Now, we still have no idea what the $k_i$ are, but if we did, we could move one $b_i$ to the front if $k_i$ is odd, and let the evens stay in place. That is, we could write it like this: $$ x = b_2 b_3 b_8 \dots \left( b_1^{k_1} b_2^{k_2-1} \dots b_n^{k_n} \right) $$ where I've said that $k_i$ was odd for $i=2,3,8,\dots$, just to have some concrete numbers to write down. Now all of the exponents in the parenthesis are even, so we can pull a 2 out, and all of a sudden we have the decomposition $x=yz$ where $y$ consists of any button at most once and $z=w^2$ is even.
The parity of $z$ is zero because all buttons there are pressed an even number of times, so the parity of $y$ must be the same as $x$, otherwise the parities on the two sides wouldn't match. Further, $y\subseteq B$ by construction since we moved at most one of each button to the front. $y$ may be empty, but this is no concern. If $z$ is empty it means that $x=y$, so a subset of the buttons yields $x$; this is our base case!
Now, we don't actually know that $k_i$ is odd for $i=2,3,8,\dots$, so we can't decompose $x$, but we do know that such a decomposition exists. So, we can search for it by considering all subsets of the buttons which parity matches $x$. This gives us a bunch of alternatives for $y$, and we can try them all. Fixing $y$ lets us compute $z=x\setminus y$, and if we chose the correct $y$, $z$ will be even and we can divide it's coefficients by 2 and recurse.
That's it!
Conclusion
I thought it was very neat how two fairly different trains of thoughts can lead to basically identical algorithms. I think I prefer the constructive bit-pattern search, especially the alternative framing of finding columns of bits that build up the final binary numbers that are the button counts, but I also appreciate the top-down thinking of the dividing method, where we can argue that a solution exists and that we will find it.
I was hoping to find a more rigorous proof of correctness than what I've written here, but I think I've spent enough time on this problem, and the holidays are almost here.
Thanks for reading.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License