It's the final day. It's a little over a week into January for me, and I have some travel plans coming up in a few days, so it's been my goal to finish Advent of Code this year before then, so I can better mentally relax while traveling. I've enjoyed it, but especially after the last week worth of problems, it's been admittedly a little stressful to push myself to finish these. Luckily, the last day of this is typically pretty easy, so I'm somewhat excited to try!

The actual problem seems... interesting. At first blush, it seems like simply iterating over every possible set of connections to see which one splits it could work, but the input has 1191 lines, which alone means means about 1.5 billion combinations to check if each line was just one connection; and each line on average has more than two connections.

If three connections are enough to split it into two groups, then that means there are already mainly two groups. One assumption that might be interesting to try is testing out connections with the assumption that, within the groups, the pairs will have multiple connected nodes in common.

a - b - c - d
| x |   | x |
e - f   g - h 

In the example above, a and b both have e and f as common neighbors, but b and c have no common neighbors. That would involve checking about 11 million pairs - a lot, but managable.

Unfortunately, checking for that it seems a lot of the connections in the input don't match that assumption - few (about 5%) have any shared neighbors with its other neighbors.

~

I took a small break to do research - likely something I should have been doing more all of this year's problems, but ah well. It turns out that, given my assumptions, I'm looking for a minimum cut, and there's a few ways to accomplish this, but it seems the best for a generic unweighted graph (like the one for this problem) is Karger's algorithm; and because I already know the minimum cut size ahead of time (3), I just need to run it until I find that.

Functionally, what it's doing is reducing the grid by merging adjacent nodes, until only two nodes remain. This includes removing the connection between the two nodes, but preserving all other nodes. Once only two nodes remain, the reduction is complete. If the number of connecting connections remaining is only 3, then the only two remaining nodes will be the merged forms of the two major groups. Because this relies on choosing a random node, this takes a variable amount of time - but usually not too large an amount;

a - b - c   ->      ab - c   ->   ab - c   ->
|   |   |   ->     / |   |   ->    | \ |   ->   etc...
d - e - f   ->   d - e - f   ->    d - ef  ->  

srand(time(NULL));
map<string, vector<string>> karger;
do {
    karger = grid;

    while (karger.size() > 2) {
        // Pick random node + neighbor
        auto leftIt = karger.begin();
        advance(leftIt, rand() % karger.size());
        auto leftId = leftIt->first;
        auto rightId = karger[leftId][rand() % karger[leftId].size()];
        
        auto left = karger[leftId], right = karger[rightId];
        
        // Erase node graph and eachother's edges
        karger.erase(leftId);
        karger.erase(rightId);
        left.erase(remove(left.begin(), left.end(), rightId), left.end());
        right.erase(remove(right.begin(), right.end(), leftId), right.end());

        // Generate & insert merged nodes; update other nodes
        vector<string> combined = left;
        combined.insert(combined.end(), right.begin(), right.end());
        string newId = leftId + "|" + rightId;
        for (auto a = karger.begin(); a != karger.end(); a++)
        {
            for (auto b = a->second.begin(); b != a->second.end(); b++)
            {
                if (*b == leftId || *b == rightId) *b = newId;
            }
        }
        karger[newId] = combined;
    }
}
while (karger.begin()->second.size() != 3);

Oddly enough, the actual connections don't need to be found, just the group sizes, so finding that out is all that's needed! And despite the random element of this, it finishes consistently quickly (under 5sec) for the full input.

Now that it's over, I do have a few thoughts about this year. It seemed a bit odd. It was noted that there weren't any "graphical" solutions, where the result was something printed to a console to be interpreted by human eyes, and I understand that. It can be hard for those that are visually impared to handle it. But what I didn't expect was just... a lot of string manipulation. Compared to previous years, there just wasn't as big of a need to come up with more complex data structures than just manipulating the strings coming from the input. It felt odd.

I feel like I was stressing myself by doing this in c++. I enjoyed it, but I think I've hit the limit of how much I can learn c++ through something like this. I can use the language competently enough for this, after doing it 3 years in a row now, but to learn any further (such as threading, templating, smart pointers, and a whole lot more) I need to move beyond the small domain of isolated puzzles that Advent of Code really is.

I think that for future years (or past years, should I tackle them) I'm going to try and do other languages. Maybe C# next, as I'm very familiar with the language, and I can focus more on the puzzles and less on the language; or something I'm wholly unfamiliar with such as Haskell. I'm not sure yet. But in future years I'll try something new.