Tag: programming

Today I got to reuse the Matrix<T> generic data structure I implemented last year. Input being a grid of characters like:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

The goal in part 1 of the puzzle was to find out how many times the word “XMAS” appears in the grid, whether it is written left-to-right, right-to-left or downwards or upwards. And diagonally, from left to right and down, or from right to left and up, as well as from left to right and up, or from right to left and down.

The Matrix implementation has an algorithm to rotate the matrix in steps of 90 degrees. So instead of traversing the grid in all those directions, I rotated it 90 degrees to find out the left-right-up-down and back occurrences of XMAS. After each rotation, I just searched let to right, covering the other directions using rotation

The diagonals are handled in the same way, but in each rotation, I only handled the upper right half of the grid, diagonally where the lines were longer than three characters. I first made the mistake of handling the corner-to-corner line in all rotated diagonals, having too large count of occurrences. When I got to see this mistake, I handled that corner-to-corner diagonal only in one of the rotations.

In all of those cases I ended up with a line, string of characters. What I needed to do then was to find out how many times the line (and the line in reversed order) contains the XMAS.

Part 2 was much more simpler than part 1, so that was quickly solved. The goal was to count how many crosses like this…:

M.S
.A.
M.S

…the matrix contains.

This required just two loops within, starting from the first line and column from the edge, finishing on second-to-last row and column, check if the cell contains an A and then check if the opposing corners are different and contain M and S.

This was quick on my work laptop (MacBook Pro M2, 2022):

$ swift run -c release AdventOfCode 4 --benchmark
Building for production...
[1/1] Write swift-version--1AB21518FC5DEDBE.txt
Build of product 'AdventOfCode' complete! (0.16s)
Executing Advent of Code challenge 4...
Part 1: 2549
Part 2: 2003
Part 1 took 0.014584666 seconds, part 2 took 0.002027958 seconds.

The matrix rotations take time, obviously, so part 1 was slower. I considered counting the results of rotated matrices in parallel, but decided not to. That may or may not produce any speed advantage, don’t know… Also could’ve tried to do not rotating in part 1, and just go all in to the matrix from all directions and back to find the words. Well’ it works so I’ll let it be.

Today’s puzzle was about parsing. Quite straightforward to implement, having done parsing earlier for different types of structured strings, like tsv, csv, json, xml, etc.

In part 1, I anticipated that part 2 would add parsing some other instructions than mul so I did implement it so. There is an Instruction structure that specifies:

• the instruction name
• expected number of parameters and
• the list of parameter values

Then the instruction is able to evaluate the result. Parsing returns an array of Instructions to execute, and then they are executed, accumulating the result of each mul instruction evaluated:

private struct Instruction {
  let instruction: String
  let params: Int
  var values: [Int] = []
    
  var result: Int {
    if instruction == "mul" {
      return values.reduce(1, *)
    }
    return 0
  }
}

In part 2, the execution just changes the state; after do instruction, following instructions are evaluated, and after don't, the instructions are ignored, until next do instruction:

func part1() -> Any {
    let instructions = parse(data, 
                     for: [
                        Instruction(instruction: "mul", params: 2)
                     ])
    return execute(instructions)
}

func part2() -> Any {
    let instructions = parse(data,
                     for: [
                      Instruction(instruction: "mul", params: 2),
                      Instruction(instruction: "do", params: 0),
                      Instruction(instruction: "don't", params: 0)
                     ])
    return execute(instructions)
}

Benchmarked:

$ swift run -c release AdventOfCode 3 --benchmark
Building for production...
[6/6] Linking AdventOfCode
Build of product 'AdventOfCode' complete! (2.55s)
Executing Advent of Code challenge 3...
Part 1: 188116424
Part 2: 104245808
Part 1 took 0.00304425 seconds, part 2 took 0.004164459 seconds.

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.