Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Incorrect Password

Advent of Code 2015 - Day 11

Day 11: Corporate Policy

Useful Links

‹›

Concepts and Packages Demonstrated

Regular Expressions (Regex)Recursionord()chr()Exceptions

Problem Intro

We need to devise a system that automatically generates a password based on the previous password. We need to generate new passwords by incrementing password characters from the rightmost character, in the same way that we would increment a number. Each new password must be exactly 8 lowercase characters. In addition, we’re giving a set of rules to match.

The input is simply the initial password we need to increment from. E.g.

cqjxjnds

This is fairly simple. We can do all the necessary string rule matching using regex. The slightly tricker bit is how we increment the string. I’ve elected to do this with some recursion.

Part 1

We’re provided with a set of rules:

Given Santa’s current password (the puzzle input), what should his next password be?

First, I define the rules we need to match against, using regular expressions:

# validate straight
STRAIGHT_MATCH = re.compile(r"abc|bcd|cde|def|efg|fgh|ghi|hij|ijk|jkl|klm|lmn|mno|nop|opq|pqr|qrs|rst|stu|tuv|uvw|vwx|wxy|xyz")
# Two non-overlapping pairs of any character
PAIRS_CHARS_MATCH = re.compile(r"(.)\1.*(.)\2")
# match any of i, o, u
BAD_CHARS_MATCH = re.compile(r"[iol]")

Rules explained:

Now I create a function that checks our rules:

def check_rules(a_password):
    """ Match the supplied password against our set of validation rules """
    if not STRAIGHT_MATCH.search(a_password):
        return False

    if BAD_CHARS_MATCH.search(a_password):
        return False
        
    two_pairs_match = PAIRS_CHARS_MATCH.search(a_password)
    if not two_pairs_match:
        return False
    else:
        pair_one, pair_two = two_pairs_match.groups()
        if pair_one == pair_two:
            # the two pairs must be different, e.g. aa and bb, but not aa and aa
            return False

    return True

This function passes in the password we want to check, and then checks it against our three regular expressions. If any of these expressions doesn’t much, then the function returns False. The only point worth mentioning is that when we’re applying the PAIRS_CHARS_MATCH rule, we check the two groups returned by any match, to determine if they are different. For example, if we applied this rule against aaefgaa, the regex would return two groups: aa and aa. If the two pairs are the same, then our rule has failed, and we return False.

Finally, if we’ve satisfied all the rules, we return True.

Next, I create a function that increments the password.

def increment_pwd(pwd):
    """ Recursive function that increments password supplied pwd by 1. 
    E.g. aaa -> aab; aay -> aaz; aaz -> aba
    
    Throws an IndexError if we try to increment a zero-length password
    """

    last_col = len(pwd) - 1
    char = pwd[last_col]
    left_chars = pwd[:last_col]
    new_char = next_char(char)

    if (new_char) == 'a':
        # We've rolled over from z to a, so we need to increment one column left
        # So pass in all pwd chars on the left, exluding rightmost column, and call this method recursively
        left_chars = increment_pwd(left_chars)
    
    new_pwd = left_chars + new_char
    return new_pwd

This function is recursive. This is how it works:

Note: there is a scenario where this function can throw an IndexError, as explained in the function comments. Imagine if our password is all z characters. In this scenario, each character will wrap around to a. Eventually, the recursive call to increment_pwd(left_chars) with an empty input string. In this situation, the call to len(pwd) will return 0, the last_col will be set to -1, and the attempt to index this string will fail with an IndexError. We’ll handle that later.

Once we’ve returned from this function, we test our newly constructed password, using the function we’ve already described.

Now let’s have a look at the next_char() function. This function has the job of incrementing the supplied character. E.g.

a -> b -> c... -> y -> z -> a

def next_char(a_char: str):
    if (a_char != 'z'):
        # get ascii code, add 1, then convert back to a char
        return chr(ord(a_char)+1)
    else:
        # if we're incrementing 'z', then we need to wrap around to 'a'
        return 'a'

This function is simple enough. We use ord() to change the current character to its unicode integer value. E.g.

Character Unicode Value
a 97
b 98
c 99
y 121
z 122

We then increment that value, and then we use chr() to convert back again. E.g. ord('a') gives us 97. We add 1 to get 98. And then chr(98) gives us b.

The exception is if our input character is z. In this case, we know we want to wrap around and return an a. Simple!

Now let’s put it all together:

def main():
    old_pwd = 'cqjxjnds'
    new_pwd = find_next_password(old_pwd)
    print(new_pwd)

def find_next_password(new_pwd: str):
    new_pwd_valid = False
    while not new_pwd_valid:
        try:
            new_pwd = increment_pwd(new_pwd)
            new_pwd_valid = check_rules(new_pwd)
        except IndexError:
            # thrown if we reach all z
            print("Max value reached")
            break
    return new_pwd

We start with our old_pwd, which is our input data. Then we pass this into the find_next_password() function. This function:

Part 2

We’re told Santa’s password has expired again. What is the next valid password?

Erm, okay. So, all I need to do is call my function again. Wow, easiest Part 2… ever!!

def main():
    old_pwd = 'cqjxjnds'

    # Part 1
    new_pwd = find_next_password(old_pwd)
    print(new_pwd)

    # Part 2 - just do it again!!
    new_pwd = find_next_password(new_pwd)
    print(new_pwd)

Here’s the output:

cqjxxyzz
cqkaabcc
Execution time: 1.4652 seconds

Fast enough.

On to the next challenge!

‹›