Advent of Code 2020: Day 4
, 8 min readadvent of code 2020
Part 1
You arrive at the airport only to realise that you grabbed your North Pole Credentials instead of your passport. While these documents are extremely similar, North Pole Credentials aren’t issued by a country and therefore aren’t actually valid documentation for travel in most of the world.
It seems like you’re not the only one having problems, though; a very long line has formed for the automatic passport scanners, and the delay could upset your travel itinerary.
Due to some questionable network security, you realise you might be able to solve both of these problems at the same time.
The automatic passport scanners are slow because they’re having trouble detecting which passports have all required fields. The expected fields are as follows:
byr (Birth Year), iyr (Issue Year), eyr (Expiration Year), hgt (Height), hcl (Hair Color), ecl (Eye Color), pid (Passport ID), cid (Country ID)
Passport data is validated in batch files (your puzzle input). Each passport is represented as a sequence of “key:value” pairs separated by spaces or newlines. Passports are separated by blank lines. Here is an example batch file containing four passports:
ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cmiyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929
According to the above rules, your improved system would report 1 valid passports. Count the number of valid passports - those that have all required fields. Treat cid as optional. In your batch file, how many passports are valid?
You can read the full text here.
Oh no. It looks like we need to implement a fake passport control system, the main issue is: I’m rubbish at ingesting data in C++! The input is a series of lines where each line contains several “key:pair” tokens which are space-separated. The information is divided into separate documents using blank lines.
Fortunately, for part 1, all we need to is ensure that the passport documents have all of the required keys. I’m going to use my new (limited) regex knowledge to implement a pattern matching system.
First of all, we need to open the file and loop through looking for all of the “key:pair"s. We’re going to use the following regex pattern:
|
|
This identifies the keys, which are always 3 lower case characters. These are followed by a “:” and then by a string. At this point, we don’t really know anything about the string, so I’m just setting it as a sequence of characters, except space as the “key:value” pairs are space-separated.
Awesome! We can now pattern match, we know which list of keys is required to make the passport valid. Thus, we can turn this into a working solution.
|
|
Perfect. We’ve ingested the data and validated that all of the required fields are present. That’s the first ⭐ in the bag!
Part 2
The line is moving more quickly now, but you overhear airport security talking about how passports with invalid data are getting through. Better add some data validation, quick!
You can continue to ignore the cid field, but each other field has strict rules about what values are valid for automatic validation:
byr (Birth Year) - four digits; at least 1920 and at most 2002.
iyr (Issue Year) - four digits; at least 2010 and at most 2020.
eyr (Expiration Year) - four digits; at least 2020 and at most 2030.
hgt (Height) - a number followed by either cm or in:
If cm, the number must be at least 150 and at most 193.
If in, the number must be at least 59 and at most 76.
hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.
ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
pid (Passport ID) - a nine-digit number, including leading zeroes.
cid (Country ID) - ignored, missing or not.
Your job is to count the passports where all required fields are both present and valid according to the above rules.
You can read the full text here.
We now continue along a similar vein. Still, ensuring that the required fields are present, we also have to validate their contents according to the rules above.
We can just add some extra functions to our previous solution. After we have ingested the data and confirmed that all of the required fields are present, we can loop over each of the keys and validate them individually.
A quick exploration of my input suggests, that when present, the birth year, the issue year and the expiration year are always numbers. Excellent, that means we don’t have to do too much here. We can just implement a few helper functions of the form:
|
|
where we convert our string to an integer and check the bounds. This process is the same for issue year and expiry year. Next we have the height, for this we’re using regex again,
|
|
We check to see if the value of “hgt” is some numbers followed by either “cm” or “in”. Then we just bounds-check the value of the number. The code repeats this for inches.
Next we have the hair color, “hcl”, for this we use regex again,
|
|
here we use the pattern matching to identify a “#” followed by 6 characters which are either numbers or letters, a-f. Next up is eye colour, “ecl”, this needs to be a value in the list “amb”, “blu”, “brn”, “gry”, “grn”, “hzl”, “oth”. This one is easy:
|
|
Then finally, we are onto the passport ID. Let’s go back to our good friend regex one last time,
|
|
we just search for a pattern which is a 9 digit number.
Throughout the validation functions, I have used the symbols “^” and “$” at the beginning and ends of my pattern, respectively. These symbols ensure that the pattern is the entire string. If we didn’t do this then we may find a 9-digit passport ID within a 10 digit string - which would be wrong.
All we need to do now is add the following code to the loop from part 1,
|
|
which validates all of the fields, if they are present, and counts how many entries are valid in total.
That’s both stars: ⭐⭐
Reflections
Today’s puzzle was more an exercise in data hygiene than algorithms. However, the optimal solution is probably to read in each key:pair, one at a time, validate them. As soon as a single key:pair is invalid, for part 2, we can stop validating further entries. However, for part 1, we still have to keep reading in the inputs to see if we have all of the required fields.
The problem today will be O(N)
where N
is the number of documents that we must validate. Assuming the map
lookup is O(1)
, which is not currently true but can be achieved with an unordered_map
.
This was a really good opportunity for me to use more regex, and I think I really benefited from it. I hope you did too, see you tomorrow!
I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators