# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python # Advent of Code 2015 - Day 11

## 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:

• Must have one straight of at least three characters. E.g. `cde`.
• Must not contain the letters `i`, `o`, `l`.
• Must contain at least two different, non-overlapping pairs, e.g. `aa` and `zz`.

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
``````

Rules explained:

• The first one is obvious. It’s just a bunch of straights and we need to match against any one of them.
• The second is a bit more tricky.
• We use `"(.)\1"` to mean: match any character, and then any subsequent character that is the same. So this would match `aa`, `bb`, etc.
• Then we use `".*"` to match 0 or more intervening characters.
• Then we use `"(.)\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.
• Note that as it stands, the `PAIRS_CHARS_MATCH` will match any string that contains two non-overlapping pairs, but it doesn’t check if the pairs are different. So, `aaghiaa` would 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 """
return False

return False

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:

• We get the rightmost character and increment it. (We’ll define the function that does that next.)
• We add the incremented character to all the preceeding characters, to create the new password.
• The interesting bit is where we check if the incremented character is an `a`.
If it is, then it means we’ve wrapped around from `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.

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'
print(new_pwd)

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:

• Increments the current password by 1.
• Tests whether the incremented password is valid.
• Repeats the above for as long as long as the incremented password isn’t valid.
• Catches the `IndexError` if 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.

## 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
print(new_pwd)

# Part 2 - just do it again!!
``````cqjxxyzz