🌻 - 2024 DAY 12 SOLUTIONS -🌻 - eviltoast

Day 12: Garden Groups

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

  • cabhan@discuss.tchncs.de
    link
    fedilink
    arrow-up
    3
    ·
    17 days ago

    Rust

    I essentially used flood fill to collect each region. Part 1 was then relatively easy: for each point, check how many neighbors are outside of the region.

    Part 2 took me forever, and I ended up looking for hints online, where I discovered that an easy way to count the number of sides is to instead count the number of corners. Doing this for “normal” corners (e.g. in a square) was relatively easy, but “reverse corners” took me a long time. Corners like here what we see in the NE corner of the first C in the third row here:

    ....
    ..C.
    ..CC
    ...C
    

    I’m more or less happy with my solution, but my brain is now totally fried.

    https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day12.rs?ref_type=heads

    use std::collections::HashSet;
    
    use crate::grid::{Coordinate, Direction, Grid};
    use crate::solver::DaySolver;
    
    fn perimeter_score(c: Coordinate, grid: &MyGrid) -> usize {
        let plant_type = grid[c];
    
        Direction::orthogonal_iter()
            .map(|d| grid.neighbor_in_direction(c, d))
            .map(|c_opt| match c_opt {
                None => 1,
                Some(c) => if grid[c] == plant_type {
                    0
                } else {
                    1
                }
            })
            .sum()
    }
    
    type MyGrid = Grid<char>;
    
    struct Region {
        #[allow(dead_code)]
        plant_type: char,
        coordinates: HashSet<Coordinate>,
    }
    
    impl Region {
        fn new(plant_type: char, coordinates: HashSet<Coordinate>) -> Region {
            Region { plant_type, coordinates }
        }
    
        fn iter(&self) -> impl Iterator<Item = &Coordinate> {
            self.coordinates.iter()
        }
    
        fn part1_score(&self, grid: &MyGrid) -> usize {
            self.coordinates.len() * self.coordinates.iter().map(|c| perimeter_score(*c, grid)).sum::<usize>()
        }
    
        fn part2_score(&self, grid: &MyGrid) -> usize {
            let area = self.coordinates.len();
            let sides = self.number_of_corners(grid);
    
            area * sides
        }
    
        fn number_of_corners(&self, grid: &MyGrid) -> usize {
            self.coordinates.iter().cloned()
                .map(|coordinate| {
                    // How many corners do we have from here?
                    // println!("Checking {}", border_coordinate);
    
                    let corner_count = Direction::diagonal_iter()
                        .filter(|corner_direction| {
                            // Either:
                            // 1) Both neighbor directions are not 100% in the region
                            // 2) Both neighbors are in the region, but the corner itself isn't
    
                            let corner_in_region = match grid.neighbor_in_direction(coordinate, *corner_direction) {
                                None => false,
                                Some(c) => self.coordinates.contains(&c),
                            };
    
                            let both_neighbors_not_in_region = corner_direction.neighbor_directions().iter()
                                .all(|direction| match grid.neighbor_in_direction(coordinate, *direction) {
                                    None => true,
                                    Some(c) => !self.coordinates.contains(&c),
                                });
    
                            let both_neighbors_in_region = corner_direction.neighbor_directions().iter()
                                .all(|direction| match grid.neighbor_in_direction(coordinate, *direction) {
                                    None => false,
                                    Some(c) => self.coordinates.contains(&c),
                                });
    
                            both_neighbors_not_in_region || (both_neighbors_in_region && !corner_in_region)
                        })
                        .count();
                    // println!("Corner count = {}", corner_count);
                    corner_count
                })
                .sum()
        }
    }
    
    fn parse_input(input: String) -> MyGrid {
        input.lines()
            .map(|line| line.chars().collect())
            .collect::<Vec<Vec<char>>>()
            .into()
    }
    
    fn find_region_at(grid: &MyGrid, start: Coordinate) -> Region {
        let plant_type = grid[start];
        let mut coordinates = HashSet::new();
        let mut frontier = vec![start];
    
        while let Some(coordinate) = frontier.pop() {
            if grid[coordinate] == plant_type  && !coordinates.contains(&coordinate) {
                coordinates.insert(coordinate);
                frontier.extend(grid.orthogonal_neighbors_iter(coordinate));
            }
        }
    
        Region::new(plant_type, coordinates)
    }
    
    fn find_regions(grid: &MyGrid) -> Vec<Region> {
        let mut visited_coordinates: HashSet<Coordinate> = HashSet::new();
        let mut regions = vec![];
    
        for coordinate in grid.coordinates_iter() {
            if !visited_coordinates.contains(&coordinate) {
                let region = find_region_at(grid, coordinate);
                visited_coordinates.extend(region.iter().cloned());
                regions.push(region);
            }
        }
    
        regions
    }
    
    pub struct Day12Solver;
    
    impl DaySolver for Day12Solver {
        fn part1(&self, input: String) -> usize {
            let grid = parse_input(input);
            let regions = find_regions(&grid);
    
            regions.into_iter()
                .map(|region| region.part1_score(&grid))
                .sum()
        }
    
        fn part2(&self, input: String) -> usize {
            let grid = parse_input(input);
            let regions = find_regions(&grid);
    
            regions.into_iter()
                .map(|region| region.part2_score(&grid))
                .sum()
        }
    }
    
    • Quant@programming.dev
      link
      fedilink
      English
      arrow-up
      1
      ·
      12 days ago

      Counting the number of corners was a very useful hint for part 2. I had the most trouble with detecting the double corners, i.e. like in the example where the two B fields touch diagonally:

      AAAAAA
      AAABBA
      AAABBA
      ABBAAA
      ABBAAA
      AAAAAA
      

      Still, I would’ve taken a lot longer and probably made really-bad-performance-code without reading this :D