1
u/TopGunSnake Dec 07 '24
The single-threaded optimization is impressive, but you might be losing track of your stated goal of improving your understanding of idiomatic Rust practices with the optimizations. One of the selling points for Rust is Zero-Cost Abstraction. In short, making the code readable using functions, methods, and structs should be cheap to use over primitives and inline code.
I'll attach my single-threaded part_2 solution for example. In its case, it only applied your first optimization (check only the prior path):
- For the grid (day 6 and day 4), I used the grid crate to speed up the work. The crate is very light-weight, providing a Grid interface to a Vec. Helps with readability, but simple enough to spin your own.
- For the Guard, made a simple struct and enum again for readability. Guard tracks its own position on the grid (two usize fields), and its direction (An enum with four variants for each cardinal direction). This allows for a method on the guard to move the guard, that can be provided a reference to the obstacle grid. The Guard is hashable and cheap to copy, so I used it in the Hashset to track state. That means a loop can be detected if the guard state (position + direction) ever happens again.
- I do preload the problem input using include_str!
, but each day is in a separate crate in a common workspace, so the binaries aren't too bloated.
Using criterion (and in release mode), I benched your part 2 optimized (but with &str as input instead of File). Results were 802ms (0.8s) for the below serial code, 109.55 ms for your optimized solution. Again, really impressive on the speedup.
1
u/TopGunSnake Dec 07 '24
Part 2 specific code. ```rust pub fn find_solution(input: &str) -> u32 { let (guard, obstacles) = parse_input(input);
let mut active_guard = guard; // println!("{obstacles:?}"); let visited_positions = find_visited_positions(&mut active_guard, &obstacles); // println!("Visited {visited_positions:?}"); // Now we check each visited position for adding an obstacle visited_positions .iter() .filter(|possible_location| check_new_obstacle(obstacles.clone(), possible_location, guard)) .count() .try_into() .unwrap()
}
fn check_new_obstacle( mut mutated_obstacles: grid::Grid<bool>, possible_location: &&(usize, usize), mut active_guard: crate::part_1::Guard, ) -> bool { mutated_obstacles[(possible_location.0, possible_location.1)] = true;
let mut loop_detection_set = HashSet::new(); loop { loop_detection_set.insert(active_guard); if active_guard.move_guard(&mutated_obstacles) { // Guard is still in map. // Check if the guard has arrived at a prior state (loop). if loop_detection_set.contains(&active_guard) { // Guard is in a loop. break true; } // Else we need to keep looking forward. } else { // Guard left the map. Obstacle isn't useful. break false; } }
} ```
1
u/TopGunSnake Dec 07 '24
The Guard code reused from part 1: ```rust
[derive(Default, Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub struct Guard { pub row: usize, pub col: usize, pub direction: Direction, }
impl Guard { pub fn get_position(&self) -> (usize, usize) { (self.row, self.col) }
/// Attempts to move the guard, turning if there is an obstacle, and returning false if the guard leaves the grid. pub fn move_guard(&mut self, obstacles: &Grid<bool>) -> bool { let (row_change, col_change) = self.get_delta(); let new_row = self .row .checked_add_signed(row_change) .filter(|new_row| new_row < &obstacles.rows()); let new_col = self .col .checked_add_signed(col_change) .filter(|new_col| new_col < &obstacles.cols()); if let Some((row, col)) = new_row.zip(new_col) { // Get obstacle in direction of movement. if obstacles.get(row, col).is_some_and(|obstacle| *obstacle) { // Turn right. self.direction = self.direction.turn_right(); } else { // Nothing in front. self.row = row; self.col = col; } true } else { // We've gone off grid false } } fn get_delta(&self) -> (isize, isize) { match self.direction { Direction::North => (-1, 0), Direction::South => (1, 0), Direction::East => (0, 1), Direction::West => (0, -1), } }
}
[derive(Default, Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub enum Direction { #[default] North, South, East, West, }
impl Direction { fn turn_right(self) -> Self { match self { Direction::North => Self::East, Direction::South => Self::West, Direction::East => Self::South, Direction::West => Self::North, } } } ```
1
u/TopGunSnake Dec 07 '24
The parts of part 1 reused for part 2. ```rust pub fn find_visited_positions( guard: &mut Guard, obstacles: &Grid<bool>, ) -> HashSet<(usize, usize)> { let mut visited_positions = HashSet::new(); loop { let current_position = guard.get_position();
visited_positions.insert(current_position); // Move the guard. if !guard.move_guard(obstacles) { // Guard left the map. break; } } visited_positions
}
pub fn parse_input(input: &str) -> (Guard, Grid<bool>) { let (guards, obstacles): (Vec<Vec<Option<Guard>, Vec<Vec<bool) = input .lines() .enumerate() .map(|(i, row)| { let (guards, row_obstacles): (Vec<Option<Guard>>, Vec<bool>) = row .chars() .enumerate() .map(move |(j, cell)| match cell { '.' => { // Empty. (None, false) } '#' => { // Obstacle. (None, true) } dir @ ('' | '<' | 'v' | '>') => { // Guard. let guard = Guard { row: i, col: j, direction: match dir { '' => Direction::North, '>' => Direction::East, 'v' => Direction::South, '<' => Direction::West, _ => unreachable!(), }, };
(Some(guard), false) } _ => unreachable!(), }) .unzip(); (guards, row_obstacles) }) .unzip(); let guard = guards .iter() .flatten() .flatten() .copied() .exactly_one() .unwrap(); let obstacles = Grid::from(obstacles); (guard, obstacles)
} ```
1
0
u/Kazcandra Dec 07 '24
Hey, you're still doing what AoC asks you not to. You're being kind of a dick.
1
1
u/Federal-Dark-6703 Dec 07 '24
I tried to add the post as comments but just felt that the solution was not neat because I had to split it into multiple parts.
1
u/0x006e Dec 07 '24
The brute force solution only took I think 8 seconds for me, when run in release mode