I used Rust for day 6.
Setup
I read the input file and parse it into a useful data structure. I also define a few example inputs copied from the problem statement. Then, I run the part one and part two functions and print out the answers.
fn main() -> io::Result<()> {
let inp: String = read_to_string("input.txt")?;
let parsed = parse_input(inp.to_string());
println!("part 1: {}", part1(&parsed));
println!("part 2: {}", part2(&parsed));
Ok(())
}
const EXAMPLE: &'static str = "
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
";
const EXAMPLE_2: &'static str = "
...........#.....#......
...................#....
...#.....##.............
......................#.
..................#.....
..#.....................
....................#...
........................
.#........^.............
..........#..........#..
..#.....#..........#....
........#.....#..#......
";Note how an io::Result<()> is returned from the main function and the ? operator is used to exit early if reading the file fails for some reason.
Parsing
We have a grid in which several obstacles (indicated with a #) are placed and the initial position of a guard (indicated with ^) is marked. I chose to parse this into a hash map with (row, col) coordinates as the key and chars as the value.
fn parse_input(inp: String) -> HashMap<(i32, i32), char> {
inp.trim().lines().enumerate().flat_map(|(row, line)| {
line.trim().chars().enumerate().map(move |(col, ch)| ((row as i32, col as i32), ch))
}).collect()
}Part One
We need to find the number of unique positions the guard visits before leaving the grid. The guard keeps going in its current direction until it hits an obstacle. Upon hitting the obstacle, the guard turns right 90 degrees. It keeps on going like this until it eventually leaves the grid.
#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
enum Direction {
Up,
Down,
Right,
Left,
}
impl Direction {
fn offset(self) -> (i32, i32) {
match self {
Direction::Up => (-1, 0),
Direction::Down => (1, 0),
Direction::Left => (0, -1),
Direction::Right => (0, 1),
}
}
fn turn(self) -> Self {
match self {
Direction::Up => Direction::Right,
Direction::Right => Direction::Down,
Direction::Down => Direction::Left,
Direction::Left => Direction::Up,
}
}
}
impl Default for Direction {
fn default() -> Self {
Direction::Up
}
}To keep track of the guards direction, I defined an enum for the four directions the guard can go in, with methods for getting the next direction after turning and the coordinate deltas corresponding to each direction.
Now to actually solve the problem, I have a current position and current direction variable to keep track of where we are on the grid and a hash set of positions that were visited. The hash set automatically gets rid of duplicate values which lets us easily find the number of unique positions that were visited by getting the hash set’s length.
fn part1(input: &HashMap<(i32, i32), char> ) -> usize {
let mut current_position = *input.iter().find(|&(_, &c)| c == '^').unwrap().0;
let mut current_direction = Direction::default();
let mut visited: HashSet<(i32, i32)> = Default::default();
visited.insert(current_position);
loop {
let next_position = (current_position.0 + current_direction.offset().0,
current_position.1 + current_direction.offset().1);
match input.get(&next_position) {
None => break,
Some('#') => {
current_direction = current_direction.turn();
}
Some('.') | Some('^') => {
current_position = next_position;
visited.insert(current_position);
}
_ => {}
}
}
visited.len()
}To find the path of the guard, firstly the next position is calculated by adding the current turn’s offset to the current position.
Now, there are three cases that can happen:
- The grid doesn’t contain the next position, which means we fall off the grid and exit the loop.
- The grid contains an obstacle at the next position, so we turn.
- The grid is empty, so we go to the next position and add that position to our visited set.
We loop like this until we fall off the grid.
Part Two
For the second part, we need to force the guard to go in a loop by placing a single obstacle. This can be done with many different positions for the new obstacle: we need find out how many such positions are there.
Firstly, we can eliminate a lot of positions by only considering placing obstacles on the guard’s original path. Then, for each position on the guard’s original path, we test out if placing an obstacle there causes the guard to go into a loop.
fn part2(input: &HashMap<(i32, i32), char> ) -> usize {
let start_position = *input.iter().find(|&(_, &c)| c == '^').unwrap().0;
let mut current_position = start_position;
let mut current_direction = Direction::default();
let mut visited: HashSet<((i32, i32), Direction)> = Default::default();
let mut new_obstacles = HashSet::new();
loop {
let next_position = (current_position.0 + current_direction.offset().0,
current_position.1 + current_direction.offset().1);
if check_for_loop(current_position, current_direction, start_position, input, &visited) {
new_obstacles.insert(next_position);
}
visited.insert((current_position, current_direction));
match input.get(&next_position) {
None => break,
Some('#') => {
current_direction = current_direction.turn();
}
Some('.') | Some('^') => {
current_position = next_position;
}
_ => {panic!()}
};
}
new_obstacles.len()
}How do we find out if placing an obstacle causes a loop? We modify the grid, placing the obstacle at the given position and then traverse the grid again, keeping track of the visited positions and directions at each position. If we visit a position travelling in the same direction as before, we must be in a loop.
Note that just tracking the visited position will not work, as the path can intersect itself without being in a loop.
One interesting thing is how I am able to use the loop statement as an expression to return the answer. In Rust, this is only possible for loop loops as other loops may exit without hitting a break statement.
Some mistakes I made when solving this part were:
- Only making the guard turn at each position instead of actually placing an obstacle in that position. This is incorrect because the guard can hit the new obstacle multiple times in its loop.
- Starting at the place just before the new obstacle instead of starting at the actual start. I’m not sure why this is incorrect, but it probably has something to do with placing obstacles at path intersections. This is why the redundant
current_position,current_direction, andvisitedparameters exist in thecheck_for_loopfunction.
fn check_for_loop(
mut current_position: (i32, i32),
mut current_direction: Direction,
start_position: (i32, i32),
grid: &HashMap<(i32, i32), char>,
visited: &HashSet<((i32,i32), Direction)>) -> bool
{
let mut grid = grid.clone();
let mut visited = HashSet::new();
let next_position = (current_position.0 + current_direction.offset().0,
current_position.1 + current_direction.offset().1);
grid.insert(next_position, '#');
current_position = start_position;
current_direction = Default::default();
loop {
if visited.contains(&(current_position, current_direction)) {
break true;
}
visited.insert((current_position, current_direction));
let next_position = (current_position.0 + current_direction.offset().0,
current_position.1 + current_direction.offset().1);
match grid.get(&next_position) {
None => break false,
Some('#') => {
current_direction = current_direction.turn();
}
Some('.') | Some('^') => {
current_position = next_position;
}
_ => {panic!()}
};
}
}