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.
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]")
"(.)\1"to mean: match any character, and then any subsequent character that is the same. So this would match
".*"to match 0 or more intervening characters.
"(.)\2"to mean: match any character, and then any subsequent character that is the same. It’s the same as the first rule, but uses
"\2", since we’re now matching against second group, rather than the first group.
PAIRS_CHARS_MATCHwill match any string that contains two non-overlapping pairs, but it doesn’t check if the pairs are different. So,
aaghiaawould match okay. But we need this to not be okay. We’ll deal with that later, in the code.
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. If the two pairs are the same, then our rule has failed, and we return
Finally, if we’ve satisfied all the rules, we return
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:
z. And in that case, we now need to increment the column on the left. To do this, we recursively call the same function, passing in all the password characters except the one we just incremented.
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.
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
The exception is if our input character is
z. In this case, we know we want to wrap around and return an
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:
IndexErrorif we’ve reached the maximum value for the password, i.e. all
z. Now would be a good time to check out my page on exception handling works in Python. We only use exceptions to handle conditions that we believe to be abnormal.
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
On to the next challenge!