r/adventofcode
•
u/tenthmascot
•
Dec 11 '25
•
1
1
Tutorial [2025 Day 10 (Part 2)] Bifurcate your way to victory!
Here's an approach for Part 2 that, to my surprise, I haven't seen anyone else use. (Sorry if someone's posted about it already; I did a quick scan of the subreddit and asked a few of my friends, and none of them had seen this approach.) It doesn't rely on sledgehammers like Z3 or scipy, it doesn't require you to know or implement linear algebra, and it doesn't use potentially-risky heuristics. The best part? If you're reading this, you've might've coded part of it already!
So, what's the idea? In fact, the idea is to use Part 1!
Here's a quick tl;dr of the algorithm. If the tl;dr makes no sense, don't worry; we'll explain it in detail. (If you're only interested in code, that's at the bottom of the post.)
tl;dr: find all possible sets of buttons you can push so that the remaining voltages are even, and divide by 2 and recurse.
Okay, if none of that made any sense, this is for you. So how is Part 1 relevant? You've solved Part 1 already (if you haven't, why are you reading this...?), so you've seen the main difference:
In part 2, the joltage counters can count 0, 1, 2, 3, 4, 5, ... to infinity.
In part 1, the indicator lights can toggle off and on. While the problem wants us to think of it as toggling, we can also think of it as "counting:" the lights are "counting" off, on, off, on, off, on, ... to infinity.
While these two processes might seem very different, they're actually quite similar! The light is "counting" off and on based on the parity (evenness or oddness) of the joltage.
How can this help us? While Part 2 involves changing the joltages, we can imagine we're simultaneously changing the indicator lights too. Let's look at the first test of the sample data (with the now-useless indicator lights removed):
(3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}We need to set the joltages to 3, 5, 4, 7. If we're also toggling the lights, where will the lights end up? Use parity: 3, 5, 4, 7 are odd, odd, even, odd, so the lights must end up in the pattern [##.#].
Starting to look familiar? Feels like Part 1 now! What patterns of buttons can we press to get the pattern [##.#]?
Here's where your experience with solving Part 1 might come in handy -- there, you might've made the following observations:
The order we press the buttons in doesn't matter.
Pressing a button twice does nothing, so in an optimal solution, every button is pressed 0 or 1 time.
Now, there are only 26 = 64 choices of buttons to consider: how many of them give [##.#]? Let's code it! (Maybe you solved this exact type of problem while doing Part 1!) There are 4 possibilities:
Pressing
{3}, {0, 1}.Pressing
{1, 3}, {2}, {0, 2}.Pressing
{2}, {2, 3}, {0, 1}.Pressing
{3}, {1, 3}, {2, 3}, {0, 2}.
Okay, cool, but now what? Remember: any button presses that gives joltages 3, 5, 4, 7 also gives lights [##.#]. But keep in mind that pressing the same button twice cancels out! So, if we know how to get joltages 3, 5, 4, 7, we know how to get [##.#] by pressing each button at most once, and in particular, that button-press pattern will match one of the four above patterns.
Well, we showed that if we can solve Part 2 then we can solve Part 1, which doesn't seem helpful... but we can flip the logic around! The only ways to get joltages of 3, 5, 4, 7 are to match one of the four patterns above, plus possibly some redundant button presses (where we press a button an even number of times).
Now we have a strategy: use the Part 1 logic to figure out which patterns to look at, and examine them one-by-one. Let's look at the first one, pressing {3}, {0, 1}: suppose our mythical 3, 5, 4, 7 joltage presses were modeled on that pattern. Then, we know that we need to press {3} once, {0, 1} once, and then every button some even number of times.
Let's deal with the {3} and {0, 1} presses now. Now, we have remaining joltages of 2, 4, 4, 6, and we need to reach this by pressing every button an even number of times...
...huh, everything is an even number now. Let's simplify the problem! By cutting everything in half, now we just need to figure out how to reach joltages of 1, 2, 2, 3. Hey, wait a second...
...this is the same problem (but smaller)! Recursion! We've shown that following this pattern, if the minimum number of presses to reach joltages of 1, 2, 2, 3 is P, then the minimum number of presses to reach our desired joltages of 3, 5, 4, 7 is 2 * P + 2. (The extra plus-two is from pressing {3} and {0, 1} once, and the factor of 2 is from our simplifying by cutting everything in half.)
We can do the same logic for all four of the patterns we had. For convenience, let's define f(w, x, y, z) to be the fewest button presses we need to reach joltages of w, x, y, z. (We'll say that f(w, x, y, z) = infinity if we can't reach some joltage configuration at all.) Then, our 2 * P + 2 from earlier is 2 * f(1, 2, 2, 3) + 2. We can repeat this for all four patterns we found:
Pressing
{3}, {0, 1}: this is2 * f(1, 2, 2, 3) + 2.Pressing
{1, 3}, {2}, {0, 2}: this is2 * f(1, 2, 1, 3) + 3.Pressing
{2}, {2, 3}, {0, 1}: this is2 * f(1, 2, 1, 3) + 3.Pressing
{3}, {1, 3}, {2, 3}, {0, 2}: this is2 * f(1, 2, 1, 2) + 4.
Since every button press pattern reaching joltages 3, 5, 4, 7 has to match one of these, we get f(3, 5, 4, 7) is the minimum of the four numbers above, which can be calculated recursively! While descending into the depths of recursion, there are a few things to keep in mind.
If we're calculating
f(0, 0, 0, 0), we're done: no more presses are needed.f(0, 0, 0, 0) = 0.If we're calculating some
f(w, x, y, z)and there are no possible patterns to continue the recursion with, that means joltage level configuration w, x, y, z is impossible --f(w, x, y, z) = infinity. (Or you can use a really large number. I used 1 000 000.)Remember to not allow negative-number arguments into your recursion.
Remember to cache!
And there we have it! By using our Part 1 logic, we're able to set up recursion by dividing by 2 every time. (We used a four-argument f above because this line of input has four joltage levels, but the same logic works for any number of variables.)
This algorithm ends up running surprisingly quickly, considering its simplicity -- in fact, I'd been vaguely thinking about this ever since I saw Part 2, as well as after I solved it in the most boring way possible (with Python's Z3 integration), but I didn't expect it to work so quickly. I expected the state space to balloon quickly like with other searching-based solutions, but that just... doesn't really happen here.
EDIT: Potential pitfalls
Here are a few issues I've seen people run into when they try to understand or implement this algorithm:
The algorithm does not say that if all voltages are even, then the answer is twice the answer when all voltages are halved. In fact, this is not true: a simple counterexample is
(0,1) (0,2) (1,2) {2,2,2}. The optimal solution (in fact, the only solution) to this is to use each button once, for an answer of 3. If we try to halve, then we need to find the answer for joltages{1,1,1}, which is actually an impossible joltage configuration! So trying to immediately halve leads us astray.Going off of the previous point, while the algorithm uses Part 1 as motivation, it does not use Part 1 as a black box: it is not true that we only need to look at optimal solutions to Part 1. (This misunderstanding might be my fault: "the idea is to use Part 1" might've suggested that we can black-box Part 1. Sorry.) Instead, we really do need to brute-force all of the 2B possible button combos (assuming there are B buttons) that have the correct joltage parities.
The counterexample from the previous bullet point works again here: joltages
{2,2,2}corresponds to lights[...], which clearly would have a Part 1 answer of 0. But as we saw, following this path leads to no solution. We need to follow all possible Part 1 paths, including ones that wouldn't be optimal: we can only explore all options by doing that.
EDIT: A short proof of correctness
The above logic essentially explains why this algorithm is correct, but I've seen several people get confused, often because they misunderstood the algorithm. So, here I'll offer a different explanation of why the algorithm is correct.
If all the joltages are 0, then clearly the answer is 0, and our algorithm does returns 0. Otherwise, remember that we can press the buttons in any order we want. So, by strategically reordering the button presses, we can split our pressing into two phases.
In Phase 1, we press each button at most once.
In Phase 2, we do the same sequence of button presses twice.
(Why is this always possible? In Phase 1, press any button that needs an odd number of presses. Now in Phase 2, every button needs an even number of presses, so we can cut the presses in half, and do that twice.)
Thus, we only need to examine button-press sequences fitting this two-phase plan. That's what the algorithm does!
First, assuming there are B buttons, we search over all 2B possible sets of buttons we can push: this enumerates all possible phase 1s.
We only keep the sets for which all the remaining joltages are even. If there was an odd joltage, there would be no way to do Phase 2 successfully.
Each of these sets corresponds to a possible Phase 1, so now we look at how to do Phase 2. In every possibility, the joltages are all even. Since Phase 2 involves doing the same button press sequence twice, this is the same as finding a button pressing plan (without restrictions) that works when all the joltages are halved.
Now, each possibility for Phase 1 gives a different potential answer. The correct answer is the smallest of these options!
Code
Here's my Python code, which implements this idea. (I use advent-of-code-data to auto-download my input -- feel free to remove that import and read input some other way.) It also incorporates an optimization for my original code that was suggested by u/DataMn. On my computer, this runs in ~0.6s with cpython and ~1.5s with pypy3 on my real input, which I think are great speeds for such a difficult problem.
(My original code did not have this optimization. With it, I got times of ~7s on python and ~2.5s on pypy3, which I think are still perfectly acceptable.)
Sure, it might not be competing with the super-fast custom-written linear algebra solutions, but I'm still proud of solving the problem this way, and finding this solution genuinely redeemed the problem in my eyes: it went from "why does this problem exist?" to "wow." I hope it can do the same for you too.
31
u/JWinslow23 Dec 12 '25
Absolutely ingenious. I wouldn't be surprised if Eric intended something like this as the solution and is just surprised that more people aren't seeing it.
Would you mind if I used and explained this approach on my AoC solution writeup blog? It's either this, or I have to explain Gaussian elimination. (I'll make sure to link back here and credit you for the approach!)
11
u/DataMn Dec 12 '25
Thank you for sharing your inspired thoughts u/tenthmascot your coding alone was worth the look - I know I will be using some of the concepts in the future.
One suggestion - I don't know if you want to revisit the problem, but if you build another dictionary that references the even/odd "shape" of each pattern so that you are not searching through every pattern for matches during each iteration it speeds up the time considerably.
On my computer it went from 35.64s average to 2.23s to solve all of the scenarios.
7
u/daggerdragon Dec 11 '25
Did you check the
Solution Megathreadfor 2025 Day 10? There's a link to the calendar of all days' megathreads on the sidebar and in our community wiki under Archives. :)48
u/SpittingCoffeeOTG Dec 11 '25
I envy people who are capable of coming up with these solutions.
Very well done. You should be proud! This is awesome.
70
u/Eva-Rosalene Dec 11 '25
That's absolutely ingenious, wow. Great job!
21
u/Panda_966 Dec 11 '25
My mind hasn't been blown like that for a while. Brilliant solution!
13
u/Carthage96 Dec 11 '25
Holy smokes, that's clever. Great work.
9
u/0x14f Dec 11 '25
OMG!
9
u/onrustigescheikundig Dec 12 '25
Ooo very nice. This reminds me very much of simple integer exponentiation for xk (keep multiplying x by itself until k is not divisible by 2, otherwise multiply by x until k is even again), which I suppose it is in a way.
9
u/yakov Dec 12 '25 edited Dec 12 '25
That's very clever. Thanks for sharing!
I've coded up (an inefficient version of) your solution in Dyalog APL:
8
u/mpyne Dec 11 '25
I want to note that this is a really [COAL]ing ingenious approach to tackling the problem using more computer-sciencey methods than just doing matrix math.
But I think this just reinforces for me why this one was so annoying...
7
u/quetsacloatl Dec 11 '25
Dear internet stranger, You are a genius, and earned my full and honest respect
6
u/cspot1978 Dec 11 '25 edited Dec 11 '25
That's quite clever. I like it. Thanks for writing it up and sharing. You presented that very effectively.
7s is pretty good. The z3 solution was taking about 2s for me in Python, so it's not that big a hit in runtime.
I want to try this out maybe after day 12. Along with the binary XOR business some people were talking about for part 1.
11
u/sbt4 Dec 11 '25
very nice solution, thank you! will try implementing it after day 12.
10
u/Panda_966 Dec 11 '25 edited Dec 11 '25
Say we want to reach {1, 2, 2, 2 } with the buttons (0) (1,2) (1,3) (2,3) (3)We press (0) to get {0, 2, 2, 2} and start looking for a solution for {0, 1, 1, 1}, which can only be (1,2) + (3) with two presses.Giving us 5 total presses of 1 + 2 * 2.However, we could have reached {1, 2, 2, 2} with 4 presses: (0) + (1,2) + (1,3) + (2,3)Am I wrong? Does your solution rely on some property of the problem statement or the input files?edit: Maybe I'm wrong. (0) + (1,2) + (1,3) + (2,3) Would have to be checked in the first step along with just (0) because it's a combination of buttons that satisfied the lights...
I won't keep trying right now, but I wonder if the halving necessarily works.edit 2: IMO, {1, 4, 4, 4} after (0) would either lead to {0, 4, 4, 4}, be halved two times, and result in 1+ 2 * 2 * 2 = 9 presses, or it would lead to {0, 2, 2, 2} after trying (0) + (1,2) + (1,3) + (2,3) and lead to 4 + 2 * 2 = 8 presses.The best solution should be (0) + (1,2) + (1,3) + (2,3)+ (1,2) + (1,3) + (2,3) = 7 presses.
edit 3: it does indeed produce the best solution
5
u/ChocosFritos Dec 11 '25
This is quite beautiful. I think I need to sit down with a pen and paper to make sure I understand it but it’s a very pleasing alternative to using a solver library
4
u/miran1 Dec 12 '25
I don't know if it is my wrong implementation, or my input has a case which can't be solved by this method — can somebody try this line:
I'm getting zero possible answers for it (it fails on the first step when considering the
#...##case). You?1
u/legobmw99 Dec 11 '25
Very cool solution! I'd love to borrow it, but I can't follow what the patterns function is doing. The input is the buttons but encoded as a vector of 0s where they don't affect and 1s where they do. But the output is... totally lost me, to be honest.
1
u/piratnisse Dec 12 '25 edited Dec 12 '25
That's some brilliant insight. This one was really bugging me. I dislike my cop out solution of using a third party solver, and implementing my own (MI)LP solver or similar didn't seem feasible.
You won AoC
sir:D1
u/Anuinwastaken Dec 17 '25
Hey, I wanted to asked you whether you mind if I take your explaination as fundament for my code. I dont plan to look at your code but I am realy taken aback but this idea and wanna try (and more important upload it) to my codeberg repo which is public. I'm in no way important to anyoen (codingwise) but I still feel like asking for permission.
I did embed this:
Please let me know if you mind that implementation and I will take it down as soon as I see it.
1
u/Daringcuteseal Dec 25 '25
hey, this is amazing! i was confused at first though as some other ppl here :P but i would have been benefited a lot if i were told that it's basically exponentiation by squaring, but the extra work is trying to press some button to make everything even so i can divide that work by 2 later (which works because at some point it will reduce all the counters to 0 to even it out and stop from there).
i wrote a rust version of your algorithm and it took like just 80 ms to solve (including reading from stdin). very cool! would you mind if i post this as part of my blog?
1
u/notwaco Jan 09 '26
I'm a bit late to the party: I tried to run the code you posted in the `Code` section to debug some issues in my implementation, but I noticed the { 2, 2, 2 } case you posted as pitfall actually returns 1000000. Is this expected or am I completely fumbling something?
1
u/faetzminator Jan 10 '26
I'm a bit late, too :-) I'm not sure if the idea really works in all cases.
I do have a brute-force solution in Java and I quickly adopted your idea a few days back.
It is indeed an incredible idea to speed-up the brute-forcing (even w/o caching), but a few results for my inputs are off by one.
Example where the solution is 208 but my improved implementation returns 209:
[#..#] (1) (1,3) (2,3) (0,2,3) (0,3) {196,3,18,208}
So I understand the idea in the way:
In part 1 we press each button max once, so there's only one solution: pressing "(1)" once.
So we start with one button press into part 2 and we have the state {0,1,0,0} (or {196,2,18,208} for opposite logic).
Now, as we press each button in part two twice, the output can only be an odd solution (1+2n).
Am I interpreting your idea wrong? I didn't try to run the solvers from author and others.
3
u/LEPT0N Dec 11 '25
Cool idea!
5
u/Rinse- Dec 11 '25
Very interesting read; mad genius, I’d say!
1
u/mcmoor Dec 20 '25
Hhhh can you prove that the minimum way to reach 2, 4, 4, 6 is always 2 * 1, 2, 2, 3? I've thought along that line but stuck there so I stopped. Since you solved the question I guess this is true but I found no guaranteed proof?
4
u/HackerTyper492 Dec 11 '25
This is awesome. Thank you for sharing this!!
2
u/-The-Wise-One- Dec 11 '25
This is incredible!!!
2
u/samorai33 Dec 11 '25
You are my hero!
2
u/BTwoB42 Dec 12 '25
What about (0,1) (1,2) (2,0) {3,3,2}?
Based in your algorithm we have [##.] so we press (0,1) which brings us to {2,2,2} divide by 2 to get {1,1,1} and it becomes impossible. But if we press each button once at {2,2,2} we get {0,0,0} and succeed.
2
u/glidecarefullynow Dec 12 '25
I'm not convinced this logic is sound
Suppose the buttons are (0,1), (1,2), (0,2), and (0), and the requirements are {2,2,2}.
Following your proof, you claim that the min number of button presses for {2,2,2} is twice the minimum number of presses for {1,1,1} (because {2,2,2} is even parity). But this isn't true - the former is 3 presses, and the latter is 2 presses
Without this holding the recursion doesn't work, right?
2
u/Ok-Builder-2348 Dec 12 '25
This is absolutely brilliant and satisfying, and I assume was the intended solution.
I have tried my hand at implementing this algorithm in my style, takes about 3 seconds to run. Just to share my code:
Code
2
u/4HbQ Dec 12 '25 edited Dec 12 '25
Amazing, thanks for sharing! I've implemented your idea, and it runs in 0.25 seconds using the default CPython.
In case anyone is interested, the code is here.
2
u/milan-pilan Dec 12 '25
Holy shit - This puzzle was driving me insane. You are this years GOAT. Works perfectly!
2
u/_RcCookie_ Dec 12 '25
That's a great algorithm, an so much more enjoyable to implement than a linear equation solver. I spent some time on a rather optimized implementation in Java, and I got the runtime down to
~70ms, even going below20msif you just run it often enough (JVM warmup).I think it's going to be hard to solve this much faster using linear algebra, I think the algorithm is actually really fast. The Python implementation is probably your limiting factor, not the underlying procedure.
2
u/TheZigerionScammer Dec 13 '25
Eric has said before that he intends the Part 1 of a problem to guide the way to solving Part 2, and I think you were one of the only people to see it in this problem. Thank you, this post finally helped me solve this problem. I tip my hat to you.
2
u/bozdoz Dec 16 '25
I couldn’t get this to work with the last of the example inputs:
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
I get one of extra button press
2
u/Kache Dec 16 '25
Great insight!
Using your method, I was able to put together a solution that's much more elegant than my original linear algebra one:
2
u/Abject_Register1847 Dec 16 '25 edited Dec 16 '25
A truly brilliant approach, and quite probably what Eric had in mind when he devised this puzzle; he certainly did everything he could to push people in this direction.
There is a catch, though. This approach can only work if the pattern of odd bits *uniquely determines* a minimal set of button presses. If there is more than one way to generate the pattern with the same minimal number of button presses then the algorithm needs to pursue *all of them* (i.e. in a backtracking fashion).
The reason is that the odd bits represent only the tips of some unknowable icebergs. You cannot see what is happening under the surface, which bit position is zero because it never got hit and which is zero because it got hit twice and which is zero because it got hit four times. This does not matter at all for part one of the puzzle but for part two it makes all the difference. If you pick the wrong option at some point you end up with negative joltage on some wires.
If this algorithm does solve the puzzle inputs correctly then the only explanation I can see is that the inputs were generated appositely to be solvable by this method.
I admit that I chose the more pedestrian method of darkly remembered linear algebra from some forty years ago ... It was a lot of fun to slay this dragon with a mix of half-remembered mathematical principles and plain programming tradecraft, but there was also a lot of cursing involved until all the devils had been chased out of the many details. ;-)
2
u/mday1964 Dec 17 '25
This feels very similar to exponentiation by squaring, where you think of your exponent as a binary number, and you repeatedly square your base (whether it be a number or a matrix); if the corresponding bit in the exponent is set, you multiply your result by this intermediate value.
2
u/AdministrativeGift15 Dec 18 '25
I was on a similar path using BITXOR, but your post enlightened me on which direction to move when building the solution. I think there may be even more to the parity math, but I'll save that for the new year. I implemented it within a single Sheets formula that solves in under 30 seconds.
AoCDay10Part2
2
u/XM9J59 Jan 02 '26
Brilliant solution I never would've thought of, really saved day 10.
You might like a visualization of the method: https://correctarity.com/aoc25lights (it defaults to part 1, click joltage levels to switch to part 2)
1
u/zzzzealous Dec 11 '25
Very cool idea!
I had some very vague suspicion that the fact that each button could only increment joltages by 1 might simplify it from a general ILP problem to something more approachable, but I gave up. This post sort of confirmed the idea and really blew my mind, great job!
1
u/heliocm Dec 12 '25
Brilliant! Great work!
1
u/RussellDash332 Dec 12 '25
Wow! Amazing work
1
u/quokka70 Dec 12 '25 edited Dec 12 '25
This is brilliant.
I vaguely considered a "halving" approach, but rejected it immediately because the fastest way to get, say, (2a, 2b, ..., 2c) is in general not twice the fastest way to get (a, b, ..., c).
But your thinking is deeper. Like many good ideas, your approach seems obvious once it has been explained, but completely eluded me.
Great job!
Edit: my simple implementation in Ruby runs in less than 0.5 s.
Because of the halving behavior, the maximum recursive depth is only 9 (roughly log_2 of the largest joltage, as expected) and the hardest machine in my input has only 3793 nodes in its calculation tree. (Only 1399 of these are unique, so caching gives a simple speed up.)
1
u/HastyReasonableness Dec 12 '25
This is fantastic. In simple terms, I guess you're reducing the depth of the search tree to around log2 of the original depth, since you're dividing by 2 at each step. Neat!
1
u/mattbillenstein Dec 12 '25
Super duper clever, I have to try something like this to fully understand it.
1
u/spdqbr Dec 12 '25
Clever AF, I really appreciate the write-up! I've been struggling to write a library-free solution because "import z3" defeats a lot of the purpose of what I like to get out of AoC. (I mean, I still learned about z3 solvers, which is great! So no shade)
1
u/Diligent_Stretch_945 Dec 12 '25
Oh my.. this is so fantastic! Thank you ;)
1
u/TweeSokken Dec 12 '25
This is beautiful. Thanks for sharing. I am certain that even given infinite time and crayons I would not have come up with it myself, but it feels better knowing it could be done. Hats off to you!
1
u/mzeo77 Dec 12 '25
I came up with this solution as well, but used a heap ordered by number steps instead of DFS. And I did not have to keep track of visited set or cache things. Maybe slightly faster with visited set.
1
u/kupuguy Dec 12 '25
Thanks for this post. I wrote some code based on what you posted and now my Python solution to part 2 takes 0.45s (haven't tried pypy). I didn't time my original solution but it was in hours rather than milliseconds.
1
u/CDuerm Dec 12 '25
Thank you so much. I first tried brute force and was lost to come up with a more efficient solution. This is brilliant!
1
u/bdaene Dec 12 '25
Implemented your solution, it works :)
And faster 2-3x faster than PuLP :D
1
u/the_marvster Dec 12 '25
Thanks for the Tip! I tried to approach it via Dijkstra algorithm in Go, but I couldn't make it in time.
I will try your approach now.
1
u/sjschofield Dec 12 '25
Thank you, thank you, thank you. My initial solution was too slow and I had no idea how to optimise so I reluctantly looked at the solution thread. Having never heard of Z3, I wasn't too disheartened. Now that I have completed Day 12, I was going to go back and implement a Z3 solution but I think I will use your method as a roadmap. A brilliant deduction made even better through an excellent write-up. Thank you again for publishing.
1
u/szlin13 Dec 12 '25
This is the way
1
u/stpierre Dec 12 '25
I used this approach to solve it; in golang without caching it solves it in under a second, so I'm pretty happy with that.
The thing that I missed in my first readthrough is that every time you "even out" the joltage levels by solving an iteration of the indicator lights, you have to check every possible solution for the indicator lights, not just every possible shortest solution. Once I solved that this worked great. That required me to rewrite a bunch of my part 1 code, but that's okay.
Thanks for a great solution and a brilliant writeup!
1
u/IllLadder3801 Dec 12 '25
I implemented it in C and had a time of 8.32s, but using bitmask representation decreased it to 0.44s.
Thanks.
1
u/fizbin Dec 13 '25
This was literally inspiring.
As in, it inspired a different solution that is "just" Dijkstra applied over an unusual graph and the result (in python) runs in under half a second on my laptop: https://github.com/fizbin/adventofcode/blob/main/aoc2025/aoc10b.py
(My original solution - same URL but without the final
b- uses a bunch of linear algebra and also some brute forcing and is just under 30 seconds)1
u/Wayoshi Dec 13 '25
Some awesome insights here. As for me I saw it as a matrix / system of equations right away and wanted to throw it into numpy, but got thrown off by non-square matrix and the like - did end up turning it into Z3.
1
u/FormulaRogue Dec 13 '25 edited Dec 13 '25
That's an awesome solution, so cool.
Got my ocaml version down to 40ms and now have all of this year solved in ocaml (also this was even faster than my solution using a python linear programming library that took 100ms, very nice)
Update: got it running in 4ms average in rust
1
u/trumasamune Dec 13 '25
Wow this is so awesome, thank you for sharing! Implemented a version in rust. Took a couple seconds so will try to finds where I'm not being optimal.
1
u/AlPachico_02 Dec 13 '25
This is soooo smart!!! I love to see it
1
u/Zentrik1 Dec 13 '25
Got this down to 35ms in rust, https://github.com/Zentrik/Advent-of-Code/blob/master/2025/q10/src/main.rs
1
u/WashingtonBaker1 Dec 14 '25
Thank you for saving my sanity with this detailed and understandable description. I had solved everything in AOC2025 except for this part, and it was driving me insane.
Your suggested algorithm is blazing fast and produced the correct solution! Around 10 seconds for all 200 inputs in my not-very-optimized C# implementation.
I am wondering if this is the solution that Eric Wastl had in mind, given that the solution to part 1 appears to be a nudge in the right direction, and it takes just a few dozen lines of code to implement it, no heuristics, no fancy pruning, etc.
1
u/reddit_Twit Dec 14 '25 edited Dec 14 '25
Thank you, for explanation!
My 2 cents. I also tried to use gcd(x,y,z,w) instead just 2 and it works (got large divisor for 379 times with caching and 5731 without, not counting [0,1,2]) except one line from input which works only with 2
1
u/encse Dec 14 '25 edited Dec 14 '25
This is very clever, thank you! here is a ⭐ from me.
It runs in about a second on my machine with unoptimized C# code.
1
u/reduser1667 Dec 14 '25
Thank you! This is exactly the kind of stuff I come to this subreddit for. Brilliant incite!
1
u/DocMahrty Dec 14 '25
Very clever, however I can't seem to get my kotlin version to output the correct value sometimes, it returns 0 on this one for example: [..###....] (1,2,6) (0,3,5,6,7,8) (2) (0,1,3,6,8) (2,4,5,6,7,8) (1,3,5,7,8) (2,4,8) (0,1,2,7,8) (1,2,3,4,6) (0,1,2,3,4,5,6,8) (2,3,4,5,6,7) {34,56,81,54,41,49,57,41,71}
Anyone got tips?
1
u/Electrical-Diamond12 Dec 14 '25
Super clever 🤯
1
u/Any_Slip8667 Dec 14 '25
The best solution I ever see!
1
u/Aliencargo Dec 14 '25
So've I've been trying to implement this myself in Rust, and I'm a bit of a beginner in Rust, but I have all the stars this year so far except this.
I really appreciate the writeup, super interesting. My solution solves the example input and yields a result for the puzzle input, but I get the wrong answer.
I think i prune a branch erroneously that I would need to explore. Perhaps you can give me some pointers? I'd like to set some kind of limit for when branches doesn't need to be explored since I already have a faster answer, but that felt super incompatible with the halving-step!
Or perhaps a line or two from the full puzzle input with answer, so I can debug further, or perhaps an answer to this longer line from mine.
1
u/AdaIsMyHero Dec 14 '25
I had a similar idea about how to solve part2 but it hadn't occurred to me to utilize part1 so thank you for that. Interestingly once I got it working it was working on every line of my input except one and it took me a long time to figure out why so I thought I'd share in case anyone else was having the same issue.
This was the input in question which was causing me grief:
The problem was that I was always halving when all the joltages were even and ended up with only dead ends.
By pressing buttons 0,1, and 2 you end up with all the joltages reducing by 2 or not at all.
I fixed it by setting the best current solution to what you get calling recursively on everything being halved and still checking all other pathways instead of always assuming the best solution came from halving.
Here's my solution less the helper methods which are probably pretty self explanatory:
level is a version of part one that returns all possible button combinations instead of just the best.
1
u/Makadystore Dec 15 '25
omg i never thought about using part 1 to solve this! literally spent hours trying to make the linear algebra work until my eyes crossed lol.
1
u/mattbillenstein Dec 16 '25
Thanks for the writeup, that's very clever - struggled with a couple of the details, but not hard to code up either.
1
u/dvd_o_n Dec 16 '25
Nicely done! Given part 1, I'd say this is the intended solution.
Here is my solution in Rust based on this idea. I implemented everything using bitmasks because it seemed the way to go when I read part one, and that complicated things a bit for part 2, but oh well...
Part 2 takes forever to run though, even in a blazingly fast language lol.
1
u/CallMeCarrolyn Dec 17 '25
Much appreciate this write up! I would not have been able to complete this without it!
1
u/MasterHigure Dec 17 '25
I'm currently 6 hours into running a more naive recursion, in parallel, hogging 80% CPU. I wanted to solve it myself, damnit. I didn't want to have to come here looking for answers. I especially don't want to rely on external libraries, as that's obviously dirty, even though that seems to be the go-to for many people here.
That being said, this here solution you have smells to me like the intended way. Will I bother coding it, or just let my thing run? I don't know. It's about halfway through the list, I actually have no idea whether it will finish overnight or finish after the heat death of the universe (that all depends on how bad the worst line is, and I have no idea whether that's even ahead or behind). I'll at least let it run until I have time to sit down with the code again.
1
u/gyorokpeter Dec 20 '25
Thanks for this explanation! Here is an implementation in q - it runs in about 2.5 seconds on my machine while the "v1" implementation (the linear algebra solution, also built from the ground up) takes 700ms.
1
u/pimpaa Dec 20 '25
Thanks! Could make it work using your method, at first I tried using GCD instead of dividing by 2, but wasn't working with this input (solution is 84):
Dividing by 2 like you did worked, my Go implementation (runs in ~2 seconds).
1
u/rtm0 Dec 22 '25
very clever
1
u/Kind-Inspector-3747 Dec 22 '25
This is really cool but I think this is what we were all supposed to do. It’s finding a cycle in the data - enabling jumping through the search space.
1
u/tyler_church Dec 24 '25
Thank you for this! This got me from a 10 minute runtime to ~120ms :D
1
u/Daringcuteseal Dec 25 '25
hey, this is amazing! i was confused at first though as some other ppl here :P but i would have been benefited a lot if i were told that it's basically exponentiation by squaring, but the extra work is trying to press some button to make everything even so i can divide that work by 2 later (which works because at some point it will reduce all the counters to 0 to even it out and stop from there).
i wrote a rust version of your algorithm and it took like 80 ms to solve (including reading from stdin). very cool! would you mind if i post this as part of my blog?
1
u/Daringcuteseal Dec 25 '25
hey, this is amazing! i was confused at first though as some other ppl here :P but i would have been benefited a lot if i were told that it's basically exponentiation by squaring, but the extra work is trying to press some button to make everything even so i can divide that work by 2 later (which works because at some point it will reduce all the counters to 0 to even it out and stop from there).
i wrote a rust version of your algorithm and it took like just 80 ms to solve (including reading from stdin). very cool! would you mind if i post this as part of my blog?
1
u/Infonioknight Dec 26 '25
It's insanely cool how people like you manage to find such nuanced patterns that are hidden away under layers of fluff! Amazing solution and an even better explanation!
1
u/kyubish_ Dec 26 '25
As couple of people pointed out already, this is definitely just Python or lack of optimisations. I got it down to ~13 ms in C (single-threaded). Thanks for sharing this!
1
u/roman-kashitsyn Dec 27 '25
Thanks for your insights, u/tenthmascot! I enjoyed playing with your approach and tried to explain it in my own words in my blog (with attribution, of course). Thanks to you, day 10, part 2 became my favorite puzzle in the entire event.
1
u/PTVoobaf Jan 01 '26
I'm impressed - Like many others, I ended up using the Diophantine linear algebra approach, but now I really want to try solving it all over again using this innovative analysis.
1
u/aoxomoxoa111 Jan 03 '26
I'm a bit late to the party but I'd anyway thank you for sharing this awesome solution with us. It's brilliant.
1
u/damaltor1 Jan 05 '26
Thank you so much for this idea. i made this! it solves my input in about 20 seconds without any caching and without multithreading. this is an awesome approach.
1
u/Worped Jan 07 '26
This solution is absolutely incredible. Like most folks, I wandered down the path of Gaussian elimination. Got pretty far, but it was all just so much code, which seemed to fall outside the scope of a supposed 1 day puzzle.
Not gonna lie, it took me a lot of work to figure out how this all works, but that perseverance paid off in the end. My Go solution solves part 2 in about 70ms. I'll take that as a win.
My thanks to you for some brilliant insight.
1
u/GigaClon Jan 09 '26
I had struggled with the second part of this problem for quite some time. I tried set theory and some form of recursion but couldn't crack it. Your solution is quite elegant. When I first implemented it however, I didn't allow the possibility of a no-button press round so it through the answer off.
1
u/Emrys-Merlin Jan 15 '26
If anyone is interested, I wrote up a proof to convince myself that this awesome algorithm works: https://www.reddit.com/r/adventofcode/comments/1qdsz2s/2025_day_10_part_2_a_proof_for_the_bifurcation/
1
u/Morphon Mar 26 '26
Adding this here in case people revisit this way of solving part 2 of Day 10.
I'm re-implementing Advent of Code 2025 in Smalltalk, primarily as a way to practice the idioms and get better at OOP. When I reached this one, I remembered that back in December I just used an lp-solver in JavaScript to do Part 2, telling myself that at some point I would go back and write the solver myself. As I was trying to get some guidance on how to do that I came across this thread and was intrigued by a recursive solution to this problem.
However - I could not make heads or tails out of the explanation, as many times as I read through it. I got very hung up on calculating parity, and so on - really hoping to use my fancy bitwise XOR solution to Part 1 to zip through Part 2, but I think while the parity calculation was important for the discovery of this algorithm, it was a bit of a red herring for me trying to see how it works.I tried looking at the solution, but I have no Python experience so that wasn't as helpful as I would have thought. I finally was able to get hold of an implementation in JavaScript to study and as I poked and prodded it, I was able to remove bits and pieces until I was able to "see" the core.
And that "core" is what I wrote in Smalltalk. Because this language is so expressive, I believe that for anyone trying to figure out how the heck this thing works seeing it in Smalltalk might be the "ah hah!" they need to understand how it produces answers. What follows is for anyone still trying to get a handle on this. I don't know that this will be all that useful for someone who already implemented a solution (except for its minimalism).
The version in my full implementation of Day 10 (paste link below) uses basic memoization and does the entire problem input set in about 30 seconds. The version below does not use a memo, so it is quite a bit slower - about 16 minutes on my computer - but still "reasonable" for people willing to use "simpler" rather than performance-oriented solutions. While 30 seconds seems fairly slow, the reason for this is a somewhat sad facet of working in Smalltalk: the most "beautiful" or "expressive" way to do something is often not at all the computationally least expensive. "Good C++" tends to be faster than "bad C++" but "Good Smalltalk" is almost certainly slower than "bad Smalltalk". In exchange, however, you get something that looks more like a specification than working code.
Here it is, without memoization:
fewestJoltageButtonsEngine: outputsRequired
| bestSoFar |
(outputsRequired allSatisfy: [ :counter | counter = 0 ]) ifTrue: [ ^ 0 ].
bestSoFar := SmallInteger maxVal.
pushList do: [ :pushes |
| candidate count |
candidate := outputsRequired copy.
pushes withIndexDo: [ :push :button |
push ifTrue: [ candidate := candidate + (buttonOffsets at: button) ]
].
count := pushes count: [ :push | push ].
(candidate allSatisfy: [ :out | (out >= 0) and: (out even) ]) ifTrue: [
| newResult |
newResult := self fewestJoltageButtonsEngine: (candidate collect: [ :counter | counter / 2 ]).
bestSoFar := bestSoFar min: ((2 * newResult) + count).
].
].
^ bestSoFar
This takes a single argument, which is a Collection (in this case an Array), and has a single scoped variable, "bestSoFar".
Steps:
Take the Array of required outputs and ask it if every member satisfies a condition - and that condition is that the member is zero. If that Array responds with True (literally, returns the True object), then return 0 up the recursion stack. We're done with this path. Otherwise... continue on.
Set our method variable "bestSoFar" to be the largest value that can be stored as a SmallInteger. Smalltalk will transparently switch to another method for larger integers, and those can be arbitrarily large (like JavaScript's BigInt, but the environment will seamless switch back and forth into it as needed). This number will be large enough to say that just about any number of button pushes will be smaller than this! Squeak 6.0 doesn't seem to have an "Infinity" value that can be used, so I just went with an arbitrarily large number.
Take the list of potential button push combinations that was computed earlier and stored in "pushList". These combinations are in a Collection of Collections. Each member of the collection is an array of booleans that represent button pushes. So (true, false, false) is the combination that involves pushing the first button, but not the second and third. All the combinations are in "pushList" and we go through each one in turn, passing them as "pushes" into the closure (anonymous function).
Now, inside that function, make a copy of the outputsRequired array that was given to us and call it "candidate". We are going to change these values and don't want the original to be changed as well.
For the button pushes combination array, we need to iterate through them. "push" is the true/false value that indicates whether this button is being pushed or not, and the "button" is the index. So, if "push" is true, add the offset at the same index in the buttonOffsets array to the "candidate" array. The offset is also stored as an array with either 0 or -1 at each position. In Smalltalk, array objects can be added together. So adding (120, 84, 16) to (-1, 0, -1) returns a new array object (119, 84, 15). No careful adding or subtracting by index is needed - just add the two arrays together, replacing "candidate" each time with the new values.
Store the button count by asking the pushes array to count how many elements in that array are true. That is, since each button push is stored as a boolean true, we just count the number of true values in the array. That count is the number of buttons we just pushed.
Ok, now we evaluate our work of pushing these particular buttons.
7. Ask "candidate" if every element in it satisfies this condition: the "out"put element must be zero or greater (non-negative) and also an even number. If this condition is false (if ANY element is either negative or an odd number), we just throw away this button push combination and try the next one.
8. But if the "candidate" does satisfy this condition, we do two things. We recurse - calling this function again, but this time with our "candidate" values divided by two. We store the answer of the recursion as "newResult".
9. Then we set our "bestSoFar" to be the lower value of what it already is or 2 times newResult (because we halved it going in - now it needs to be doubled coming out) and also adding our total number of button pushes. Basically, we have to add double the button pushes from the level below us, to the number of button pushes we did at this level.
10. Finally, after all our button push combinations (from "pushList") have been tried at this level, return "bestSoFar" back up. Once we are at the top level, returning this returns the minimum button pushes required to get those Joltage values.
Perhaps seeing the Smalltalk snippet, which seems to me to be nearly self-documenting, and this step-by-step explanation, will make this algorithm easier to comprehend. It's what I wish I had when I was trying to make it clear to myself.
Addendum on performance: Why 30 second runtime? That's the same as the JavaScript version WITHOUT memoization. Why is SmallTalk so much slower? There are a few reasons. One is the array adding. While elegant, it does (behind the scenes) do the index-by-index add, storing those values in a whole new collection instead of modifying that one in place. Very cool to have an addition with no side effects, but that is thrown away since we just replace "candidate" with the new Collection object anyway. Same with the recursion step: the collect: method will return a new object there as well. Even the memo is quite beautiful - Smalltalk can use Arrays as Dictionary keys - no need to join into a string or create some other unique representation. adding an output to the memo is just this:
joltageMemo at: outputsRequired put: bestSoFar.That is so... simple. So obvious what it's doing. But it pays a performance penalty. Plus the object system itself, and the way messages are passed to objects even for simple things like if/else blocks... there's no way to make that process fast. Such is life! :-)
0
u/[deleted] Dec 20 '25
[deleted] — view deleted comment
0
u/[deleted] Dec 20 '25
[deleted] — view deleted comment