Day 4: Ceres Search

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
    2
    ·
    edit-2
    14 days ago

    Rust

    I had a hunch about part two that didn’t pay off, so I over-coded this instead of just using an array of arrays.

    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 {
        fn all() -> &'static [Direction] {
            &[
                Direction::N,
                Direction::NE,
                Direction::E,
                Direction::SE,
                Direction::S,
                Direction::SW,
                Direction::W,
                Direction::NW,
            ]
        }
    }
    
    #[derive(Debug, PartialEq, Eq)]
    struct WordSearch {
        grid: Vec<char>,
        width: usize,
        height: usize,
    }
    
    impl FromStr for WordSearch {
        type Err = Report;
    
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let grid: Vec<_> = s.chars().filter(|&ch| ch != '\n').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 WordSearch {
        fn neighbour(&self, i: usize, dir: Direction) -> Option<usize> {
            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 % width != 0 => Some(i + width - 1),
                W if i % width != 0 => Some(i - 1),
                NW if i >= width && i % width != 0 => Some(i - width - 1),
                _ => None,
            }
        }
    
        fn word_count(&self, word: &str) -> Result<usize> {
            let mut found = 0;
            for i in 0..self.grid.len() {
                for dir in Direction::all() {
                    if self.word_present(word, i, *dir) {
                        found += 1;
                    }
                }
            }
            Ok(found)
        }
    
        fn x_count(&self) -> Result<usize> {
            let mut found = 0;
            for i in 0..self.grid.len() {
                if self.x_present(i) {
                    found += 1;
                }
            }
            Ok(found)
        }
    
        fn word_present(&self, word: &str, location: usize, dir: Direction) -> bool {
            let mut next = Some(location);
            for ch in word.chars() {
                let i = if let Some(i) = next {
                    i
                } else {
                    // Off the edge
                    return false;
                };
    
                if self.grid[i] != ch {
                    return false;
                }
                next = self.neighbour(i, dir);
            }
            true
        }
    
        fn x_present(&self, location: usize) -> bool {
            if self.grid.get(location) != Some(&'A') {
                return false;
            }
            let diags = [
                (Direction::NE, Direction::SW),
                (Direction::NW, Direction::SE),
            ];
            diags.iter().all(|(dir_a, dir_b)| {
                let Some(a_idx) = self.neighbour(location, *dir_a) else {
                    return false;
                };
                let Some(b_idx) = self.neighbour(location, *dir_b) else {
                    return false;
                };
                let a = self.grid[a_idx];
                let b = self.grid[b_idx];
                (a == 'M' && b == 'S') || (b == 'M' && a == 'S')
            })
        }
    }
    
    fn part1(filepath: &str) -> Result<usize> {
        let input = fs::read_to_string(filepath)?;
        let grid = WordSearch::from_str(&input)?;
        grid.word_count("XMAS")
    }
    
    fn part2(filepath: &str) -> Result<usize> {
        let input = fs::read_to_string(filepath)?;
        let grid = WordSearch::from_str(&input)?;
        grid.x_count()
    }
    
    fn main() -> Result<()> {
        color_eyre::install()?;
    
        println!("Part 1: {}", part1("d04/input.txt")?);
        println!("Part 2: {}", part2("d04/input.txt")?);
        Ok(())
    }