DEV Community 👩‍💻👨‍💻

Cover image for AoC 2015 - Day 11 - A little more RegEx

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:

Screenshot of Advent of Code 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'
            return l + chr(ord(r) + 1)
        return ''
Enter fullscreen mode Exit fullscreen mode

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'])):
Enter fullscreen mode Exit fullscreen mode

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):
    if ord(password[i]) == ord(password[i+1])-1 and 
       ord(password[i]) == ord(password[i+2])-2:
        has_straight = True
Enter fullscreen mode Exit fullscreen mode

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:
Enter fullscreen mode Exit fullscreen mode

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:
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)

Update Your DEV Experience Level:


Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. 🛠