https://adventofcode.com/2025/day/11
8267 paths from DAC to OUT
Bajillion paths from FFT to OUT
20,785 paths from SVR to FFT (reverse search)
Bajillion paths from SVR to DAC (reverse search)
So SVR to FFT. I don’t think there are cycles (?) so just need FFT to DAC. Multiply SVR to FFT, FFT to DAC, and DAC to OUT.
Number of nodes in the frontier starting from SVR.
0 4
1 35
2 91
3 229
4 644
5 1712
6 12320
7 60338
8 152311
9 379047
10 1234446
11 4557127
12 13741500
13 34334142
14 75600783
15 236311299
16 1015883428
After that it slows down too much.
From FFT.
0 5
1 7
2 10
3 116
4 239
5 453
6 1215
7 2556
8 21415
9 74616
10 176558
11 450420
12 1542639
13 4542210
14 19500438
15 61854057
16 155740859
From DAC.
0 2
1 4
2 11
3 143
4 310
5 684
6 1526
7 3788
8 8267
9 8267
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
DAC is only 9 levels away from OUT.
Backwards from OUT.
0 18
1 42
2 105
3 229
4 539
5 1160
6 2221
7 28873
8 75541
9 177723
10 314127
11 1628138
12 3616326
13 25949478
14 61589280
15 169624925
16 394163183
Backwards from FFT.
0 3
1 9
2 25
3 387
4 1103
5 2788
6 7298
7 15437
8 20785
9 16157
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
Backwards from DAC
0 1
1 2
2 2
3 32
4 78
5 186
6 400
7 1874
8 4570
9 24714
10 53696
11 122382
12 360278
13 981708
14 4056712
15 12963462
16 41927610
17 152209460
There are sooo many paths between FFT and DAC. Damn. I noticed the paths being picked up were 17-18 nodes deep so I set a max depth of 20 but yeah, it’s taking a looong time. Might be on the order of minutes instead of hours at least, based on how long it was taking to find paths between SVR and FFT and then DAC and OUT.
Max depth of 15 yields zero results in 2.5 seconds. 16 is 35,360 in 9 seconds 17 is 113,866 in 30 seconds
I guess I’m expecting 18 to take 1.5-2 minutes?
18 is 711,296 in 1:11
If I get the same amount twice in a row then I’ll know my answer, right? I would make a bet on that for a puzzle dataset, anyway. (-:
The answer should be 20,785 * X * 8,267 = 171,829,595 * X
19 is 1,859,248 in 3:41
20 … I should wait at least 12 minutes for that. I’m pretty surprised the pattern of multiplying the time by three for each depth is holding relatively well. I guess the size of the search tree is increasing by that amount, too?
Making these puzzles… you must get really good at calculating complexity.
Aha! Same answer!
19 and 20 are both 1,859,248. And it took 11:55 so the time complexity is still consistent.
So the answer should be… 3.194739683×10¹⁵?
Uh oh. That’s probably too big if I can’t even get the calculator to give me the number.
1859248 * 171829595 = 319473830844560
Oh phew! It was correct.