From ede035778a970fee998c22c3ccea2db762f6d3ea Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Sat, 24 Dec 2022 14:50:34 +0100 Subject: [PATCH] Day 18 part 2 --- src/day18.rs | 114 ++++++++++++++++++++++++++++++++++++++++++--------- src/days.rs | 7 +++- 2 files changed, 100 insertions(+), 21 deletions(-) diff --git a/src/day18.rs b/src/day18.rs index a75ddb7..9614166 100644 --- a/src/day18.rs +++ b/src/day18.rs @@ -4,6 +4,15 @@ pub struct Cube { z: i32, } +#[derive(Clone, Copy)] +pub enum Element { + Empty, + Obsidian, + Droplet, +} + +type Mat3D = Vec>>; + pub fn parse(input: &str) -> Vec { input .lines() @@ -22,8 +31,17 @@ pub fn parse(input: &str) -> Vec { .collect() } -pub fn surface(cubes: &[Cube]) -> i32 { - let mut matrix: Vec>> = Vec::new(); +static NEIGHBOURS: [(i32, i32, i32); 6] = [ + (1, 0, 0), + (-1, 0, 0), + (0, 1, 0), + (0, -1, 0), + (0, 0, 1), + (0, 0, -1), +]; + +pub fn surface(cubes: &[Cube]) -> (i32, Mat3D) { + let mut matrix: Mat3D = Vec::new(); for c in cubes { for _ in matrix.len()..=c.x as usize { @@ -33,24 +51,17 @@ pub fn surface(cubes: &[Cube]) -> i32 { matrix[c.x as usize].push(Vec::new()) } for _ in matrix[c.x as usize][c.y as usize].len()..=c.z as usize { - matrix[c.x as usize][c.y as usize].push(false) + matrix[c.x as usize][c.y as usize].push(Element::Empty) } - matrix[c.x as usize][c.y as usize][c.z as usize] = true; + matrix[c.x as usize][c.y as usize][c.z as usize] = Element::Obsidian; } let mut surface: i32 = 0; for x in 0..matrix.len() as i32 { for y in 0..matrix[x as usize].len() as i32 { for z in 0..matrix[x as usize][y as usize].len() as i32 { - if matrix[x as usize][y as usize][z as usize] { - for (dx, dy, dz) in [ - (1, 0, 0), - (-1, 0, 0), - (0, 1, 0), - (0, -1, 0), - (0, 0, 1), - (0, 0, -1), - ] { + if let Element::Obsidian = matrix[x as usize][y as usize][z as usize] { + for (dx, dy, dz) in NEIGHBOURS { let (x, y, z) = (x + dx, y + dy, z + dz); if x < 0 || x >= matrix.len() as i32 @@ -58,9 +69,9 @@ pub fn surface(cubes: &[Cube]) -> i32 { || y >= matrix[x as usize].len() as i32 || z < 0 || z >= matrix[x as usize][y as usize].len() as i32 - || !matrix[x as usize][y as usize][z as usize] + || matches!(matrix[x as usize][y as usize][z as usize], Element::Empty) { - surface = surface + 1; + surface += 1; } } } @@ -68,11 +79,69 @@ pub fn surface(cubes: &[Cube]) -> i32 { } } - surface + (surface, matrix) } -pub fn surface_without_trapped_air(cubes: &[Cube]) -> i32 { - 0 // TODO +enum FloodResult { + TouchingLimits, + InnerSurface(i32), +} + +fn flood(m: &mut Mat3D, x: i32, y: i32, z: i32) -> FloodResult { + let mut to_visit = vec![(x, y, z)]; + let mut surface = 0; + let mut touching_limits = false; + + while let Some((x, y, z)) = to_visit.pop() { + if let Element::Droplet = m[x as usize][y as usize][z as usize] { + continue; + } + + m[x as usize][y as usize][z as usize] = Element::Droplet; + for (dx, dy, dz) in NEIGHBOURS { + let (x, y, z) = (x + dx, y + dy, z + dz); + if x < 0 + || x >= m.len() as i32 + || y < 0 + || y >= m[x as usize].len() as i32 + || z < 0 + || z >= m[x as usize][y as usize].len() as i32 + { + touching_limits = true; + continue; + } + match m[x as usize][y as usize][z as usize] { + Element::Empty => to_visit.push((x, y, z)), + Element::Obsidian => surface += 1, + Element::Droplet => (), + } + } + } + + if touching_limits { + FloodResult::TouchingLimits + } else { + FloodResult::InnerSurface(surface) + } +} + +pub fn surface_without_trapped_air(outer_surface: i32, mut m: Mat3D) -> i32 { + let mut inner_surface = 0; + for x in 0..m.len() { + for y in 0..m[x].len() { + for z in 0..m[x][y].len() { + if let Element::Empty = m[x][y][z] { + if let FloodResult::InnerSurface(s) = + flood(&mut m, x as i32, y as i32, z as i32) + { + inner_surface += s; + } + } + } + } + } + + outer_surface - inner_surface } #[cfg(test)] @@ -96,9 +165,14 @@ mod tests { #[test] fn part1() { let cubes = parse(CUBES); - assert_eq!(surface(&cubes), 64); + let (surface, _) = surface(&cubes); + assert_eq!(surface, 64); } #[test] - fn part2() {} + fn part2() { + let cubes = parse(CUBES); + let (surface, obsidian) = surface(&cubes); + assert_eq!(surface_without_trapped_air(surface, obsidian), 58); + } } diff --git a/src/days.rs b/src/days.rs index 2dc6343..28f5a5a 100644 --- a/src/days.rs +++ b/src/days.rs @@ -181,5 +181,10 @@ pub fn day17() -> String { pub fn day18() -> String { let cubes = day18::parse(&fs::read_to_string("data/day18.input").unwrap()); - format!("part1: {}, part2: {}", day18::surface(&cubes), 0) + let (surface, obsidian) = day18::surface(&cubes); + format!( + "part1: {}, part2: {}", + surface, + day18::surface_without_trapped_air(surface, obsidian) + ) } -- 2.45.2