Advent Of Code – Corporate Policy – Puzzle 11

Here is the eleventh part of a long series on Advent Of Code. You can find the previous part here.

For this new post, we are going to solve the problem from 11^th December 2015, named "Corporate Policy". The solution I will propose is in C++, but the reasoning can be applied to other languages.

Part 1

The Problem

The full version of this problem can be found directly on the Advent of Code website, I will only describe the essence of the problem here:

There is a new policy on the password in the North Pole, and Santa’s password just expired. To remember his new password, Santa increments his old password string repeatedly until it is valid. To increment is just like to count with numbers: xx, xy, xz, ya, yb, and so on. Increase the rightmost letter one step; if it was z, it wraps around to a, and repeat with the next letter to the left until one doesn’t wrap around.

The policy specifies that the password must match the following requirements: Unfortunately for Santa, a new Security-Elf recently started, and he has imposed some additional password requirements:

• Passwords must have eight letters
• Passwords must include one increasing straight of at least three letters, like abc.
• Passwords may not contain the letters i, o, or l, which are confusing letters.
• Passwords must contain at least two different, non-overlapping pairs of letters, like aa.

For example, the next password after abcdefgh is abcdffaa. And now, we have to find Santa’s new password.

Solution

First of all, we have to be able to "increment" a password. Indeed, a character doesn’t have natively such behavior, so we must create our own PasswordCharacter:

class PasswordChar
{
public:
    // ... others functions

    void increment()
    {
        value = willWrapAroundToA () ? 'a' : value + 1;
    }

    bool willWrapAroundToA () const { return value == 'z'; }

private:
    char value{'a'};
};

Here you have only the methods that will be interesting for this exercise. So we have a PasswordChar that can be incremented, and when it reaches the letter ‘z’, it will wrap around, and we will be able to get that information to be able to increment the next letter as necessary.

Now that we have a character that can be incremented, we now need a password composed of several of those characters and which can be incremented too.

class Password
{
    // ... other functions

    void increment ()
    {
        for(int index {static_cast<int>(value.size()) - 1}; index >= 0 ; --index)
        {
            const auto characterWillWrap = value[index].willWrapAroundToA();
            value[index].increment();
            if(!characterWillWrap)
            {
                break;
            }
        }
    }

private:
    std::array<PasswordChar, 8> value;
};

So there it is, the password! To make sure it matches the first requirement, we will use a std::array of size 8. And we have an increment function too, which, when called, is going to increment each letter of the password, from the end, to the beginning, but stop incrementing is one character does wrap around after an increment.

Good, now we have a password that can be incremented, and that matches the first requirement. All we have to do then, is to make sure that the password is safe, which means that it match the three last requirements and we are done. Following the Single Responsibility Principle, we will have three functions (actually, some methods since I’ve made them part of the Password class).

Let’s start with the simplest, the forbidden letters.

bool Password::hasNoConfusingLetters() const
{
    return std::none_of(std::begin(value), std::end(value), [](const auto& passwordChar)
    {
        return passwordChar == 'i' || passwordChar == 'o' || passwordChar == 'l';
    });
}

The std makes it much simpler, don’t you think? This std function, none_of, will return true if none of the elements in value return true when passed to the lambda function. So useful! I love it. 

Well, now, let's see the next requirement, the increasing straight of three letters:

bool Password::hasIncreasingStraight() const
{
    for(auto index = size_t{0}; index < value.size() - 2; ++index)
    {
        if(value[index] == value[index + 1] - 1 && value[index] == value[index + 2] - 2)
        {
            return true;
        }
    }
    return false;
}

No std algorithm for this one, sadly, but still pretty straight forward. We have to be careful with the bounds, to make sure we stay in the array of characters, not like I did when I’ve first written this function. 

And finally the last requirement, the two non-overlapping pairs:

bool Password::hasTwoNonOverlappingPairs() const
{
    bool hasAtLeastOnePair{false};
    for(auto index = size_t{0}; index < value.size() - 1; ++index)
    {
        if(value[index] == value[index + 1])
        {
            if(hasAtLeastOnePair)
            {
                return true;
            }
            hasAtLeastOnePair = true;
            ++index;
        }
    }
    return false;
}

This one is far less easy to read. So I’m going to explain it a little more in detail.

We are going through the password. We check if there is a pair between the current letter and the next one (so we stop just before the last letter to avoid being out of the array). If this isn’t a pair, we go to the next letter, but if it is a pair, that is when it gets interesting. We check we already have found a pair. If this is the case, that's it, we match the requirement. But if not, that means that is the first pair we have found. So we register this information, and skip the next letter to avoid finding overlapping pairs.

Now, we can combine, with && operators, those functions in one, named isSafe to easily know if a password is safe.

So now, we can increment a password and check if a password matches the requirements. All we have to do, is to combine those features to find the next safe password for Santa.

Password newPassword (oldPassword);
do
{
    newPassword.increment();
} while (!newPassword.isSafe());

Voilà! By the end of this loop, we have our password ready for Santa to use it. 

Part 2

We will go quickly on this part, since the problem to solve is the same. Indeed, in this part, we need to find the next password of the password we have found in the previous part.

Personally, I’ve directly passed the password of Part 1 to the same program, to find the solution of this part. But if you want, you can also modify the program to make it find the second next password, by running the do-while loop twice.

I encourage you to look at the solution on my GitHub to look how I did that, since I use CMake to build and check the solution I’ve found.

Conclusion

You can note that the solutions, written in this post, don’t include all the sources to make running programs, but only the interesting part of the sources to solve this problem. If you want to see the programs from end to end, you can go on my GitHub account, explore the full solution, add comments or ask questions if you want to, on the platform you read this article, it will also help me improve the quality of my articles.

Here is the list of std methods that we have used, I can’t encourage you enough to look at their definitions:

• std::none_of
• std::array
• std::begin
• std::end

Thank you for reading, hope you liked it!

And until next part, have fun learning and growing.