Day 12: Advent of Code 2017 Catchup

Day 12 of the 2017 Advent of Code was a fun one. In it, we're given a series of 'programs' that are connected to one another via 'pipes,' and we have to find out, no matter how roundabout the path, how many programs can connect to program 0.

Now I'm sure there are many ways to do this, but this seemed like a logical place to implement a recursive function to me.

First, though, we have to model the data. It could likely be modeled as a graph, but I used a multimap. A multimap is an associative C++ STL container that acts exactly like a map, except we can repeat keys: that is, one key can be associated with multiple values.

First I parsed the input: we've got 2000 of these programs, oh my. But no problem! Using a std::stringstream we're able to grab the id, throw away the 'pipe,' and insert entries into the multimap using this id. I'm no expert at input parsing but here's the process I used inside my while loop:

        int id;
        std::string num;
        std::string throwaway;
        std::stringstream ss(line_buffer);
        ss >> id;
        ss >> throwaway;
        while(ss.good())
        {
            getline(ss, num, ',');
            pipeline.insert(std::pair<int, int>(id, stoi(num)));
        }

pipeline is my multimap that will hold essentially, a list of every connection that exists in the input set.

Anyway, now we've got a multimap with thousands of connections listed: how do we analyze it?

void find_group(std::multimap<int, int> &pipeline, int current_id, std::vector<int> &group)
{
    if (std::find(group.begin(), group.end(), current_id) == group.end())
    {
        group.push_back(current_id);
        for (auto x : pipeline)
        {
            if (x.first == current_id)
            {
                find_group(pipeline, x.second, group);
            }
        }
    }
}

This could be refactored and is a bit messy (I don't like nesting that deeply usually,) however it gets the job done. This is a recursive function, essentially a function that calls itself. Recursive functions need a base case in which the recursion will terminate. We get that here by checking if the current_id is already in the group: if so, the function skips to the end.

If the current_id is NOT found in the currently listed group (modeled as a vector<int>) we insert it into the vector with group.push_back, then iterate over the 'pipeline' list of connections until we find another match. Once this match hits, we call the function again, this time feeding 'current_id' the number of the program that is piped into the current one.

The 'group' vector is passed by reference, so the vector gets filled up with a list of every program that the INITIAL current_id can reach through the pipeline. We do a simple group.size() check on it to find out how many programs are in the group we asked for initially, and bada bing bada boom Bon Jovi we get our answer to part 1.

If you're not particularly familiar with recursion, I recommend reading up on it a bit and experimenting with it: it's a valuable tool to keep in the toolbox when dealing with certain problems in computer science, and it's not really as complicated as its reputation may have you believe.

For part 2, we're given another directive: to find out the number of distinct 'groups' in our input pipeline: that is, groups of programs that are NOT connected to any other group.

    for (int i = 0; i < NUM_PROGS; i++)
    {
        if (std::find(grp.begin(), grp.end(), i) == grp.end())
        {
            num_groups++;
        }
        find_group(pipeline, i, grp);
    }

Using the find_group function from before, we iterate NUM_PROGS times (2000 in this case, which could easily be calculated programmatically, but I just looked at the line number and declared a constant) and use 'i' as more than just an iteration factor: we check if program #i has already been divided into a group: if not, we know that it must exist in some group, even if it's just itself, so we increment num_groups, and then run the find_group() function on it, essentially filling the grp vector with every program we've 'seen before' in the process.

Special shoutout to my Northern Illinois University 'Data Structures and Algorithms' course for this one: finding a use for a multimap AND using recursion? The professor would be proud.