Hacker News Reader

Comment by adventofshmode | Hacker News Reader

I got stuck on the graph-cut puzzle for FOUR MONTHS. I had to write a force-directed graphing engine to find the longest three edges to cut.

After I solved it I looked at other people's solutions and they used Meta's proposition solver in about 10 lines. Seemed like a massive cheat to me.

View on HN

Oh man, this is my best memory of last year's AoC. After uselessly noodling for a while, I used Graphviz to draw the graph to an SVG file. It drew two messy balls of yarn neatly connected by three edges.

My script still says "TODO: find a real solution". Good times.

This was the day 25 problem: given a graph of ~1600 nodes and ~3500 edges, find the 3 edges that if deleted divide the graph into 2 components. I looked over some of the solutions and it surprised me how few used the simplest method: for each edge with endpoints u, v in the graph, delete it and then find another path P1 between u and v. Then, for each edge e1 in P1, delete it and then find another path P2 between u and v. Then, for each edge e2 in P2, delete it and then try to find another path between u and v. If there is no path, (u, v), e1, e2 is your cut-set. Otherwise, add e2 back and try the next edge in P2. When you've exhausted P2, add e1 back and try the next edge in P1. When you've exhausted P1, add (u, v) back and try the next edge in the graph. It's 3-6 loops deep depending on how you count, but it works. My python implementation completes in under 2 minutes, but it varies because it appears the standard python data structures have some nondeterminism, and I may have had a lucky draw with my puzzle input.

I have a self-imposed goal of not using third-party libraries for any of the solve logic. It feels more satisfying to do it myself, even if it takes longer.

Like Minecraft, everybody should play it however they want, it's just a game.

Which one was the "graph-cut puzzle" ? I've had a few where I couldn't do them on the day, either I was busy or I found them harder than usual or sometimes both.

It looks like in 2023 I took until almost New Year's Eve to finish, but until like the 21st of December I was fine, I got thrown off by travel and other commitments in the last few days as they got more difficult.

What solver are you referring to? I've used z3 and OR-tools, but I find it so difficult to model problems in either one that I seldom get good usage of either one.

Reply on news.ycombinator.com