DEV Community

loading...

[Advent of Code 2020] Day 2 Step-by-Step Tutorial (TypeScript)

kais_blog profile image Kai Originally published at kais.blog Updated on ・7 min read

This post was originally published at kais.blog. It is part of a series of step-by-step tutorials about the Advent of Code 2020 event.

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

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 = [
  "5-7 f: fxfkffffff",
  "4-7 h: hrjhxlhh",
  "11-12 v: vvvwdvvvvvvvvv",
  
];
Enter fullscreen mode Exit fullscreen mode

Solution

Puzzle

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

Day 2: Password Philosophy

Part 1

This time the list entries from the input consist of a password policy and a password. We should find how many passwords are valid according to the given policies. So let's take a look:

1-3 a: abcde
Enter fullscreen mode Exit fullscreen mode

Here 1-3 a means, that the character a should be 1 to 3 times in the password abcde. If this is true we should consider this password as valid. The first thing to do here is parsing the input. We want to split the string 1-3 a: abcde into multiple variables. Let's look at the string again and think about which variables we'll need. 1 is the minimum frequency. Let's call it min. 3 is the maximum frequency. We use max then.
a is our given character and abcde is the password.

To split the string we can make use of a RegExp. The following RegExp literal has multiple capturing groups, so we can grab the segments from it.

//                1     2     3     4
const regex = /^(\d+)-(\d+) (\w): (\w+)$/;
Enter fullscreen mode Exit fullscreen mode

Let's use this RegExp regex to parse a line.

const match = regex.exec(entry);

if (!match) {
  // This should never happen. We somehow messed up or the input is malformed.
  throw new Error();
}

const min = parseInt(match[1]);
const max = parseInt(match[2]);
const character = match[3];
const password = match[4];
Enter fullscreen mode Exit fullscreen mode

We can access the capturing groups via the match variable.
I've assigned the segments to the variable names I've explained before. Note that I also converted match[1] and match[2] to a number. That's because min and max are better represented as numbers.

Nice, the line has been split into useful variables now. What now? We want to find out whether the password is valid according to the current password policy.

So let's take a look at our example input from the beginning:

1-3 a: abcde
Enter fullscreen mode Exit fullscreen mode

We want to know if the password contains a at least 1 times and at most 3 times. That means that we are only interested in the character a. Let's remove all characters from the password that we don't care about. Note that after parsing the line, we have a variable character that contains the character for this password policy.

[...password].filter((c) => c === character)
Enter fullscreen mode Exit fullscreen mode

So we use the spread operator to split a string into single characters. Then we can iterate over each character c and compare it with the current character. If they are equal, we keep the character, else we drop it. This leaves us with an array containing only the given character.

Now that the array got filtered, we just need the current length, and we instantly know, how often the character is in the password. Let's assign the length of the filtered array to a variable.

const count = [...password].filter((c) => c === character).length;
Enter fullscreen mode Exit fullscreen mode

Ok. We know how often the given character is in the password. We still have to check if it violates the rule for minimum or maximum occurrence. Good thing we've parsed the line before and assigned the allowed minimum and maximum to the variables min and max:

if (count < min || count > max) {
  //
}
Enter fullscreen mode Exit fullscreen mode

That's it. We can check the validity of the password for each line. But wait a minute. We'd like to know how many passwords are valid. So we should keep a counter.

let valid = 0;
Enter fullscreen mode Exit fullscreen mode

Ok, we are ready to look at each line from the puzzle input. We can iterate through them, use the RegExp, check the password validity and add to the valid counter if the password is valid. Let's go, we'll use what we've implemented before:

let valid = 0;

const regex = /^(\d+)-(\d+) (\w): (\w+)$/;

for (const entry of lines) {
  const match = regex.exec(entry);

  if (!match) {
    throw new Error();
  }

  const min = parseInt(match[1]);
  const max = parseInt(match[2]);
  const character = match[3];
  const password = match[4];

  const count = [...password].filter((c) => c === character).length;

  if (count < min || count > max) {
    continue;
  }

  valid++;
}

return valid;
Enter fullscreen mode Exit fullscreen mode

So, we initialize the counter, prepare the RegExp und iterate through all of the lines. We parse them and assign relevant data to the variables min, max, character and password. We take a look at the characters of password and check whether the password is valid according to the password policy. If it is not valid, we can use continue to NOT count up and keep on looping with the next line. If it is valid, we just increment the valid counter and keep on.

After the loop has finished, our counter valid contains a number that says how much passwords were valid. We have solved the puzzle. Yeah!

Part 2

Wow, really? It was a lie all along? Well... Ok, let's take a look at the sample input again:

1-3 a: abcde
Enter fullscreen mode Exit fullscreen mode

So in part 1 we were saying that 1 and 3 references the min and max frequency for the character. Jokes on you, in part 2 of the puzzle it means that the first (1) OR third (3) character of the password MUST be the given character (here: a). Also note, that the character should occur EXACTLY ONCE in the password.

We can reuse some of our stuff from before. We've created a RegExp to split the string into segments. I'm putting it here again, just to make it easier for you:

//                1     2     3     4
const regex = /^(\d+)-(\d+) (\w): (\w+)$/;
Enter fullscreen mode Exit fullscreen mode

This time capturing group 1 is NOT our minimum and capturing group 2 is NOT our maximum. They are describing at which index the character MUST BE. It's either at the index we know from capturing group 1 or the index we know from capturing group 2, not both.

Another thing we should consider is, that this index access is not zero-based. So if the input says 1-3 it actually means something like i[0] or i[2]. We are using zero-based indices in TypeScript.

Using our implementation from part 1, we can parse a line with the RegExp and assign the indices we should look at to the variables i and j.

const match = regex.exec(entry);

if (!match) {
  throw new Error();
}

// Here we used `i` and `j` instead of `min` and `max`.
const i = parseInt(match[1]) - 1;
const j = parseInt(match[2]) - 1;
const character = match[3];
const password = match[4];
Enter fullscreen mode Exit fullscreen mode

Note that we are looping through all entries in the array of lines. So entry corresponds to a single line. The first thing we could do is look the indices specified by i and j. We know that password should contain character at i or j, but not at both indices. So just do a quick check if the characters at i and j even differ.

if (password[i] === password[j]) {
  continue;
}
Enter fullscreen mode Exit fullscreen mode

If both characters are the same, we can stop caring about the current line and continue with the next line in the loop. So now we have to check, if the password contains the character either at i or at j. Let's do this:

if (password[i] !== character && password[j] !== character) {
  continue;
}
Enter fullscreen mode Exit fullscreen mode

With this implementation we can stop caring about the current line, if the character is neither found at index i nor at index j. If it IS found, we are not done yet. We are missing a simple step:

valid++;
Enter fullscreen mode Exit fullscreen mode

Yeah, the password is valid according to the new rules from part 2. We can increment our valid counter we've specified in part 1. Here's the full solution:

const regex = /^(\d+)-(\d+) (\w): (\w+)$/;

let valid = 0;
for (const entry of lines) {
  const match = regex.exec(entry);

  if (!match) {
    throw new Error();
  }

  const i = parseInt(match[1]) - 1;
  const j = parseInt(match[2]) - 1;
  const character = match[3];
  const password = match[4];

  if (password[i] === password[j]) {
    continue;
  }

  if (password[i] !== character && password[j] !== character) {
    continue;
  }

  valid++;
}

return valid;
Enter fullscreen mode Exit fullscreen mode

That's it, we simply return the value of valid and we know how many passwords are valid according to the given password policy for the password.

Conclusion

Day 2 was a little bit more difficult than day 1. However, I still consider it very easy. Again, there is stuff you can optimize - if you want. The solution(s) above are enough to solve the puzzle. In general - don't do stuff you aren't gonna need later.

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

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

This post was originally published at kais.blog.

Discussion

pic
Editor guide