diff options
-rw-r--r-- | input/day_14.txt | 100 | ||||
-rw-r--r-- | src/day_14.rs | 138 | ||||
-rw-r--r-- | src/lib.rs | 1 | ||||
-rw-r--r-- | src/main.rs | 3 |
4 files changed, 241 insertions, 1 deletions
diff --git a/input/day_14.txt b/input/day_14.txt new file mode 100644 index 0000000..e301e58 --- /dev/null +++ b/input/day_14.txt @@ -0,0 +1,100 @@ +.O..OO#......O...O...#.O.#....O..#....O..O#..O##O#.....OO##.O.....#.....O.....O.####.##O##.O.O.#.O.O +.#O#OO.....#O.....#....OO####.OO..O....#.#....#......#O#.....O.O.......O...OO#...O.....#.#.O#..##.#. +#...O....OO.#...O.O..O..#...O....#...##......O..#...O.#O.O.....O.......O.O.#..##...#O..#..#.......#O +#.O.O.....#O##O.......O..O#O..........O##...#O.#.....O..O.##.#.#...#..#.#O..O.....O........O....#O.. +.....O....#O.........O....O.OOO.#.#...O###.#.#O..O...#.#.#....O...O.O..O.#O#.O.#.O....O#.#...OO#...# +O.O.O#.#....##O..#..O.OO.#....O#O.O..OOO..O#O......#...#.#..O......#......O.OOO##.......O#.O.#...... +O.......OO..O..O.O..OO...#OO.O#....O..##O.O.OO....O.O....#......O..O.OO.O....OO...OOO.OO.OO.#.O...OO +OOO..O.#.O.......O....O...O.#O.......O.O.......##.#..OOO#..#...#...O............O.O...O#.O...OO.#O## +.......##.O.O..#.#O..#O..O.##.#...........##.##O.O#.OO#..O......O..............#...O..O#...OO..O#..# +.....#.....#....O....O...#.....O#.O.#..O#O.O.O..#.#...O...O..OO...OO..........OO#...##...O..#.O..#O. +OO..#O.....O#..#..OO....O.OO..#....#.O.#.#.#....O.....O#O...............#.......O..O#O.....O#......# +.OO.....O#O...#...##.O.#.O....O...O.#.........O.#.......O.O..#O..#...O.OO..O#O.O#.........O.....O... +..O.......O#O.#O..O.#.....#.OO##OO...##...O.O..#..OO.....#.O.#OOO.O#O....OOOOO.O.O....OO#..#...OOOO. +...O..O....#.#..####..OO...O...#.O.O#O#O..#.....#.O#........OO.O##...#...O.O..O#O.O...#..O...#....O. +#..O...O#...O..O....#.....#OO..O..O...O#.#.OO.O.O....#.O..O....#O....O..OO.O#..O..#.O.O..OO.....#O.. +.#O.#.#...O#....O..##..OO..#.....#..O...O#O#O...##OO..#.O.O......O.#O.......OO..O#.O#O...O.......... +.O.O......#O.#OO.O.....#...........O....OO#O.O.....O...#..O...O...#......#.OO...#.#.#..O.#O......OO# +..#O..#.#.O...OOO.O.O..##..OO......O.O......O.##.....O......#OO...O.O.#.#..##.OOOOO.#.#.....OO..O... +....O..#.O.O...#..O#..#...............O...O..................#.O.#...#OOOOO#.......#.#...#.O.#..#.#O +..#.#O....#..#O.O#.....OO#.........O...O.O...#..O#.#..O.#..O#....#..O..O....#......O.O..O.#O.O.#..O# +...#.#O...#O..O#....O#.#......##OO#...O...O.....#.##..#......#O..#.O.......O....O..............#O.OO +.....O..#..#.......O#.O.O.#.O.#.....O#..#O#OO..##...#.##..........#OOOO..OO#..O...OO#...O.....##..O. +.##..O..O.O#.O........O.#.O..#O...O.....#............O.O.O.....#.......OO.#.##O........#.OO.##OO..#. +.#..O#O..###O#.#.OOO........#...#.O....OO...O..O##...#.#..#.O.......OO.#....O.#..#..###O.OOO..#...#. +......O...OO.#O.....O..O......OO..###..###...O..##..#.............O..OO#..#.....O..#...#.##..O#O..O. +......O.##O..O#..O..O....#..O#..#.....#O##...O..........O....O##...#...O..O....#.O.O..O..OO..O....O. +O#.#..O.OO.O...O..#OOOOO#.OOO..#O#O..OO.O#....OO..#.##.##..#.O#............O.....#..#..OO.O....#O.#. +..#.O.O.....O.O#..O.#.O#.O.#..O...O..........O#...O....#..O#.O#.OOO...OO..#O..#O.O..#.#O#OO.....O... +O..O#O.....#.#O.......#.#OO...O#...O..O.O..O..O.#.O##O.#.....O#.#O....##...##.O..O.O...............O +OO...##..O.#......O.....#O...OO.#.O.O....O.#.#.OO..OO.#....OOO...O..#....#.O..#....#O...#......#O.#. +..O##O..O.O.O##...O......#..O.O.O###.O..O...#O....O...........##.OO...O.#.###O#.#.O...##.O......#.O# +..OO...O.O#..O......OO....#..#...O.O..#.O....#O.#.O.#..OOO#..O.O.O.O##.O....OO.O..O.O###.#O.O...OO.O +...........OO.O.#...O..O#..OO.....O.O..O.#.#.OOO#.O..OO#.O....O..O..#.OO#O.#.##O.....#...#.......... +..O.#..OO.O.O#.....O.O.#.O##O#O.O.O#........#..O#.......O.O..#.##....OO..#.O...O..#.......O.OOOO...O +....O.#..OOO#..#.#..#.........#..#.#.O...OO..........O#O...O..OO..#.O..O.....O.....O....#..#.....O.. +OO#.#O..OO...O..O#....#O...O.##...##..#.#..#.O.##..#..#......O.#.O.O.##..OO........OO...O.OO#....O.. +O#.#......O.O..O#.#...OO#O......O#OO.OO.....O..O#.......#...O###..#..O#O..#........#O..OOOO#.O#..O#. +...O.###.#.........O....OO.O##...##....#.O#O........O........O...#.#........#O......O........O##O..O +....O.#.O#.#..O.......##.#.#..O.O.O.......#O..#.#O.O.#....O......O...O....#.....O...#O.....O.#.....O +#.....O.#...O.#..O##..O...##..O...#.....O...#....O##OO#O#...O.....#O..O..#...O.OO.O..O.....#.OO...O. +...O....O.#..O....O..#...##.....#....#.................#...O....O.O.OO##...O#......O.#.#.#.........O +.O.O..O...O..O#.O......#O.#O....#..OO.O.O..............#O....O....O....#..#.O.....#OO...O..#.O..O#.O +O.#.#..O.OO..O.....O#O.O.#..O..#..OO...OO.....O.........#O...........##.O.....#...O#O.#....OO.O.O.O# +.O.O.#OO#OO.O.OOOO.#...OO.OO.OO#O.O..O#...O....##.#..#....O.....#..#......O..O.....OO....O.O.O#.OO#. +..OO...#..#.O.OO..#......O#.#.O...O.OO..#O..O..#..O.##..O...##.O.....#.#.#.#..###O.......#..##..O.O# +...O...O.O...O#...#....O.OOO...OOOO.OO#....O#..O#.##...##O.O...#O.O......#....#O.O..O...#O..OO...OO. +.##...OO.##..O.........#.......#.#.....O.O.#....O.#....OO..##O..O#.....O#O....OO..O....O....O...O... +O........O##...#...#.O....O...#OOOO##..O...OO.....##......#..O.O#.O..O#O..#O...#.......#......O.OO.. +.OOO..#O.O#O.O..O...O..OO.O.....#...#.O#OOO..#.OOO.#...#....OO.OO.O.#...#.O....O.....#..O.O#.O...OO. +O.......#...OO..O.#..#O..#...OO.##O..#O.O...#.O..#..O#.....O..#...#OO...##..#............O.....O#... +#OO...OO.O.OO...#OO.#......O...#..#....O.#....#O.#O.#.O.##....O..O..O.#O.O.....#..........#....OO.O. +..O......O.#.O.OO...O.#...O.O#.##......OO.....#O.#...O.OO..#O..#...#..#.O......O#.#...O....O###O.O.. +.#...OO.#.#.O...#...O...O..#..#..#..#...OO...#.OO......O..O#..O.O.O.O...#.O...#.......OO.....OO...O. +O.O.O...O.O..O..O##......#...#...O..O.O..#.O.#...O...O.#....#...O.O.#.##O#..#..#....O#O.#O##.OO#.O.. +.#......O.....O.....#....#..O.....#.....#O..O#.........#OO#...O##.O.....O.#..OO.........O.....#..O.. +..O....##.O..O..O..#.O#...O......OO.OO....##..#..#...#.##O....O#..O.O....#.O##.....#O#...OO...#O.O.. +OO...#.O...O#..O..O.....O...#..O..#.#..OO#O.###.#...OO..#.....O....O#.O..#OO..##..#O..O.OO.....##.O. +.#.........#..#O......O..OO...#...O#..OO.O#....O#........OO.#......O..#..O##O.O.....OOO.OO.........O +#..OOO...O..OO#..O......#O......#..O.OOO#..OO...O.OOO##.O...O.O.O..#...O...#...#..O.OOOO..O..O...... +...#..#O....O.O#O.OOOO..O.O...#.O.#..OO....OOOO....O.O#...............O#......O.........#.#..O..O..# +..#.....OO..#.#.O#O..O.O#O...#.....O.#....#.O#O#..#.#.....##..O..O#.OO...OO....O.OO.O.O#O..###....O. +...O..O.......#.O.O......O........O......#...O....O....#O#.#.OO...#.#.O.O...##...#O.O...OO...O...... +###O.##..O##O...........#..##O.....OO..O..#.O....O................O....#.#O#.#.O...#.....O...O##O##. +.O.....O...O#O....OO#.O#...#......#...O...O..#.#........#.#.##.........O.##.O.OO#.#.#..#.....O#..... +OO...........#O.O#.O...#...OO....#.#....#O..OO...OO....O..#O..O.O....#.O.O....O....O#.##O..#O..O#O#O +..O##.....#.O.#...O##..O#.O.O.#O#..#O..O.OO#O..#..#...#..#....O.....#.....OOO.#.O....#.O#...#....O## +....O.O.#..O.##.#.O.#.O..O....O..O#.#..#...OO....OO#O#....###.#OO..#.....##.....#.###.O...#..O#O#... +.#...#...O.#OO...#O..O.##.#.O.......OO..#.O..#...#........O.O.......#..O.##...##........O...O...O.O. +...#...#O#.O#.......O..O...O#O...O#.OO.........O#.O...O..O....#O.O...#O.#OO...O..O....#O..O......#.. +....O.....O.....#...#O.O.#OO..#.OO#O...##..O#...##..........O..O.#..OOO#..O...#..#O.O......#OOO.O..O +.#.O..O.........OOO........#O.OOO.......O.O..O.#O......#..#O#...O...#O....O.##.O....#.OO...O.OO.#... +..#..#O..O#O....#..#.##O..#..O...#....#O........O.O.......O..OOOO#...#.O.O..O..O.#..#O.....#..O.O... +..#....O.......OO.....O......O.#O###.OOO.##OO.OO...#..O.OO.OO..#...O.......O.O.O..#O...#.#........O. +..#...O..#...O..#.##......OO.O..#..O.OOO.##O.OO.O..##.##.OO#.OO...#...#.....#O.O...O...O..#...#...OO +#....##OO..#.......O..O.OO.....OO..#...#.O##..O.O.......#.##.OO.O...#..#.#.O#..O.....##...##O...#.O# +O....O#....OO.......O.O......O.O.#O.O#...#.O#....O.O....#.#....#.#.##.O........#.#...O..O...O....O.O +.OO.O.OO......#....O#.O..#..O.#..#O....O..O#........O...#....O....#..#........O..O........O.O....#.. +...O..OO.O....O..OO#.O#O..OO#....O#.##...#.....O#..#O.#..#..#.#....O#.##...#...#O...###...###....... +..O.O#..#.OO.#..O........O..O#...O..#..O.OO...#O..##O...#.#....O.#..#......O.O..#O...#O.#...#O...OO. +..O...O#..O#.O.#O.OOO..#.#......OO#.#..#......#O.......O..O.#O....#.##......#....O#..###.O......O..O +...#.O....#O..##...#............O.O......##..O..#.O..#.O.O.O...OO.O#....O#OO.##O..#..O....#.O#..#... +#..#.#.#...OO....O.###.....O...O..O#.O...O.#....#O#...O...O..#..O........O..O..#.......O..O.....O.#. +#......#...O...O.........#..#O.....#..O..#.O...#O#.O#.#O#.#..O..O...#O.##..#O.....#.........#.#...OO +###OO.....O##.##.O.O.O..#.....O..#O.###.O.#..O...##O##...#O....#......#.O##...#.O...O#O#..#...O.#O.O +....O....#.OOO.#..O..#.O..O....O....#...O.............#O##OO...OO....#.OO...#OO......O..O..OO#.O...# +..O.#..##.....O.#O.#O.#...O#O.#O.O#OO#.O.O.#....##.O..#OOO....##OO.##..OO.O#..O....#.#......#......# +O...#..OO.O..O#.........O##..O....#....#OO#....#O....O..O..#..O...##.....#.....OO...#.O.#O...#.....# +OO.O.#...#.O#.O.O.....#..#...OO.##.O##.OO.....O...#..O.......OO#.O.......#OO.#O..#.O...........#.##. +.O...O##...O.O.OO......O#..O.###O...........O...#.O....OOO.#.....OOOO.#......O.....O..O.....#....... +.O..#O.OOO...#.O.#.O##....##.....#....#.O..#.O......O.....O...O..#O#..#O.#.O......O....O..#O.#...... +.#.O...#...O..#..#.....O..O.......#....O.#...O#.#OO..#.O#....O.O...#....O..#OO..#.......O.##...O..O. +#.OO.#...#....O#.....#...O.....#.#OO...#..O..OO.#......#.....#.O#...#.O.......#....O.#..#..O...O#..# +#...#O..##.#...#...O...##.#...#.#.#....##.O....O.O##..#O...#.OO...#O.....#O..#..#.O##...OO..O.#O..#. +#.#....O.......#...O....#......OO.#O..#O#..O.#....O.....#O.O.O..O.#..O.O......O...##..O..##.#....#.. +....#..#.O.#...O.O.O.#O..O......O.O.....#...O.#O..#....#.O.O.O......OO....##....#.O.O.O....O..#...O. +.OO....#.....O....##...O.......#...#.OO.O#....OO#.#OOO#.#O#...O.O#....O#..O..O.#O...##.....OO..O.... +O........#....#OOO...O..###..O...O.....O#...#.O.O..O.........OO....O..#O...OOO#.#.......O...#..O.#.. +.O#..OO.##.O.....O.....#..#..#OO...#.....#O.....#..O...O..OOO...O.#.#...O..O.....O.#O..OO.O##....OO. +O..O#..#...#.O...#O.........O.#.........O..#O......#..O.O.O.#..#O.##.#...#.......#...###O#..O...O... +##..O#.OO.#.O#O.O#......#.....O......O...OO....O..O..O....O..O.O.O.........O.#.O.....OO...##....#O.O diff --git a/src/day_14.rs b/src/day_14.rs new file mode 100644 index 0000000..27d9f63 --- /dev/null +++ b/src/day_14.rs @@ -0,0 +1,138 @@ +use std::collections::HashMap; + +use crate::{Problem, Solution}; + +pub struct Day14; + +impl Problem for Day14 { + const DAY: u8 = 14; + + const INPUT: &'static str = include_str!("../input/day_14.txt"); +} + +impl Solution for Day14 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { + let mut grid = input + .lines() + .map(|s| s.chars().collect::<Vec<_>>()) + .collect::<Vec<_>>(); + + print_grid(&grid); + + tilt_grid(&mut grid); + + print_grid(&grid); + + Ok(grid_load(grid)) + } + + fn part_2(input: &str) -> anyhow::Result<Self::Answer2> { + let grid = input + .lines() + .map(|s| s.chars().collect::<Vec<_>>()) + .collect::<Vec<_>>(); + + Ok(process_grid(grid, 1000000000)) + // 105606 == + } +} + +type Grid = Vec<Vec<char>>; + +fn process_grid(mut grid: Grid, count: usize) -> usize { + let mut cache = HashMap::new(); + for i in 0..=count { + for _ in 0..4 { + tilt_grid(&mut grid); + grid = rotate_grid(&grid); + } + + if let Some(cycle) = cache.insert(grid.clone(), i).map(|n| n + 1) { + println!("\rcycle found: {cycle} - {i}"); + return process_grid(grid, count % (i - cycle)); + } + } + + print_grid(&grid); + + grid_load(grid) +} + +fn print_grid(grid: &Grid) { + println!( + "{}\n", + grid.iter() + .map(|v| v.iter().collect::<String>()) + .collect::<Vec<_>>() + .join("\n") + ) +} + +fn tilt_grid(grid: &mut Grid) { + for col in 0..grid[0].len() { + for mut row in 0..grid.len() { + if grid[row][col] == 'O' { + grid[row][col] = '.'; + while row > 0 && grid[row - 1][col] == '.' { + row -= 1; + } + grid[row][col] = 'O'; + } + } + } +} + +fn rotate_grid(grid: &Grid) -> Vec<Vec<char>> { + let mut rot: Vec<Vec<char>> = vec![vec!['.'; grid.len()]; grid[0].len()]; + for (col, v) in rot.iter_mut().enumerate() { + for (row, c) in v.iter_mut().rev().enumerate() { + *c = grid[row][col]; + } + } + rot +} + +fn grid_load(grid: Grid) -> usize { + grid.iter() + .rev() + .enumerate() + .map(|(row, v)| { + v.iter() + .filter(|&&c| c == 'O') + .map(|_| row + 1) + .sum::<usize>() + }) + .sum() +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: &str = indoc::indoc! {" + O....#.... + O.OO#....# + .....##... + OO.#O....O + .O.....O#. + O.#..O.#.# + ..O..#O..O + .......O.. + #....###.. + #OO..#.... + "}; + + #[test] + fn test_part_1() -> anyhow::Result<()> { + Ok(assert_eq!(136, Day14::part_1(INPUT)?)) + } + + #[test] + fn test_part_2() -> anyhow::Result<()> { + Ok(assert_eq!(64, Day14::part_2(INPUT)?)) + } +} @@ -21,6 +21,7 @@ pub mod day_10; pub mod day_11; pub mod day_12; pub mod day_13; +pub mod day_14; pub trait Problem { const DAY: u8; diff --git a/src/main.rs b/src/main.rs index f7dd64e..dee8e7f 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,7 +1,7 @@ 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, day_11::Day11, day_12::Day12, - day_13::Day13, Solution, + day_13::Day13, day_14::Day14, Solution, }; fn main() -> anyhow::Result<()> { @@ -18,6 +18,7 @@ fn main() -> anyhow::Result<()> { Day11::solve()?; Day12::solve()?; Day13::solve()?; + Day14::solve()?; Ok(()) } |