Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 2 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

For those of you not familiar with Advent of Code, here’s a quick description, taken straight from their “About” page…

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contestinterview prepcompany traininguniversity courseworkpractice problems, or to challenge each other.

You don’t need a computer science background to participate – just a little programming knowledge and some problem solving skills will get you pretty far. Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

Advent of Code has been around since 2015, and each year, its puzzles have all been centered around a “Save Christmas” theme. Over the past five holidays seasons, programmers all over the world have solved problems using code in order to:

This year’s puzzles are about saving the well-earned vacation you’re taking, after having saved Christmas five years in a row. Day 1’s puzzles had you fix an expense report that you had to deal with before you could go on vacation, and I posted my Python solution yesterday.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 2 challenge.

The Day 2 challenge, part one

Meme: When you remember the password to your account on the first try, featuring Fat Thor holding his hammer and saying “I’m still worthy!”

Here’s the text from part one of the challenge:

Day 2: Password Philosophy

Your flight departs in a few days from the coastal airport; the easiest way down to the coast from here is via toboggan.

The shopkeeper at the North Pole Toboggan Rental Shop is having a bad day. “Something’s wrong with our computers; we can’t log in!” You ask if you can take a look.

Their password database seems to be a little corrupted: some of the passwords wouldn’t have been allowed by the Official Toboggan Corporate Policy that was in effect when they were chosen.

To try to debug the problem, they have created a list (your puzzle input) of passwords (according to the corrupted database) and the corporate policy when that password was set.

For example, suppose you have the following list:

1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc

Each line gives the password policy and then the password. The password policy indicates the lowest and highest number of times a given letter must appear for the password to be valid. For example, 1-3 a means that the password must contain a at least 1 time and at most 3 times.

In the above example, 2 passwords are valid. The middle password, cdefg, is not; it contains no instances of b, but needs at least 1. The first and third passwords are valid: they contain one a or nine c, both within the limits of their respective policies.

How many passwords are valid according to their policies?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through the usual process of bringing it into Python by pasting it into a triple-quoted string and assigning it to the variable raw_input.

I then split the string into an array, using the newline character as the delimiter. I named the array split_input.

Here’s the code, with the data abridged for brevity:

raw_input = """3-5 f: fgfff
6-20 n: qlzsnnnndwnlhwnxhvjn
6-7 j: jjjjjwrj
8-10 g: gggggggggg
5-6 t: ttttttft
6-11 h: khmchszhmzm
4-6 q: qqbjqqqj

...

3-6 h: hdhjhhhhchh
11-12 r: zrrkcrrrrrlh
7-9 v: vhqvlvwvzqwqvrxvjnf
1-5 r: rvmjr"""

split_input = raw_input.split("\n")

Formatting the data

One of the best things you can do while taking on an Advent of Code puzzle is to convert the data set you’re given into a format that will make it easier to solve the problem. The second part of the puzzle is usually based on the same data, and having it already in a helpful format will save you a lot of time.

With that in mind, my next step was to define a function that would convert each line in split_input into a dictionary. For example, when given the following line…

6-11 h: khmchszhmzm

…the function would produce the following dictionary:

{
"min": 6,
"max": 11,
"char": h,
"password": khmchszhmzm
}

Here’s the function:

def convert_to_password_and_policy_dict(line):
    password_and_policy_dict = {}
    password_and_policy_list = line.split()
    
    min_max = password_and_policy_list[0].split("-")
    password_and_policy_dict["min"] = int(min_max[0])
    password_and_policy_dict["max"] = int(min_max[1])
    
    password_and_policy_dict["char"] = password_and_policy_list[1][0]
    
    password_and_policy_dict["password"] = password_and_policy_list[2]
    
    return password_and_policy_dict

I used convert_to_password_and_policy_dict() in a list comprehension to convert split_input into a list of “password and policy” dictionaries named passwords_and_policies:

passwords_and_policies = [convert_to_password_and_policy_dict(password_and_policy) for password_and_policy in split_input]

Here’s a peek at passwords_and_policies’ contents:

>>> passwords_and_policies
[{'min': 3, 'max': 5, 'char': 'f', 'password': 'fgfff'},
 {'min': 6, 'max': 20, 'char': 'n', 'password': 'qlzsnnnndwnlhwnxhvjn'},
 {'min': 6, 'max': 7, 'char': 'j', 'password': 'jjjjjwrj'},
 {'min': 8, 'max': 10, 'char': 'g', 'password': 'gggggggggg'},
 {'min': 5, 'max': 6, 'char': 't', 'password': 'ttttttft'},

...

 {'min': 6, 'max': 12, 'char': 'g', 'password': 'dmgggpgggwczggghggm'},
 {'min': 3, 'max': 6, 'char': 'h', 'password': 'hdhjhhhhchh'},
 {'min': 11, 'max': 12, 'char': 'r', 'password': 'zrrkcrrrrrlh'},
 {'min': 7, 'max': 9, 'char': 'v', 'password': 'vhqvlvwvzqwqvrxvjnf'},
 {'min': 1, 'max': 5, 'char': 'r', 'password': 'rvmjr'}]

I then wrote a function that takes a “password and policy” dictionary and returns True if the dictionary’s password meets its policy:

def meets_password_policy(password_and_policy):
    char_count_in_password = password_and_policy["password"].count(password_and_policy["char"])
    return password_and_policy["min"] <= char_count_in_password <= password_and_policy["max"]

I used that function as the criteria for a filter() to create a list of only “password and policy” dictionaries whose passwords met their policies:

valid_passwords = list(filter(meets_password_policy, passwords_and_policies))

The solution to the first puzzle is the number of dictionaries in the resulting list, valid_passwords:

>>> len(valid_passwords)
564

I entered this result and completed the first challenge.

The Day 2 challenge, part two

Meme: Sorry, but your password must contain an uppercase letter, a number, a hieroglyph, a feather from a hawk, and the blood of a unicorn.

Here’s the text from part two of the challenge:

While it appears you validated the passwords correctly, they don’t seem to be what the Official Toboggan Corporate Authentication System is expecting.

The shopkeeper suddenly realizes that he just accidentally explained the password policy rules from his old job at the sled rental place down the street! The Official Toboggan Corporate Policy actually works a little differently.

Each policy actually describes two positions in the password, where 1 means the first character, 2 means the second character, and so on. (Be careful; Toboggan Corporate Policies have no concept of “index zero”!) Exactly one of these positions must contain the given letter. Other occurrences of the letter are irrelevant for the purposes of policy enforcement.

Given the same example list from above:

  • 1-3 a: abcde is valid: position 1 contains a and position 3 does not.
  • 1-3 b: cdefg is invalid: neither position 1 nor position 3 contains b.
  • 2-9 c: ccccccccc is invalid: both position 2 and position 9 contain c.

How many passwords are valid according to the new interpretation of the policies?

Since I already had the data in a nice, usable format, solving part two of the puzzle was easy. I simply wrote a new function that takes a “password and policy” dictionary and returns True if the dictionary’s password meets the policy described in part two:

def meets_new_password_policy(password_and_policy):
    first_position = password_and_policy["min"]
    char_in_first_position = password_and_policy["password"][first_position - 1] == password_and_policy["char"]
    
    second_position = password_and_policy["max"]
    char_in_second_position = password_and_policy["password"][second_position - 1] == password_and_policy["char"]

    return char_in_first_position ^ char_in_second_position

Note the return statement. While Python has the and and or keywords for logical and and or, it uses the ^ character for logical exclusive or.

I used that function as the criteria for a filter() to create a list of only “password and policy” dictionaries whose passwords met their policies, according to the new rules:

new_valid_passwords = list(filter(meets_new_password_policy, passwords_and_policies))

The solution to the second puzzle is the number of dictionaries in the resulting list, new_valid_passwords:

>>> len(new_valid_passwords)
325

Upon entering that result, the Day 2 challenge was complete!

Other days’ solutions:

Here are my solutions for other days in Advent of Code 2020:

2 replies on “My solution to Advent of Code 2020’s Day 2 challenge, in Python”

Good stuff so far thankyou. I’m trying to gain familiarity with Python, and your Pyhonesque answers are always muchore succinct than mine. Plus I’ve learnt about filter, map, combinations and that ^ is an exclusive or (I used !=) Which is odd given that && must be spelt as and.

On to day 3

Leave a Reply

Your email address will not be published. Required fields are marked *