Advent of Code Day4: Ceres Search

December 4, 2024

6 min read advent-of-code swift 

Today (1)https://adventofcode.com/2024/day/4 wasn’t so much about graph theory once you read the questions, but I took a similar approach to solving the problem. Parsing was trivial; just read a nested array of Characters.

My solution can be found on Github (2)https://github.com/Abizern/aoc-swift-2024/blob/main/Sources/Day04.swift

Part 1 #

The word search game is about finding the word “XMAS” in any direction.

I used a simple search to get the positions of the Character “X” as a tuple, as my start positions.

With an enum to specify directions as compass points: North, North East, West etc

  enum Direction: Equatable, CaseIterable {
    case n, ne, e, se, s, sw, w, nw // Compass points
  }

Then I created a type to represent candidates:

  struct Candidate {
    let partial: String
    let direction: Direction
    let position: (Int, Int)
    var isValid: Bool {
      partial == "XMAS"
    }
  }

To start with, given a position for an “X” I created all possible candidates and put them in an array. This is what I meant when I said I took a graph theoretical approach, don’t check the point, just add it to a list to check later. I did this with a method:

  struct Candidate {
    // ...
    static func initial(row: Int, col: Int) -> [Candidate] {
      var accumulator = [Candidate]()
      for direction in Direction.allCases {
        accumulator.append(Candidate(partial: "X", direction: direction, position: (row, col)))
      }
      return accumulator
    }
  }

Now I can use this to create an array of all the starting points with their directions to search.

  func countOccurrencesAround(_ position: (Int, Int), rows: [[Character]]) -> Int {
    var count = 0
    let dimensions = (width: rows[0].count, height: rows.count)
    var candidates = Candidate.initial(row: position.0, col: position.1)[...]

    while let candidate = candidates.first {
      var newCandidates = candidates.dropFirst()
      if candidate.isValid {
        count += 1
        candidates = candidates.dropFirst()
      } else {
        if let next = candidate.next(rows: rows, dimensions: dimensions) {
          newCandidates.append(next)
        }
      }
      candidates = newCandidates
    }

    return count
  }

For each candidate in this list, if it is valid, I increment the count of found words. If it is not valid, I try to create a new candidate, by adding a value in the search direction to the list. This creation method is long winded, but it’s easy to write by following a process:

  struct Candidate {
    // ...

    func next(rows: [[Character]], dimensions: (width: Int, height: Int)) -> Candidate? {
      guard "XMAS".hasPrefix(partial) else { return nil }

      var newRow = position.0
      var newCol = position.1
      switch direction {
      case .n:
        guard position.0 > 0
        else { return nil }
        newRow = position.0 - 1
      case .ne:
        guard position.0 > 0,
              position.1 < dimensions.height - 1
        else { return nil }
        newRow = position.0 - 1
        newCol = position.1 + 1
      case .e:
        guard position.1 < dimensions.width - 1
        else { return nil }
        newCol = position.1 + 1
      case .se:
        guard position.0 < dimensions.width - 1,
              position.1 < dimensions.height - 1
        else { return nil }
        newRow = position.0 + 1
        newCol = position.1 + 1
      case .s:
        guard position.0 < dimensions.height - 1
        else { return nil }
        newRow = position.0 + 1
      case .sw:
        guard position.0 < dimensions.width - 1,
              position.1 > 0
        else { return nil }
        newRow = position.0 + 1
        newCol = position.1 - 1
      case .w:
        guard position.1 > 0
        else { return nil }
        newCol = position.1 - 1
      case .nw:
        guard position.0 > 0,
              position.1 > 0
        else { return nil }
        newRow = position.0 - 1
        newCol = position.1 - 1
      }

      let value = rows[newRow][newCol]
      let newPartial = partial + String(value)
      return Candidate(partial: newPartial, direction: direction, position: (newRow, newCol))
    }
  }

If the current partial string is not part of “XMAS” I return nil

If it is, then after some wordy checks to make sure the next search position is within the bounds of the grid I create a new candidate and add that to the end of the list.

By the time the list is empty, I’ve searched all valid candidates around the start position and I can return the count.

To get the answer, I map this function to each start point and sum the results:

func countOccurences(_ rows: [[Character]]) -> Int {
    let starts = findStarts("X", rows: rows)
    let count = starts.map {
      countOccurrencesAround($0, rows: rows)
    }.reduce(0, +)

    return count
  }

And that’s it for the first part.

Part 2 #

This is simpler than part 1. I followed a similar method to part 1 by first finding all the possible start positions — an “A” character.

  func hasCross(_ position: (Int, Int), rows: [[Character]], dimensions: (width: Int, height: Int)) -> Bool {
    let row = position.0
    let col = position.1
    var result = false

    guard (1 ..< dimensions.width - 1).contains(row),
          (1 ..< dimensions.height - 1).contains(col)
    else { return false }

    let ne = rows[row + 1][col + 1]
    let se = rows[row + 1][col - 1]
    let sw = rows[row - 1][col - 1]
    let nw = rows[row - 1][col + 1]

    switch (nw, se) {
    case ("M", "S"):
      if (sw == "M" && ne == "S") || (sw == "S" && ne == "M") { result = true }
    case ("S", "M"):
      if (sw == "M" && ne == "S") || (sw == "S" && ne == "M") { result = true }
    default: result = false
    }
    return result
  }

First, I make sure that the start position is at least one row and column in from the edge, and then I check the diagonally opposite corners. If one contains M the other must contain an S and vice-versa, I do this for both sets of corners, and if both checks pass then the position has a valid “X-MAS”

To get the solution I map this function onto the list of start points, filter them for validity and return the count.

  func countCrosses(_ rows: [[Character]]) -> Int {
    let dimensions = (width: rows[0].count, height: rows.count)
    let starts = findStarts("A", rows: rows)
    let count = starts.map {
      hasCross($0, rows: rows, dimensions: dimensions)
    }.filter { $0 }.count

    return count
  }

Final Thoughts #

>