Day 4: Passport Processing

As ever, the Elves are showing how disorganised their data management is by showing us a peek at their passport management system; I suppose GDPR isn’t a thing for them!

Multiple passports exist in a file and are separated by empty lines, which are neccessary to denote different entries because the passport fields lay over one or more lines. We need to read this data in and count how many passport entries contain all the required fields. As an aside, I fear for what data structures Eric has previously come into contact with to devise such a hideous format!

My early morning brain created a plan of attack, I would normalise the passport entries into strings where I could then convert them to Passport types using a failable initialiser and count how many were returned. This resulted in the following code, plus an initialiser on Passport which uses regular expressions to find the fields and throws an error if any of them are missing.

input.lines
  .reduce(into: [String]()) { result, line in

    guard line.count > 0 else {
      // Start new passport
      result.append("")
      return
    }

    var passport = result.last ?? ""
    passport.append(" ")
    passport.append(line)

    if result.count > 0 {
      result[result.endIndex - 1] = passport
    } else {
      result.append(passport)
    }
  }
  .compactMap {
    do { return try Passport(string: $0) }
    catch { return nil }
  }

This code builds up the passport rows by reducing our messy lines into a new string array. If the line is empty, we append a new string to the array and return early. Otherwise we take the line and append it to the last existing passport, or start a new passport in the case that it’s the first line. I disliked that there were two conditions for starting a new passport string, especially when one was only used on the first run. I suppose I could have improved it by seeding the reduce with [""] instead, so there would always be an element in the resulting array.

Once I had submitted the solution for the first part, I actually did something I don’t often do. I was so unhappy with this code that I went back to find a better solution before proceeding to tackle part two. A clue that a better solution may reveal itself came pretty quickly when I saw that I had used do/catch in the compactMap rather than the shorthand try? which would return nil if an error was thrown. I was clearly not thinking clearly when writing this solution.

A lunchtime walk, clearing my head and mulling things over gave me some clarity and lead to a massive purge of the ugly code I had written earlier in the day. The Swift standard library has a function to split collections around a separator, resulting in an array of slices and we can use this to split the array based on empty lines. We can then take each slice, which itself is a collection of strings and join them up with a separator of a space. This will result in the normalised data where each row represents each passport.

input.lines
  .split(whereSeparator: { $0.isEmpty })
  .map { $0.joined(separator: " ") }
  .compactMap { try? Passport(string: $0) }

Validation

Happy enough with final solution to part one, I start looking at part two which requires us to validate each field using a set of given rules. Normally I would put the validation into the type creation itself, so that if you had a Passport value, you would know it’s valid, because it would be impossible to create an invalid Passport. For production code, I would still totally use this approach and Alexis King has a comprehensive write up about that concept.

However, I remembered an idea I had back in June for a Validator<Value> type that allows you to build up a series of validations on Value’s properties. The type I made back then was simple enough, which worked with one small trick.

Swift 4.2 introduced @dynamicMemberLookup which allowed us a way to add properties dynamically to types. However, Swift 5.1 added a superpowered version of this when it gave us @dynamicMemberLookup using key paths. A KeyPath<Value, Property> defines how to get from a value to one of its properties. Or property of a property. Or a property of a property of a property. Well you get the idea.

This addition allows us to write a dynamic member subscript and the compiler will then make properties available on our type and provide complete typesafety about what is returned. Here we have a type Foo<Value>, if we create one using a String then this Foo<String> will have a count property because String has a count property. When we call count on it, Swift knows that it must return a type Foo<Int> because the key path includes that type information.

@dynamicMemberLookup
struct Foo<Value> {
  let value: Value
  subscript<Property>(
    dynamicMember keyPath: KeyPath<Value, Property>
  ) -> Foo<Property> {
    let property = value[keyPath: keyPath]
    return Foo<Property>(value: property)
  }
}

let foo = Foo(value: "String") // Foo<String>
let count = foo.count // Foo<Int>

My idea was that you could return a closure from this call, such that you could set things using the value’s properties rather than just retrieving values. This Validator would supply two public functions, one to validate a given value and a dynamic member subscript that would provide a closure to be called with a closure that validates the property which I’ll call the property validation function. This is all a bit functions within functions stuff!

When the subscript is called with the property validation function, a new Validator is returned that adds that property validation function to the existing Validator’s list of property validation functions. This is similar to how Swift Sequence or SwiftUI View operators work. In this way we can create a validator which validates many properties of a value by chaining into this subscript and the result will be a Validator that requires all property validation functions to pass in order for the value to be valid.

It’s probably easier to understand with a use case, the following code shows how you could use it to validate that strings are an even number of characters in length.

let validator = Validator<String>()
  .count { $0.isMultiple(of: 2) }
  .first { $0 == "B" }

validator.validate("A")  // false
validator.validate("AZ") // false
validator.validate("B")  // false
validator.validate("BZ") // true

We can see the use of the key path dynamic member lookup in the use of the calls to count and first on the validator. The former returns the function ((Int) -> Bool) -> Validator, where Int comes from the type of count. The call to first thus returns ((Character?) -> Bool) -> Validator.

Calling count providing a function that validates the string’s length returns a new Validator<String> with the validation applied. We can then chain with first to provide a function that validates the string’s first character.

Now when we go to use the validator by calling validate with a string, it will run through all of the applied validations to determine whether the string is valid. You can see that it will only return true when the given string has a length which is a multiple of 2 and where it starts with a “B”.

It turns out that the resulting Validator code is surprisingly small at just 35 lines of code, however for advent of code I decided to tie in a couple of other concepts from my shared library.

extension Predicate {

  static func isWithin<Range: RangeExpression>(
    _ range: Range
  ) -> Predicate where Range.Bound == Value {
    Predicate(range.contains)
  }
}

extension Predicate where Value: Equatable {

  static func isWithin(_ values: Value...) -> Predicate {
    Predicate(values.contains)
  }
}

extension Predicate where Value == String {

  static func matches(
    _ pattern: RegularExpression.Pattern
  ) -> Predicate {
    guard let regex = try? RegularExpression(pattern: pattern) else {
      return Predicate { _ in false }
    }
    return Predicate(regex.matches)
  }
}

I had a Predicate type and using this rather than a function to represent a validation allows me to then extend it to provide conveniences to create predicates on common behaviours like whether a value is within a given range, whether a value exists in a given variadic list or whether a string matches some regular expression pattern.

let validator = Validator<Passport>()
  .birthYear(.isWithin(1920...2002))
  .issueYear(.isWithin(2010...2020))
  .expirationYear(.isWithin(2020...2030))
  .height(.matches("^(1[5-8][0-9]|19[0-3])cm|(59|6[0-9]|7[0-6])in$"))
  .hairColor(.matches("^#[0-9a-f]{6}$"))
  .eyeColor(.isWithin("amb", "blu", "brn", "gry", "grn", "hzl", "oth"))
  .passportID(.matches("^[0-9]{9}$"))

return input.lines
  .split(whereSeparator: { $0.isEmpty })
  .map { $0.joined(separator: " ") }
  .compactMap { try? Passport(string: $0) }
  .count(where: validator.validate)

This allowed me to define the requirements in a concise manner, which reads almost like the actual spec from the puzzle. It also allowed me to write them in the best way for each property – for the years it was easier to describe them needing to be within a certain range, whereas some others required me learning some more regular expressions.

At the end of this, I could then replace .count from the first part, with one that accepts the validator’s validate function to determine whether each element is counted.