Day 2: Password Philosophy

Advent of Code 2020

Today’s challenge revolves around a password database which has been corrupted. We are tasked with finding the number of passwords it contains that are valid for a given rule, all while ignoring the North Pole Toboggan Rental Shop’s questionable password storage policies.

I treated day 2 as an excercise of parsing the the input data to helpful data structures, which I then used to solve the puzzle. Each line of the puzzle has a password and a rule for validation and each rule has a character and a range of the expected amount of times that character should be present.

With this outline I modeled the types I would need. I tend to prefer stronger typing than weaker, so that I always know what I’m dealing with. I even went so far as to make a specific Password type that was in retrospect probably not truly required for today’s challenge.

In general though, I find compilations issues easier to reason about if there’s a type in them, and these can occur often while chaining many operations on Sequence. It’s just a lot simpler to know that you have a Password at any given point rather than a String, where it may be the password or the current line or even the puzzle input!

struct Line {
  let rule: Rule
  let password: Password
}

struct Password: RawRepresentable {
  let rawValue: String
}

struct Rule {
  let amount: ClosedRange<Int>
  let character: Character
}

My parsing code is a simple series of inits which take the input (1-3 a: abcde) and split it down to the four component parts. Splitting on the colon to find the password, the space to find the character and the dash to find the lower and upper bounds of the range.

Once parsed into this data structure it’s simple to understand the solution using an extension to Rule to provide the validation.

try input.lines
  .map(Line.init)
  .count(where: { $0.rule.validate($0.password) })

extension Rule {
  func validate(_ password: Password) -> Bool {
    let count = password.rawValue.filter { $0 == character }.count
    return amount.contains(count)
  }
}

Part 2 provides a different form of validation to perform, so the parsing code from part 1 can remain, with nothing more than to add a second validation function and calling that instead.

extension Rule {
  func validate2(_ password: Password) -> Bool {
    let start = password.rawValue.startIndex
    let lower = password.rawValue.index(start, offsetBy: amount.lowerBound - 1)
    let upper = password.rawValue.index(start, offsetBy: amount.upperBound - 1)
    let lowerMatch = password.rawValue[lower] == character
    let upperMatch = password.rawValue[upper] == character
    return lowerMatch != upperMatch
  }
}

Regular Expressions

Throughout the day, I was niggled by the thought that my simple string-splitting parsing might be improved upon using fancier techniques, specifically regular expressions.

I’ve dabbled in using regular expressions (regex) to check the validity of strings over the years, where by dabbled I mean I’ve searched the web endlessly for the correct mystical incantations. It’s safe to say: I am a regex noob and find them ever so slightly intimidating.

Paul Hudson’s really quick guide to pattern matching gave me my first clues and showed me that regex can be used to capture values and not just validate inputs. Inside a regular expression, you can use parentheses () to create a capturing group, which can be used to extract information from the input string.

Foundation has NSRegularExpression, which has the power to do all of this work, but the API is slightly cumbersome. Wrapping it using a custom type made it a little nicer and succint to work with. The following is the total solution for part 1 using regular expressions.

let regex = try RegularExpression(pattern: "([0-9]+)-([0-9]+) (.): (.+)")
return try input.lines.count(where: { input in
  let match = try regex.match(input)
  let lower = try match.integer(at: 0)
  let upper = try match.integer(at: 1)
  let character = try match.character(at: 2)
  let password = try match.string(at: 3)
  let count = password.count(of: character)
  return (lower...upper).contains(count)
})

It’s quite a lot less code in the solution, albeit much more dense than my type-heavy first solution.

The defined regular expression (\d+)-(\d+) (.): (.+) captures four groups:

1 or more numbers
1 or more numbers
Any single character
1 or more characters

These translate into our lower and upper bounds, the search character and the passord respecively. Once we have these pieces of information, we can simply see if the number of occurances of the character in the password is within the range that is required.

I now have two solutions to compare. A more verbose, typed solution which explicity and clearly states what the code is doing and a more succinct piece which you can read and reason about in just a couple of lines. Performance-wise, the two are indistinguishable from one another, which is unsurprising given the lengths of the strings involved and that both are doing similar amounts of work.

This regular expression variant does have a singular benefit that because I didn’t have types set up, I could rename my variables for the second part. For instance the two numeric values are no longer the lower and upper bound of a range but two indices in the password – in my original solution, I just brutalised the use of the closed range to get at the values after the data had been parsed.

I’m going to keep the regular expression code in as they may prove useful to have in my toolbelt for other puzzles.

Other notes

As a throwback to last year, u/mzprx42 wrote an Intcode program to solve today’s problem.
u/theChief__ provides another visualisation in the form of dropping numbers.