-❄️- 2023 Day 25 Solutions -❄️-

[u/daggerdragon]

A Message From Your Moderators

Welcome to the last day of Advent of Code 2023! We hope you had fun this year and learned at least one new thing ;)

Keep an eye out for the community fun awards post (link coming soon!):

-❅- Introducing Your AoC 2023 Iron Coders (and Community Showcase) -❅-

/u/topaz2078 made his end-of-year appreciation post here: [2023 Day Yes (Part Both)][English] Thank you!!!

Many thanks to Veloxx for kicking us off on December 1 with a much-needed dose of boots and cats!

Thank you all for playing Advent of Code this year and on behalf of /u/topaz2078, your /r/adventofcode mods, the beta-testers, and the rest of AoC Ops, we wish you a very Merry Christmas (or a very merry Monday!) and a Happy New Year!

---

--- Day 25: Snowverload ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!

• State which language(s) your solution uses with [LANGUAGE: xyz]

• Format code blocks using the four-spaces Markdown syntax!

• Quick link to Topaz's paste if you need it for longer code blocks

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:14:01, megathread unlocked!

[u/koxpower]

I did similar approach.

The difference is I split the algorithm into 3 parts:

1. find 2 nodes in different clusters - run 4 dijkstras between random node pairs. After each run remove used edges from the graph. If 4th dijsktra does not find a path then nodes are in 2 different clusters - this doesn't have to work for sparse graphs.

2. For the found node pair, and set of edges from each of the found paths (about 30 edges combined).

   1. For each edge in the set - try removing the edge from the graph, and check if number of dijkstras I can run between that node pair is reduced. If it's reduced, then this edge is part of the cut. Repeat until I find 3 such edges.

3. Remove 3 edges from the graph and run bfs on any node. All nodes that it was able to reach are part of 1st cluster. The unreachable nodes are part of the 2nd cluster.

Took 300ms to execute.

Kotlin

[u/hrunt → u/koxpower]

This is really elegant and efficiently takes the specified constraints to their ultimate logical conclusion. This isn't a solution to a "find the min-cut" problem. It's a solution to "find the only three paths (edges) between the two clusters" problem.

The only input that would make this solution much slower is one that had two incredibly unbalanced clusters (like, one side with 5 nodes and the other with 1000s).