Advent of Code – Day 11

Tags: advent-of-code data-structure algorithms practice

Welcome to day 11 of advent of code where will be helping Santa to create secure passwords. We have already been given how to create new passwords but there is a new security guy who has come up with three new requirements to make the passwords more secure. So let’s start by tackling these three requirements.

We are essentially trying to check the password for three conditions and it can easily be done by using pattern matching by regular expressions.

The 3 conditions of Security Department

Condition 1

The first condition is to find if the given password contains at least two double pairs of letters. We will use Regex.Matches which gives a MatchCollection containing all the matches present for the given regular expression. If we have more than 2 distinct pairs, then we are good.

private static bool ContainsAtLeastTwoDoublePairs(string password)
{
    var matches = Regex.Matches(password, @"(\w)\1", RegexOptions.IgnoreCase);
    if (matches.Count < 2)
    {
        return false;
    }
    else
    {
        var values = new List<string>();

        foreach (Match match in matches)
        {
            values.Add(match.Value);
        }
         return values.Distinct().Count() >= 2;
    }
}

Condition 2

The second condition is to find at least 1 run of 3 or more characters. We can iterate through the password and for each character check the next two characters. we would want that the difference between the successive characters is always 1. If that’s not the case till the very last character and the condition is not satisfied, then we simply reject the password.

private static bool ContainsAtLeastOneRun(string password)
{
    char current, next, nexter;
    for (int index = 0; index < password.Length; index++)
    {
        // If this condition is true, then there is no run
        // possible of length 3 or more
        if (index >= password.Length - 2) return false;

        current = password[index];
        next = password[index + 1];
        nexter = password[index + 2];

        // This means we have found a single run of chars, which is the minimum
        // to pass.
        if (((int)next - (int)current == 1) &&
            ((int)nexter - (int)current == 2))
        {
            return true;
        }
    }
     return false;
}

Condition 3

The third condition is pretty easy to understand. We simply have to check whether the string contains the letters i, o or l and if it is then we reject the password.

private static bool NotContainsIOL(string password)
{
    var match = Regex.Match(password, @"i|o|l", RegexOptions.IgnoreCase);
    return !match.Success;
}

The three conditions can be clubbed together to check the validity of the password.

public static bool IsValidPassword(string password)
{
    return NotContainsIOL(password) &&
        ContainsAtLeastOneRun(password) &&
        ContainsAtLeastTwoDoublePairs(password);
}

Incrementing the Password

With these three conditions being taken care of we can concentrate on creating the iterator of the password with takes in a password and returns a new password by incrementing it.

The first step in tackling this requirment is to reverse the password because that will make on the algorithms a bit more symmetric. Then you can start from the beginning (which would have been the end of the original password) increment the characters from left to right. If the first character is z then we increment it and increment the rest of the string. If the first character is anything other than z then we do not touch the rest of the string.

Since C# doesn’t provide a method to reverse a string (unless you treat it as an IEnumerable<char>), the following method works well for non-unicode strings which we have for this problem. More solutions are here.

private static string Reverse(string s)
{
    var array = s.ToCharArray();
    Array.Reverse(array);
    return new String(array);
}

private static string Increment(string password)
{
    if (string.IsNullOrEmpty(password))
    {
        return string.Empty;
    }

    var firstChar = password[0];
    if (firstChar == 'z')
    {
        return NextChar(firstChar).ToString() + Increment(password.Substring(1));
    }
    else
    {
        return NextChar(firstChar).ToString() + password.Substring(1);
    }
}

Next Password

The last step is to start with a password, call the Increment function and keep calling it unless we find valid password which passes the IsValidPassword check above.

public static string NextValidPassword(string password)
{

    var currentPassword = NextPassword(password);

    while(!IsValidPassword(currentPassword))
    {
        currentPassword = NextPassword(currentPassword);
    }

    return currentPassword;
}

private static string NextPassword(string password)
{
    var reversedPassword = Reverse(password);
    var next = Increment(reversedPassword);
    return Reverse(next);
}

I have kept all the functions here static because none of these depend on the shared state. In fact there is no shared state here. Everything is kind of functional – it depends on whatever the argument is passed in and simply returns a new output.

The code is present at github.