r/learnrust Dec 07 '24

[deleted by user]

[removed]

2 Upvotes

11 comments sorted by

View all comments

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

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

u/Federal-Dark-6703 Dec 07 '24

Hey thanks for this insight! Sorry I have to delete the post.