day 20

4 files changed, 238 insertions, 0 deletions

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<bool>,
+    map: Grid<bool>,
+    outer: bool,
+}
+
+impl Image {
+    fn new(algorithm: Vec<bool>, map: Grid<bool>) -> Self {
+        Self {
+            algorithm,
+            map,
+            outer: false,
+        }
+    }
+
+    fn enhance(&mut self) {
+        let mut new_map: Grid<bool> = 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<usize>, Option<usize>)] = &[
+                    (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<Image> {
+    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<i64> {
+    for _ in 0..2 {
+        image.enhance();
+    }
+    Ok(image.count_true())
+}
+
+pub fn part2(mut image: Image) -> anyhow::Result<i64> {
+    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<i64> {
@@ -78,6 +80,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> {
         (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<usize> for Row {
+    type Output = Self;
+    fn add(self, other: usize) -> Self::Output {
+        Self(self.0 + other)
+    }
+}
+
+impl std::ops::Add<Row> for usize {
+    type Output = Row;
+    fn add(self, other: Row) -> Self::Output {
+        Row(self + other.0)
+    }
+}
+
+impl std::ops::Add<usize> for Col {
+    type Output = Self;
+    fn add(self, other: usize) -> Self::Output {
+        Self(self.0 + other)
+    }
+}
+
+impl std::ops::Add<Col> for usize {
+    type Output = Col;
+    fn add(self, other: Col) -> Self::Output {
+        Col(self + other.0)
+    }
+}
+
 #[derive(Default, Clone)]
 pub struct GridRow<T: Default + Clone> {
     cells: Vec<T>,
@@ -12,6 +40,10 @@ impl<T: Default + Clone> GridRow<T> {
     pub fn iter(&self) -> impl Iterator<Item = &T> + Clone {
         self.cells.iter()
     }
+
+    pub fn get(&self, col: Col) -> Option<&T> {
+        self.cells.get(col.0)
+    }
 }
 
 impl<T: Default + Clone> std::ops::Index<Col> for GridRow<T> {
@@ -50,6 +82,10 @@ impl<T: Default + Clone> Grid<T> {
         Col(self.rows[0].cells.len())
     }
 
+    pub fn get(&self, row: Row) -> Option<&GridRow<T>> {
+        self.rows.get(row.0)
+    }
+
     pub fn cells(&self) -> impl Iterator<Item = &T> {
         self.rows.iter().flat_map(|row| row.cells.iter())
     }