Day 6: Guard Gallivant

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • Deebster@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    5 days ago

    Rust

    Only part 1 because I’m meant to be leaving for a holiday in a few hours and haven’t packed yet. Part two looks simple enough to add:

    part 2 plan

    Change seen positions set to include direction, if pos+dir already seen then it’s a loop. Test all spaces.

    Edit: I did the change on my phone (which was painful).

    use std::{collections::HashSet, fs, str::FromStr};
    
    use color_eyre::eyre::{Report, Result};
    
    type GridPosition = usize;
    
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    enum Direction {
        N,
        E,
        S,
        W,
    }
    
    impl Direction {
        fn clockwise(&self) -> Self {
            match self {
                Direction::N => Direction::E,
                Direction::E => Direction::S,
                Direction::S => Direction::W,
                Direction::W => Direction::N,
            }
        }
    }
    
    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    enum Thing {
        Guard(Direction),
        Obstruction,
        Space,
    }
    
    #[derive(Debug, PartialEq, Eq)]
    struct LabMap {
        grid: Vec<Thing>,
        width: usize,
        height: usize,
    }
    
    impl FromStr for LabMap {
        type Err = Report;
    
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let grid = s
                .chars()
                .filter_map(|ch| {
                    use Thing::*;
                    match ch {
                        '^' => Some(Guard(Direction::N)),
                        '>' => Some(Guard(Direction::E)),
                        'v' => Some(Guard(Direction::S)),
                        '<' => Some(Guard(Direction::W)),
                        '#' => Some(Obstruction),
                        '.' => Some(Space),
                        '\n' => None,
                        _ => unreachable!(),
                    }
                })
                .collect::<Vec<_>>();
            let width = s
                .chars()
                .position(|ch| ch == '\n')
                .ok_or_else(|| Report::msg("grid width cannot be zero, or one line"))?;
            let height = grid.len() / width;
            Ok(Self {
                grid,
                width,
                height,
            })
        }
    }
    
    impl LabMap {
        fn neighbour(&self, i: GridPosition, dir: Direction) -> Option<GridPosition> {
            let width = self.width;
            let length = self.grid.len();
            use Direction::*;
            match dir {
                N if i >= width => Some(i - width),
                E if i % width != width - 1 => Some(i + 1),
                S if i + width < length => Some(i + width),
                W if i % width != 0 => Some(i - 1),
                _ => None,
            }
        }
    
        fn guard_pos(&self) -> Option<(GridPosition, Direction)> {
            self.grid
                .iter()
                .enumerate()
                .filter_map(|(pos, &thing)| match thing {
                    Thing::Guard(dir) => Some((pos, dir)),
                    _ => None,
                })
                .next()
        }
    
        fn path_len(&self) -> usize {
            let mut positions = HashSet::new();
            let mut next = self.guard_pos();
            while let Some((pos, dir)) = next {
                positions.insert(pos);
    
                next = self.neighbour(pos, dir).map(|npos| match self.grid[npos] {
                    Thing::Space | Thing::Guard(_) => (npos, dir),
                    Thing::Obstruction => (pos, dir.clockwise()),
                });
            }
            positions.len()
        }
    
        fn num_loops(&self) -> usize {
            (0..self.grid.len())
                .filter(|&pos| matches!(self.grid[pos], Thing::Space))
                .map(|pos| {
                    let mut grid = self.grid.clone();
                    grid[pos] = Thing::Obstruction;
                    LabMap {
                        grid,
                        width: self.width,
                        height: self.height,
                    }
                })
                .filter(LabMap::is_loop)
                .count()
        }
    
        fn is_loop(&self) -> bool {
            let mut positions = HashSet::new();
            let mut next = self.guard_pos();
            while let Some((pos, dir)) = next {
                let is_new = positions.insert((pos, dir));
                if !is_new {
                    return true;
                }
    
                next = self.neighbour(pos, dir).map(|npos| match self.grid[npos] {
                    Thing::Space | Thing::Guard(_) => (npos, dir),
                    Thing::Obstruction => (pos, dir.clockwise()),
                });
            }
            false
        }
    }
    
    fn part1(filepath: &str) -> Result<usize> {
        let input = fs::read_to_string(filepath)?;
        let map = LabMap::from_str(&input)?;
        Ok(map.path_len())
    }
    
    fn part2(filepath: &str) -> Result<usize> {
        let input = fs::read_to_string(filepath)?;
        let map = LabMap::from_str(&input)?;
        Ok(map.num_loops())
    }
    
    fn main() -> Result<()> {
        color_eyre::install()?;
    
        println!("Part 1: {}", part1("input.txt")?);
        println!("Part 2: {}", part2("input.txt")?);
        Ok(())
    }