From 0f3fe685ba8219795b4832daa880215bbbd5d904 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Fri, 13 Dec 2024 16:57:53 +0100 Subject: [PATCH] Day 12 --- src/day12.rs | 228 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/days.rs | 9 ++ src/main.rs | 4 +- 3 files changed, 239 insertions(+), 2 deletions(-) create mode 100644 src/day12.rs diff --git a/src/day12.rs b/src/day12.rs new file mode 100644 index 0000000..84081ea --- /dev/null +++ b/src/day12.rs @@ -0,0 +1,228 @@ +use std::io::BufRead; + +use nalgebra::DMatrix; +use rustc_hash::FxHashMap; + +type Garden = DMatrix; + +pub fn read(reader: &mut dyn BufRead) -> Garden { + let mut data: Vec = Vec::new(); + let mut nb_rows = 0; + for l in reader.lines() { + nb_rows += 1; + data.append(&mut l.unwrap().chars().collect::>()); + } + Garden::from_row_slice(nb_rows, data.len() / nb_rows, &data) +} + +#[derive(PartialEq, Eq, Hash)] +enum FencePosition { + Up, + Down, + Left, + Right, +} + +struct Fences { + horizontal: FxHashMap<(FencePosition, usize), Vec<(usize, usize)>>, // (j1, j2) indexed by i. + vertical: FxHashMap<(FencePosition, usize), Vec<(usize, usize)>>, // (i1, i2) indexed by j. + merge_fences: bool, +} + +impl Fences { + pub fn new(merge_fences: bool) -> Self { + Self { + horizontal: FxHashMap::default(), + vertical: FxHashMap::default(), + merge_fences, + } + } + + pub fn clear(&mut self) { + self.horizontal.clear(); + self.vertical.clear(); + } + + fn add_horizontal(&mut self, position: FencePosition, i: usize, j: usize) { + let fences = self.horizontal.entry((position, i)).or_default(); + if self.merge_fences { + match ( + fences.iter().position(|(_, j2)| *j2 == j), + fences.iter().position(|(j1, _)| *j1 == j + 1), + ) { + (Some(p_left), None) => fences[p_left].1 = j + 1, + (None, Some(p_right)) => fences[p_right].0 = j, + (Some(p_left), Some(p_right)) => { + fences[p_left].1 = fences[p_right].1; + fences.remove(p_right); + } + (None, None) => fences.push((j, j + 1)), + } + } else { + fences.push((j, j + 1)); + } + } + + fn add_vertical(&mut self, position: FencePosition, i: usize, j: usize) { + let fences = self.vertical.entry((position, j)).or_default(); + if self.merge_fences { + match ( + fences.iter().position(|(_, i2)| *i2 == i), + fences.iter().position(|(i1, _)| *i1 == i + 1), + ) { + (Some(p_above), None) => fences[p_above].1 = i + 1, + (None, Some(p_below)) => fences[p_below].0 = i, + (Some(p_above), Some(p_below)) => { + fences[p_above].1 = fences[p_below].1; + fences.remove(p_below); + } + (None, None) => fences.push((i, i + 1)), + } + } else { + fences.push((i, i + 1)) + } + } + + pub fn add(&mut self, position: FencePosition, i: usize, j: usize) { + match position { + FencePosition::Up => self.add_horizontal(position, i, j), + FencePosition::Down => self.add_horizontal(position, i + 1, j), + FencePosition::Left => self.add_vertical(position, i, j), + FencePosition::Right => self.add_vertical(position, i, j + 1), + } + } + + pub fn count(&self) -> usize { + self.horizontal.values().fold(0, |acc, f| acc + f.len()) + + self.vertical.values().fold(0, |acc, f| acc + f.len()) + } +} + +pub fn total_price(garden: &Garden, merge_fences: bool) -> usize { + let nrows = garden.nrows(); + let ncols = garden.ncols(); + let mut visited = DMatrix::::repeat(nrows, ncols, false); + let mut to_visit = Vec::new(); + let mut fences = Fences::new(merge_fences); + + let mut price = 0; + for j in 0..ncols { + for i in 0..nrows { + let region = garden[(i, j)]; + fences.clear(); + to_visit.clear(); + to_visit.push((i, j)); + let mut area = 0; + while let Some((i, j)) = to_visit.pop() { + if visited[(i, j)] { + continue; + } + visited[(i, j)] = true; + area += 1; + + for (position, i2, j2) in [ + (FencePosition::Up, i.wrapping_sub(1), j), + (FencePosition::Down, i + 1, j), + (FencePosition::Left, i, j.wrapping_sub(1)), + (FencePosition::Right, i, j + 1), + ] { + if i2 >= nrows || j2 >= ncols || garden[(i2, j2)] != region { + fences.add(position, i, j); + } else { + to_visit.push((i2, j2)); + } + } + } + + price += area * fences.count(); + } + } + price +} + +#[cfg(test)] +mod tests { + use super::*; + + static GARDEN_1: &str = "AAAA +BBCD +BBCC +EEEC"; + + static GARDEN_2: &str = "OOOOO +OXOXO +OOOOO +OXOXO +OOOOO"; + + static GARDEN_3: &str = "EEEEE +EXXXX +EEEEE +EXXXX +EEEEE"; + + static GARDEN_4: &str = "AAAAAA +AAABBA +AAABBA +ABBAAA +ABBAAA +AAAAAA"; + + static GARDEN_5: &str = "RRRRIICCFF +RRRRIICCCF +VVRRRCCFFF +VVRCCCJFFF +VVVVCJJCFE +VVIVCCJJEE +VVIIICJJEE +MIIIIIJJEE +MIIISIJEEE +MMMISSJEEE"; + + #[test] + fn part1() { + let garden1 = read(&mut GARDEN_1.as_bytes()); + assert_eq!(total_price(&garden1, false), 140); + + let garden2 = read(&mut GARDEN_2.as_bytes()); + assert_eq!(total_price(&garden2, false), 772); + + let garden3 = read(&mut GARDEN_3.as_bytes()); + assert_eq!(total_price(&garden3, false), 692); + + let garden4 = read(&mut GARDEN_4.as_bytes()); + assert_eq!(total_price(&garden4, false), 1184); + + let garden5 = read(&mut GARDEN_5.as_bytes()); + assert_eq!(total_price(&garden5, false), 1930); + } + + #[test] + fn part2() { + let garden1 = read(&mut GARDEN_1.as_bytes()); + assert_eq!(total_price(&garden1, true), 80); + + let garden2 = read(&mut GARDEN_2.as_bytes()); + assert_eq!(total_price(&garden2, true), 436); + + let garden3 = read(&mut GARDEN_3.as_bytes()); + assert_eq!(total_price(&garden3, true), 236); + + let garden4 = read(&mut GARDEN_4.as_bytes()); + assert_eq!(total_price(&garden4, true), 368); + + let garden5 = read(&mut GARDEN_5.as_bytes()); + assert_eq!(total_price(&garden5, true), 1206); + } + + static GARDEN_6: &str = "XXXXXX +XOOOOX +XOXXXX +XXXEEE"; + + #[test] + fn part2_b() { + let garden6 = read(&mut GARDEN_6.as_bytes()); + assert_eq!(total_price(&garden6, true), 234); + } +} diff --git a/src/days.rs b/src/days.rs index 40049bb..2851217 100644 --- a/src/days.rs +++ b/src/days.rs @@ -105,3 +105,12 @@ pub fn day11(reader: &mut dyn BufRead) -> String { stones_75.values().sum::() ) } + +pub fn day12(reader: &mut dyn BufRead) -> String { + let garden = day12::read(reader); + format!( + "part1: {}, part2: {}", + day12::total_price(&garden, false), + day12::total_price(&garden, true) + ) +} diff --git a/src/main.rs b/src/main.rs index 56d74f2..a081792 100644 --- a/src/main.rs +++ b/src/main.rs @@ -13,7 +13,7 @@ mod day08; mod day09; mod day10; mod day11; -// mod day12; +mod day12; // mod day13; // mod day14; // mod day15; @@ -44,7 +44,7 @@ fn main() { days::day09, days::day10, days::day11, - // days::day12, + days::day12, // days::day13, // days::day14, // days::day15, -- 2.45.2