Month: December 2024

Advent of Code Day 2 – Red-Nosed Reports

I woke up early (not by choice) and read today’s part 1 puzzle description in bed and at breakfast coffee. The part 1 was relatively quick and easy to implement, among replying to emails. Code spoilers below.

Then I had other things to do, went for a run (7 km, really windy, cloudy and partly rainy), then sauna and lunch. I tend to take Monday mornings to myself since I teach from 12 until 18.30.

In between supervising students in Zoom (and handling emails), I worked on the part 2 of the puzzle. I tried to find a fancy mathematical way to handle the part 2 change to part 1. Couldn’t get any of those attempts to work (I am not a math person) so I ended up in recursively trying to remove a single element from the data to see if it then satisfies the puzzle problem.

I’m sure there is a fancy solution using cleverly all the Swift algorithms and data structures etc. My solutions tend to be plain old imperative programming style kind of solutions. Well at least I got it working, and it’s not slow:

$ swift run -c release AdventOfCode 2 --benchmark
Building for production...
[5/5] Linking AdventOfCode
Build of product 'AdventOfCode' complete! (1.84s)
Executing Advent of Code challenge 2...
Part 1: 663
Part 2: 692
Part 1 took 0.003531042 seconds, part 2 took 0.005103042 seconds.

This year’s puzzles (so far) do not require any especially fast ways to do things, though, data sets are small… Maybe they’ll come later.

Here’s the part 1 solution for today’s puzzle:

func part1() -> Any {
    var safeLines = 0
    let matrix: Matrix<Int> = parse(data: data)
    for lineNumber in 0..<matrix.height {
      let line = matrix.elements[lineNumber]
      let direction = line[1]! - line[0]!
      if abs(direction) > 3 || direction == 0 {
        continue
      }
      var lineIsSafe = true
      for columnNumber in 2..<line.count {
        let nextDirection = line[columnNumber]! - line[columnNumber - 1]!
        if direction.signum() != nextDirection.signum() || abs(nextDirection) > 3 || nextDirection == 0 {
          lineIsSafe = false
          break
        }
      }
      if lineIsSafe {
        safeLines += 1
      }
    }
    return safeLines
}

For Part 2 I implemented a recursive function to solve the partially safe lines to see if changing one level would satisfy the puzzle, limiting the level of recursion so that only one attempt is made to fix an issue in one of the items in the levels by removing it:

private func isSafe(_ line: [Int?], level: Int) -> Bool {
    var diffs: [Int] = []
    for index in 1..<line.count {
      diffs.append(line[index]! - line[index - 1]!)
    }
    let tooLargeDiffsCount = diffs.filter( { abs($0) > 3 } ).count
    let noDiffCount = diffs.filter( { $0 == 0 } ).count
    var dirChangeCount = 0
    for index in 1..<diffs.count {
      if diffs[index] != diffs[index - 1] {
        if diffs[index].signum() != diffs[index - 1].signum() {
          dirChangeCount += 1
        }
      }
    }
    if tooLargeDiffsCount == 0 && noDiffCount == 0 && dirChangeCount == 0 {
      return true
    } else if level < 1 {
      for index in 0..<line.count {
        var attempt = line
        attempt.remove(at: index)
        if isSafe(attempt, level: level + 1) {
          return true
        }
      }
    }
    return false
}

I might check later how others have solved the puzzle to see if I’d get some inspiration for other styles of solving the puzzle in Swift.

Advent of Code 2024 Day 1

Participating the Advent of Code this year, as far as I am able to. That is, depending on how busy I am at work and at home.

Last year I got 30 stars, about 15 days of participation, last day I got stars (2) was Dec 16th. I missed some second stars for some days. As warmup for this year, I finished one missing second star from last year, now totaling 31 stars out of 50.

For today, the first day, I got two stars:

$ swift run -c release AdventOfCode 1 --benchmark 
Building for production...
...
Build of product 'AdventOfCode' complete! (0.35s)
Executing Advent of Code challenge 1...
Part 1: 1938424
Part 2: 22014209
Part 1 took 0.000817167 seconds, part 2 took 0.0012365 seconds.

Update (16.40 pm): I took a closer look at the Part 2 and managed to get a significant (relative) performance increase:

Part 1 took 0.000780209 seconds, part 2 took 0.000682292 seconds.

Improved time of 0.000682292 seconds is 55% of the original time of 0.0012365 seconds so almost a half.

The goal here is basically to find how many times a value in table 1 appears in table 2. I first sorted both tables and used Swift filter() to filter out and count the matching values from table 2 (original timing above).

Then I changed it to a simple O(n2) loop without any sorting, which to my surprise performs nicely with the data where n = 1000 (only). That takes about 0.00098nn seconds, usually, better than the original solution using sorting and filtering.

Then I wanted to see how much time I can slice off when adding back sorting of the tables and then use binary search to search for the first occurrence of the value in the second table, and step through the equal values in the table 2, counting how many times they occur. This was the fastest solution. Thought the first was shortest in lines of code, this is much faster.

End update.

Not taking too much stress out of this, not aiming to be fast and do not attempt to be at top of the leaderboards. Today I am 33rd on private SwiftLang leaderboard, but may soon fall down.

I’ve heard last year was more difficult than usual. Last year was my first, and this year I am more prepared. I brought in some utility code I wrote last year to this year project, and also searched for some nice snippets from others, porting some code from other languages to Swift.