From 4575bcbc1b563a2cb3b456e20d05ed3d4e96d08b Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Thu, 14 Dec 2023 01:13:26 -0500 Subject: day 14 --- benches/2023.rs | 5 ++ data/2023/14.txt | 100 +++++++++++++++++++++++++++++++ src/bin/2023/day14.rs | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2023/main.rs | 2 + 4 files changed, 267 insertions(+) create mode 100644 data/2023/14.txt create mode 100644 src/bin/2023/day14.rs diff --git a/benches/2023.rs b/benches/2023.rs index 211b2f4..9a96e8a 100644 --- a/benches/2023.rs +++ b/benches/2023.rs @@ -27,6 +27,8 @@ mod day11; mod day12; #[path = "../src/bin/2023/day13.rs"] mod day13; +#[path = "../src/bin/2023/day14.rs"] +mod day14; // NEXT MOD day!(2023, 1, day1); @@ -42,6 +44,7 @@ day!(2023, 10, day10); day!(2023, 11, day11); day!(2023, 12, day12); day!(2023, 13, day13); +day!(2023, 14, day14); // NEXT DAY fn bench_2023(c: &mut criterion::Criterion) { @@ -60,6 +63,7 @@ fn bench_2023(c: &mut criterion::Criterion) { day_combined!(2023, 11, day11); day_combined!(2023, 12, day12); day_combined!(2023, 13, day13); + day_combined!(2023, 14, day14); // NEXT DAY COMBINED }) }); @@ -81,5 +85,6 @@ criterion::criterion_main!( bench_2023day11, bench_2023day12, bench_2023day13, + bench_2023day14, // NEXT GROUP ); diff --git a/data/2023/14.txt b/data/2023/14.txt new file mode 100644 index 0000000..146bd48 --- /dev/null +++ b/data/2023/14.txt @@ -0,0 +1,100 @@ +O...#.O.OOO.OO.O.OOO...........OO#..##...#...#.O.#.O....#.##..#.#.OOO.O....#....O...O..OOOO.O#...... +O#OO....#O....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.....O.....O...O##. +..O...#OO..O....OO.....OOOO#O.OO..#.........O.O........O..#.........##...O.........O#..O.....#O.OO## +OO.O....#O#..O..#.OO....OO.#.OO...##.O..O..O....OO...O....#.....#..O#OO....#....O.....OO.#.O......OO +#....O...O#..O.O...O...#O#O.#....O.##..#..........OO.#....O#O#..O.OOO.O....O.O.O.O#.O..O..O....O..O. +#.O#..O......OO.#.......O......#.#.O..##..OO..##O.#.O.O#...#.....O.#.O.OO#.O.O#...O.O.#....#.#OOO... +#..O.O.O..O.#.#.#..O#OO.O.O...#.......#...#.#....O.....OO..#.....O....#O...#O..##.O.#....O.....O.O#. +.#O..#........OO.OOO..O...O.O..#O#OO.O.#..#..O.....O.OO..O..#...O......O.O##.O.OO.#..O........#..... +.O.O.O........O..#.O.##....#.#.#..OO..#....O.O.O.O.....#.#..O....OO..O#..O###.OO.OO....#..#..O.##O.. +O.O......#..##.O...#O.#OO.#..O..O...O.#OO...O..OO.O.O..OO....O.#.#.O#O#..O.#.#.OOOO..OO.O.O.O.O.#..O +O#.....#OO#....O..#..O##..OO.............#O#OO.##...O.......##......#O....O.#.O......##...........O. +...##.##..#O......#.......#.....#...#O.O.....#...O..O........O...OO.O..#....##....#O....#...O.O....# +..O.....OO.#..#O#.#OO..O.....O.......O.OOO#OOO.....O..O..O#...........##O..O.#...O.OOO..O.##O.#..#.O +.##...OOO.....#.O...#.O......#.O.O....O......#OOO...#..#.#.#.O...O.O.#.O.###.OO##O....O....#.##..#.. +O..#.#.........O#...O...O.##..#....O.#..#O...##.OOOO#O#.......#..#.........#OO.##..#......O.##...... +..#O...#......O.#.OO..#..O..O#....O.....#....O.#.#......####..##OO.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...OO..OO.##..#.#O....O.......OO...O.....#..O..#....O.#...#...OO. +OO...#..#.#..O.OO#O#..##...#...O..#...........O.O.OO.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....#OO#....#.###O#..OO..##..#..##.....O.O.O........O.O.O.O#...O..#O#..O........#.O###..O.#. +O.#...O.O.OO#..##....OO...O.....O.O.#O....#...#....##.#..#OO...O#O....O...O.#O....#..#...OO..O.#.... +..#...O......O#..O.#..#O#.#OO..#O.O..O..#...#........OOO#.OO.....O##O..#..OO.O##..O..#..O.O...O..O.. +...##.#O.###.###...O..#.#O..#..O....O.#O......O.#....O..OOO..O..O..#..O.#.#.....O.#.#...O#.O..O...OO +...O.#....#..O##..#....O..O...O....OO.#.O..#O....#.....#.#........O....O#O.O....O...#.O..#..O.O#OO.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.O...#.O..O.#..O#O...O.#......O.#O..#O#....O#..#....##.#.O.#..##.....#.#.#.....O.# +.O##..#.#O.OOO...O.O..OOO..O..#.O..#..#..OO#..OO...O..O..O.O#O.#.....#O.#.#...#O#.O.O.OO..O.......#. +O..O#.OO.#O..O.##..O..OO#.O.....O.O..##....#O...#..#.#O.#O.O#..O...O.#OO#O.O..#.......O.......O..... +..#.#.##O...#.O.O..O...OO.....O#.....O.#...#O.#O.#....##O.....OOO.O..OO....O.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...#.#OOO....OO.O.O#O##........#..O.O...O. +..OOO.O..O#..O#OO.#....O.............#....##.#O...O...O##.O..O..##.....O#....#O#...O.O#.O.#..OOO...# +.#.#..O.O.....#O#.....OO#..O.O..O.O............O..#.#.#.#......####.#O#..#..OO.O.OO#..O#.##....O#..O +........##O.#.......OO......O.OO.##..#..O......O#O...#...O.#......#OO..........O..OO...##..#..O.O.O. +..O#.O...#..O..O.##.....O..##....#...O..#.O..#..O.#.OO...###...#..O..O#..O.O..#.#....O#..#.#......O# +...#..#.#.#..#O..OO#..O.O#...........O.........#.O.OO..#.......O#....O.....#OO.....OO..OO...O.O.O.#. +...O#O......#...O...O..#.O.O#.#O.#....#.OO#.....O.O.#...O.#....O.#...#..O#..#..OOO.O..O.....O#....#O +..O..OO...O..#.#.O..#..#.O.#.O##O..OO..O........#....O##...#....#.#O.#..#......#....#.......O....... +#.........#.O#......OO............O.#......OO.O.#.OO.#..OO..O.##........#O#..OO.#...#.#.O.OO.#.O..#. +...O...#O...O....#..O#O#......#..OO#.O##OOO.#..#O.O#..O...O......O#......OOO..#...#O..OO#........... +.#.#..O#..O......#...O....OOO..#..........O....#..##..#...OO#...O.#.O.#.O......#....O##O..#OOO...... +...O.##...#..O.......#.#.O..O..#.O.....OOOOOOO...#.....O.....#.....O...OOO.##...O#.OO.OO.#...#O#O... +....#.O..#.O.O..O..O#..O.#.......#....#.#....O.....O#....O##O..O..##.O#..OOO#..O.......#.O..O#OO..O. +##.O.............#.#....O...O.......#O#.....OO#O......O..#.......#.#..#...#.......O.O..O....O.#....# +..O..#O..#...#.........O..#.....O.O.#.....O..#..#O....O..O.....##.#...O..O.#..OO#O#...####.O.......# +.O#.#O#..O#...#.O......OOO.O.#..O.O#.#....####......##.O.O.#...#..#O..O........O.....#........O..#.. +.O..O#....O.....O#.O.OOOO##.O..#OO.........##.O.##O...#O...#.O#OO##.....O....O###....###.#.........O +...O##O...O.O..........O#...O#.O...#O..O..##...O#.....O#.O....O...O#.##...#........OOO.O#....OO..### +O.O.O.....O.O..O....O#.OO.O.....O...#..#O#OO...OO..OO.O....#.O.OO....#..O.#O...O...#O#.O#...#.....OO +....#.....##.O#O..#O...OO...O#.#O..#.........OO..#......O..####OOO#...O#.............#.O....O.O..#OO +##O..O.O......O......OOOO..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.#.O.O##.....O#..........O..O.....O.#. +....#...O.#...#.#.#.#.O.....O.OO#..O...O#..OOO.OO..O.#.........O.......OO..O..#.#...........#....... +O##...#......#OO..O...O..#O.#OO.##.O.O....#.....O.O.....#O.#....#....O.#.OO..##............#O...O.#. +.OO..##....#.OOO...O.O....O..O.........##..O#.O.OO.....#..OO#....O.O#.#..O.OOO...#.....O#...O.O..O.O +O.O...OO#...O.....O..#.O.........O.O.#...OO....#..O.O..OOO.O..#.O.#.##O#.#OOO.#..#O..O............#. +#..O.O..OO.#O.....#.O.#..O.........#.OO..##.O....#O..OO.O.O.O#.O...OO...O..O.O.O.#..O.....#.O....... +O##..O...##....#O..........O..#..O..O.#.#..O..#.O....#OO......##OOO.##......##.....O.#.........#.... +..#.....#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.O..O..OO..##.........O..O +#...O..#O.O..#O..O...#.O.#......O#....#.....O.##..OOO.....O...O.OO#......O...O..O.###OO...#OO.O.OO.# +O#..O....#O.....O#....O..#.O.###..O.OO.#....#...#.O..#O...O.O..O.O........O..#O.O.O..OOO.O..OO..O.#O +#O#.O....#..#......#.#........O...#......#..#.O........O..O.....#............O#..#O#OO#....O.OOOO#.O +...OOO.O........#..O...........#..#O...#.#OOO#....OO.O....#...##.#...#O...#.....OO.#...O..##.O....O. +O.O......#..#.#...OO..##O#..#O.OOO##...O.#O.......O....OOOO.O..O....#.OO#.O...#..O..O.#....#...O..#O +...O..OOO.#OO..O..#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....#O.O.O##.#.... +...OO......O#...#.O.#....O.OO.O.##.O..O......#.O.O.O...#O.O.O.O.....##....#...##...#....#OO..#OO#.## +....O....##..##.#.OO....##.....#.....O.O..OO..O...##...#..O##.##......OO.O...OO...OOO..O...##.#.#.O. +#.....O..O.....#.......#.O...........OO..O..O..#......O#.#.OO....#........#..#O.#O#...#..#OOO......O +.O###OO.O##......OO...##O....#..#.....##..#.#OO....#.O.O...#......O....#..O.O..O#O#.###......O....#. +.O..#OO...O#O.....O...#O.O..O..O..##.O..O#.O#.OO..O..O#....O.O.O...OO#....O....O.OOO.O....O...#.##.. +.O........OO...#.OOO..O.#O.##..#..........O..........#.O...OO#.#..O.#O##O...#.....#O#.O#.......#.... +OO.O.......##..O#OO...#.#.#.#.O..O......#..#OO.#...O............#.#.#.##....O.O..#...OO#.##..#O..O.. +O..OO.....#..##.O.#O.....O.O.#...O#.#...#O.OO...O.O..#.##O..OO#..O...##..OO#..O##...O.....#.#..O#.OO +.O...#..#O#..OOO..O#.O#..#O...O.O#.....#...........O.##....O..O...#.OO............O.O#.....#O.O#..O. +..O.O.........#O...#...#..O#.#...#OO##..O#...#.OO#O....OO.O#O......OO...O#O.O....O#O..O#........O..O +#...O....OO.O#..#.#......#.....O#...O.#.O..O...#..O.O..O.O.#OO.O....#....#.......O......O...#.#..#.. +.O..OO.O.#O....##O#..O.#O.#.#..#....##.#O...#.O......#.OO#...#O...O.#...O.OO.#.O.#.O...O....#...#... +..OO......O.O....O#..O..##.###.....O.#..##.#.O......O...#...#..O...O.O.#....#.#...O.O.#........#.#.. +#...#..#.......#.O.O..#..OO..O.O..OOO.O..O..#......O..O..#OO##....O.#.#.O#O#..O#.##.O...#..#.O....#. +#.O#O.O.OOOO#...#..O#..#O#O..#....O...#.OO.#.###.O.......OO.O..O..OOO.#O.O.........#...#.O..O..O...# +.#.O..##..O...O....O......OO.............O.....OO#O..#.....#.OOO##O.OO........#..#.##..OO..........O +OOOOO....#O.O......O.#O#...#...#.#.#OO.O.#..O..##...##...O.....O...O...O##O..O.#O..O#.O...O.O...OOO. +.O..#..#.#..O.O.##O....#......O#.OOO..O....#O.#.###O.#.#.OO.O.#.OO.........#....#..OO.O.O.O##.#.##.. +#O...O..O..O.O.O..........#.#...#O.O......O.O#...OO...#..O..O.....OO...#....#.##......O.........OO.O +..O..##..O.....O.O.....O.O.....O.O...##...O.......#...OO...#..O...#OO.O..#OO..#...#....OO###.O.....O +#...O......#.OO.....O......###..#...#...#.#.....OO#.#.O#..#......O....O.O...#..O#O#..##....#...#.... +..O..#O...#.......O##..#.....O#..O#...OO.#..#.O.O..O..O#.#.OO.O.#..O..O..##...#.O....OO#O........... +.###.O.....#...#......#..#.....#..#....#..O.O....O.#..#..#O#.......#.O.O.....OO#.O...#OO.#..OO#..... +.#.....O...#O.........#....##.O......O.OO##...#.....#..#..O##.#...#..O..#O.O..#O...O..O.O...O.....O. +.#....##....O....O..OO....OO..#..#..OO...O..#.O.O..#..O###.O...#O.#.O.O.O.OO........###....OOO.....# +#.#..O..#.O#...#O.....#..O#.OO..O.#..OOO..O..#...O..O......O..#........#.#O#..O..O#OO.##.#.#.....#.O +......#.#.....O#....OO#...O#.#.O.O#.....O...##..###.....O#.....#..OO#.......OO....#...#.O......O.... +.........O.#........O...O#.#....O..#..O#OOO..#...O.O.....#.#OO.O.OO......#.....OO#O...O...#...#O..OO +..O#..OO.OO#..O##.O..O.##O....#..O##.......#..O........#.O......#....#O..OOO#..OO.O...#...##O.O...OO +..#.....OOO..O.#O#.O##..##..O#.##..OO...#..O..O..#.OOO...O..O.#..O#..#.OO#..O.OO...OOO..O...O..#.... diff --git a/src/bin/2023/day14.rs b/src/bin/2023/day14.rs new file mode 100644 index 0000000..76debd0 --- /dev/null +++ b/src/bin/2023/day14.rs @@ -0,0 +1,160 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash, Default)] +pub enum Cell { + #[default] + Floor, + Cube, + Round, +} + +impl std::fmt::Display for Cell { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!( + f, + "{}", + match self { + Self::Floor => '.', + Self::Cube => '#', + Self::Round => 'O', + } + ) + } +} + +impl TryFrom for Cell { + type Error = anyhow::Error; + + fn try_from(value: u8) -> std::result::Result { + Ok(match value { + b'.' => Self::Floor, + b'#' => Self::Cube, + b'O' => Self::Round, + _ => bail!("unknown tile {value}"), + }) + } +} + +fn tilt( + mut map: Grid, + roll: impl Fn(Row, Col, Row, Col) -> Option<(Row, Col)>, +) -> Grid { + loop { + let mut changed = false; + for row in map.each_row() { + for col in map.each_col() { + let Some((next_row, next_col)) = + roll(row, col, map.rows(), map.cols()) + else { + continue; + }; + if map[row][col] == Cell::Round + && map[next_row][next_col] == Cell::Floor + { + map[next_row][next_col] = Cell::Round; + map[row][col] = Cell::Floor; + changed = true; + } + } + } + if !changed { + break; + } + } + map +} + +fn north(row: Row, col: Col, _rows: Row, _cols: Col) -> Option<(Row, Col)> { + if row > Row(0) { + Some((row - 1, col)) + } else { + None + } +} + +fn west(row: Row, col: Col, _rows: Row, _cols: Col) -> Option<(Row, Col)> { + if col > Col(0) { + Some((row, col - 1)) + } else { + None + } +} + +fn south(row: Row, col: Col, rows: Row, _cols: Col) -> Option<(Row, Col)> { + if row < rows - 1 { + Some((row + 1, col)) + } else { + None + } +} + +fn east(row: Row, col: Col, _rows: Row, cols: Col) -> Option<(Row, Col)> { + if col < cols - 1 { + Some((row, col + 1)) + } else { + None + } +} + +fn weight(map: Grid) -> usize { + map.indexed_cells() + .map(|((row, col), cell)| { + if *cell == Cell::Round { + (map.rows() - row.0).0 + } else { + 0 + } + }) + .sum() +} + +pub fn parse(fh: File) -> Result> { + Ok(parse::grid(parse::raw_lines(fh), |c, _, _| { + c.try_into().unwrap() + })) +} + +pub fn part1(map: Grid) -> Result { + Ok(weight(tilt(map, north)).try_into().unwrap()) +} + +pub fn part2(mut map: Grid) -> Result { + let orig_map = map.clone(); + let mut seen = HashMap::new(); + let mut i = 0; + loop { + map = tilt(tilt(tilt(tilt(map, north), west), south), east); + let seen_times: &mut Vec<_> = seen.entry(map.clone()).or_default(); + seen_times.push(i); + if seen_times.len() > 1 { + break; + } + i += 1; + } + let found = seen + .into_iter() + .find_map(|(_, v)| if v.len() == 2 { Some(v) } else { None }) + .unwrap(); + let iterations = + found[0] + ((1_000_000_000 - found[0]) % (found[1] - found[0])); + map = orig_map; + for _ in 0..iterations { + map = tilt(tilt(tilt(tilt(map, north), west), south), east); + } + Ok(weight(map).try_into().unwrap()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2023, 14).unwrap()).unwrap()).unwrap(), + 109596 + ); + assert_eq!( + part2(parse(parse::data(2023, 14).unwrap()).unwrap()).unwrap(), + 96105 + ); +} diff --git a/src/bin/2023/main.rs b/src/bin/2023/main.rs index 2ee1dc4..af0836a 100644 --- a/src/bin/2023/main.rs +++ b/src/bin/2023/main.rs @@ -24,6 +24,7 @@ mod day10; mod day11; mod day12; mod day13; +mod day14; // NEXT MOD #[paw::main] @@ -43,6 +44,7 @@ fn main(opt: Opt) -> Result<()> { 11 => advent_of_code::day!(2023, opt.day, opt.puzzle, day11), 12 => advent_of_code::day!(2023, opt.day, opt.puzzle, day12), 13 => advent_of_code::day!(2023, opt.day, opt.puzzle, day13), + 14 => advent_of_code::day!(2023, opt.day, opt.puzzle, day14), // NEXT PART _ => panic!("unknown day {}", opt.day), } -- cgit v1.2.3-54-g00ecf