Advent of Code 2023 part 9

Day 25

Intro

The final day! I’m a bit surprised I made it this far to be honest, I’ve never written anything blog like in my life really up to this point. Having said that, my final shoutout with be to NetworkX. Like Z3, I personally don’t use this since I like vanilla Java, but for leaderboard pushing, this will almost certainly increase your odds. Unfortunately, unlike Z3, this is for Python only, so you are a bit out of luck if you don’t code in Python (although I’m sure there exists similar options in your favorite language of choice). NetworkX trivializes a large amount of graph problems since it’s probably a lot of powerful functions for getting distances, connectedness, etc…

Day 25 (Snowverload)

A slight spoiler to those who haven’t finished AoC this year and haven’t done AoC in the past, but Day 25 part 2 is always the same. Once you’ve completed part 1, part 2 will ask you for all the other 49 stars, and if you have them you immediately can complete the day and get the 50th star. If you don’t have everything else done, you cannot proceed. Thus the part 2 leaderboard generally is very close to the part 1 leaderboard, as most people contesting for the leaderboard tend to have all the previous days done. This also means that if you want to contest the part 2 leaderboard, make sure you have Days 1-24 done before the Day 25 problem releases.

Ok now onto the actual problem. Similar to Day 23, this is actually a direct theoretical problem. Finding the minimum amount of edges to cut (or “disconnect” as the problem statement say) is known as the Minimum Cut problem. I know, creative naming. In this case, there’s no tricks like Day 23. The typical solution, known as the Stoer–Wagner algorithm is a polynomial time algorithm, which works perfectly fine for the problem at hand. However, it’s not a particularly famous algorithm, so for the purposes of solving fast, it’s likely not actually best to try to learn an algorithm from scratch. Instead, I’ll share a few ways to get creative (if all you care about is learning the algorithm itself, totally fine, the wikipedia page I linked contains an in depth description and example implementation).

First idea, don’t code at all. There are a lot of graph visualization tools, such as GraphViz and Flourish, which can take a given graph and show you how it’s connected. Since in general visualizations will try to group closely connected points, basically any visualization will show two large connected groups with three edges in between, then you can manually remove those edges from your data, and run a BFS from a random node to get how many nodes it’s connected to. And once you know the size of one group, the size of the other group is known and you have your answer.

Alternatively, you can offload the actual algorithm to a networking tool. For this, NetworkX definitely reigns supreme. It has a direct function called minimum_cut, and many more useful tools that turns this problem into just a few lines of Python code, and is relatively fast. I didn’t code this day in Python, but from reading comments it sounds like a reasonable NetworkX implementation takes about a second to run.

Finally, one more option for if you want to code, but don’t have a great networking package at your disposal, you can use some more time intensive methods. One is the pure brute force way, of just trying to remove every combination of 3 edges and seeing if the resulting graph is connected. Another is to use Dijkstra’s from every node to every other node. This works here because any two nodes on opposite sides of the 3 edge cut must pass through one of the those three edges, so the top three edges will be the ones in the cut. I ended up going with the last way for coding, although during the actual competition I personally used Flourish.

Thanks for following along, and I hoped that I was able to be of value to you, whether in the various shoutouts, algorithms, or just following along in my commentary. This will probably be the last AoC related post until next year, hope to see you then!

Times

To read this, left to right is “Day”, “Part 1 time”, “Part 1 rank”, “Part 1 global points”, “Part 2 time”, “Part 2 rank”, “Part 2 global points”

A pretty average day. Took a while to find a free online tool where I could visualize the graph.

Run time:

Not ideal, part 1 comes out to around 900ms (turns out bfs on every single node takes a while). However, I was able to optimized day 21 part 1 from 1.7 seconds to ~10ms, so my total time is actually down from yesterday. Excluding day 23 the total run time is roughly 2.8 seconds.

Breakdown:

Day 23: 8s part 1, 30s part 2

Day 25 part 1: 900 ms

Day 16 part 2: 900 ms

All 44 other parts combined: 1000ms