Passport Processing
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-13 23:45:46

## [Advent of Code 2020 Day 4](https://adventofcode.com/2020/day/4)

## Task: Solve for X where...
```
X = the number of valid passports
```
1. All required keys are present
2. All values associated with required keys are correct

### Example input
```
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
```

It represents:
- A list of passport data
- Each passport contains up to 8 key:value pairs

## Part 1
1. Considering three algorithmic ingredients
2. Writing the algorithm

### Considering three algorithmic ingredients
1. Regular expression
2. Length
3. Includes

#### Regular expression
- For each passport, identify each of the eight keys
```
/(ecl|pid|eyr|hcl|byr|iyr|cid|hgt)/g
```

#### Length
- From the list of matches, check the count
- If it's 8, the passport must be valid
- If it's 6 or less, the passport must be invalid

#### Includes
- If it's 7, check for inclusion of `cid` as a key.
- If it is, that means we're missing a required key, so it must be invalid
- If it isn't, then we must have all required keys, so the passport must be valid

### Writing the algorithm
```
Split the input at each double-new-line character into an array of strings

For each item in the array of strings
  Change the item to an array of matched keys found using the regular expression above

Filter the array of matched keys to only include 'true' values where:
    1. The array's length is 8
    2. The array's length is 7 and it doesn't include 'cid'

Return the length of the filtered array
```

## Part 2
1. A litany of utility functions and regular expressions
2. Storing the functions as methods on an object
3. Small addition to the root regular expression
4. Writing a working algorithm

### A litany of utility functions and regular expressions
- Beyond identifying passports with required keys present, I must now ensure their values are valid
- It seems I'll need utility functions and regular expressions to check each key's value

`byr` `iyr` `eyr` are similar:
```
Return true if:
  String length is 4
  Value is within a range
```

`hgt` is a regular expression, then a few checks:
```
Regular expression:
/(\d+)(\w+)/

Return true if:
  String matches the regular expression
  Depending on 'cm' or 'in', the value is within a range
```

`hcl` is a regular expression:
```js
/#([0-9a-f]{6})/
```

`ecl` is a regular expression:
```js
/(amb|blu|brn|gry|grn|hzl|oth){1}/
```

`pid` is a regular expression:
```js
/^\d{9}$/
```

`cid` is always true.

### Storing the functions as methods on an object
```
rules = {
  byr()...,
  hgt()...,
  ...
}
```

Each key:value pair match has this structure
```
['byr', '2000']
```

So I can run the test using:
```
rules[key](value)
```

### Small addition to the root regular expression
Part 1 featured a regular expression to capture each key:
- Where each key could be one of eight 3-letter combinations
```js
/(ecl|pid|eyr|hcl|byr|iyr|cid|hgt)/g
```

Part 2 requires a regular expression that captures key and value:
- Where value could be one or more letters, one or more digits, or a single hashtag
```js
/(ecl|pid|eyr|hcl|byr|iyr|cid|hgt):([\w|\d|#]+)/g
```

### Writing a working algorithm
```
Split the input at each double-new-line character into an array of strings

For each item in the array of strings
  Change the item to an array of matched keys found using the updated regular expression above

Filter the array of matched keys to only include 'true' values where:
  1. The array's length is 8
  2. The array's length is 7 and it doesn't include 'cid'

Filter the array of valid - in that all required keys are present - passports to only include 'true' values where:
  Every value for each key returns 'true' for the appropriate test found in the 'rules' object for that key

Return the length of the filtered array
```

I recall skipping this puzzle the first time I read it because I knew it would require regular expressions.

This time around, I felt delightfully comfortable building each RegEx.

It continues to feel rewarding when these early-day puzzles feel easier than anticipated.