## DEV Community 👩‍💻👨‍💻 is a community of 963,503 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Jules

Posted on

# AoC 2015 - Day 11 - A little more RegEx

Santa has a strange (and dangerous!) way of choosing passwords -- here's how it's described in the puzzle:

All of which is a long way of saying:

1. To find Santa's next password, we have to increment the existing password, which comprises of eight characters.

2. We increment the password until three rules are met.

## Incrementing letters

This looks annoyingly simple on its surface, but actually took me a while to figure out.

If the existing password is `abc`, we are going to increment it to `abd`. All well and good, but what happens when we get to `abz`? We increment the same way we would a number, and start on the next column, so we get `aca`.

I've assumed that the next password after `zzzzzzzz` is `aaaaaaaa`, but thankfully, we never get to this situation in the real puzzle. I ended up thinking of the password as a Base 26 number, not that it helped with the coding.

Here's how I ended up incrementing Santa's password, which involved recursion!

``````def incr_string(s):
if len(s):
l, r = s[:-1], s[-1]
if r == 'z':
return incr_string(l) + 'a'
else:
return l + chr(ord(r) + 1)
else:
return ''
``````

What we're doing here is splitting the string into two parts: (i) everything up to the last letter, and (ii) the last letter. If we're lucky enough not to have to roll a `z` into an `a`, we convert it into its Ascii number, add one, then convert it back to a character.

If the last character is a `z`, we go off to the function again to increment the string without its last character, then return that result with an 'a' on the end. And, of course, if the existing password is `abcdzzzz` we get quite deep into the recursion!

## The Rules

Once we've incremented the password, it's time to check whether it passes all the rules:

1) Passwords must include one increasing straight of at least three letters, like abc, bcd, cde, and so on, up to xyz. They cannot skip letters; abd doesn't count.

Thanks to the second rule below, I ended up with a shortish list of triplets that are actually allowed:

``````if sum(map(s.count, ['abc', 'bcd', 'cde',
'def', 'efg', 'fgh',
'pqr', 'qrs', 'rst',
'stu', 'tuv', 'uvw',
'vwx', 'wxy', 'xyz'])):
``````

However, there were lots of arguably better ways of finding increasing straights in the megathread, including looping through the word and checking consecutive letters:

``````has_straight = False
for i in range(len(password) - 2):
has_straight = True
break
``````

Surprisingly, I haven't found anyone using a RegEx approach to finding three consecutive letters.

2) Passwords may not contain the letters i, o, or l, as these letters can be mistaken for other characters and are therefore confusing.

This, by now, was a lot more straightforward, like counting vowels on Day 5:

``````if sum(map(s.count, 'iol')) == 0:
``````

3) Passwords must contain at least two different, non-overlapping pairs of letters, like aa, bb, or zz.

Here's where I needed some RegEx, and really needed to read the puzzle better, having completely missed the word 'different'. For longer than I care to admit, I was allowing passwords like `abcxxdxx`, without noticing the pairs have to be different.

First of all, we need some working RegEx. The pattern for finding identical non-overlapping pairs of letters in a string is `(.)\1` which you can verify here. I used `findall()` to retrieve all the matching pairs, which I then shoved into a set to make sure I had more than one different pair:

``````if len(set(re.findall(r'(.)\1', s))) > 1:
``````

And that's basically it. Take the existing password (the puzzle input) and increment it until it meets the rules.

Unusually for Advent of Code, Part 2 was simply to find the second password, so there was no more code to write. Onwards!