Advent of Code 2020: Day 4

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:

iyr: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:

1

 std::regex reg("([a-z]{3}):([^\\s]+)");

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// Make a "dictionary" to store key:value pairs
std::map<std::string, std::string> documents;
while(std::getline(myfile, line)){
    // Loop through all key:value pairs along the line
    std::sregex_token_iterator it = {line.begin(), line.end(), reg, {1, 2}};
    while(it != std::sregex_token_iterator()){
        // When we find a pair store in map in the form
        std::string k = *it;
        it = std::next(it);
        std::string v = *it;
        // map[key] = value;
        documents[k] = v;
        it = std::next(it);
    }
    // If this line is blank, then we have finished with an
    // individual passport
    if (line == ""){
        bool valid = true;
        // We now loop over and check every required field is present
        // if the field is missing it will be ""
        for(auto &k : required){
            if (documents[k] == "") valid = false;
        }
        ans1 += valid;
        // Reset documents for next person
        documents.clear();
    }
}

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:

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:

1
2
3
4
5
6

bool valididate_byr(std::map<std::string, std::string> &documents){
    int val = std::stoi(documents["byr"]);
    if ((val >= 1920) && (val <= 2002))
        return true;
    return false;
}

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,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

bool valididate_hgt(std::map<std::string, std::string> &documents){
    const std::regex reg1("(^[0-9]{3}cm$)");
    const std::regex reg2("(^[0-9]{2}in$)");
    std::sregex_token_iterator it;
    it = {documents["hgt"].begin(), documents["hgt"].end(), reg1, 1};
    if(it != std::sregex_token_iterator()){
        int val = std::stoi(*it);
        if ((val >= 150) && (val <= 193)) return true;
    }
    ...
}

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,

1
2
3
4

bool valididate_hcl(std::map<std::string, std::string> &documents){
    const std::regex reg1("(^#[0-9a-f]{6}$)");
    ...
}

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:

1
2
3
4
5
6

bool valididate_ecl(std::map<std::string, std::string> &documents){
    const std::vector<std::string> ecls = {"amb", "blu", "brn", "gry", "grn", "hzl", "oth"};
    for (auto v : ecls)
        if (documents["ecl"] == v) return true;
    return false;
}

Then finally, we are onto the passport ID. Let’s go back to our good friend regex one last time,

1
2
3
4

bool valididate_pid(std::map<std::string, std::string> &documents){
    const std::regex reg1("(^[0-9]{9}$)");
    ...
}

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,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

if (valid){
    valid *= valididate_byr(documents);
    valid *= valididate_iyr(documents);
    valid *= valididate_eyr(documents);
    valid *= valididate_hgt(documents);
    valid *= valididate_hcl(documents);
    valid *= valididate_ecl(documents);
    valid *= valididate_pid(documents);
    ans2 += valid;
}

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

Comments