Advent of Code 2020 Day 4 - Solution + Tutorial (TypeScript)

Prerequisites

I assume you've put your puzzle input into an array called lines where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const lines = [
  "byr:2010 pid:#1bb4d8 eyr:2021 hgt:186cm iyr:2020 ecl:grt",
  "",
  "pid:937877382 eyr:2029",
  "ecl:amb hgt:187cm iyr:2019",
  "byr:1933 hcl:#888785",
  "",
  "ecl:hzl",
  …
];

Solution

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 4: Passport Processing

Part 1

So, we want to find the valid passports. First thing we can notice: The data per passport is scattered over several lines. Let's make the data easier to work with. We want to combine all data per passport to a single line. So:

"byr:2010 pid:#1bb4d8 eyr:2021 hgt:186cm iyr:2020 ecl:grt",
"",
"pid:937877382 eyr:2029",
"ecl:amb hgt:187cm iyr:2019",
"byr:1933 hcl:#888785",
…

should become

"byr:2010 pid:#1bb4d8 eyr:2021 hgt:186cm iyr:2020 ecl:grt",
"pid:937877382 eyr:2029 ecl:amb hgt:187cm iyr:2019 byr:1933 hcl:#888785",
…

Now what are we going to do? We can join all lines and separate them with a newline. Then, we can split again and look for double newlines. That is the point where a new passport begins.

const passports = lines.join("\n").split("\n\n");

After we've done that, a single passport's data is still separated by newlines. Let's split the data again and join them with spaces instead. Our code from above becomes:

const passports = lines
  .join("\n")
  .split("\n\n")
  .map((data) => data.split("\n").join(" "));

Good! Now we have an array passports where each item is a single line with all the passport data. Our task is now to find out, how many passports are valid. A passport is considered valid if it has all required fields.

Following the puzzle description, we can create a new array holding the required fields:

const requiredFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"];

We want to filter out all invalid passports. So let's remove every passport that misses ANY field from the array. Therefore, we can use the Array#filter method:

passports.filter((passport) => {
  //
})

Okay, we somehow have to determine, if any field is missing. Remember our passport looks like so:

"byr:2010 pid:#1bb4d8 eyr:2021 hgt:186cm iyr:2020 ecl:grt"

Let's use some simple code to split this line into key-value pairs:

const data = passport.split(" ").map((pair) => pair.split(":"));

So what's happening here? The passport is split into smaller strings. We first split whenever we find a single space. Now we have an array with values like byr:2010 and pid:#1bb4d8. These values, arrays themselves, can be split further into key-value pairs. That's what happening in the code example above. Our data looks like:

["byr", "2010"],
["pid", "#1bb4d8"],
["eyr", "2021"],
…

Let's add this data to a Map. This way it's easily accessible.

const map = new Map<string, string>();
data.forEach(([key, value]) => {
  map.set(key, value);
});

Now back to checking whether the passport is valid. A passport is considered valid if it has all required fields. Good thing we've initialized requiredFields already. Let's use it to check the passport:

requiredFields.every((field) => map.has(field));

Maybe Array#every is new for you. It checks the condition in the callback for every array item. Only if it returns true every single time, then the return value is true. That's ideal for checking the passport. We use each field to check whether our newly created map has that field. If any field is missing this returns false.

Combine that with our code from before, and we have filtered out all invalid passports:

return passports.filter((passport) => {
  const data = passport.split(" ").map((pair) => pair.split(":"));

  const map = new Map<string, string>();
  data.forEach(([key, value]) => {
    map.set(key, value);
  });

  return requiredFields.every((field) => map.has(field));
}).length

Simply return the Array#length and we know how many passports are valid. Nice! We did it!

Here's the full solution again:

const passports = lines
  .join("\n")
  .split("\n\n")
  .map((data) => data.split("\n").join(" "));

const requiredFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"];

return passports.filter((passport) => {
  const data = passport.split(" ").map((pair) => pair.split(":"));

  const map = new Map<string, string>();
  data.forEach(([key, value]) => {
    map.set(key, value);
  });

  return requiredFields.every((field) => map.has(field));
}).length;

Part 2

So part 2 wants us to check each passport field for a specific format. That was pretty obvious. At least I expected something like that for part 2. Nevertheless, let's tackle it.

Basically we can reuse a lot of our code from part 1. It's still easier to work with the passports if each passport is on a single line. So, this code from part 1 is left unchanged.

const passports = lines
  .join("\n")
  .split("\n\n")
  .map((data) => data.split("\n").join(" "));

If you need an explanation, scroll up to part 1. I've explained a bit further what we've done there.

Also, again, we want to filter passports. So we'll use the Array#filter method again, and we'll put our passport data into a Map.

passports.filter((passport) => {
  const data = passport.split(" ").map((pair) => pair.split(":"));

  const map = new Map<string, string>();
  data.forEach(([key, value]) => {
    map.set(key, value);
  });
  
  // …
});

However, we have to change a bit for the validation of a passport. Remember, in part 1 we defined a variable requiredFields like so:

const requiredFields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"];

This time, we have to check not only whether a passport is missing any of them but also, whether the format of the field is correct. Instead of using requiredFields, let's create a variable named fieldDefinitions:

const fieldDefinitions = {
  byr: …,
  iyr: …,
  eyr: …,
  hgt: …,
  hcl: …,
  ecl: …,
  pid: …,
};

Okay, now the keys of fieldDefinitions correspond to each field we have to check. The values, however, can be used to specify the format. As we are working with simple strings here, why not just use Regular Expressions?

We can define a RegExp literal for each field and then check the passport data for validity. So, for each field, let's check what the puzzle description says about it:

byr (Birth Year) - four digits; at least 1920 and at most 2002.

How to translate that into a RegExp literal? Well, it's four digits. So we can do it like so:

/^\d\d\d\d$/

Well, yeah, that could be simplified to /^\d{4}$/. However, this is not enough. It's not like ANY digit is valid. It has to satisfy a certain range. Let's rework our RegExp:

/^(?:19[2-9][0-9]|200[0-2])$/

Woah! Ouch! If you are not familiar with regular expressions, that might hurt. I'll try explaining it step-by-step. If you know what I've done there, you can skip this part, as always.

So, instead of \d{4} which denotes four digits, we'd like to say: Allow every 4-digit number from 1920 to 2002. The regex describes that. If the first two digits are 19 it might be followed by any digit from 2-9. That's important because 1910 is considered invalid. After that 2-9 it might be any digit. OR it could start with the three digits 200 followed by a single digit from 0 to 2. The | notation might be read as OR.

I've also used this weird (?:…) stuff. That's a non-capturing group. A simple capturing group uses parentheses. With ?: it means, that we don't want to extract this stuff, we just want to group it. And that's enough for us.

Phew, I hope this clears a bit of the confusion. If not, I'd suggest reading up a bit on regular expressions. It's confusing at first, but learning it is worth it.

Now we can create regular expressions for each of the fields and add them like so:

const fieldDefinitions = {
  // 1920-2002
  byr: /^(?:19[2-9][0-9]|200[0-2])$/,
  // 2010-2020
  iyr: /^(?:201[0-9]|2020)$/,
  // 2020-2030
  eyr: /^(?:202[0-9]|2030)$/,
  // 150-193cm or 59-76in
  hgt: /^(?:(?:1[5-8][0-9]|19[0-3])cm|(?:59|6[0-9]|7[0-6])in)$/,
  // starting with # followed by six times 0-9 or a-f
  hcl: /^#[0-9a-f]{6}$/,
  // any of the amb, blu, brn, gry, grn, hzl or oth
  ecl: /^(?:amb|blu|brn|gry|grn|hzl|oth)$/,
  // 9 digits
  pid: /^\d{9}$/,
};

This might be confusing. Maybe I should create another post on validating stuff with regular expressions. Hit me up on Twitter if you think I should do that!

Nevertheless, we've added regular expressions for checking the validity of every field. Remember how we've checked the passports in part 1? We can almost reuse that code. We did it like so:

requiredFields.every((field) => map.has(field));

Last time, requiredFields was an array. Now we have an object called fieldDefinitions where the key is the field and the value is a regex. Let's refactor our code a bit so we can use that:

return Object.entries(fieldDefinitions).every(([field, regex]) => {
  return map.has(field);
});

We can make use of the Object#entries method to make the object iterable. Now the first parameter is an array that looks like [key, value]. We are using array destructuring here, to extract the key and value and name it field and regex.

There is one tiny step missing. We have checked whether the passport is missing any field, BUT we don't know if the field is correctly formatted. Let's use our defined regexes to change this:

return Object.entries(fieldDefinitions).every(([field, regex]) => {
  return map.has(field) && regex.test(map.get(field)!);
});

There's a RegExp#test method that we can use to check the field. We retrieve the field value from the map and use regex.test to check it against our regular expression. Note the ! behind map.get(field). We tell the TypeScript compiler here, that WE KNOW that map.get(field) will not return undefined. That is because we've already checked it in the condition before, but the TypeScript compiler does not know this. So we'Ll help it out.

Nice! Now we can combine everything together and return the length of the filtered array. Then we know how many passports are valid.

Here's the full solution for part 2:

const passports = lines
  .join("\n")
  .split("\n\n")
  .map((data) => data.split("\n").join(" "));

const fieldDefinitions = {
  byr: /^(?:19[2-9][0-9]|200[0-2])$/,
  iyr: /^(?:201[0-9]|2020)$/,
  eyr: /^(?:202[0-9]|2030)$/,
  hgt: /^(?:(?:1[5-8][0-9]|19[0-3])cm|(?:59|6[0-9]|7[0-6])in)$/,
  hcl: /^#[0-9a-f]{6}$/,
  ecl: /^(?:amb|blu|brn|gry|grn|hzl|oth)$/,
  pid: /^\d{9}$/,
};

return passports.filter((passport) => {
  const data = passport.split(" ").map((pair) => pair.split(":"));

  const map = new Map<string, string>();

  data.forEach(([key, value]) => {
    map.set(key, value);
  });

  return Object.entries(fieldDefinitions).every(([field, regex]) => {
    return map.has(field) && regex.test(map.get(field)!);
  });
}).length;

Conclusion

Phew! That was a bit more complicated. Maybe those regular expressions are going to haunt you. I hope not. Maybe I'll write about them later.

The most important thing here was to format the input and make it more usable. In general, I think it's a good idea to reformat the input into a format that's easier to handle.

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!