Overview

Today’s question was, in my opinion, much simpler to answer than the previous day’s question. At least, complexity wise. Today is all about strings and learning how to play with them in your language.

Today’s answer is written in swift! All you swifties make sure to share this post because this gift is for you!

Enough chatter, let’s get into Day 2 of Advent of code 🍺 🎄 🎅

Problem Statement

“Their password database seems to be a little corrupted: some of the passwords wouldn’t have been allowed by the Official Toboggan Corporate Policy that was in effect when they were chosen.

To try to debug the problem, they have 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.

In the above example, 2 passwords are valid. The middle password, cdefg, is not; it contains no instances of b, but needs at least 1. The first and third passwords are valid: they contain one a or nine c, both within the limits of their respective policies.

How many passwords are valid according to their policies?“

Part 2)

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! The Official Toboggan Corporate Policy actually works a little differently.

Each policy actually describes two positions in the password, where 1 means the first character, 2 means the second character, and so on. (Be careful; Toboggan Corporate Policies have no concept of “index zero”!) Exactly one of these positions must contain the given letter. Other occurrences of the letter are irrelevant for the purposes of policy enforcement.

Given the same example list from above:

• 1-3 a: abcde is valid: position 1 contains a and position 3 does not.
• 1-3 b: cdefg is invalid: neither position 1 nor position 3 contains b.
• 2-9 c: ccccccccc is invalid: both position 2 and position 9 contain c.

How many passwords are valid according to the new interpretation of the policies?

Problem Requirement List

Let’s break down the requirements list for both problems and then see if we can architect a solution that will allow us to reuse as much code as possible between the problems … and maybe even change allow for new password requirements to be added to the validator!

Part 1 requirements:

• We need to be able to read in a line and separate the entered password and the password policy values
• We need to create a password policy that is based on letter occurrences in the string
• We need to apply that policy with the entered policy values to our entered password

Part 2 requirements:

• We need to be able to read in a line and separate the entered password and the password policy values
• We need to create a password policy for finding letters at indices and ensuring only one index matches that letter
• We need to apply that policy with the entered policy values to our entered password

As you can probably tell, the two questions are nearly identical. The only change between them is the way that we validate the password. Let’s go ahead and write a solution that will allow us to plug and play any password validator that we want! That way Santa doesn’t have any trouble in the future.🍺 🎄 🎅

My Solution

My solution is probably over-engineered. I’m proud of it though. I won’t beat you in code golf but I can tell you santa is checking ✅ off my PR and not yours 😉

First I created a way to break up the inputs and apply a validator to the broken inputs. I’m not going to provide the file reader that I created because that’s about as boring and annoying as writing Angular (did I just hear shots fired? 🔫 ).

struct PasswordPolicy {
    let num1: Int
    let num2: Int
    let char: String
}

func parseInput(line: String) -> (String, PasswordPolicy) {
    let components = line.components(separatedBy: .whitespaces)
    let bounds = components[0].components(separatedBy: "-")
    return (components[2], PasswordPolicy(num1: Int(bounds[0])!, num2: Int(bounds[1])!, char: String(components[1][0])))
}

/// Main method for getting the number of valid passwords
func numberOfValidPasswords(passwordsAndPolicies: [(String, PasswordPolicy)], passwordValidator: (String, PasswordPolicy) -> Bool) -> Int {
    return passwordsAndPolicies.filter { passwordValidator($0.0, $0.1) }.count
}

Now, all that’s left to do is create the two password validators and we’re done!

/// Ensures password meets the defined letter ocurrence for the policy
func letterOccuranceValidator(for password: String, given passwordPolicy: PasswordPolicy) -> Bool {
    let letterCount = password.filter { String($0) == passwordPolicy.char }.count
    return passwordPolicy.num1 <= letterCount && letterCount <= passwordPolicy.num2
}

/// Validates passwords based on the characters at the index,
/// Remember that they don't know anything about 0 indexing so we need to account for that
func letterPositionValidator(for password: String, given passwordPolicy: PasswordPolicy) -> Bool {
    guard passwordPolicy.num2 < password.count else { return false }
    return (password[passwordPolicy.num1 - 1] == passwordPolicy.char) != (password[passwordPolicy.num2 - 1] == passwordPolicy.char)
}

Now you can pass in any validator to the numberOfValidPasswords function and get your answer🍻 !

Notice that both of these solutions are O(n*s) where n is the number of strings and s is the length of the longest string. This is because when we parse each line of input, we a split on the string based on a separator. The split function (or components) must iterate over the whole string to ensure all splits are executed.

If your validator has a complexity greater than O(s), for instance O(q) where O(q) > O(s), then the complexity will become O(n*q) because the processing of each string will now be upper bounded by O(q) and not O(s).

Oh I also forgot one thing… Damn swift Strings…

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

Wrap Up

Hope you enjoyed Day 2 of Advent of Code! I tried to be a little bit more clean and concise in my 5 minute timer, but that did cause me to increase the number of lines of code.

Maybe tomorrow I’ll try to write a one or two liner? 🤔 Let me know if that’s something you’re in. Maybe we can play a little code golf and put our scores in the comments ⬇️

Let me know in the comments ⬇️ if you were able to come up with this solution on your own! I can’t always promise the best complexity (cause I’m not going to cheat) but if you can do better, let me know down below!

As always, if you liked today’s content, make sure you subscribe to the newsletter down below and if you want to support my coffee addiction, help me out by buying me a coffee! It keeps me going to create more AWESOME FREE CONTENT FOR YOU! Thanks for taking the time to unwrap some bytes with me. Cheers! 🍻 🎄 🎅

Shoutout to Mel Poole on Unsplash for the awesome photo!