Discussion thread for day 25 of the Advent of Code - https://adventofcode.com/2023/day/25
This problem was quite difficult for me. I needed to glance through Reddit help to get some guidance. I was worried about how much I was struggling on Part 1 since Part 2 would be even harder. Thankfully, once I got Part 1, Part 2 was not too hard to complete after that, which brought me a great sense of relief! My solution is no where near as efficient as I would have liked, and took ~1 hour to run.
Workflow:
At first glance, I understood this quiz is to solve Graph problem, so started with visualization. And, as I predicted, Graph network gave me a quick solution, however, I admit my method was a kind of 'bypass'...not straight way.
I respect @AndrewDMerrill, because he solves this quiz by configuring the solid logic without counting on visualization.
Visualizing the data is very useful to find the solution. The Network Analysis is also useful on this day.
The production data is very big, so it took much time to show the result, but it can work.
Is this way BaseA? I only find the data pattern using Network Analysis tool( this is not R/Python).
But once I got 50 stars on Jan 3rd, I re-tried this day using any logic. This solution is known as Minimum cut problem of Graph Theory.
7. Cut the last node from the graph. In this case, you need to delete 3 edges(blue edges on figure above). This is the cut number.
8. Merge last two nodes and update the node and edge list.
9. Repeat 1-8 until the one node remains.
10 The minimum cut is the minimum of procedure 7. And you can know the edges which should be cut by examine the last node in the maximum adjacency order that recorded the minimum cut, you get.This macro needs the node list and edge list that are updatable. However the Iterative macro has only one Iterative Input/Output. So I merge those data. When I use each data, I separate them using Data Type field which I distinguish them and the Filter tool.
This macro algorythm :
1. Separates the data into node and edge lists
2. Put the data into a macro that creates a maximum adjacency order
3. Update the node and edge lists to merge last 2 nodes
4. Repeat 1-3 until only one node remains
The AoC 2023 was also really tough challenge. And also I learned the new things from this challenge. My regret is that I could not complete all the challenges in 2023 but last year I got 41 stars in 2022(I got the remaining star in 2023), but I got 48 stars in 2023. This is a lot of progress than last year.
And I appreciate the all challengers together who enjoy this challenge in Alteryx community. It was very stimulating for me. And special thanks for Alteryx community team, @NicoleJ and @JoshuaB . I would also like to personally thank the members of the Tokyo User Group ( @gawa , @DaisukeTsuchiya , @Tokimatsu @Qiu @Yoshiro_Fujimori ) for having fun with me.
Advent of Code 2023 was a pleasure to attend from day one. I'm glad I was able to finish.
Finally, my workflow detects min-cut less than 1 minute.
I studied Stoer–Wagner algorithm, I'm not sure this is same as Nagamochi-Ibaraki algorythm. I arranged these as below.
1. Select one appropriate edge.
no clues at all...just copying.
point | count of loss connection (removed a) |
a : f, d, b | n/a |
b : f, a, c | 1 |
c : b, e, d | 0 |
d : a, e, c | 1 |
e : d,c | 0 |
f : a, b | 1 |
point | count of loss connection (removed a, b) | count of loss connection (removed a, b, f) |
a : f, d, b | n/a | n/a |
b : f, a, c | n/a | n/a |
c : b, e, d | 1 | 1 |
d : a, e, c | 1 | 1 |
e : d, c | 0 | 0 |
f : a, b | 2 | n/a |