img of Advent of Code 2024 - Day 6: Guard Gallivant

Advent of Code 2024 - Day 6: Guard Gallivant

Attention!

  • Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.

  • My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time the challenges.

  • Every challenge = different language - just for fun and learning.

  • I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.

Today, I’m tackling a challenge set in a North Pole prototype suit manufacturing lab back in the year 1518, where I’m asked to help the Historians avoid an inconvenient time paradox while they search for the Chief. The problem involves predicting the path of a guard patrolling the lab, and ensuring The Historians can safely avoid them. The guard follows a strict pattern and must navigate through the lab based on its obstacles.

The solution for today’s challenge will be implemented in Rust.

Part One: Predicting Path

The first task is to figure out how many distinct positions the guard will visit before leaving the mapped area. The lab map is a 2D grid, with the guard initially facing upwards (^). The guard moves according to the following protocol:

If there’s an obstacle directly in front of the guard, it turns right 90 degrees. Otherwise, it moves one step forward in its current direction. I was tasked with determining how many distinct positions the guard will visit before it exits the area. This is essentially about simulating the movement of the guard and keeping track of the distinct positions the guard visits.

Example input

....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...

Code for reading the input

Let’s start with a function that read the input file and returns the lab map: 2d vector filled with boolean -> true means an obstacle, false means empty space.

// lib.rs
pub fn parse_input(input: &str) -> Option<(Vec<Vec<bool>>, Position)> {
  let mut starting_pos = Position { x: 0, y: 0 };
  // world map is a 2D vector of booleans (true = obstacle, false = empty space)
  let lab_map: Option<Vec<Vec<bool>>> = match fs::read_to_string(input) {
    Ok(contents) => Some(
      contents
        .lines()
        .enumerate()
        .map(|(row, line)| {
          line.chars()
            .enumerate()
            .map(|(col, ch)| match ch {
              '#' => true,
              '^' => {
                starting_pos.x = col as isize;
                starting_pos.y = row as isize;
                false
              }
              _ => false,
            })
            .collect::<Vec<bool>>()
        })
        .collect::<Vec<Vec<bool>>>(),
    ),
    Err(_e) => None,
  };
  lab_map.map(|lab_map| (lab_map, starting_pos))
}

It is called from the main function:

// main.rs
fn main() {
  let filename = "input.txt";
  if let Some((lab_map, starting_pos)) = aoc6::parse_input(filename) {
    let r1 = aoc6::part_one(&lab_map, starting_pos);
    let r2 = aoc6::part_two(&lab_map, starting_pos);
    println!("Part one: {}", r1);
    println!("Part two: {}", r2);
  } else {
    println!("Error parsing input");
  }
}

Before running the simulation, I transformed the lab map into 1d vector of booleans for easier access to the elements. I also created a struct to represent the guard’s position and direction, same for the lab (our world map). Then I created a struct for Position and an enum for Direction.

Most of the elements listed above have their impl block with methods, for example: to move the guard, turn it, and check if the guard is still in the lab. I will not list all of them here, (find them in the repository) but the most important will be listed in the next sections.

struct Lab {
  vector: Vec<bool>,
  height: usize,
  width: usize,
}

struct Guard {
  pos: Position,
  dir: Direction,
}

pub struct Position {
  pub x: isize,
  pub y: isize,
}

enum Direction {
  N,
  S,
  E,
  W,
}

Code for Part One

To solve this, I broke down the task into two key steps:

  • Simulation: The guard’s movement was simulated using a Guard struct, which tracks its position and facing direction. A loop repeatedly checks whether the guard is facing an obstacle and either turns or moves forward accordingly.
  • Counting Visited Positions: A HashSet keeps track of all distinct positions visited by the guard.

The part_one creates an environment for the guard and then simulates its movement. It counts the number of distinct positions visited by the guard before it exits the lab.

The guard ‘step’, ‘turn_right’ are methods on the Guard struct that use it’s state to check the position and direction using Direction enum method.

// lib.rs
pub fn part_one(lab_map: &Vec<Vec<bool>>, starting_pos: Position) -> usize {
  let lab = Lab::new(lab_map.len(), lab_map[0].len(), flatten_lab_map(lab_map));
  let mut guard = Guard::new(starting_pos, Direction::N);

  count_visited_places(&lab, &mut guard)
}

fn flatten_lab_map(map: &Vec<Vec<bool>>) -> Vec<bool> {
  map.iter().flatten().cloned().collect()
}

fn count_visited_places(lab: &Lab, guard: &mut Guard) -> usize {
  let mut visited = HashSet::default();
  visited.insert(guard.pos);

  while !lab.out_of_bounds(guard.pos) {
    if lab.at_obstacle(guard.step(false)) {
      guard.turn_right();
    }
    visited.insert(guard.step(true));
  }
  visited.len() - 1
}

To know next direction and what will be the position of the next step I implemented two methods on the Direction enum. It switches from North to West, South to East, and so on. If the current direction is North (N), it changes to West (W), and this cycle continues for all the directions.

The second method, next_step_position, calculates the new position based on the current direction. It takes a Position struct and adjusts either the x or y coordinate according to the direction. For North (N), it decreases the y value, while for South (S), it increases the y value. Similarly, moving East (E) decreases the x value, and moving West (W) increases the x value. The function then returns the updated Position.

// lib.rs
impl Direction {
  fn next_direction(&mut self) {
    *self = match self {
      Direction::N => Direction::W,
      Direction::S => Direction::E,
      Direction::E => Direction::N,
      Direction::W => Direction::S,
    }
  }

  fn next_step_position(&self, mut pos: Position) -> Position {
    match self {
      Direction::N => pos.y -= 1,
      Direction::S => pos.y += 1,
      Direction::E => pos.x -= 1,
      Direction::W => pos.x += 1,
    }
    pos
  }
}

Quite important here is the Lab struct and its methods. It has methods to check if the guard is out of bounds or if there is an obstacle in the way. There is not much to say about it, the code is quite simple and straightforward.

The hardest part here is to calculate the position in the 1d vector, which should be understood like:

// 2d vector
[
  [0, 1, 2]
  [3, 4, 5]
  [6, 7, 8]
]

// 1d vector
[0, 1, 2, 3, 4, 5, 6, 7, 8]

To access the element at position (1, 2) (row 1, column 2), you apply the formula:

index = row * width + column

So, the element at (1, 2) corresponds to index 5 in the flattened 1D array which is the 6th element.

// lib.rs

impl Lab {
  fn new(height: usize, width: usize, vector: Vec<bool>) -> Self {
    Self { vector, height,width }
  }

  fn out_of_bounds(&self, pos: Position) -> bool {
    return pos.x < 0 || pos.y < 0
            || pos.x >= self.width as isize
            || pos.y >= self.height as isize;
  }

  fn at_obstacle(&self, pos: Position) -> bool {
    if self.out_of_bounds(pos) {
      return false;
    }
    self.vector[pos.y as usize * self.height + pos.x as usize]
  }

  fn move_obstacle(&mut self, pos: Position, obstacle: bool) {
    self.vector[pos.y as usize * self.height + pos.x as usize] = obstacle;
  }
}

And that’s it! The solution for Part One is ready. Now, let’s move on to Part Two.

Part Two: Creating a Loop

In Part Two, the challenge expands. The Historians need to place a new obstruction in the lab to trap the guard in a loop, preventing it from leaving the area. My goal is to determine all possible positions where a new obstruction can be placed to cause this looping behavior.

Key Insight

The main idea here is to find positions where placing a new obstruction causes the guard to get stuck in a perpetual cycle. The algorithm simulates the guard’s movement again, but this time, I’m testing whether placing a new obstruction at each position will cause the guard to enter a loop.

To do this, I simulate adding an obstruction at each possible position, then check if the guard enters a loop. If it does, that position is a valid candidate for the obstruction.

But how to check if the guard is in a loop? I already track the visited positions in the count_visited_places function. I can use this information to detect a loop. If the guard revisits a position, it means it’s stuck in a loop. The key here is the direction -> if the guard is in the same position and facing the same direction, it means it’s in a loop.

Code for Part Two

The part_two function works similarly to part_one, but calls the count_infinite_loop_ways function. The magic happens there.

// lib.rs
pub fn part_two(lab_map: &Vec<Vec<bool>>, starting_pos: Position) -> usize {
  let lab = Lab::new(lab_map.len(), lab_map[0].len(), flatten_lab_map(lab_map));
  let guard = Guard::new(starting_pos, Direction::N);

  count_infinite_loop_ways(&lab, &guard)
}

fn count_infinite_loop_ways(lab: &Lab, guard: &Guard) -> usize {
  (0..lab.width)
      .into_par_iter()
      .map(|x| {
        let mut new_lab = lab.clone();
        (0..lab.height)
          .filter(|y| guard.loops_at(x, *y, &mut new_lab))
          .count()
        })
      .sum()
}

The count_infinite_loop_ways function iterates over all possible positions in the lab and checks if the guard enters a loop when an obstruction is placed at that position. It uses the loops_at method on the Guard struct to simulate the guard’s movement and check if it enters a loop. The loops_at method is de facto the most important piece of code in this solution but I didn’t want to place it here without the context.

// lib.rs
impl Guard {
  // skipping less important methods

  fn loops_at(&self, x: usize, y: usize, lab: &mut Lab) -> bool {
    let new_pos = Position {
      x: x as isize,
      y: y as isize,
    };

    if self.pos == new_pos || lab.at_obstacle(new_pos) {
      return false;
    }

    lab.move_obstacle(new_pos, true);
    let is_cycle = self.in_cycle(lab);
    lab.move_obstacle(new_pos, false);
    is_cycle
  }

  fn in_cycle(mut self, lab: &Lab) -> bool {
    let mut visited = HashSet::default();
    visited.insert(self.point());

    while !lab.out_of_bounds(self.pos) {
      while lab.at_obstacle(self.step(false)) {
        self.turn_right();
      }
      self.step(true);
        if !visited.insert(self.point()) {
          return true;
        }
    }
    false
  }
}

In the loops_at method, I first check if the guard is already at the position or if there is an obstacle there. If so, I return false because the guard can’t enter a loop in these cases. Then, I place an obstruction at the position and check if the guard enters a loop by calling the in_cycle method. The in_cycle method simulates the guard’s movement and checks if it enters a loop. It uses a HashSet to track visited positions and returns true if the guard revisits a position. self.pint() returns a tuple with the guard’s position and direction.

And that’s it! The solution for Part Two is ready. Now, let’s move on to the conclusion.

Final Solution Code

The final solution code can be found on my GitHub repository.

If you like the content, don’t forget to give it a star ⭐.

Part One Complexity:

  • Time Complexity: O(N), where N is the number of steps the guard takes before exiting the lab.
  • Space Complexity: O(P), where P is the number of distinct positions visited.

Part Two Complexity:

  • Time Complexity: O(W * H), where W is the width of the lab and H is the height, as we check each position in the lab.
  • Space Complexity: O(W * H), for storing the lab map and simulation data.

Conclusion

In conclusion, this challenge, set in a 1518 North Pole prototype suit lab, presented a unique and complex task that required careful attention to both simulation and algorithmic efficiency.

Rust, though incredibly powerful and fast, posed a challenge in terms of writing clear and effective code, particularly when managing the simulation of the guard’s movement and detecting loops.

I rewrote the code couple of times (the performance was terrible). While difficult, Rust’s strong type system and memory safety features made this challenge not only a test of algorithmic skills but also of how to work effectively within its ecosystem.

Of course my work look like a beginner’s code until the soulution was ready, then I spent some time to refactor it reading documentation, searching for different rust features and so on.

I’m happy with the final result.

Tomorrow… Swift.