From 438e87ea9e746aa8a85c9c6243ea7f111f82292f Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Mon, 20 Dec 2021 13:26:14 -0500 Subject: day 20 --- data/2021/20.txt | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/2021/20/mod.rs | 96 +++++++++++++++++++++++++++++++++++++++++++++++++ src/2021/mod.rs | 4 +++ src/util/grid.rs | 36 +++++++++++++++++++ 4 files changed, 238 insertions(+) create mode 100644 data/2021/20.txt create mode 100644 src/2021/20/mod.rs diff --git a/data/2021/20.txt b/data/2021/20.txt new file mode 100644 index 0000000..a0ef982 --- /dev/null +++ b/data/2021/20.txt @@ -0,0 +1,102 @@ +#.#.##...###......#.##..#..##....#.#.##...#..###....##...#####.#...#.#.#...#..###..#...#......####..#.#..########.#.###......##.##...###.###..######.....####.#..#.#..##..###..####..#....####..######.###..###.........##.##.###......##...#####.######..#.....##..#..#...#.#...#..#..#.#..#..#.##..#####..##.###.####...#..#....##....####...#.#.#.#.#.###...##..#....##......####.##.###...#####..##..#.#...#..#.#..####.###..###..#..####....#.#.##.#..#...#.#...##...#..#.#.##...##..##.####..#...###.#...#####.######..... + +...#.#...####.##.####.#...#..##.###..##...###..#.#.#.#...##....#####..#...##.#.##.#.#.....###.#....# +.##.####......##.#.#..#.#.#.#.##....#..##...###.#..#..#.##...##.#..##.###.#......###....#..##.###..# +####.#.####...#.#.#.#....#...#.##..###.#####..#...#.#..#.#.#.####...##.##..#.#.#..##.########..###.. +.####......#.##.##.##.#.#.....##..#.##....#######.##..##.####.#..#.#.#.#.#.###.#..#......#.#.#..###. +..#.#.####..#.#.#....##....#...######..##......#.......###.#..###.#.#.#.#.###.##..#.####.....#.##.#. +.#..##..#####.....#....#.#.#..###..#.###.#.###.##..##.#.###...#.##....##...#.###.#.##....#...###..## +.#.##.####.##.##..#..#.##..##.##..##..#.##..#.######..####.##.#.##....##..#.##.####.##...####....##. +##..#.#####.#.#.#..#...#...#.....##.#...#.##.#.#.#.#.....##...#.#.....##..##..###.#.####..#...##...# +##..#.#.##.####....##.#.#..#.#.#.###.#.#..#.#.....#..##.##.#.#...##....##.########.#..#.....##...### +######......#..#.#.####.#.###.#################.##..#.###.##.#...#..###.##..##..##..#..#.##..#.##.## +...##.#.###.........#...#...##.###...######..#.#...#........##.#...###.###.###...#...#.......#####.# +.#....##...##.#.#.##.#..########.#..#..#..#.##.##..###.##.#..##.#.#.#....#..##...###..###.##.#.##.## +.##.......##.#.#...#.##.##..#.#...#..####.#....###..#.#.....#.###....#...#.##.....#..#...##.##...### +..###.#..##..#....#...#.#.##.##.#.#.#.##.###.#####..###....#......##.....##..#..####.#....#####.#... +#...#.##.#.#.#...#####.#..##.######......##.#.#.#..#..#.##.######..#.##...##.##.##..#.#....##.###..# +##.##.##..#.##.########.##..##.##..####..#...####.######.####..####.#.#.#.#..#.##....#.##.#..#..###. +#..#####.##..#.###.#.##.##.###....###.#..#.####..##...#...###.#..#.....##...#..####.#...###.#.####.. +....#.#####..##.###..#..#.....##..##.#...#.#..##.##.#.##..##....#.##..##..###...##.#..#.#.###..#..#. +.#########..####.###...#.##.#.##..###....##.#..#...##....#.####.#..#.###.#.###....#......#...#.##.#. +.#######....####..##..#..#....#..#.####........#.##.#..##.######.#.###.###.###..##..####...##..#.##. +.#....###.####.###..#..##......##.##.##...#..##...##.####..##....######..####.#..##..#######.#.#...# +.#.####..########.#.#.######...##.###...#.....#...###....###..####.........#.###.#.....#.###.##..##. +...#.#.#..#.###..###.##.#.#.##...#..####.#..#.#...#....##.##.###.####.###...##..#.#......##..#...... +.#...######.#.##....##.##.##.....#...#.#.#######.#.#..###.#.#...##...#....#.#...#...#...##.###.###.. +.#...#..##.##.###.....##..#.###..####.##.########...#.##.....####...##...#.#..#....#...##.#.#..####. +..##...##.#..####...#.#...##.##..##..##..##..#..#...##..#..###.#..###..#..#....#..##....##...######. +##..###...##...##.#.#######..#.#.#..#...#.#..#..#....###..#.#####.##.#...##..#.....#..##.###..#.##.. +###.#.#..##.#.####..######....#.#.##....###.##.#.##..###.#.#...#..#####....#########...##..#....#.## +#..#####.....##.#.#.###.#.#.......####..#.##.#.####.#..#...#...#.#.###.######.##..##..#.......####.. +...#####..#.####.#..##.####.#####...#.#...#####.##.##..#..#...##.###..#.#.###.#....#..##..###.##.#.# +.##..#.##...##..#.#.##.#.#...#..####..#......##.###.#.##.#.#....####..#..#.####..###..#..#.#.###.#.# +#.#####..#.###.#.#.###.#.#...#.#....###.#..#.####...#####.#..##...##......###.##..#.###.#..####.#.#. +#..#......###...#.#...###....###.#####....#.#.###.##.#.#...##.....#.#####................#.###..#..# +#....##....#.#..####..#.##.####.###.###..####.##.....###.##.##...#..#...#.###...#####......#...#.... +##.#..#.##..##..##.#.#.#.#.##.######.#..#.#..###.#....#...#.#.#.#.....#....##..##....####..#.##..### +.##..#.#.####...##...#.######.....#.#...#####...##########.....##.###..#..######..#.#.....##..###..# +####..#.#...#...###.#####.##.#...#####..#.....#.#####.##..#.##.#.#.###.#...#.#.#####.......##.####.# +...###.##..###.#.#.#..##..#####......#####..#..##.##.....####..###...#...#####.....#.#....###...#.#. +..#..#.#.....##.#.#...#.......##.###.....###..#####.#####.#..###..###..#..#.#.#.#..###.#.###..#.#.## +####..#.##.##...#.#.#.##.#.#.#..#..#####..##.#.####.#..#######.####.#....#..###.##.#...##...###.#.#. +..#...#..#...#.####.##..##..#######.#.##.####.#..#......#.#.###.##.#..#.#.....##....#.#.#.#.##.###.# +.###..###.#...##..#....#.#..##..#.###.#...##.######.####.###.#..##..###.##.#.#....#.#...#...###.##.# +#....#.#....#..#####..##..#.##.#.#..##.##.#.....#.##..##..##........#.##...##.#.#..##.#.#..###....#. +##...#......#.#.#.#......#..#.#..#######...#.####..#...###..#...#..#...####..#.#.##....#...##..#.... +.####...##..###.##....#.#..#...#.##.#.##.#####.####.....#...#..#..#..##.#..####.#.#..###....##...#.# +#..####.#.#.######.####.#..#####..#.####...#.#.#.##..##..#.##.#.#.##.#..#..##.###.#.#..#.##..####.## +.#.###.....###....#...#..#.#####..#####..###..#..#...##...#.###..#..#.##..#..####..##..##########... +.#.....##..#.#.##...#...#.#.#.#.#..#.###...##.#.####.....#....#.....#.#.####..###.#######..#..##.#.. +....##...#...####..###.##.#.#.#...##.##...####..##..###..#.#.######.##.....#............#.######.#.. +..#....#....#..##.....#.#.##....###.##..###.#####...#....#.#.#....##.#.#.#.#.....#.#.....##...#.#.#. +.##...#.#.##.######..#.####..######.##.....##.##..##....#...#..##.#..#....#.##...#....#.##...##.#.## +#...#.#...##.#.##.##..#..####.#...###.#...##.##....#.#..##.......##....####...#...#.......#....####. +.#.##..###.##.##...##.#..##.###.#.#.#####.#.###...#.##....#...#..##..###..#..##.##.#..##.#.#....##.. +###.##.##..##.#.###.#...###.#..#.#.####..###.##.##..###.#####...##.....####.#.##.###..####.#..#.#.## +#....#.#.##...##.#...#......#####..###.#.##..#.####..##..#..##..###...###.#.#.##.##..####.###.....#. +#.##..#...#.#..##..##..#..###..##.#.###....#.#.####.##.##.###.#..#.##...#.###.##.#...#.#.##...#..... +#......#......#.#.#.######.##.#.###.###..#..####...##.#.######..#.....###..#.....#########.#####.##. +.#.#.#.##.#.###...#..#.##...#...##.#####.###..####.##..........####..#.#####.####..#.##.#####..###.. +...##.###.#.####.###.#.#.#.##...#####.#.......##.##...####.#..###....###.#..###..#.#####..#.###..#.. +#.#....#....###.###..##.##.##.##.#..###.##.....#.##.###...#.###....###.####...#.####...#.###.#.##### +##....#..#......##.###.....##.###.##..##.#.##...#..#.##.##.##..##.#...#...#...#.#.#.#.##.###.....### +.###..##.#....#..###..#.#.#..####.#.#.#.##.#...###.#.##....##..###.....#.##.....#......###.####..#.. +.....##.#...#####.#..###....#.#.#.#..##.###.#########.#.##..##.#.#.####..##..##..##.#..#.....#.#.#.. +#.####.#....##..#########...#.####..#.......#....##.#...##.#.##.##...#.#.#...#..###.#.#..#####.##..# +..#####...#.#.###......#....#...###...##.##...##.#..##.#.#..##.##.###.#....##.##...#####.......####. +#..##.###.....#...#.#.###.####..###.#....#..#...###.##.....#.##..##..###..##.##.###..#.#..#..#...#.. +##.###.....##.....##.#######.#.##....###.####.....#..##.#.###.#.#......##..####.#.####.##.#.##...### +###..#..######..#.#.#...##..#.#...####...##........####....#...#..#########.#.###.##.##.#####...##.. +..#####.#.####...#.######.#..#.#.#.#....#...#.###...###.###..#...##..##..#####..#####.###..#.#.#.##. +##.#..###..###.#.......##..####..######.#..#.####.##....#####.#.#.###.#..###..########..####..#..#.. +##.#.####....#.#.##..#..#..######.#..##.#.##..###.#..#.#....#.##...#.##.####...####.....##.##.##..## +####..##....#..#.#.#.....#..#...#.#...#..###...##.#.###.#...#.##..##..###..###....#..########.#....# +##..#...#.#.....#####..##..##....#......##.#.#...#..#####....##..#.##.........#.#.##...#.#.#..#.#.#. +##...###..#.###...###.###.##...##.#.##...#...####..#.#.#.###...######......##..###.....#..#.##...#.# +#.#....#.####.##.#.#.#.##..#.##.......#..##..#..##.##.##.#..##..#.##.#.#####.......#####..#........# +.#.#..###..#....#.#.....#.##..#....#..##..##..##.#....###..#.######.#.#...#..###......####....####.. +.#...###.....#...#....#.##.##.#........####.####..#....#..#....#.#.#..#.#.##.#.######.#...###.##.### +...#.#.#..##.#..#.##.#.#.##.##...##....###.....#####...#.#..#.##.#.####..##..#..#....#.##.##.##..##. +####....###..#..####.##.#..##.#..##.#.......###..#.##....#..#####.##..##.#...####..#.#..#.#.####...# +.#..###....#..#####.##..##...#.#...#.##.#..#....#.#.##.#.#.......#.#....#...#....#...#...#..##.#.... +#.#...####.#.##..###..#.##.##.#.##.#..##.#.##.###..#.###.#..##.#..#..#.#.####.#.###.##..#..#....##.. +.....#...#.####.#..##..#######.#.#.#...#.#####.#.#...#...####.....###.###.##..##..#..#..#.#..######. +#..#.#.####..###.###..#.##...##..###.##.###..#.####.#####.....###..###..#.#...#.#.########.#.##..##. +####..###..#...###.#.##.#.###..#.#...##.##....#####......###..##....###..#.#.#..##..######..####.#.. +...#....##.###..#.##.##..##..#.#.##.##...######....#....##.#.#.#.##.#...####...##...#.####.#.#.##.#. +...##...#.##..###.###...#.#.#.#.##.####...#.###..####..#...###.....#....####..##.#..##......#..#.#.. +.#.#..#.....#.#.###....#.###.#..#..###...#.#####....#.....###.#..###.##.#..#...#.####..#.###.####... +.####..#..##....#.##.##.#...#.###....#....#.##..#...#...##...#...###....###.##.#..#.###.#.##.#..###. +##.###.#...#.....#.#.#......#.##..#.#.##.##...###...#.###.####..###..#..###.#..#.#...#...#......##.. +######...##.##..#...##.#.###.#.####.#.##.##...###.#.#.....###.##.##....##.##....##.##.#..##..#.##### +#...#..#...####.#.###.##...#...#..##.#..##.....##.#..#.#..#....##.##..##..#..#.###..###.#......#..## +.##.##.######..#.##....#...#.....#.#.###....######..#.#..##.###......##.#..#.#.####..#...###.###.#.# +..#.#...##.#.....######.....####...##.###.#..#..#..######....###.....##...###..#.#####.#..##.###.### +###........#.##..##.........#.##.....#..#.####.##...........###...#.#.###..###..#..###...#......#### +#...#.......#.##.#.#.##.#.#.##.#.#..#...##..#..#####.#.##.##.#####.####...#..##.#.###...#..##..##... +..#......#..#####.....#.##.....#..#..#####..#.....###..##.####.###...#####.#...##.#..#.......#.....# +###..#.#.###.#.#..##..##..##...#.#........#...#...#.#.#..#.##.##.....#.##.###############.##...#.#.. +.#.#....#..##.......#........#..#...#.#.##.#...##.#.#.#.#.#..##...#.####.##.#.#...#...##.##########. +.######.##.........#.########....#.######....##.##.#..####.###.##.#..##..##..####.#...#####...##.#.# +...#..#.#..#.#..#.#.#########.#..##.#.#.#.#.#########....#...####...#.#..#.......#.##....####....### diff --git a/src/2021/20/mod.rs b/src/2021/20/mod.rs new file mode 100644 index 0000000..a46acab --- /dev/null +++ b/src/2021/20/mod.rs @@ -0,0 +1,96 @@ +use crate::util::grid::*; + +pub struct Image { + algorithm: Vec, + map: Grid, + outer: bool, +} + +impl Image { + fn new(algorithm: Vec, map: Grid) -> Self { + Self { + algorithm, + map, + outer: false, + } + } + + fn enhance(&mut self) { + let mut new_map: Grid = Grid::default(); + new_map.grow(self.map.rows() + 2, self.map.cols() + 2); + for row in 0..new_map.rows().0 { + for col in 0..new_map.cols().0 { + let neighbors: &[(Option, Option)] = &[ + (row.checked_sub(2), col.checked_sub(2)), + (row.checked_sub(2), col.checked_sub(1)), + (row.checked_sub(2), Some(col)), + (row.checked_sub(1), col.checked_sub(2)), + (row.checked_sub(1), col.checked_sub(1)), + (row.checked_sub(1), Some(col)), + (Some(row), col.checked_sub(2)), + (Some(row), col.checked_sub(1)), + (Some(row), Some(col)), + ]; + let neighbors = neighbors.iter().map(|neighbor| { + if let (Some(row), Some(col)) = neighbor { + self.map + .get(Row(*row)) + .and_then(|row| row.get(Col(*col)).copied()) + .unwrap_or(self.outer) + } else { + self.outer + } + }); + let mut idx = 0; + for neighbor in neighbors { + idx = idx * 2 + if neighbor { 1 } else { 0 }; + } + new_map[Row(row)][Col(col)] = self.algorithm[idx] + } + } + self.map = new_map; + if self.outer { + self.outer = self.algorithm[511]; + } else { + self.outer = self.algorithm[0]; + } + } + + fn count_true(&self) -> i64 { + if self.outer { + panic!("infinite"); + } + self.map.cells().filter(|c| **c).count().try_into().unwrap() + } +} + +pub fn parse(fh: std::fs::File) -> anyhow::Result { + let mut lines = crate::util::parse::lines(fh); + let algorithm = lines.next().unwrap(); + let algorithm: Vec<_> = algorithm + .as_bytes() + .iter() + .map(|b| match b { + b'#' => true, + b'.' => false, + _ => panic!("bad algorithm"), + }) + .collect(); + lines.next().unwrap(); + let map = crate::util::parse::bool_grid(lines, b'#', b'.'); + Ok(Image::new(algorithm, map)) +} + +pub fn part1(mut image: Image) -> anyhow::Result { + for _ in 0..2 { + image.enhance(); + } + Ok(image.count_true()) +} + +pub fn part2(mut image: Image) -> anyhow::Result { + for _ in 0..50 { + image.enhance(); + } + Ok(image.count_true()) +} diff --git a/src/2021/mod.rs b/src/2021/mod.rs index a5b6ab3..aee18bd 100644 --- a/src/2021/mod.rs +++ b/src/2021/mod.rs @@ -36,6 +36,8 @@ mod day17; mod day18; #[path = "19/mod.rs"] mod day19; +#[path = "20/mod.rs"] +mod day20; // NEXT MOD pub fn run(day: u8, puzzle: u8) -> anyhow::Result { @@ -78,6 +80,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result { (18, 2) => day18::part2(day18::parse(crate::util::data(2021, 18)?)?), (19, 1) => day19::part1(day19::parse(crate::util::data(2021, 19)?)?), (19, 2) => day19::part2(day19::parse(crate::util::data(2021, 19)?)?), + (20, 1) => day20::part1(day20::parse(crate::util::data(2021, 20)?)?), + (20, 2) => day20::part2(day20::parse(crate::util::data(2021, 20)?)?), // NEXT PART _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)), } diff --git a/src/util/grid.rs b/src/util/grid.rs index 47e10fb..c394008 100644 --- a/src/util/grid.rs +++ b/src/util/grid.rs @@ -3,6 +3,34 @@ pub struct Row(pub usize); #[derive(Copy, Clone, Hash, Eq, PartialEq)] pub struct Col(pub usize); +impl std::ops::Add for Row { + type Output = Self; + fn add(self, other: usize) -> Self::Output { + Self(self.0 + other) + } +} + +impl std::ops::Add for usize { + type Output = Row; + fn add(self, other: Row) -> Self::Output { + Row(self + other.0) + } +} + +impl std::ops::Add for Col { + type Output = Self; + fn add(self, other: usize) -> Self::Output { + Self(self.0 + other) + } +} + +impl std::ops::Add for usize { + type Output = Col; + fn add(self, other: Col) -> Self::Output { + Col(self + other.0) + } +} + #[derive(Default, Clone)] pub struct GridRow { cells: Vec, @@ -12,6 +40,10 @@ impl GridRow { pub fn iter(&self) -> impl Iterator + Clone { self.cells.iter() } + + pub fn get(&self, col: Col) -> Option<&T> { + self.cells.get(col.0) + } } impl std::ops::Index for GridRow { @@ -50,6 +82,10 @@ impl Grid { Col(self.rows[0].cells.len()) } + pub fn get(&self, row: Row) -> Option<&GridRow> { + self.rows.get(row.0) + } + pub fn cells(&self) -> impl Iterator { self.rows.iter().flat_map(|row| row.cells.iter()) } -- cgit v1.2.3-54-g00ecf