AoC '20: Those Darn Queues

AoC '20: Those Darn Queues

Have you ever arrived at the airport, only to realise you had forgotten your passport? No, me neither. Alas, our intrepid vacationer appears to have done precisely this, bringing their 'North Pole Credentials' instead. Similar to a passport, the North Pole Credential does not have an associated country code since, well, the North Pole is not a country.

The queues at passport control are long and do not appear to be moving fast. Breaking through some remarkably lax network security, we discover that the automated gates are struggling to detect which passports have all of the required fields. We can solve both of these problems easy.

Day 4: Passport Processing

Digging a little deeper, we discover that the scanners are looking for eight fields. These are the birth year of the owner, BYR; the year of issue, IYR; the expiration year, EYR; the height of the owner, HGT; their hair colour, HCL; their eye colour, ECL; the passport ID, PID; and the ID of the country of issue, CID.

Part 0 — Parsing our Input

The passport scanners store their batch data in plain text, and we're able to pull it quite readily. One of the files we obtain looks like this.

ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm

iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929

hcl:#ae17e1 iyr:2013
eyr:2024
ecl:brn pid:760753108 byr:1931
hgt:179cm

hcl:#cfa07d eyr:2025 pid:166559648
iyr:2011 ecl:brn hgt:59in

The first of these is, presumably, valid, as all eight fields are present. The second, we assume, is not correct as it is missing the height field. The third passport is curious as, like ours, it is missing the country ID. We anticipate that this is also a North Pole Credential. The fourth is missing the country code, which is acceptable; however, it is also missing the birth year and is as such invalid. A blank line separates each passport.

We'll loop over each line, keeping a record of the passport we're currently reading. Each time we encounter a blank line, we push the present passport into an array and start a new one. The passport fields themselves are well-formed, and we read them using a simple regular expression.

(\w{3}):([^\s\r\n]+)

So, what's going on here? Well, we begin by capturing the first three word characters. Next, after a colon, we capture everything that is not a whitespace character. We do this by placing a caret at the beginning of our character list. Pulling all of the above together, we get the following.

var currPassport = [String:String]()
input.components(separatedBy: .newlines).forEach { line in
    if (line.isEmpty) {
        passports.append(currPassport)
        currPassport = [String:String]()
    } else {
        line.groups(for: #"(\w{3}):([^\s\r\n]+)"#).forEach { grp in
            currPassport.updateValue(grp[1], forKey: grp[0])
        }
    }
}
passports.append(currPassport)

Part 1

Passport batches parsed, we need to understand how many of the passports are valid. Filtering is an excellent way to achieve this goal. We can begin by configuring a dictionary of string keys and boolean values, to indicate whether or not a field is required.

let fields = [
    "byr": true,
    "iyr": true,
    "eyr": true,
    "hgt": true,
    "hcl": true,
    "ecl": true,
    "pid": true,
    "cid": false
]

Then, we can easily filter our array of passports.

let valid = passports.filter { passport in
    fields.allSatisfy { field in
        return !field.value || passport.keys.contains(field.key)
    }
}.count

In this block, we filter out any passwords that do not satisfy the criteria. The allSatisfy method executes a closure for each key-value pair in fields. Should any return false, the passport is filtered out. Firstly, we bail early if the field is not required by checking that the inverse of field.value is true. If we consult our earlier table, we know that this will only be truthy for the cid field. If the field is required, we can then check that the passport contains it by testing the corresponding key in the passport dictionary.

Executing this filter, we can establish that, of those given, 208 passports are valid.

Part 2

To our relief, the line has started to gain pace. We cannot help but overhear a conversation between two passport control personnel, though. It turns out our fix is letting through invalid passports! We best add some validation and, luckily, quickly locate a file that establishes some rules.

  • The birth year must be at least 1920 and at most 2002.
  • The issue year must be at least 2010 and at most 2020.
  • The expiration year must be at least 2020 and at most 2030.
  • The height must be a number, followed by a unit. If the unit is centimetres, the height must be at least 150 and at most 193. If the unit is inches, the height must be at least 59 and at most 76.
  • The hair colour must be a six-digit base-16 number, preceded by a pound sign.
  • The eye colour must be exactly one of amb, blu, brn, gry, grn, hzl or oth.
  • The passport ID must be exactly nine digits.
  • We ignore the country ID.

We'll need to write a new filter that accounts for all of these, but we can begin with a familiar-looking starting point.

let valid = passports.filter { passport in
    fields.allSatisfy { field in
        var result = false
        if !field.value {
            result = true
        } else if passport.keys.contains(field.key) {
            let value = passport[field.key]!
            /* ... */
        }
        return result
    }
}

Here, we check if the field is optional and then ensure that the passport contains it. The surrounding code does not change from the first part of this solution. Providing the field is required, and the passport has it, we can then begin our validation steps. When analysing the requirements, three distinct groups arise. Let's start with birth year, issue year and expiry year.

switch (field.key) {
case "byr":
    let i = Int(value)!
    result = clamp(i, 1920, 2002) == i
case "iyr":
    let i = Int(value)!
    result = clamp(i, 2010, 2020) == i
case "eyr":
    let i = Int(value)!
    result = clamp(i, 2020, 2030) == i

Inside a switch statement, we define the first three cases. In each, we wish to confirm that the value in the passport matches itself when clamped. If it does not, the values are invalid. Moving on, the next group are the hair colour, eye colour and passport ID.

case "hcl":
    result = value.matches(#"#[0-9a-f]{6}"#)
case "ecl":
    result = value.matches(#"(amb|blu|brn|gry|grn|hzl|oth){1}"#)
case "pid":
    result = value.matches(#"^[0-9]{9}$"#)
default:
    result = false

We can validate each of these using a straight forward regular expression. For hair colour, we look for a pound symbol followed by precisely six base-16 digits. For eye colour, we look for the appropriate one of the given colour codes. Lastly, for the passport ID, we look for precisely nine numbers. Notable in the last case is the use of the caret and dollar sign. These are anchors, and they ensure that our search criteria starts and ends with the first and last digits, respectively. In this instance, anchors prevent us from accidentally matching a nine-digit number in a larger number. Additionally, we define a default case that results in false. Whilst the case should never arise, it is required to ensure the switch statement is exhaustive.

The last case is an intersection of the former two. Let's take a look.

case "hgt":
    if value.matches(#"(\d+)(cm|in)"#) {
        let groups = value.groups(for: #"(\d+)(cm|in)"#).first!
        let num = Int(groups[0])!
        let unit = groups[1]
        switch (unit) {
        case "cm":
            result = clamp(num, 150, 193) == num
        case "in":
            result = clamp(num, 59, 76) == num
        default:
            break
        }
    } else {
        result = false
    }

We define another regular expression, which looks for one or more digits, followed by either cm or in. If the value in of the height field in the passport matches this, we go on to process it in the same way as we did the first group. If the units are in centimetres, we clamp between 150 and 193, and, if they are inches, 59 and 76. Again, we ensure that the input value matches the clamped value and discard the passport if not.

After executing our new validation routine, we observe that there are 167 valid passports.

Complete Code

You can find my complete solution here.

Show Comments