diff options
-rw-r--r-- | input/day_11.txt | 140 | ||||
-rw-r--r-- | src/day_11.rs | 155 | ||||
-rw-r--r-- | src/lib.rs | 1 | ||||
-rw-r--r-- | src/main.rs | 3 |
4 files changed, 298 insertions, 1 deletions
diff --git a/input/day_11.txt b/input/day_11.txt new file mode 100644 index 0000000..8fbd6cf --- /dev/null +++ b/input/day_11.txt @@ -0,0 +1,140 @@ +..#............................#....................................................................................#..........#........#... +..........#.........................................#....................................................................................... +...................#..........................................................................#............................................. +.....................................................................................#.............................................#........ +.......#.......#.............#..........#......#...................#.....#.................................................................. +................................................................................#..................#..............#......................... +....................................#....................................................................................................... +...........#...................................................................................#......................................#..... +.......................................................................................................................#.........#.......... +.....................#.................................................#...................#.................#..............#............... +....#...........................................#...............#........................................................................... +.........................#.......................................................................#.......................................... +...................................#......................#.......................................................#.......................#. +..................#...........................................................#.......................#.................#...........#....... +..........#........................................................#..........................................#............................. +.............................................#.........#.....#.............................................................................. +.......................#.....................................................................#..............................#..........#.... +.............................#.......................................................#...........................#.......................... +..#...........#.......................#.....................................#............................................................... +...........................................................#.............................................#.................................. +......#..........................................................#......#........................................................#.......... +................................#.........#...........#....................................#........#...................#..................# +...........................#..................................................#..............................#.............................. +..............................................#.................................................#........................................... +.#.................................................................................................................#........................ +.......................................................................#.................................................................... +...............#.............................................................................................................#..........#... +.................................#.............................#............................................#............................... +.....#.................#...................#................................................................................................ +....................................................#...................................................#............#...................... +...........#.....#...................................................................#............................................#......... +..............................................#...........................................................................#................. +...#.........................#.....................................................................#........................................ +.........................................................#...................................#........................................#..... +.........#....................................................#........#................#.....................#............................. +........................#..........................................................................................#........................ +..............#...................................#............................#.............................................#.....#........ +.................................#................................................................#......................................... +..................#........................#...............#................................#.............#.............................#... +..........#........................................................#............................................................#........... +..#.....................................................................................#.............................#..................... +..........................#..........#..................................#......................................#...........#................ +................................................................#........................................................................... +................#................................#..........................#............................................................... +...........................................#..................................................#.....#.......#............................... +..........#............................................#.....................................................................#.............. +.......................#....................................#...........................................................#..............#.... +.....#.........................#........#..............................................#.................#........................#......... +.................#....................................................#............................................#........................ +....................................#...............#................................................#...................................... +.........................#........................................#................#.......#...................#............................ +....................................................................................................................................#....... +...........#...................................#...........................#......................#.........................#..............# +..................................#......#.................................................................................................. +......#....................#.........................#..................................................#................................... +......................#...................................#......#.....#.................................................#.................. +..............#..............................................................................#.................#.....................#...... +............................................................................................................................................ +#.............................#................#....................................................................#....................#.. +............................................................................................................................................ +........#...........................................#....................................................................................... +...................................................................#..........#..................#.......................................... +.....................#............#........#.............................................#............#................#.................... +................#............................................................................................................#.............. +...............................................................................................................#...................#........ +........................#......#..........................#.....#......#................................................................#... +................................................#..........................................#.............#.................................. +......................................#..............................................................................#...................... +..#.................................................................#.........#............................................................. +..........#.....#...............................................................................................#...........#............... +.................................#....................................................................#..............................#...... +.....................................................#........................................#........................#.................... +..........................................#..................#............#................................................................. +......................#...............................................................#..................#.........#............#........... +......#........................................................................#............................................................ +...................................#...................................#..................................................#................. +...................................................#.........................................#.................#............................ +...........................#...................................#.....................................................................#...... +........................................#................................................................................................... +................#......................................#........................#.........#.....#........................................... +...........#......................#.....................................................................#................................... +....#....................#...................#...................#................................................#...........#...........#. +............................................................................................................................................ +............................................................................................................................................ +.....................................#....................................#................................................................. +.......................#..................#........#............................#................#.............#............................ +...............#...............................................#......................#..............................................#...... +............................................................................................................................................ +.................................#...........#.....................#....................................................#................... +............................................................................................................................................ +..#........#..........#...............#..................................................................#..........#......................# +............................................................#............................#.................................................. +.................................................................#..........#.................................#.................#........... +.............................#......................#....................................................................................... +....#..................................................................................................................................#.... +...................#...............#..................................................#....................#................................ +.........................................................#......................................#...................#..............#........ +.....................................................................#...................................................#.................. +........................#...................................................................#..................#............................ +...#.....#...............................#....................#............................................................................. +................#...............#........................................................................................................... +.....................#........................................................#.....................................................#....... +..............................................#.......#................#...............................................#...................# +.........................................................................................#...............#...................#.............. +.#...........................#.......#...................................................................................................... +.............................................................................................................#........................#..... +.................................#.......................................................................................................... +...........#........................................................................................#.............................#......... +................#...............................................#............................#...................#.......................... +...#............................................................................#........................................................... +....................................................#.......#.......#......#...........................................................#.... +.........................#.................................................................................................................. +....................#...............#.........................................................................................#............. +.........................................................#....................#......................#...................................... +....#........................#...............#........................#...............#..................................................... +..........#......#....................................................................................................................#..... +..............................................................................................#...................#......................... +.......................................................#...................................................#.................#.............. +..........................#....................#............................................................................................ +........................................#......................#.........#...............#.......#......................#.........#.....#... +...............................#....................................#....................................................................... +........#...........#.............................#......................................................................................... +...#...........#...................................................................#..................#............#........................ +...........................#..............................#...................................#............................................. +...................................#.............................#..........................................#............................... +..............................................#........................#........#..........................................#................ +.......................................................................................#.............................#..............#....... +.........................................#.................................................................................................. +.....#............#......................................#.....#............................#............................................... +............................#............................................................................................................... +.......................#.........#........................................#..............................#...............................#.. +..#...........#.......................................#.........................#........................................................... +.......................................#.........................#.......................................................................... +............................................................#............................................................................... +.......#......................#........................................#................................................#..............#.... +..............................................................................................................#............................. +...............................................#.....................................................#...................................... +......................#..................................................................#......#.................................#.......#. +..#.......#................#......#..................................#.......#.....................................#........................ +................#...............................................#..................#....................#..................#................ diff --git a/src/day_11.rs b/src/day_11.rs new file mode 100644 index 0000000..54e02ca --- /dev/null +++ b/src/day_11.rs @@ -0,0 +1,155 @@ +use std::collections::{BTreeSet, HashMap}; + +use crate::{Problem, Solution}; + +pub struct Day11; + +impl Problem for Day11 { + const DAY: u8 = 11; + + const INPUT: &'static str = include_str!("../input/day_11.txt"); +} + +impl Solution for Day11 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { + solve(input, 2) + } + + fn part_2(input: &str) -> anyhow::Result<Self::Answer2> { + solve(input, 1000000) + } +} + +fn solve(input: &str, rate: usize) -> anyhow::Result<usize> { + let mut graph: Graph = input.parse()?; + + graph.expand(rate); + + let mut nodes = graph.into_nodes(); + + let mut edges = HashMap::new(); + while let Some(node) = nodes.pop_first() { + for other in nodes.iter() { + edges.insert((node, *other), node.dist(other)); + } + } + + Ok(edges.values().sum()) +} + +#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +struct Node { + id: usize, + row: usize, + col: usize, +} + +impl Node { + fn dist(&self, other: &Node) -> usize { + self.row.abs_diff(other.row) + self.col.abs_diff(other.col) + } +} + +#[derive(Debug, Default)] +struct Graph { + inner: Vec<Vec<bool>>, + row_values: Vec<usize>, + col_values: Vec<usize>, +} + +impl Graph { + fn rows(&self) -> usize { + self.inner.len() + } + + fn cols(&self) -> usize { + self.inner.first().map(|v| v.len()).unwrap_or_default() + } + + fn expand(&mut self, rate: usize) { + let mut rows = vec![false; self.rows()]; + let mut cols = vec![false; self.cols()]; + for row in 0..self.rows() { + for col in 0..self.cols() { + rows[row] = rows[row] || self.inner[row][col]; + cols[col] = cols[col] || self.inner[row][col]; + } + } + + self.row_values = rows + .iter() + .map(|not_expanded| (!not_expanded).then_some(rate - 1).unwrap_or_default()) + .collect(); + + self.col_values = cols + .iter() + .map(|not_expanded| (!not_expanded).then_some(rate - 1).unwrap_or_default()) + .collect(); + } + + fn into_nodes(self) -> BTreeSet<Node> { + let mut nodes = BTreeSet::new(); + let mut id = 0; + + for (row, v) in self.inner.into_iter().enumerate() { + for (col, value) in v.into_iter().enumerate() { + if value { + id += 1; + nodes.insert(Node { + id, + row: row + self.row_values[0..row].iter().sum::<usize>(), + col: col + self.col_values[0..col].iter().sum::<usize>(), + }); + } + } + } + + nodes + } +} + +impl std::str::FromStr for Graph { + type Err = std::convert::Infallible; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + Ok(Self { + inner: s + .lines() + .map(|s| s.chars().map(|c| c == '#').collect::<Vec<_>>()) + .collect::<Vec<_>>(), + ..Default::default() + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: &str = indoc::indoc! {" + ...#...... + .......#.. + #......... + .......... + ......#... + .#........ + .........# + .......... + .......#.. + #...#..... + "}; + + #[test] + fn test_part_1() -> anyhow::Result<()> { + Ok(assert_eq!(374, Day11::part_1(INPUT)?)) + } + + #[test] + fn test_part_2() -> anyhow::Result<()> { + Ok(assert_eq!(8410, solve(INPUT, 100)?)) + } +} @@ -16,6 +16,7 @@ pub mod day_07; pub mod day_08; pub mod day_09; pub mod day_10; +pub mod day_11; pub trait Problem { const DAY: u8; diff --git a/src/main.rs b/src/main.rs index ad87f73..ebc6a9e 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,6 +1,6 @@ use aoc_2023::{ day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, day_05::Day05, day_06::Day06, - day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, Solution, + day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, day_11::Day11, Solution, }; fn main() -> anyhow::Result<()> { @@ -14,6 +14,7 @@ fn main() -> anyhow::Result<()> { Day08::solve()?; Day09::solve()?; Day10::solve()?; + Day11::solve()?; Ok(()) } |