Advent of Code 2023 Day 25: Snowverload
HTML-код
- Опубликовано: 9 фев 2025
- My AoC repository: github.com/hyp...
Join my Discord! / discord
Want to improve your mastery or learn a new language? Try Codecrafters, a platform where you learn by building your own project! I've always believed that learning by doing is the best way to learn to code by far, so check them out with my link! app.codecrafte.... You can sign up for free and try out some of their streams including full beta projects for free (no credit card required) and you'll get a 40% discount on annual subscriptions!
(Disclaimer: I receive commissions on paid memberships through my link, but Codecrafters is not a sponsor of this channel, does not endorse any of my content, and does not review any of my videos.)
love you
Thanks for all these video's! I havent had enough time to finish every days challenge, so ill have to revisit them later, but they'll be of great help ^^
The maximum traffic through 3 paths will work only in condition that 50% of nodes are one side of those weak edges and 50% in the other side. For instance assume one node at one side, and all nodes in other side, the smallest paths will be internal and not go through those 3 edges that connects that alone to the rest of the graph, hence it'll not be highest traffic region.
Thank you very much for these videos - you provide very clear thinking in all of them!
As for a straightforward solution that doesn’t require a graph library: What I did was select a pair of nodes far apart (pick one node, do BFS traversal of the graph, pick the node you hit last, and you have your pair). Then 3 times I did this:
* Find any path between the two nodes.
* Remove that path.
Now the two nodes should be disconnected, and you can count the number of reachable nodes from your pair.
(Update: Ditch the part about how to find the initial two nodes. Just pick a random node as the first in the pair, and try every other node as the other node in the pair. Then try the “remove 3 paths” part for each pair. If that leaves you with two distinct graphs, you have your solution, otherwise continue with the next pair - remember to reset your graph between every pair of nodes you have. You will get there eventually.)
Thanks for your awesome explanations!!
Thanks for the whole series! My solution of the 25th day was to pick the first node of the graph and determine the 4-connected component the node is member of. My assumption was that the whole graph consists of two 4-connected components that are linked together by the 3 edges we're looking for. So the first node is necessarily member of one of the two components. And for each other node, if there are at least 4 edge-distinct paths, between the first node and other node, then the other node is member of the first component. So this way, I determine the first 4-connected component and the other component consists of all the remaining nodes.
Oh this looks like the best approach. Glad I saw this comment
I was able to solve it with Karger's algorithm (see the wikipedia page), resp. its improved variant Karger-Stein algorithm. It is a randomized algorithm which gave an answer within a minute (and I probably did not use an optimal data structure for the graph).
Thanks a lot for publishing your videos. I learned a lot.
I heard about that, but I wasn't sure how to deal with its probabilistic correctness and find a solution I found satisfactory to present.
I did the same. Can't give a running time because its probabilistic, but it did finish eventually.
@@squeezy7252 It looks like I was lucky. When I ran the next time, it took more than 10 minutes, but finished.
@@hyper-neutrino you're given the value of the min cut (3) so you can repeat until you find a solution that produces the specified min cut value
Here's my solution: git.sr.ht/~sgeisenh/aoc2023/tree/main/item/25.py
Like another commenter pointed out, Ford-Fulkerson (deterministic max flow) can be fast enough for this problem, because we only have to look if the flow is greater than 3 or not. My implementation runs in about 2 seconds.
I used Ford-Fulkerson dfs maxflow to compute the flow between every adjacent pair of points, truncated when the flow is found to be greater than 3. Thus, There are at most 4 augmenting paths to be found for each pair. It should be
O(E^2) in total. I have no idea why my impl was slow like running for around 1min, but i think this should be an acceptable approach
Thank you for all your work, you have helped me a lot to understand these topics. You are amazing!
Thanks for the content, great quality as always. Hope to see you next year with aoc 2024. I also would like to see a video on tips on how to get better at this type of problem solving. Happy hollidays!
Thanks for the series and Merry Christmas! A similar heuristic to what you discussed in the video is to generate a number of random spanning trees; each spanning tree has to contain (at least) one of the three edges that we are after. If you look at the frequency of how often each edge appears in the spanning trees, you find the three edges quite quickly. 1k spanning trees is more than enough (100 usually works); here is an example of the top 4 edges for a random run: [(('gmr', 'ntx'), 896), (('mrd', 'rjs'), 891), (('gsk', 'ncg'), 888), (('gmr', 'zkb'), 648)] - notice the gap between the top 3 and the fourth edge. This is a heuristic, i.e. it doesn't guarantee the correct solution for general graphs but works well for this puzzle.
The "BFS between all pairs of nodes" can be sped up dramatically by doing a single source, all nodes BFS. This will generate the shortest path from a single node to all nodes.
With my code, I computed every shortest path and it ran in a few seconds with Python.
I realized that a bit late lol
merry christmas🎉
Thanks for the videos! My approach to find the three edges was to go through all the pairs of edges and remove them (logically) from the graph. In the remaining graph I used a DFS modification that checks if the graph contains an edge that is a bridge (similar to en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan's_bridge-finding_algorithm). If a bridge is found we have our three edges, else we check the next pair of edges. The runtime was not great but this solution doesn't rely on any heuristics.
You calculate connectivity like you said, you just have to walk from each to each (it doesnt take that long, because on every step you save the path and add_up the connectivity); You end up with basically maybe 10 nodes that stand out from the rest so just try to snip combination of three until it falls appart (luckily most of the high connectivity nodes or edges dont connect to other high connectivity nodes). It takes like 3 seconds for me, which is good for the number of nodes I think (I walk a second time after snipping to compare the visited list to all nodes).
Thanks for making the series, I watched all of latter videos and learned a lot from them. I wanted to ask, what comes after the advent of code? Do you do anything similar outside of december? I'm a Data Engineer trying to find SW Engineer internship this summer and these have been teaching me many useful CS concepts.
I'm still studying Computer Science (going into my 4th year soon) and I also do software development both in personal projects and for a living during work terms (and after graduation).
I used Edmund-Karp to compute the shortest augmenting path between 2 pairs. Edmunds-Karp guarantees that the cardinality of the numbers of paths found is maximal. With Menger's theorem, I know that the min pairwise s-t cut is the equal to the max number of s-t paths.
So I just repeated Edmund Karp until 3 paths are found. Once I have 3 paths, I know 1 of the edges to cut is on each of the paths, so I just tried all combinations.
I'm sure this is not optimal, though. So I need to find a better way
It finds solution in 1-4 seconds. There's probably a way to optimize this by picking nodes that are "far" apart.
I might be wrong but since the graph is unweighted and there are about 1500 nodes, doing a BFS from every node to reach every other node is actually quite fast. Its basically 1500 * (1500 + number of edges) iterations which is just a few millions. I did that for my solution and it runs in a few seconds in javascript
Yep, it's because I forgot you can BFS to all destination nodes at the same time
I tried expressing this as a SAT problem (my preferred solver has predicates for strongly connectedness) but just couldn't do it. Then spent a few hours trying to implement Karger's randomised min-cut, but could only get it down to 4 edges. Eventually gave up and used networkx too, which only took a few mins and a few lines of code. Oh well.
I'm still on day 14, part 2, but ya it's been great coding with you again this year. I'm still not sold on the heavy use of list comprehension as it doesn't really speed up the execution. I can see how it reduces typing, but really it's just so much harder to read. Anyway thanks for the vids and maybe I'll get to day 25 in the next couple weeks.
Fair enough. I think it just depends on preference as I find comprehensions to make more sense than construction, and honestly I can read two or even three nested comprehensions without any issues intuitively. Thanks for watching!
Yeah, I just visualized the graph and found the pairs manually. I’m too tried from celebrating Christmas to program anything clever
Ha, same. I just threw the graph into matplotlib, found the 3 wires, and done 😊
But good to know about nx.minimum_edge_cuts. Probably would have saved me a minute or two.