General Discussions
Discuss any topics that are not product-specific here.
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:
Macro 1 (Finds the shortest path from arbitrary node to all other nodes):
Macro 2 (Finds the next 3 shortest unique paths between two nodes):
Macro 3 (Finds shortest path between two nodes for a given map; used in macro 2):
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 @CoG, 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.
I can find the three edge which I should delete.
Is this way BaseA? I only find the data pattern using Network Analysis tool( this is not R/Python).
And also, the Make Group tool is really useful to count each group items.
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.
Thery overview :
The algorithm assigns what is called a maximum adjacency order to the nodes of the graph. The nodes are numbered, and the node most closely connected (with the greatest number of connected edges) to the first numbered node is selected. The node with the last number is then cut from the graph, and the number of cuts is noted. We then merge the last numbered node with the one numbered before it (the node list and the edge list must be updated). This is repeated, and the smallest number of cuts is the minimum number of cuts.
The original source is as follows. But sorry for this url is Japanese.
https://www-or.amp.i.kyoto-u.ac.jp/demo/MINCUT.html
The algorithm detail :
How to create a maximum adjacency order :
The first node can be chosen at random, but you should to choose the nodes that are strongly connected to the selected node one after another. First, consider the following graph.
1. First, select A randomly. This is labeled as 1.
2. Select the node that has strongly connected with selected A. Any one is fine because the connected node is all one, so choose one. For example, let's select B. This is labeled as 2.
3. Now I selected A and B. So let's find the next strongly connected nodes. I colored the candidate nodes as green(C,D or F).
C is the most strong connected with A and B because the connected edges are 2(with A and B). This is labeled as 3.
4. Repeat 1-3. Finally, I can label it as follows:
This is the maximum adjacency order.
And then, there are some tasks.
6. Look at the last two selected nodes(G and H).
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.The macro to make the maximum adjacency order :
This macro algorythm :
1. Select nodes that are strongly connected to the selected node (nodes with a large number of connected edges)
2. Update the node list to keep the selected nodes as a selected group.
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 Node merge macro does not count the minimum edge, however it outputs the maximum adjacency order. I calculate the minimum cuts using that list after the macro.
This will find the three edges that should be cut.
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.
2. Group the edges together (contraction).
3. Calculate the number of cuts, and output an edge set when the minimum cut is updated.
4. Select the node most strongly connected to the selected edge group.
5. Find the edge related to the selected node and go to 2.
At first, I try to use Karger's algorithm, but not so faster for Day25 problem.
no clues at all...just copying.
my understanding is from the post is,
Map have 2 group (G and S) and 3 lines to cut.
start, pick random point to remove, it will be either G or S.
compare back to the data, count the missing connection for each point.
example:
1. remove random point at first, count the missing connection
| 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 |
2. Remove the point with most missing connection, it means that this point is part of the group from points removed.
if there have more than 1 is same count, take either one.
Keep remove until it had only 2 lines variance in sum (for this example, question should use 3 instead)
| 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 |
in the end, the example above is a, b, f is one group, and d, e, c is another group.
to get the answer, total points of 6 (a, b, c, d, e, f) - count point remain of 3 (d, e, c) - = count of group one of 3 (a, b, f)
however, it would not show which is 3 lines to disconnected.
potential risk: if first 2 point removed is the connections to cut (point d is removed after a), it will turn wrong result.
I use random tool to pick random point when max count > 1
.
