Day 4: Printing Department

Rust

I pulled out some code from last year to make representing 2D grids as a vector easier, so this was quite straightforward. 2.5ms runtime (including reading/parsing the input twice cos of TDD).

impl Grid {
    fn neighbour(&self, i: usize, dir: Direction) -> Option<bool> {
        let width = self.width;
        let length = self.grid.len();

        use Direction::*;
        match dir {
            N if i >= width => Some(i - width),
            NE if i >= width && i % width != width - 1 => Some(i - width + 1),
            E if i % width != width - 1 => Some(i + 1),
            SE if i + width + 1 < length && i % width != width - 1 => Some(i + width + 1),
            S if i + width < length => Some(i + width),
            SW if i + width - 1 < length && !i.is_multiple_of(width) => Some(i + width - 1),
            W if !i.is_multiple_of(width) => Some(i - 1),
            NW if i >= width && !i.is_multiple_of(width) => Some(i - width - 1),
            _ => None,
        };
        .map(|i| self.grid[i])
    }

    #[rustfmt::skip]
    fn cell_accessible(&self, i: usize) -> bool {
        Direction::ALL
            .iter()
            .filter(|&&dir| self.neighbour(i, dir).unwrap_or(false))
            .count() < 4
    }

    fn num_accessible(&self) -> usize {
        self.grid
            .iter()
            .enumerate()
            .filter(|&(i, &is_occupied)| is_occupied && self.cell_accessible(i))
            .count()
    }

    fn remove_accessible(&mut self) -> Option<usize> {
        let removables = self
            .grid
            .iter()
            .enumerate()
            .filter_map(|(i, &is_occupied)| (is_occupied && self.cell_accessible(i)).then_some(i))
            .collect::<Vec<_>>();

        let count = removables.len();
        if count > 0 {
            for idx in removables {
                self.grid[idx] = false;
            }
            Some(count)
        } else {
            None
        }
    }

    fn remove_recursive(&mut self) -> usize {
        let mut total_removed = 0;
        while let Some(removed) = self.remove_accessible() {
            total_removed += removed;
        }
        total_removed
    }
}

::: spoiler Full code

use std::{fs, str::FromStr};

use color_eyre::eyre::{Report, Result};

#[derive(Debug, Copy, Clone)]
enum Direction {
    N, NE, E, SE, S, SW, W, NW,
}

impl Direction {
    const ALL: [Direction; 8] = [
        Direction::N,
        Direction::NE,
        Direction::E,
        Direction::SE,
        Direction::S,
        Direction::SW,
        Direction::W,
        Direction::NW,
    ];
}

#[derive(Debug, PartialEq, Eq, Clone)]
struct Grid {
    grid: Vec<bool>,
    width: usize,
    height: usize,
}

impl FromStr for Grid {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let grid: Vec<_> = s
            .chars()
            .filter_map(|ch| match ch {
                '.' => Some(false),
                '@' => Some(true),
                '\n' => None,
                _ => panic!("Invalid input"),
            })
            .collect();
        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 Grid {
    fn neighbour(&self, i: usize, dir: Direction) -> Option<bool> {
        let width = self.width;
        let length = self.grid.len();

        use Direction::*;
        match dir {
            N if i >= width => Some(i - width),
            NE if i >= width && i % width != width - 1 => Some(i - width + 1),
            E if i % width != width - 1 => Some(i + 1),
            SE if i + width + 1 < length && i % width != width - 1 => Some(i + width + 1),
            S if i + width < length => Some(i + width),
            SW if i + width - 1 < length && !i.is_multiple_of(width) => Some(i + width - 1),
            W if !i.is_multiple_of(width) => Some(i - 1),
            NW if i >= width && !i.is_multiple_of(width) => Some(i - width - 1),
            _ => None,
        };
        .map(|i| self.grid[i])
    }

    #[rustfmt::skip]
    fn cell_accessible(&self, i: usize) -> bool {
        Direction::ALL
            .iter()
            .filter(|&&dir| self.neighbour(i, dir).unwrap_or(false))
            .count() < 4
    }

    fn num_accessible(&self) -> usize {
        self.grid
            .iter()
            .enumerate()
            .filter(|&(i, &is_occupied)| is_occupied && self.cell_accessible(i))
            .count()
    }

    fn remove_accessible(&mut self) -> Option<usize> {
        let removables = self
            .grid
            .iter()
            .enumerate()
            .filter_map(|(i, &is_occupied)| (is_occupied && self.cell_accessible(i)).then_some(i))
            .collect::<Vec<_>>();

        let count = removables.len();
        if count > 0 {
            for idx in removables {
                self.grid[idx] = false;
            }
            Some(count)
        } else {
            None
        }
    }

    fn remove_recursive(&mut self) -> usize {
        let mut total_removed = 0;
        while let Some(removed) = self.remove_accessible() {
            total_removed += removed;
        }
        total_removed
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let grid = Grid::from_str(&input)?;
    Ok(grid.num_accessible())
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let mut grid = Grid::from_str(&input)?;
    Ok(grid.remove_recursive())
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d04/input.txt")?);
    println!("Part 2: {}", part2("d04/input.txt")?);
    Ok(())
}