Day 1: Report Repair

Advent of Code 2020

This year we’re apparently not saving Christmas, but instead saving our vacation. This will definitely please the redditor who created this bingo card where the free middle space was “We have to save Christmas”. 😆

The first part seems trivial enough, go through a list of values, find the first two that add up to 2020 and then multiply them together. I quickly made use of the new swift-algorithms package and its implementation of combinations(ofCount:)

input.integers
  .combinations(ofCount: 2)
  .first(where: { $0.sum() == 2020 })
  .map { $0.product() } ?? 0

Part two is similar except we need to find the first three values in the list that add up 2020. Based on above, it was a fairly trivial modification to find the answer and finish the day’s puzzles before a morning run. 🏃‍♂️

input.integers
  .combinations(ofCount: 3)
  .first(where: { $0.sum() == 2020 })
  .map { $0.product() } ?? 0

As the day went on, I ended up discussing the puzzle with a fair number of people and concluded that my solution was very slow in comparison to theirs. I was seeing people with solutions taking milliseconds and mine was taking around 1.3s to complete!

Towards the end of the day, Mike helped me understand where the slowness in my code was coming from. Although combinations(ofCount:) is fast to create, the length of its output determines how much is subsequently filtered on. Because every item needs to be paired with every other item, combinations(ofCount: 2) ends up a complexity of O(n²) and using combinations(ofCount: 3) requires that every item is paired with every other item and every other other item, so it is O(n³).

To remove one of the loops of complexity in the solution above, we can use two key pieces of information:

Set.contains is an O(1) operation
The numbers need to add up to 2020

In the first part we can get a set of the values, then simply loop through the numbers until we find the first element where the result of subtracting it from 2020 exists in the set of values. We know that if that other value exists in the set this is the first combination that adds up to 2020 that are both in the initial array of values.

let values = Set(input.integers)
return input.integers
  .first(where: { values.contains(2020 - $0) })
  .map { $0 * (2020 - $0) } ?? 0

For the second part, we perform the same trick of keeping a set of the values to look up against, but this time we do use combinations(ofCount:) to give us pairs of numbers, and subtract their sum from 2020 and see whether the set contains that value. Now we’re only finding pairs of combinations rather than three values, the solution is now O(n²) rather than O(n³).

let values = Set(input.integers)
return input.integers
  .combinations(ofCount: 2)
  .first(where: { values.contains(2020 - $0.sum()) })
  .map { $0.product() * (2020 - $0.sum()) } ?? 0

These changes took my time to solve part 2 from 1300ms to just 13ms! I was fairly happy with my original solution and liked how clean it looked, but it’s nice to be able to make improvements in the early days of the Advent of Code, so that I can apply that skill to later challenges.

Other notes

u/theChief__ presented a totally trippy visualisation.
u/that_lego_guy continued their tradition by completing the puzzle using Excel.
u/creamisse wrote a solution in their own language consisting of nothing but various modification of the letter A. 😂
u/ExtraOlive635 didn’t realise it was a coding challenge and took 40 minutes to solve day 1 by hand. Good effort!