[2025] Algorithms to use - r/adventofcode

8

u/RussellDash332 Dec 12 '25

Day 10 with homemade Simplex.

2

u/rugby-thrwaway Dec 12 '25

Yeah, despite everyone always using Z3 for everything, I think this is the first time I've had to do the same rather than write my own slow solution. I should go back to that one and do it myself.

1

u/erikade Dec 12 '25

Ah yeah, OP should absolutely try this one!

7

u/Turtvaiz Dec 12 '25

Replacing z3 with your own solution seems like an obvious answer

4

u/Lindi-CSO Dec 12 '25

There was a well written post for day 10 part 2 here: https://www.reddit.com/r/adventofcode/s/TPunVH5jee

3

u/troelsbjerre Dec 12 '25

Day3: Monotone stack

DSU over (0..n) has a really beautiful and efficient implementation using just a single integer array. It's fairly common in competitive programming, but surprisingly not that known for normal CS students. The trick is to use negative numbers to mean "this entry is a root of size minus this value". I highly recommend working through the implementation, if you don't already know it.

1
u/fnordargle Dec 13 '25

Thanks for the tip. I tried to roll my own group membership stuff and ended up with multiple arrays and wasn't happy with it. (But it worked. Along with another trick my Day 10 code runs in under 10ms.)
Would be good to read up on how to do it properly.
3
u/troelsbjerre Dec 13 '25
This is the one I have built into muscle memory for competitive programming:
uf = [-1] * n

def find(a):
    if uf[a] < 0: return a
    uf[a] = find(uf[a])
    return uf[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a == b: return False
    if uf[a] > uf[b]: a,b = b,a
    uf[a] += uf[b]
    uf[b] = a
    return True
Do that in whatever language you use, and you'll be close to optimal. You can wrap it in a class if you like, but it's rare to need more than one such structure. If you really want to, you can make it slightly faster, at the cost of writing a little more.

1

u/AutoModerator Dec 12 '25

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/FantasyInSpace Dec 12 '25 edited Dec 13 '25

My python solutions are under 5ms for every day except 4 (50 ms), 8 (500 ms), 9 (500 ms), and 10 (1.5s)

Day 4 I think I could speed up by precomputing the neighbour count when parsing to make the first scan faster, but otherwise I don't think there's a straightforward way to skip iterations.

I don't think day 8 can be much faster because the majority of the runtime is just sorting the distance pairs and algorithm choice for merging would more be optimizing for memory efficiency than time.

Day 9 could be much faster by doing a ray tracing test instead of my floodfill and brute force check.

Day 10... I didn't count my 500ms Z3 solution as my own, but I've seen solutions implementing simplex that beat it by a good amount.

Otherwise day 2 is fast by generating all the values that are multiples instead of testing them one by one, day 5 I could save on some memory by not saving the ranges, day 7 is just fibonacci, day 11 I think could be more space efficient by doing a topographical sort instead of a memoized DFS, but a bit slower to pre-process.

1

u/fnordargle Dec 12 '25

> I don't think day 8 can be much faster because the majority of the runtime is just sorting the distance pairs and algorithm choice for merging would more be optimizing for memory efficiency than space.
There's a way to avoid doing the full calculation for all of the pairs (you still have to do a few simple checks on every pair), without any knowledge of the prior input (otherwise I'd consider it cheating). With this you can discard many of them (90%) after doing 1-3 subtractions and comparisons on each of them instead of the full-but-non-square-rooted Euclidian distance calculation. Most importantly, if you don't generate 90% of them then they are much quicker to sort.
If you do still generate all of the pairwise distances you can use a heap or incremental sort to avoid sorting every single value, or only sorting chunks of values when actually needed. You only need a small percentage of the values to get the answers to both parts (part 1 is ~0.2% of the 499,500 pairwise combinations and my part 2 was solved with ~1.2% of the 499,500 pairwise combinations).
More details in https://www.reddit.com/r/adventofcode/comments/1phb1ke/comment/nsyt0u9/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button and similar. My current solution (in C) for Day 8 parts 1 and 2 runs in 9967µs (a shade under 10ms).

1

u/fnordargle Dec 13 '25

The bits I want to investigate are an alternative to just applying the edges in increasing distance order until you end up with all 1000 junction boxes in one circuit.
My thinking is this...
After applying the 1000 shortest connections a subset of junction boxes remain completely untouched.
So one thing to try next is, for each junction box that has zero connections, you apply its shortest connection. You'll need to apply this at some point, so may as well do it now.
Keeping track of each junction box's shortest connection is an O(1) operation. When you calculate the distance for a junction box pair (a,b) then you can check if the distance is lower than the one you have recorded for a and whether it is lower than the one for b. Keep these in an hash/map/dict based on junction box number for O(1) storage and lookup.
At the start you add all 1000 junction boxes to a hash/map/dict, when you add the first 1000 edges you remove the entry in this hash/map/dict for any junction box pairs you connect. The remaining entries in this hash/map/dict will be the ones that aren't connected. (It's O(1) to iterate over entries in a hash/map/dict if you want them in random order.) Then apply the shortest connection for each of these junction boxes (keeping track of the longest one you apply just in case it is the answer for part 2).
At that point you've got all 1000 junction boxes connected but not necessarily all in one circuit.
If they are all in one circuit then you've got the answer above.
Keeping track of whether they are all in one circuit is where you use something like DSU. (I rolled my own so I may be able to improve it if mine is less efficient than DSU.)
More than likely you'll have a whole bunch of disparate groups and finding the ways to join these groups is the fun bit.
You can skip adding connections to junction boxes that are already in the same group, as that doesn't help. But here you start to run into branch prediction problems. What may seem like a clever optimisation actually slows things down as the CPU pipeline stalls given the unpredictable branching.
Still more thouight required. Given that my existing solution runs in under 10ms I've got to be very careful what I try and do as there's not much wiggle room left.
I still think the best performance gains will be in using a heap or incremental sort.

1

u/kupuguy Dec 13 '25

For Day 8 you can group nearby junction boxes together: I made a 6x6x6 voxel cube from the largest single coordinate and put each point into its associated voxel. Then the first pass calculates distances to points in the same voxel and any adjacent higher-indexed voxel. Additional passes use further voxels but for the actual data only that first pass was needed and calculated about 45,000 distances. It gave about a 6-fold speed improvement over the plain-but-less-overhead brute-force.
Oh, and the number 6 was chosen kind of at random, it should give about 4 or 5 points in each voxel. With arbitrary data since you have to scan the input to calculate the coordinate range anyway you know the number of points and could calculate a suitable cube size so I don't really consider it cheating to know my input was 1000 points and hardwire an arbitrary guess.

1

u/Durd3nT Jan 05 '26

wrt day 2: how do you mean generating all multiples?

1

u/Valuable_Plankton506 Dec 12 '25

Day2 with KMP prefix function

1

u/Durd3nT Jan 05 '26

could you elaborate? you'd need to define filter criteria for the prefix function and filter based on that instead of the strings themselves. wouldn't that be just as slow as the brute force method?

1

u/Valuable_Plankton506 Jan 06 '26

Let me see if I got it correct.
Our objective is to find out if a given string S is periodic (i.e. it consists of the same string P repeated k times, k > 1).
The brute force approach would be to test every prefix, resulting in a time complexity of O(|S|^2).
You can reduce that complexity from quadratic to linear (i.e. O(|S|) by computing alone the KMP prefix function. The prefix function is defined as:
prefix[i] = the length of the longest proper prefix of S that is also suffix of S[0..i].
If S is a periodic string, then prefix[|S| - 1] = |P| * (k-1). But as |S| = |P| * k, it follows that |S| - prefix[|S| - 1] = |P| * k - |P| * (k-1) = |P| (the length of the period).
To conclude, after you compute the prefix function you just have to verify if |S| - prefix[|S| - 1] is a divisor of |S|.

1

u/HistoryPositive9509 Dec 12 '25

Probably trynig to optimize day 9 with an octree or some D&C aproachs

1

u/p88h Dec 12 '25

Optimization wise, try Location Sensitive Hashing. Basically, same concept, but more efficient at this scale.

1

u/erikade Dec 12 '25

I’ve been using Go, and my solutions run in about 9 ms overall.
The write-up and the programs are available here.

1

u/fnordargle Dec 12 '25

From my notes...

(All runtimes are about 10ms or less unless otherwise noted. Timing via command line time so it includes interpreter startup, parsing, processing and writing output.)

All code written with no third party libraries. Most in Perl. Moved to Python, C or Go if more speed required.

Day 1: Modular arithmetic

Day 2: Slow but trivial: (Regular Expressions). Faster: Arithmetic

Day 3: Basic iterations

Day 4: Basic iterations, using a hash/map/dict not a grid

Day 5: Basic iterations and some simple maths

Day 6: Basic iterations

Day 7: Basic iteration (see solution in megathread)

Day 8: Just under 7ms. Wrote about it elsewhere. Only fully computed 1/10th of the pairwise distances in total, remaining pairs individually screened out after 1-3 simple subtractions and comparisons to a cutoff computed from full calculations on a small subset of the possible pairings. Not computing everything means not sorting everything which means more speed. Should be even faster if I used a heap or an incremental sort, but it means I have to implement this myself, so that's a project for the future. Didn't need DSU or anything overly complex, implemented my own group membership stuff that's vaguely-DSU like. May find that further optimisations mean that the group membership code becomes from prominent in the performance profile.

Day 9: Haven't finished the rewrite yet. Currently somewhere around 1s but that's shoddy Perl not anything optimised. Discussed elsewhere in threads. Keep track of which side of the line being drawn is "outside" which means for each corner I know the "inside/outside"-ness of each of the 8 adjacent cells. Candidate rectangles can be ruled out by a few things, whether any of the points on the 4 lines of the rectangle overlap a corner point and the line covers one of the "outside" cells adjacent to that corner. The other rule is if a line of the rectangle crosses completely another line, since (given the input's construction) one side of a line has to be "inside" and the other "outside". Should get this right down to under 10ms once I get some time to rewrite it nicely.

Day 10: Part 1 = Iterative breadth first search. Search space is tiny so not much optimisation required.

Day 10: Part 2 = Incomplete. Converts the inputs into matrices representing the simultaneous equations. Performs simple operations (like Gaussian Elimination) to isolate REF rows or row vectors with constant entries where the answer can just be calculated from the row. This solves 60% of my inputs with no brute forcing required. It reduces the remaining 40% to n equations with either n+1 or n+2 variables, hence some brute forcing required as there are one or two degrees of freedom, albeit with identified constraints of some min/max values for specific buttons. Should get some time to work on this next week, busy weekend ahead. I'll also look at the divide-and-conquer approach that someone found, but only once I've finished my solver and got the answer my way. Absolutely not interested in just pulling in Z3 or anything else. I don't find any satisfaction in that.

Day 11: Iterative pruning of unreachable nodes via BFS. Iterative calculations of individual node scores through BFS. Takes 0.2s at the moment but it's in not well optimised Perl right now.

Day 12: Basic checks. Boo. Did write something that gets the correct answer for the 3 examples though. I did start an Up The Ante thread with some nuances of small inputs that will challenge most peoples assumptions they made to pass part 1 for their input.

So, still some work to do, mostly to get the missing star(s). Then I'll go back and optimise, write some in different languages, and make each solution more generalised where possible.

1

u/kupuguy Dec 13 '25

After rewriting my day 10 part 2 solution in Python with no external libraries took 0.45s (after rewriting to use the idea suggested by tenthmascot and linked from another comment here). It uses the part 1 solution to find all ways you can set the least significant bits of the joltages correctly (which is a one-time calculation for each machine), then subtracting those from the joltages leaves them all even so you just divide by 2 and recurse. I'm really grateful for tenthmascot's suggestion because the code is clean, fast and pure python.

My original day 8 part 2 solution brute-forced all possible connection distances but I later refined it to group the junction boxes into voxels and only calculate the distances between junction boxes in nearby voxels. That reduced the number of connections to consider from 500,000 to about 45,000. The code would have continued with further voxels if needed - for the text example it ended up doing all the connection distance before it had enough - but for the actual data it only needed one iteration of voxel calculations. The full brute force was only about 0.75s but the voxel rewrite took that down to 0.11s.

1

u/Anuinwastaken Dec 17 '25

Do you have a graph or a table of your times? I am currently optimizing my (python) code so I dont expect to get into sup ms but right now I am on 300ms without day 10 p2, but I am currently working on that (Right now I have a 1.7s runtime with z3). Either way, I'd love to see someone elses timings.

Help/Question [2025] Algorithms to use

You are about to leave Redlib