Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Naughty or Nice

Advent of Code 2015 - Day 5

Day 5: Doesn't He Have Intern-Elves For This?

Useful Links

Concepts and Packages Demonstrated

Regular Expressions (Regex)Regexr - Testing Regexlist comprehensionlist countsum

Problem Intro

We’re asked to parse a list of strings, and determine which ones are naughty, and which ones are nice.

Nice strings must match the following rules:

The input data looks something like this:

ugknbfddgicrmopn
jchzalrnumimnmhp
haegwjzuvuyypxyu
dvszwmarrgswjxmb

Part 1

How many strings are nice?

We could do this the naive way. For example, for the first rule, we could iterate through all chars in the string aeiou, count how many times each appears in the line, and then add them to an overall vowel count.

But it’s actually much more efficient (and fun!) to do this with regex. And for me, this was a great opportunity to improve my regex skills.

Let’s look at the regex for each rule:

At least three vowels

([aeiou].*){3,}

Breaking it down:

At least one character repeat

(.)\1

Does not contain ab, cd, pq, xy

ab|cd|pq|xy

This is obvious. It means any of ab, or cd, or pq, or xy.

Solution

The code looks like this:

from pathlib import Path
import time
import re

SCRIPT_DIR = Path(__file__).parent 
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")

# part 1 rules
three_vowels_match = re.compile(r"([aeiou].*){3,}") # Match any vowel, three or more times
double_chars_match = re.compile(r"(.)\1")  # \1 means: repeat what we matched before
bad_chars_match = re.compile(r"ab|cd|pq|xy")

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = f.read().splitlines()

    nice_lines_count = [part_1_rules_match(line) for line in data].count(True)
    print(f"Part 1: there are {nice_lines_count} nice strings.")

def part_1_rules_match(input_line):
    if (three_vowels_match.search(input_line) 
            and double_chars_match.search(input_line) 
            and not bad_chars_match.search(input_line)):
        return True
    
    return False

Note that I’ve created a function called part_1_rules_match(). This function:

Next, we use this function in a list comprehension. I.e.

[part_1_rules_match(line) for line in data]

Simples!

Part 2

Santa has abandoned all the rules from Part 1! A nice string must now follow these rules:

How many strings are nice with the new rules?

We need two new regex rules:

A repeating pair

(..).*\1

Any two chars that repeat, with a single char between them

(.).\1

Solution

First, let’s add our regex rules:

# part 2 rules
char_pair_repeats_match = re.compile(r"(..).*\1")
xwx_match = re.compile(r"(.).\1")

The remaining code additions to solve part 2 are trivial. First, a function that tests both of the new rules, and only returns True if both rules match:

def part_2_rules_match(input_line):
    if (char_pair_repeats_match.search(input_line)
            and xwx_match.search(input_line)):
        return True
    
    return False

And finally, perform the count:

    nice_lines_count = [part_2_rules_match(line) for line in data].count(True)
    print(f"Part 2: there are {nice_lines_count} nice strings.")

The final output looks something like this:

Part 1: there are 258 nice strings.
Part 2: there are 53 nice strings.
Execution time: 0.0037 seconds