alteryx Community

# General Discussions

Discuss any topics that are not product-specific here.

## Advent of Code 2023 Day 25 (BaseA Style)

Alteryx Community Team

6 REPLIES 6
13 - Pulsar

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:

Spoiler
Main 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):

15 - Aurora

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.

Spoiler
It is obvious that some particular edge are bridges between two big groups. Just identify those critical edges in this interactive chart, and take out from the network. That's it.

I respect @AndrewDMerrill, because he solves this quiz by configuring the solid logic without counting on visualization.

17 - Castor

Visualizing the data is very useful to find the solution. The Network Analysis is also useful on this day.

Spoiler

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.

Spoiler
This theory is needed the nested Iterative macro. So it is not very fast, however it is more practical than try 3148x3148x3148=31,196,377,792 pattern. To solve this problem, I use Nagamochi-Ibaraki algorythm. I think that the iterative count is only 991,936 times using this 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 :
Spoiler

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 :
Spoiler

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.

Node merge macro :
Spoiler

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

Workflow :
Spoiler

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.

12 - Quasar

Advent of Code 2023 was a pleasure to attend from day one. I'm glad I was able to finish.

Spoiler
Later I want to try to solve this by method of @AndrewDMerrill  and @AkimasaKajitani . When I see this, I could not find the logic of detecting 4 lines. I just see the visulaization.

12 - Quasar

Finally, my workflow detects min-cut less than 1 minute.

Spoiler

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.

12 - Quasar

no clues at all...just copying.

Spoiler
copy from reddit (screenshot below). it simple to copy and understand, other are hard to understand.

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
.

Labels