Advent of Code Day5: Print Queue

December 5, 2024

4 min read advent-of-code swift 

I made a couple of mis-steps that slowed me down a little.

This was another day (1)https://adventofcode.com/2024/day/5 where part 2 wasn’t as much of a jump in difficulty, but needed careful reading; only add the middle values for lists that need sorting. You can see my full solution on Github (2)https://github.com/Abizern/aoc-swift-2024/blob/main/Sources/Day05.swift .

Part 1 #

Validate a list of numbers given a set of rules.

I first tried to read the rules into a dictionary of [Int: [Int]] for each page, show the pages that are supposed to come after it. That failed my tests because it didn’t take into account for the requirement that the rules imply a negative. If A|B then B must come after A and if B comes before A then the list is not valid. So both cases need to be encoded into the check.

Since (Int, Int) is not Hashable I created a small struct to encode first and last values and then use that as the key for my dictionary.

  struct Pair: Hashable {
    let first: Int
    let second: Int

    init(_ first: Int, _ second: Int) {
      self.first = first
      self.second = second
    }
  }

Then I created a function to iterate through the rules, encoding the correct order as true and the reverse condition as false

  func ordering(_ rules: [(Int, Int)]) -> [Pair: Bool] {
    var dict: [Pair: Bool] = [:]
    dict.reserveCapacity(rules.count * 2)
    for (first, second) in rules {
      dict[Pair(first, second)] = true
      dict[Pair(second, first)] = false
    }

    return dict
  }

The tricky part is the validation function. Since I knew that I was going to be mapping over the input list using the ordering, I wrote a function that returns the function to be used. Closures are first-class types in Swift, and this frequently makes code clearer at the call site:

  func isValidFuntion(_ ordering: [Pair: Bool]) -> ([Int]) -> Bool {
    { pages in
      let pageCount = pages.count
      for i in 0 ..< pageCount - 1 {
        for j in i + 1 ..< pageCount {
          let pair = Pair(pages[i], pages[j])
          if ordering[pair] ?? true {
            continue
          } else {
            return false
          }
        }
      }
      return true
    }
  }

This goes through the list by creating every possible pair of orderings, if they are allowed or not encoded, then it is a valid pairing. If it is specifically disallowed, then I return false without checking the rest of the list.

To get the answer I filtered for valid lists, found the midpoint using:

  func middleValue(_ list: [Int]) -> Int {
    list[list.count / 2]
  }

Note, Int division in swift means I don’t have to worry about flooring the result.

After finding the midpoint, I just summed them up.

  func part1() async throws -> Int {
    let (rules, pages) = parsedInput
    let ordering = ordering(rules)

    return pages
      .filter(isValidFuntion(ordering))
      .map(middleValue)
      .reduce(0, +)
  }

Part 2 #

If the list is invalid we should sort it, find the middle value and sum those values.

For lists in Swift, you can pass in a function to use for the comparison of two values, returning true if they are correctly ordered. As with the first part, I wrote a function that returned a sorting function:

  func sortingFunction(_ ordering: [Pair: Bool]) -> ((Int, Int) -> Bool) {
    { first, second in
      ordering[Pair(first, second)] ?? true
    }
  }

Since I already have a dictionary of what should come before what, I just used that dictionary. After that the solution was trivial:

 func part2() async throws -> Int {
    let (rules, pages) = parsedInput
    let ordering = ordering(rules)

    return pages
      .filter(isInvalidFuntion(ordering))
      .map { $0.sorted(by: sortingFunction(ordering)) }
      .map(middleValue)
      .reduce(0, +)
  }

Final Thoughts #

>