https://adventofcode.com/2025/day/10
This is the one where you’re trying to match the indicator lights on the left (part 1) and the joltage requirements on the right (part two) by pressing buttons (middle).
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
Part 1 wasn’t too bad. But the search space isn’t too big. Part 2 is definitely going to cause some search space issues. My implementation of part 1 already took several seconds to complete and that was for 500 total button presses (many more were explored, true). Part 2 is going to require many more.
So how do I approach this?
When searching the space, I can eliminate states from the frontier if they have a number which exceeds the joltage targets. There’s no way to reduce numbers, only increment them so that will reduce the search space.
I could easily write a distance function and assess how quickly a button press is converging on the target. But it won’t help detect whether I’m painting myself into a corner.
Are there other ways to assess the value of a given state relative to the target joltage schematic? Like, is it better if all the joltages are a similar distance away? Probs not…
But if I use a distance function, my search will probably press the button that increments the largest number of joltages as many times as it can, then find the button with the next largest impact… this is a decent approach, I think.
Work backwards as well as forwards?
I’ll start with a best-first search using the total difference of all joltages as the value function.
…
For the value function, I’m squaring the difference so that moving faster toward the highest joltage targets is encouraged (as opposed to just moving toward any joltage target).
…
Oh my life. Even with best-first search, one machine is taking forever to complete.
[#..#.#.#.] (1,3) (1,8) (0,6,7,8) (0,2,3,7,8) (1,2,4,5,6) (0,2,3,5,6,7,8) (1,2,3,5,6,7,8) {41,41,44,60,4,28,36,48,58}
The target joltages are as high as 60 so there are at least 60 button presses required. There are 177 machines. I’m timing how long this first one takes so I can get a benchmark.
Some ideas for improvement:
- I can use binary representations of buttons and states.
- I can stop tracking button presses… or maybe just print them when the recursion rolls up. With the number of button presses required for the real problem input it’s not really gonna help me with troubleshooting.
- I can try other value functions.
- Or a faster programming language.
…
Wow. It’s been more than fifteen minutes. At least it hasn’t crashed my computer. I wonder whether there’s a completely different way to look at it. I’m really not expecting massive improvements from any of the above, I wouldn’t think.
I gave up waiting after 22 minutes. Let’s try it out on a smaller machine from the same set.
…
There are a lot of machines where I find the solution very quickly. Machines with target joltages in the 20s and 30s. Upwards of that it starts to slow down a lot.
That said, I like that the following machine actually resolves pretty quickly even though the search space is huge because of that 157.
[.##.] (0,1) (0,1,3) (1) (2) (0,3) {14,157,2,14}
The best-first search is definitely working.
This one takes a reasonable amount of time:
[..###] (0,1,3) (1,4) (0,2,3) (0,3,4) (1,2,3) {23,26,4,27,17}
Maybe I can use that as a benchmark. 4.77s to find 35 button presses.
Not tracking the button presses gets me down to about 4 seconds. That’s actually pretty significant. I’ll also try converting to a binary implementation now… oh wait, that only made sense for the metric indicators.
…
More ideas for improving the implementation, courtesy of actual shower thoughts:
- Decrement joltage targets instead of tracking two sets of values. Maybe not that helpful.
- Discard buttons that would produce invalid results. So, say I have already reached the nth joltage target, then any buttons which would increment
nare no longer useful to me so I should discard them before searching the rest of the tree. - If I’m discarding buttons it might make sense to change my search strategy. Prioritize pressing buttons that will allow me to discard a button. That could get to a result faster, however there’s a big downside: it might not be the smallest number of button presses.
- Memoization.
is_valid_state()for example might benefit from this a lot. Alsoget_state_value().
I switched to decrementing even just for simplicity’s sake. It did speed it up, I’m getting around 3 seconds on the input from test2.txt.
Button discarding… I wonder how much it’d actually come into play. I don’t want to change my value function to try to discard early because it will miss smaller numbers of button presses. It could be a secondary part of the value function, I guess.
I’ll try implementing it. It might actually increase the amount of time spent iterating arrays rather than decreasing it.
…
Yeah, with button discard it’s actually a little worse, at least for the one test case.
…
Nice thing about memoization is it’ll improve performance for all machines.
Okay, new benchmark test3.txt. Has 8 examples (machines). With button discard it takes 5.37s. Without: 4.84s
I tried with a button check interval. At certain depths in the search I’ll see if there are any buttons that can be discarded. Right now I do it when the depth is a multiple of five. That got me down to around 4s.
…
Hmm, these are all relatively small cases. When I throw this at the first machine in my actual puzzle input it still takes over twenty seconds. Possibly much much more.
Okay, wait. There are 177 lines. Say I’m willing to wait ten minutes to solve the problem. 600 seconds. So I need each to take less than 3 seconds. Sure I just did 8 machines in 4 seconds but those are smaller target joltages. I still haven’t addressed the problem of these massive search spaces.
I’m optimizing too early? Is there another way to tackle this problem?
…
Okay, memoization needs some work. My state which is the remaining joltage values is a list right now and I can’t hash on that.
…
Taking a step back a bit.
What about pressing the same button several times. Maybe even as many times as I can. Then pressing other buttons as many times as I can.
Or combining some buttons together?
…
Trying to understand more about the problem now.
Seems like for that troublesome first machine in my puzzle input the search hovers around ~70 presses. Actually, that’s just from outputting one in every 100,000 entries so not sure how accurate that is. I’ll print low/highs.
Just realizing. It’s kinda stupid to pick ordered solutions from the set. Like, when pressing buttons, it doesn’t matter if I press [0, 1, 1, 3, 5] or [0, 1, 3, 5, 1] but I’m treating them as separate states in the search tree. Is there a way to change the search tree so that doesn’t happen? Like maybe I press button 0 a bunch of times, then discard it and never press it again. I press 1 a bunch then throw it away. I always go in ascending order. Then I can’t use my value function but wouldn’t it dramatically reduce the size of the search tree?
Also, why do I get 74 for the high number of presses and -82 for the highest value? Shouldn’t those high values be changing as much as the low values. Okay, not as much but at least changing at all? Maybe it’s because those are the highest values over 100,000 states but it seems weird.
Okay. So it is getting to the same state all the time. Oh boy. Is it using different button presses to get to that state??
Okay, phew. At least it’s using different button presses to get to those same high states.
56565656565656565656565656563333333333333333000101200101010010021101122000 56565656565656565656565656563333333333333333000101200101010011102010221000 56565656565656565656565656563333333333333333000101200101010012000101001110 56565656565656565656565656563333333333333333000101200101010020221100010101 56565656565656565656565656563333333333333333000101200101010111012012200000 56565656565656565656565656563333333333333333000101200101010110021110210000 56565656565656565656565656563333333333333333000101200101010100011100202201 56565656565656565656565656563333333333333333000101200101010101110002000110 56565656565656565656565656563333333333333333000101200101010102112000101200 56565656565656565656565656563333333333333333000101200101010120101021000102 56565656565656565656565656563333333333333333000101200101010211201100100010 56565656565656565656565656563333333333333333000101200101010200020000111001 56565656565656565656565656563333333333333333000101200101010201200101012001
But that kinda confirms what I was saying before about making different arrangements of the same button presses different states. So. Let’s do something about that.
This means I’m gonna have to search the entire space, though, no? Because I’m not taking the biggest steps or… maybe I take the biggest steps first and then retreat from there.
Yeah, okay, so order the buttons with the ones that produce the biggest increases in joltage first. Press the biggest one until I can’t anymore, then the next biggest, etc. But once I’ve pressed another button, never go back to pressing that one again.
I’m sure eventually I’ll use up that space with the maxed out biggest button and have to retreat a bit.
What if there are two biggest buttons? And pressing one of them gets me to a solution that has fewer button presses than the other?
Hmm… okay, let’s trying searching the whole tree first then see if I need to be fancy later.
..
Another approach might be, when I’m rolling up from a dead end, cache the ordered list of button presses that got me there. That way I don’t have to check all combinations of those button presses but I can still follow my value function.
Okay. First time I was ever able to produce a result for the first machine. It still took 12 seconds but that’s less than 12 minutes or whatever I let it run before. Still no idea how long it would’ve taken to complete.
I’m running it on the full puzzle input now but realizing there are cases that are much much worse than the first. The largest joltage in the first puzzle is 60. I’m stuck on one right now that has a joltage of 114. There’s another a few rows down with a joltage of 235.
The way I’m going about this right now is very naive. So say it presses 0 a bunch of times. Then it has a whole bunch of search space to get through before it realizes maybe it should press 0 one less time. And then it has to go through and search everything again. I think caching the rollups is probably a good way to go. At least get through all that search space faster.
How does that even work? Is it like, I had a state with this much joltage left: 7 4 0 0 3 1 and I had these buttons available to me: indices 5, 6, 7. And it was a dead end. So first part of the cache can be the button index. The remainder can be the state. And the cache just indicates that it was a dead end. Then I can skip dead ends earlier and earlier. Okay.
…
Lol I get no cache hits so it’s just slowing it down.
I just watched 50 seconds of the algorithm searching through the combinations of key presses. The end result doesn’t have the buttons with the most keypresses on the left. Is that okay?
0000000000000000011111112222222222222222333344444444555555555555555555556666666666
Can finding factors help us get to a solution?
Or what about sorting the buttons by how much they match the joltage targets?
Say, at the tail end, I only have one button left. It’s the one that increments 1 and 3. I should be able to look at a number and say, “if I decrement index 3 N times to bring it down to zero, then index 1 is going to be negative (invalid).” Or even “index 1 and index 3 need to be equal for this to work.”
That’s only the tail end so it won’t save too much time but can I extrapolate that?
If I only have buttons (1, 3) and (1, 8) then my state needs to have remaining joltages in indices 1, 3, and 8. And the joltages in 3 and 8 need to add up to the joltage in 1.
If I have (1, 3) and (1, 8) and (0, 6, 7, 8) … only one button can affect indices 0, 6, 7 so the joltages in those indices need to be equal and the joltage at index 8 needs to be same or higher.
The constraints are a little too much to wrap my brain around. I know I’m missing some.
One more iteration. 0,2,3,7,8 is the only one that could affect 2 so the other indices in that button need to have a joltage at or higher than 2.
Two things I’m getting from this:
- When there’s only one button that can affect an index, I can detect a dead end if the values at the other indices in that button are lower.
- If there’s only one button that can affect a given index, skip a bunch of work and just press that button until it meets the joltage value at that index. That sort of has the same effect as the first point, I guess.
Oh, I can detect a dead end early if there are no buttons that can affect a given index and the joltage is not zero.
…
Oh wow. I just added jumping. I check if the current button has a state index that only it can affect and if so, press that button to meet that joltage requirement for that state index. It executed the slow problem in 0.16 seconds.
And I can see from the debug output it did get called a bunch of times.
Ah damn, still getting stuck on the third machine in my puzzle input, though. That one has so many buttons that affect so many things it probably doesn’t have a chance to jump too much.
[..##...#.] (0,1,2,3,4) (2,3,4,5,6,8) (0,2,3,6,7) (1,2,3,4,5,7,8) (0,3,4,8) (1,2,3,4,5,6,8) (0,4,5,6,7,8) (0,1,3,6,8) (1,3,5,6,7) (0,3,5,7) {78,66,64,114,75,62,62,62,70}
The jumps are definitely accelerating the search but it’s not enough.
^ date line. It’s 2025-12-11 now.
How many times does each button factor into the joltages target and with what remainder? And then how does that relate to the actual result?
What about another kind of jump. If all remaining values are a multiple of 2, 3, 5, 7, or 9 then divide them all by that and multiply any additional presses by that.
…
Oof well that’s disappointing.
Result: 17785
./main.py input.txt 53028.53s user 31776.58s system 99% cpu 23:45:03.73 total
23 hours 45 minutes total run time to get the wrong answer! Noooo!
Brutal.
I wonder how that even happened, though. Shouldn’t it not be possible..?