Advent of Code 2024: Day 4 - Pattern Matching in Multiple Dimensions

The elves handed me what looked like a simple word search puzzle today. Find "XMAS", they said. Easy enough - until I discovered I needed to find it in every possible direction, including diagonals and backwards. Then part 2 hit me with X-shaped patterns, and suddenly I was deep in geometric territory. Let me show you how I solved this with my four languages.

The Challenge: Beyond Simple Word Search

The first part asked me to find all occurrences of "XMAS" in any direction - horizontal, vertical, diagonal, and even backwards. But part 2 threw a curveball: find X-shaped patterns where each diagonal contains "MAS" (forwards or backwards). This shift from linear pattern matching to geometric pattern recognition opened up fascinating implementation choices.

Four Languages, Four Approaches

Rust: Type Safety Meets Performance

In Rust, I started by modeling the directions and positions with zero-cost abstractions:

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Position {
    x: i32,
    y: i32,
}

const DIRECTIONS: [Direction; 8] = [
    Direction::new(0, 1),   // right
    Direction::new(1, 0),   // down
    Direction::new(1, 1),   // down-right
    Direction::new(1, -1),  // down-left
    // ... other directions
];

The beauty of Rust's implementation lies in its pattern matching for part 2:

fn check_xmas_pattern(&self, pos: Position) -> bool {
    match (
        self.get_diagonal(pos, UP_RIGHT),
        self.get_diagonal(pos, DOWN_RIGHT),
    ) {
        (Some(up), Some(down)) => 
            Self::is_valid_pattern(up) && Self::is_valid_pattern(down),
        _ => false,
    }
}

Elixir: Pattern Matching Paradise

Elixir's pattern matching made the directional checks particularly elegant:

@directions [
  {0, 1},    # right
  {1, 0},    # down
  {1, 1},    # down-right
  {1, -1},   # down-left
  {0, -1},   # left
  {-1, 0},   # up
  {-1, 1},   # up-right
  {-1, -1}   # up-left
]

defp valid_x_pattern?(diag1, diag2) do
  (is_mas?(diag1) and is_mas?(diag2)) or
    (is_mas?(diag1) and is_sam?(diag2)) or
    (is_sam?(diag1) and is_mas?(diag2)) or
    (is_sam?(diag1) and is_sam?(diag2))
end

Go: Pragmatic Grid Operations

Go's approach shines in its straightforward handling of grid operations:

func (g *Grid) getDiagonal(i, j int, d Direction) []byte {
    result := make([]byte, 3)
    for step := -1; step <= 1; step++ {
        x, y := i+d.dx*step, j+d.dy*step
        result[step+1] = g.data[x][y]
    }
    return result
}

Haskell: Pure Pattern Recognition

Haskell's solution leverages its type system for clear pattern matching:

getDiagonal :: Grid -> Position -> Direction -> Maybe String
getDiagonal grid (x, y) (dx, dy) =
    let positions = [(x + dx * i, y + dy * i) | i <- [-1..1]]
     in if all (inBounds grid) positions
            then Just [grid !! px !! py | (px, py) <- positions]
            else Nothing

Performance Optimization Through Geometry

The geometric nature of the patterns led to some interesting optimizations. In part 2, I realized I could skip the grid edges entirely since an X-pattern needs space in all directions:

fn solve_part2(&self) -> usize {
    (1..self.height.saturating_sub(1))
        .flat_map(|x| {
            (1..self.width.saturating_sub(1))
                .map(move |y| Position::new(x as i32, y as i32))
        })
        .filter(|&pos| self.get_char(pos) == Some('A'))
        .filter(|&pos| self.check_xmas_pattern(pos))
        .count()
}

Lessons in Pattern Recognition

This challenge taught me valuable lessons about pattern recognition in grids. The transition from part 1's linear search to part 2's geometric patterns showed how different abstractions can make complex pattern matching more manageable.

Rust's type system helped prevent coordinate confusion, Elixir's pattern matching made the logic crystal clear, Go's straightforward approach kept the code readable, and Haskell's pure functions made pattern composition natural.

What I love about this problem is how it demonstrates that even seemingly simple pattern matching can reveal elegant geometric properties. Whether through type-safe coordinates, pattern matching, or list comprehensions, each language offered its own insights into handling multi-dimensional patterns.