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 contest, interview prep, company training, university coursework, practice 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:
- Helping Santa with various tasks (2015)
- Assisting Santa with his rivalry with the Easter Bunny (2016)
- Debugging the “Naughty or Nice” system (2017)
- Saving Santa from evil time travelers who are altering history to erase him from existence (2018)
- Rescuing Santa, who’s stranded at the edge of the solar system (2019)
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
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:
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 ameans that the password must containaat least1time and at most3times.In the above example,
2passwords are valid. The middle password,cdefg, is not; it contains no instances ofb, but needs at least1. The first and third passwords are valid: they contain oneaor ninec, 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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…
|
1 |
6-11 h: khmchszhmzm |
…the function would produce the following dictionary:
|
1 2 3 4 5 6 |
{ "min": 6, "max": 11, "char": h, "password": khmchszhmzm } |
Here’s the function:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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:
|
1 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
>>> 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:
|
1 2 3 |
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:
|
1 |
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:
|
1 2 |
>>> len(valid_passwords) 564 |
I entered this result and completed the first challenge.
The Day 2 challenge, part two
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
1means the first character,2means 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: abcdeis valid: position1containsaand position3does not.1-3 b: cdefgis invalid: neither position1nor position3containsb.2-9 c: cccccccccis invalid: both position2and position9containc.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:
|
1 2 3 4 5 6 7 8 |
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:
|
1 |
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:
|
1 2 |
>>> 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:
I first became aware of opening for a 
Monday, September 28th: I checked my email a lot, and at 1:15 p.m., this message arrived:
