Advent Of Code 2017 Catchup Day 6

Iterators. They're confusing. They're (sorta) pointers. They're mostly pointers. But they're not quite normal pointers. They're magic in C++ and manipulating data with the standard library requires some clever usage of them.

AoC 2017 Day 6 requires us to encapsulate 16 memory banks: I used a vector to hold these banks. These banks are then redistributed simply: the bank holding the most (tie goes to the 'left' most memory bank, or lowest numbered) is 'emptied' and then that data is redistributed across the remaining banks, starting at the highest place +1, and iterating across. We need to find how many steps of this redistribution takes place before a pattern is repeated: a pattern we've seen before arises again, because of infinite loops. We all love infinite loops.

So first, an initialization! We init 'steps' to 0. We'll increment it later.

Next, a loop! We want to run this redistribution until we come across a pattern we've seen before: hence, I'm holding all the patterns we see in a "seen_before" vector, and we use the std::find to see if any of the patterns in 'seen_before' match what we're working with presently in the condition of the while loop.

    int steps = 0;
    while (std::find(seen_before.begin(), seen_before.end(), banks) == seen_before.end())
    {
        seen_before.push_back(banks);
    }

But we've got a lot more to do! Like redistributing. So we initialize an iterator to the maximum element found in the current vector of 'banks.'

We then dereference this iterator to get the value of the memory we need to redistribute, holding that in dist_value, and then assign a value of 0 to the dereferenced iterator to start the redistribution process.

        auto it = max_element(banks.begin(), banks.end());
        int dist_value = *it;
        *it = 0;

Remember, iterators are essentially pointers (C++ gurus don't come calling me on that) but they can be dereferenced: an iterator POINTS to a value, a dereferenced iterator CONTAINS the value. More or less. So we initialize the iterator to the max element, dereference it with the * operator, and then set the dereferenced iterator value to 0.

So far so good. Now we need to visit all of the other banks, one by one, dropping off one 'memory' bit into each as we come across it. For this, we'll use a simple for loop.

        for (int i = 0; i < dist_value; i++)
        {
            it++;
            if (it == banks.end())
            {
                it = banks.begin();
            }
            *it += 1;
        }
    ++steps;

This redistributes the 'dist_value' into all of the subsequent memory holes, so to speak. And we can't forget to increment our 'steps,' as this holds the answer! A simple cout of the steps variable at the end of this loop, and we have our answer: how many redistributions we faced until we found a repeat state!

EZPZ

Part 2 asks us to find how many 'steps' of redistribution are involved in the inevitable infinite loop: there are many ways to tackle this. My first solution was to iterate to find the resulting state, store this as a variable, re-iterate until that state was matched, and then find the difference of steps involved. This is naive and suboptimal coding at its finest...

But it worked!

If I were to do it again, I'd optimize things simply by adding another variable or two to keep track of states and see when one repeats. How did you do it? As we've seen, iterators are a powerful tool when used with the C++ Standard Library and a little "pointer arithmetic" magic can make tough programming challenges seem simple.

Until next time, sports fans.