December 8, 2020

Advent of Code 2020 Day 2 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. —

For this puzzle we've been given a list of password policies and passwrods and we have to determine how many passwords are valid according to their corresponding policy.

Example Input

11-3 a: abcde
21-3 b: cdefg
32-9 c: cccccccccccc

Part I

The first and second number indicate the minimum and maximum number of times a letter must appear in the passwrod.

This is pretty straight forward. For each line we should count how many times the given letter appeares in the password and then check if the count is between the two numbers. Let's take a look at the code:

1const input = `
21-3 a: abcde
31-3 b: cdefg
42-9 c: cccccccccccc
7const lines = input.trim().split("\n");
9let validCount = 0;
11for (const line of lines) {
12 // we can easily parse the line by using the character indices
13 // in the string, no need for fancy regex
15 const min = +line[0]; // the "+" symbol converts to number
16 const max = +line[2];
17 const letter = line[4];
18 const password = line.slice(7); // slice from the 7th index to the end of the string
19 const count = password
20 .split("")
21 .reduce((acc, curr) => (curr === letter ? acc + 1 : acc), 0); // fancy way to count the character
23 // increment validCount if "count" is "valid" 😄
24 if (count >= min && count <= max) validCount++;

If you're interested in how to parse each line using regex, check out this code snippet:

1const match = line.match(/^(\d)-(\d) ([a-z]): ([a-z]+)$/);
3// This won't happen with the given input but have to do this to
4// satisfy TS. Alternatively we can put a "!" at the end of the
5// line where we declared "match", but I would rather handle
6// this case in the actual code
7if (!match) continue;
9// the first value in the match array is the whole matched string
10// and the rest are the captured groups
11const min = +match[1];
12const max = +match[2];
13const [, , , letter, password] = match;

Complexity: If we neglect the length of each password, this program will run in linear time (because we're looping the array once and have no nested loops) and constant space (since we're not copying anything).

Part II

Determine how many passwords are valid if the two numbers describe the positions (1-based) that must contain the given character, for example, 2-9 c: cccccccccccc is valid because the second and ninth character in the password are "c" but 1-3 a: abcde is invalid because the thrid character in the password is not "a".

1let validCount = 0;
3for (const line of lines) {
4 const match = line.match(/^(\d)-(\d) ([a-z]): ([a-z]+)$/);
5 if (!match) continue;
7 const firstIdx = +match[1] - 1; // Subtract 1 since arrays and strings are zero-based
8 const secondIdx = +match[2] - 1;
9 const [, , , letter, password] = match;
11 if (password[firstIdx] === letter && password[secondIdx] === letter) {
12 validCount++;
13 }

Complexity: This script runs in linear time because we have only one loop, and constant space since we're not copying/storing anything.