Amirata

BlogAboutContact

December 14, 2020

Advent of Code 2020 Day 4 Solution

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. — AdventOfCode.com

For this puzzle, we're given a list of passport data and our job is to count the valid passports.

Passports are separated by a blank line and each passport is repersented as a sequence of key:value paris separated by space or newlines. Here's an example input:

1ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
2byr:1937 iyr:2017 cid:147 hgt:183cm
3
4iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
5hcl:#cfa07d byr:1929
6
7hcl:#ae17e1 iyr:2013
8eyr:2024
9ecl:brn pid:760753108 byr:1931
10hgt:179cm
11
12hcl:#cfa07d eyr:2025 pid:166559648
13iyr:2011 ecl:brn hgt:59in

Every field listed below is required except for cid which is optional:

  • byr (Birth Year)
  • iyr (Issue Year)
  • eyr (Expiration Year)
  • hgt (Height)
  • hcl (Hair Color)
  • ecl (Eye Color)
  • pid (Passport ID)
  • cid (Country ID)

Part I

Problem: Count the number of valid passports (Ones that have all the requried fields.)

Solution: We're going to parse our input and turn it into an array of objects. After that, it should be easier to determine which passports are valid.

1const input = `
2ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
3byr:1937 iyr:2017 cid:147 hgt:183cm
4
5iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
6hcl:#cfa07d byr:1929
7
8hcl:#ae17e1 iyr:2013
9eyr:2024
10ecl:brn pid:760753108 byr:1931
11hgt:179cm
12
13hcl:#cfa07d eyr:2025 pid:166559648
14iyr:2011 ecl:brn hgt:59in
15`;
16
17function parseInput(input: string) {
18 return input
19 .trim()
20 .split("\n\n")
21 .map((str) => {
22 const obj: Record<string, string> = {};
23 const pairs = str.split(/\s/).map((p) => p.split(":"));
24 pairs.forEach((p) => (obj[p[0]] = p[1]));
25 return obj;
26 });
27}
28
29// true means "required" and false means "optional"
30const validKeys = {
31 byr: true,
32 iyr: true,
33 eyr: true,
34 hgt: true,
35 hcl: true,
36 ecl: true,
37 pid: true,
38 cid: false,
39};
40
41function part1() {
42 const passports = parseInput(input);
43 let validCount = 0;
44
45 for (const passport of passports) {
46 let validKeyCount = 0;
47
48 for (const key in passport) {
49 const seenKeys = new Set<string>(); // using this set to handle duplicate keys
50
51 // if an invalid key is found, skip this passport
52 // because it can't be invalid. The actual input
53 // doesn't have any invalid keys, but we do this
54 // to be safe.
55 if (!(key in validKeys)) {
56 continue;
57 }
58
59 if (validKeys[key] && !seenKeys.has(key)) {
60 validKeyCount++;
61 seenKeys.add(key);
62 }
63 }
64
65 // if the password is valid, "validKeyCount" must
66 // be exactly "7".
67 if (validKeyCount === 7) validCount++;
68 }
69
70 return validCount;
71}

Complexity: The time complexity is linear (O(n) where n is the number of passports.) The second loop is negligible. The space complexity is constant. We are storing a few things but that's negligible compared to the size of the input.

Part II

Each field has strict rules about what is considered a valid value:

  • 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.
1function isValid(key: string, value: string) {
2 switch (key) {
3 case "byr":
4 return /^\d{4}$/.test(value) && +value <= 2002 && +value >= 1920;
5 case "iyr":
6 return /^\d{4}$/.test(value) && +value <= 2020 && +value >= 2010;
7 case "eyr":
8 return /^\d{4}$/.test(value) && +value <= 2030 && +value >= 2020;
9 case "hgt":
10 const match = value.match(/^(\d+)(in|cm)$/);
11 if (!match) return false;
12 return match[2] === "in"
13 ? +match[1] >= 59 && +match[1] <= 76
14 : +match[1] >= 150 && +match[1] <= 193;
15 case "hcl":
16 return /^#[0-9a-f]{6}$/.test(value);
17 case "ecl":
18 return /^amb|blu|brn|gry|grn|hzl|oth$/.test(value);
19 case "pid":
20 return /^[0-9]{9}$/.test(value);
21 case "cid":
22 return true;
23 default:
24 return false;
25 }
26}
27
28function part2() {
29 const passports = parseInput(input);
30 let validCount = 0;
31
32 for (const passport of passports) {
33 let validKeyCount = 0;
34 const seenKeys = new Set<string>();
35
36 for (const [key, value] of passport.entries()) {
37 if (key === "cid" || seenKeys.has(key)) continue;
38
39 if (isValid(key, value)) {
40 validKeyCount++;
41 seenKeys.add(key);
42 } else {
43 break;
44 }
45 }
46
47 // if the password is valid, "validKeyCount" must
48 // be exactly "7".
49 if (validKeyCount === 7) validCount++;
50 }
51
52 return validCount;
53}

Complexity: Same as part I; Linear time and constant space.