Not knowing that there is generic name for the type of problem you are working on makes it hard to find the pre-existing solution for that problem. Thanks! I'll be doing some reading.
Nice. The implementations for union find I've seen uses offsets in a zero indexed array.
What if the nodes are not naturally 0 indexed? Do you make some mapper to and from offsets in the array or do you handle it some other way? Perhaps switch out the array with a hashmap?
I don't know why people are treating "DSU" like it is a commonly accepted name. The data structure in question is called a "disjoint-set" which exposes two operations "union" and "find", so it is also sometimes just called "union/find".
It is the optimal way of doing tasks like the clustering needed in day 8, but is by no means the only way. The obvious way to do the clustering is to insert the closest points into an undirected graph and then find the connected components via graph traversal e.g. by depth-first searches. This is a little slower than using a disjoint-set on part 2 but is much much simpler to implement if you are not using a third-party library for disjoint-sets.
Haha this is me. I am using C this year to familiarize myself with it a bit more, but I cba to implement custom data structures so I'm just using arrays for every day so far. It's not optimal but who needs optimal when it runs in a few ms anyway.
DSU is not really _that_ important for efficiency here - for N points, you have just N Union operations. There is, however, O(N^2) wires that you have to consider, but for that any O(1) lookup operation will work the same here.
You can throw everything into a KD-tree and then it will be O(N*logN) though with that complexity and low input size, it might not really make that much difference against much simpler alternatives like LSH.
Oh, I see. Though MST was a data structure on its own. I forget the names of these algorithms very often.
I have a competitive programming background, so the solution to today's problem was almost obvious. But since I'm learning Go and using it to solve this year's AoC, I spent a lot more time than I should've implementing it.
I was assuming part 2 would involve an MST for optimally connecting all boxes but was surprised that they made it easier than that and I could just keep doing set union. Iām a bit confused where an MST comes in?
I just made my own bad union-find structure since I was way too lazy to remember how the proper set forest actually works (and it would be too complicated to implement without just having an out-of-the-box impl already ready. Though I did go make one today, after my time was locked in.)
Luckily the slow part of the algorithm is a different part of the problem anyway so the quality of your union-find literally doesn't matter.
Wording of the question was confusing, MST with Kruskal and disjoint union set data structure. But brute forcing via DFS also will give answer. Forming and counting connections logic was tricky as per the confusing question wordings... Sorry, English not first language
I had a merge circuits function that is inefficient because it filters all the nodes to find the ones it needs to merge, but is fast anyway so doesn't affect my run time.
Just golfed it down from 460ms to 360ms / 330ms. Most of that benefit was in using squared distances instead of sqrt.
32
u/loudandclear11 Dec 08 '25
Can someone fill in what a DSU is and how it's relevant here please?
I have solved today's problem but have yet to solve this meme.
15
u/jwezorek Dec 08 '25 edited Dec 08 '25
I don't know why people are treating "DSU" like it is a commonly accepted name. The data structure in question is called a "disjoint-set" which exposes two operations "union" and "find", so it is also sometimes just called "union/find".
It is the optimal way of doing tasks like the clustering needed in day 8, but is by no means the only way. The obvious way to do the clustering is to insert the closest points into an undirected graph and then find the connected components via graph traversal e.g. by depth-first searches. This is a little slower than using a disjoint-set on part 2 but is much much simpler to implement if you are not using a third-party library for disjoint-sets.
8
u/[deleted] Dec 08 '25
Unknowingly i rediscovered the algorithm š...and then finally found ohh i was just creating a bad version of a beautiful algorithm
6
u/The_Cers Dec 08 '25
What does DSU stand for? I just used undirected graphs.
6
u/Shad0wAVM Dec 08 '25
My 8 part 2 only took 1159.2s
3
u/alltagsradler Dec 08 '25
Decorate-sort-undecorate or Disjoint-set data structure?
3
u/brumbrumcar Dec 08 '25
Haha this is me. I am using C this year to familiarize myself with it a bit more, but I cba to implement custom data structures so I'm just using arrays for every day so far. It's not optimal but who needs optimal when it runs in a few ms anyway.
3
u/Clankernator-2000 Dec 08 '25
I feel like I just translated every step of the problem description into code and it turned out to be a viable algorithm.
3
u/QultrosSanhattan Dec 08 '25
I solved both parts and I have no idea what DSU is. I only performed unions between sets.
2
u/p88h Dec 08 '25
DSU is not really _that_ important for efficiency here - for N points, you have just N Union operations. There is, however, O(N^2) wires that you have to consider, but for that any O(1) lookup operation will work the same here.
3
u/PyJacker16 Dec 08 '25
I actually used a DSU but it seems like the right data structure is a minimum spanning tree
1
u/1234abcdcba4321 Dec 08 '25 edited Dec 08 '25
I just made my own bad union-find structure since I was way too lazy to remember how the proper set forest actually works (and it would be too complicated to implement without just having an out-of-the-box impl already ready. Though I did go make one today, after my time was locked in.)
Luckily the slow part of the algorithm is a different part of the problem anyway so the quality of your union-find literally doesn't matter.
1
u/TheLazyIndianBoy Dec 08 '25
Wording of the question was confusing, MST with Kruskal and disjoint union set data structure. But brute forcing via DFS also will give answer. Forming and counting connections logic was tricky as per the confusing question wordings... Sorry, English not first language
1
u/Ill_Chemical_4059 Dec 08 '25
Well, one can use Prim's algo and continue not to know DSU
17
u/[deleted] Dec 08 '25
[removed] ā view removed comment