Today I dove into path finding and state machines. The problem seemed simple at first - just simulate a guard's patrol route - but it turned into a fascinating puzzle about cycle detection. I tackled it with my usual four languages - Rust, Elixir, Go, and Haskell - and each one showed me something new about handling state and detecting patterns.

The Challenge: Predicting Patrol Patterns

The puzzle dropped me into a 1518 laboratory with a guard following an intriguingly simple protocol: turn right when facing an obstacle, otherwise move forward. This deceptively straightforward rule set led to some complex emergent behavior, especially when I started looking for patrol loops in part 2.

Four Languages, Four Philosophies

Rust: Where Performance Meets Safety

The heart of Rust's solution lies in its type system and zero-cost abstractions. Let's look at how it handles position and movement:

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Position {
    row: i32,
    col: i32,
}

impl Position {
    const fn move_in_dir(self, dir: Direction) -> Self {
        match dir {
            Direction::North => Self::new(self.row - 1, self.col),
            Direction::East => Self::new(self.row, self.col + 1),
            Direction::South => Self::new(self.row + 1, self.col),
            Direction::West => Self::new(self.row, self.col - 1),
        }
    }
}

What's fascinating here is how Rust's type system guides us toward correct code. The #[derive] attribute automatically implements crucial traits, while const fn ensures our movement calculations happen at compile time where possible. When part 2 demanded parallel processing, Rayon's parallel iterators slipped in seamlessly:

candidates
    .into_par_iter()
    .filter(|&pos| grid.creates_loop(pos, start))
    .count()

Haskell: Pure Functions and Strict Evaluation

Haskell's approach to the problem is particularly interesting. The language's purity forced me to think carefully about state management:

data State = State
    { pos :: {-# UNPACK #-} !Position
    , dir :: !Direction
    } deriving (Eq, Ord, Show)

hasLoop :: Grid -> Position -> State -> Bool
hasLoop grid obstacle start = go Set.empty start
  where
    go !visited !current
        | isOutOfBounds grid nextPos = False
        | Set.member (pos current, dir current) visited = True
        | otherwise = go (Set.insert (pos current, dir current) visited) nextState

Those UNPACK pragmas and strict annotations (!) aren't just syntax noise - they're crucial performance optimizations. Without them, Haskell's lazy evaluation would build up during my cycle detection, leading to space leaks. The where clause creates a beautiful local scope for my helper function, making the code both elegant and efficient.

Go: Simplicity in Motion

Go's implementation shows its strength in handling concurrent operations without sacrificing readability:

func (g *Grid) createLoop(obstacle Position, start State) bool {
    visited := make(map[State]struct{})
    current := start
    
    for steps := 0; steps < g.width * g.height * 4; steps++ {
        nextPos := current.pos.moveInDir(current.dir)
        if !g.isValid(nextPos) {
            return false
        }
        
        var nextState State
        if g.isBlocked(nextPos, obstacle) {
            nextState = State{current.pos, current.dir.turnRight()}
        } else {
            nextState = State{nextPos, current.dir}
        }
        
        if _, exists := visited[nextState]; exists {
            return true
        }
        visited[nextState] = struct{}{}
        current = nextState
    }
    return false
}

The explicit state management and boundary checking reflect Go's philosophy of clarity over cleverness. When it came to parallelizing the search in part 2, Go's channels provided a natural way to distribute the work.

Elixir: Pattern Matching Poetry

Elixir's solution reads almost like the problem description itself:

defp process_instruction(grid, pos, dir, seen) do
  next_pos = move_forward(pos, dir)
  cond do
    out_of_bounds?(grid, next_pos) ->
      seen
    obstacle_at?(grid, next_pos) ->
      new_dir = turn_right(dir)
      new_state = {pos, new_dir}
      if MapSet.member?(seen, new_state),
        do: seen,
        else: process_instruction(grid, pos, new_dir, MapSet.put(seen, new_state))
    true ->
      new_state = {next_pos, dir}
      if MapSet.member?(seen, new_state),
        do: seen,
        else: process_instruction(grid, next_pos, dir, MapSet.put(seen, new_state))
  end
end

The pattern matching and guard clauses make the state transitions crystal clear, while the recursive structure naturally maps to the problem's iterative nature.

Performance: The Part 2 Challenge

Part 2 transformed my simple path-finding problem into a search for cycle-inducing positions. This is where the performance characteristics of each language really came into play. Rust's Rayon made parallelization almost trivial, while still maintaining memory safety. Go's goroutines gave me fine-grained control over concurrent operations. Elixir's built-in parallelism through Task.async_stream made it easy to distribute the work across cores. Haskell relied heavily on GHC's optimizations and strict evaluation to keep memory usage in check.

Reflections on State and Cycles

What fascinates me about this challenge is how it reveals each language's approach to state management. Rust's ownership system ensures we can't accidentally share state between threads. Haskell's purity forces us to be explicit about our state transitions. Go's simplicity makes the state machine's logic clear and maintainable. Elixir's pattern matching turns complex state transitions into readable code.