Advent of Code 2020: Day 2

, 7 min read
advent of code 2020

Oh no, this problem is all about password trouble. I think we’ve all had these issues before.

Part 1

Today’s narrative continues with:

Your flight departs in a few days from the coastal airport; the easiest way down to the coast from here is via toboggan.

The shopkeeper at the North Pole Toboggan Rental Shop is having a bad day. “Something’s wrong with our computers; we can’t log in!” You ask if you can take a look. Their password database seems to be a little corrupted.

To try to debug the problem, they had created a list (your puzzle input) of passwords (according to the corrupted database) and the corporate policy when that password was set.

For example, suppose you have the following list:

1-3 a: abcde 1-3 b: cdefg 2-9 c: ccccccccc

Each line gives the password policy and then the password. The password policy indicates the lowest and highest number of times a given letter must appear for the password to be valid. For example, 1-3 a means that the password must contain a at least 1 time and at most 3 times.

How many passwords are valid according to their policies?

You can read the full text here. In summary, we have a long list of lines, each line is of the form, X-Y A: ZZZZ.

This is precisely the sort of the problem that I currently find difficult to solve in C++. I’m not familiar enough with regex to try that approach, and my knowledge of the C++ STL for string operations is limited.

My plan is to loop through each line of the file in order and read it in. When we have the line in memory, I can tokenise it. This means I will turn the line into 4 tokens: the number before the hyphen (X), the number after the hyphen (Y), the letter we are interested in (A) and finally, the password (ZZZZ).

Imagine the inputted line looks like the following, where the numbers above indicate the number of the index in the string. I’ve replaced spaces with underscores for clarity.

0 1 2 3 4 5 6 7 8 9 10 11 1 - 3 _ a : _ a b c d e

To process the first number, which is a single digit in this example but could be larger, I can select a substring which starts at index 0 and ends at the index of the dash.

In the above example, this would be,

[0] 1 2 3 4 5 6 7 8 9 10 11 [1] - 3 _ a : _ a b c d e

then I want to select the next number which goes from the index after the dash to the index before the first space,

[0] 1 [2] 3 4 5 6 7 8 9 10 11 [1] - [3] _ a : _ a b c d e

then I want to select the character after the first space as the third token,

[0] 1 [2] 3 [4] 5 6 7 8 9 10 11 [1] - [3] _ [a] : _ a b c d e

and finally, we want to start 2 spaces after the colon and run to the end of the string,

[0] 1 [2] 3 [4] 5 6 [7 8 9 10 11] [1] - [3] _ [a] : _ [a b c d e]

The code I wrote for this is below:

1
2
3
4
5
6
7
8
int dash = line.find("-");
int space = line.find(" ")+1;
int colon = line.find(":")+2;

std::string token1 = line.substr(0, dash);
std::string token2 = line.substr(dash+1, space-dash);
std::string token3 = line.substr(space, 1);
std::string token4 = line.substr(colon, line.size()-colon);

then I just need to convert the first two tokens into integers, the third token into a char,

1
2
3
int r1 = std::stoi(token1);
int r2 = std::stoi(token2);
char target = token3[0];

Now I can loop through the password (token 4) and count how many times the character, target, appears in the password. If the number of occurrences is in the range provided by the first two tokens, then this is a valid password!

1
2
3
4
5
int occ = 0;
for(int i=0; i<token4.size(); i++)
    if (token4[i] == target) occ++;

if ((occ >= r1) && (occ <= r2)) ans1++;

Repeating this process for every line gives me the number of valid passwords, and subsequently our first star of day 2, ⭐!

The full code can be found on github

Part 2

Damn! Those were the wrong password rules,

While it appears you validated the passwords correctly, they don’t seem to be what the Official Toboggan Corporate Authentication System is expecting.

The shopkeeper suddenly realizes that he just accidentally explained the password policy rules from his old job at the sled rental place down the street!

Each policy actually describes two positions in the password, where 1 means the first character, 2 means the second character, and so on. Exactly one of these positions must contain the given letter.

You can read the full text here.

Now we don’t care how many of the target letters are in the password. We just need to check if the target character is at the indices given by token 1 and token 2:

This requires just adding a small bit of code to the answer above,

1
2
if (((token4[r1-1] == target) + (token4[r2-1] == target)))
    ans2++;

This line of code asks, is the position r1 of the password equal to the target? This returns 1 for true and 0 for false. I then do the same for r2. If the sum of these values is equal to 1, then I know that only one of these is true (you could also use an XOR operator here). That means the password is valid!

Running that over the entire list of passwords and we have our second star: ⭐⭐

The full code can be found on github

Reflections

This problem was a little less algorithmic than day 1, with a much bigger emphasis on parsing the input into a manageable format. I think my code was fairly readable, but there are more efficient methods of parsing the input using regex, so I’ll read up on that for future days.

In general, my solution to both parts scales with N, where N is the number of passwords you need to check. In the first part we also loop through every character in the string, if you assume the mean string length is M then the scaling is O(N * M).

For the second part, we just check two specified indices and so the problem is independent of the password length, and only scales with the number of passwords, O(N). I’m not sure it is possible to improve the complexity of either of these algorithms today.

Anyway, I hope this was useful, see you tomorrow.

EDIT: I looked into using regex, it turns out the pattern matching can simplified to something like the following:

1
2
3
4
5
6
7
std::regex pieces_regex("(\\d+)-(\\d+) ([a-z]): ([a-z]+)");
std::regex_search(line, pieces_match, pieces_regex);

int r1 = std::stoi(pieces_match[1]);
int r2 = std::stoi(pieces_match[2]);
char target = std::string(pieces_match[3])[0];
std::string token4 = pieces_match[4];

This uses the pattern "(\d+)-(\d+) ([a-z]): ([a-z]+)" where we have specified we are looking for two numbers, which could be multiple digits, separated by a hyphen. We are also looking for a character, [a-z], and finally a sequence of characters. The regex_search checks that our input is in this format, and if it is, it extracts the 4 tokens.

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts