Solved via Bell-Fordmann, by finding the most popular edges in all the patsh from each node to others. When yor visualisator helpes with demo data and does not help with real one 😁

Super lazy today Used graphviz to find the edges to remove and then loom to do the traversals. 🙂

https://github.com/rjray/advent-2023-clojure/blob/master/src/advent_of_code/day25.clj This one SHOULD have been a breeze; I have an implementation of Karger's Algorithm from when I did the Coursera 4-class Algorithms Specialization years ago. Only... I couldn't understand my old code. I had left comments, but not enough I guess. And it required some manual adjusting to the number of iterations run in order to guarantee a cut-size of 3.

https://gist.github.com/RokLenarcic/5d2cfea99fc0383356bb5fda33500072

I used max flow algorithm to find a max flow map where max flow is 3, then I just tried removing combinations of 3 edges from that flow until I got one. That flow has 33 edges so that works fast.

But I am wondering if there’s some way to get cut set from flow map more directly, without trying every combination of those 33 edges

used karger's algorithm as well https://github.com/WaqasAliAbbasi/advent-of-code/blob/main/2023/clojure/src/advent_of_code/day_25.clj

My implementation of Karger’s runs fine on the sample, but still has not returned a result on the input. I’ll just let it heat up my computer for a little while longer…

… okay, it finally finished. My https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2023/day_25_wires.clj is short and sweet, but it doesn’t run very fast. When it returns an answer (sometimes it doesn’t) it takes about 40 seconds (one time it finished at a blazing pace of 12 seconds!). I wish I knew better concurrency tricks, I’m not very experienced with that sort of thing.

mine works in 4 sec

Thing about Karger’s, is that it uses random selection. You always have to sample multiple times to endure getting the result you need. I’m working on a rewrite of parts of mine to not have the iteration hard-coded, but my use of pmap is causing some issues.

@U66G3SGP5 how long your solution takes?

4 seconds

Not knowing, nor finding, an appropriate algorithm, just ‘discovered’ (after a day failing to come up with anything) an approach that works (for my input?): start with a random node as the start set and keep adding the neighbour node that adds the least new edges connecting the set to nodes outside the set, until there are exactly 3 such edges connecting to neighbours outside the set. Takes about 15 seconds on my phone.