AoC '20: Information Security is Hard

AoC '20: Information Security is Hard

Having solved the woes of the friendly Elves in accounting, we're finally able to head to the airport and get started on our long overdue vacation. The easiest way there, we're told, is via toboggan. Sadly the majority of our time has been consumed saving Christmas, and we haven't had much opportunity to enjoy such frivolous pursuits.

Making the smart play, we stop off at a local toboggan rental establishment only to find that they're having some password trouble. Our work never is done; it seems.

Day 2: Password Philosophy

Being the upstanding citizens that we are, we offer to help the shopkeeper out. They offer us a list of passwords, each prefixed with the corporate policy in place when the owner set it. For example, a small list of such passwords might look like this.

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

Each line contains four pieces of information. In reverse order, these are the password; a character that the password must have; the maximum number of times that character should occur; and the minimum number of times it must appear. For example, the first line offers a password of abcde which must contain the letter a between one and three times inclusive.

Our challenge is to compute the number of passwords that, according to their policies, are valid. In the above example, the first and third passwords are correct: The first contains the letter a exactly once, making it reasonable; the third contains precisely nine of the character c, rendering it okay; however the second does not contain the letter b at all!

Part 0 — Parsing our Input

Before we can get to work understanding the validity of the passwords, we must parse the input. Thankfully the format of the list we have is an excellent candidate for regular expressions. These are sequences of characters that define a pattern, with which we can search in bodies of text or validate inputs. For our information, in each line we wish to extract two sets of numbers separated by a dash; a single letter following single whitespace, and a series of alphabetical characters following a colon.

(\d+)-(\d+)\s(\w):\s(\w+)

Each pair of parentheses denotes a capturing group. Each character preceded by a backward slash has a special meaning: \d means a digit; \s, a whitespace character; and \w, a word character. Each of these matches precisely one occurrence of their class, however those followed by a + match one or more. If we were to apply this expression to the earlier password examples, the first line would yield 1, 3, a and abcde.

To keep life simple, we'll organise these data into an array of custom structures. Each contains a pair of integers (min, max) and a pair of strings (char, pw), named PwInfo.

Part 1

The first part of this challenge is a straightforward filtering operation. We want to filter out all structures that do not comply with their policies. To do this, we use Swift's built-in array filter function. For each structure, we'll filter all characters in pw that are not char and confirm that the number left over is within the inclusive range defined by min and max. Ordinarily, we may achieve the latter two of these tests with a clamp function. Interestingly, this is something that Swift appears to lack. Not to worry, though, we can implement our own.

static func clamp(_ value: Int, _ low: Int, _ high: Int) -> Int {
    return max(low, min(high, value))
}

Given a value, upper and lower bounds, we return one of the three values by finding the minimum and maximum. It's an appreciably straightforward function, and the mind boggles as to why Apple does not include one by default.

With our clamp function ready, we can go on to implement our filtering algorithm.

let valid = pwInfos.filter { pwInfo in
    let count = pwInfo.pw.filter { char in
        pwInfo.char.contains(char)
    }.count
    return clamp(count, pwInfo.min, pwInfo.max) == count
}.count

In the event that count is outside of the acceptable range, our equality test will fail. Running our filter, we find that there are 483 valid passwords in our list.

Part 2

As luck, or lack thereof, would have it, the shopkeeper has made a slight error. Whilst we validated the list correctly, the two digits in each line are in fact indices. It is explained to us that the letter given must occur at precisely one of the index given. Let's return to the earlier example.

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

The shopkeeper explains that their system is strange and doesn't have the concept of index zero. Madness, right? With the new interpretation understood, we can establish that the first password is still valid — it has an a at index one but not at position three. The remaining two are invalid — the second password does not contain a b, and the third contains c at both indices.

We can slightly alter our earlier code with a change to the filter.

let valid = pwInfos.filter{ pwInfo in
    pwInfo.char.contains(pwInfo.pw[pwInfo.min - 1]) ^
    pwInfo.char.contains(pwInfo.pw[pwInfo.max - 1])
}.count

This time, we're testing that the character at precisely one of the indices given matches our test character. Of course, there's a slight catch: This code won't compile.

Extensions and Subscripts

The square bracket notation we use to access elements in an array is called a subscript and, by design, these operate in constant time. In layman's terms, 'constant time' means that the subscript must perform just one procedure to acquire its value irrespective of the size of the underlying collection. Strings, as we know, can be viewed as an array of characters and, in many settings, a single character is of a fixed size.

Such is not the case in Swift. Swift strings use a Unicode encoding that may span one, two, three or even more bytes. As a result, it is not possible to access a character with an integer index as it would be inefficient to do so.

Swift does, however, expose the necessary building blocks we need to create our own. Extensions are a particular type of class that, as the name implies, extends an existing class. Swift also provides a mechanism for implementing subscripts, using the subscript keyword.

extension String {
    subscript (_ offset: Int) -> String {
        return String(self[index(startIndex, offsetBy: offset)])
    }
}

In this block, we create an extension of the String class containing a single subscript method. We use the index method and the start index of the string, with an offset (the subscript value) to find and return the string that represents the offset. Whilst this will be just one character, it could well span several bytes. The keyword self in this method refers to the string instance — other languages use the this keyword for the same.

Adding Operators

Another issue, perhaps unusually, is that Swift does not define an exclusive or operator for boolean types. I couldn't find a good indicator as to why this is the case, with the exception that exclusive or is just a roundabout way of saying 'not equal.' At any rate, I am a man that enjoys access to an 'exclusive or' operator, so we'll define one.

extension Bool {
    static func ^ (lhs: Bool, rhs: Bool) -> Bool {
        return lhs != rhs
    }
}

In this code, we define a special function represented by the ^ symbol, which is (pretty universally) the operator symbol for exclusive or. In this unique function, we return the result of a not equal operation on the two input values.

Part 2, Again

Returning to our code for the second stage of the challenge, having implemented the missing two operators we can recompile successfully.

Executing our solution, we're able to confirm that just 482 passwords are valid when interpreting the policies with the new scheme. Maybe now we can get to vacationing?

Complete Code

You can find my complete solution here.

Show Comments