commit ec2e4a7e3c014e1529054f5734e64d0eb2d2240d
parent ce94f146f587858be68c1a1d60cbca8c552412c3
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Mon, 20 Dec 2021 19:55:43 -0600
Add 2021 day 20
Diffstat:
| A | 2021/day20/input.txt | | | 102 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day20/main.rs | | | 142 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 244 insertions(+), 0 deletions(-)
diff --git a/2021/day20/input.txt b/2021/day20/input.txt
@@ -0,0 +1,102 @@
+###.#....#.....##....#..#####.###..#...#.####....#..##.#.#...#..###.#####..####.#.#######.#.##..#.#..##.###...###....####.####..#.#.#...##..##.#..#####..###...###.....#..#.#..##....##..#...#.#........####...#.#...##....##..###.#.#..##.#.####..##........##.##.#.#.#.#.#.#...#...###.####.#.######..#.#.##....#.##.....##.#.#.#.##...#...#.#..#..##.#######.###............####...###.#..#.###.#...#.......#.##.##...##..####.##....#####....#..#...#.#.##.#......#####....#####..#..#.##...#.#....##.##..###....##.#....##.
+
+.......#............#.##...##..#...##.#..####.#..#.##..#.##.##..#.#....#.#####.#.##..#..#..##..#.###
+.#.####.......#....##....#####.##...######.###.##....####..####.#....#..####..#....#.##..##.##..##..
+.###.##.#.##.#......#...##.#.#.##..##..##....##...#####...#####..###......####...###.#.###.##.##.##.
+###.##.....###.##...###..#..##.#.#....####..###.###..###..###.#..#..#..##...#....##..#..####..#...#.
+..#######..#...##..####.#.#.#.##.#.##.######..#.##.#..####.#.##.####.#.#..##.#.....#.#...###.###....
+#.###.#....#.###..#.....##....#..##.....#####..###.#..#.####..#....#......#.#.##.#...#####..#.#.####
+.###.##.##.##..#...#.#.###.#.#####.########.....#####.#.......##...##....#.#.###...#..#...##.#.#.#..
+.###..###....###.###.###.##.###...##.##.....####.#.##.##..#####.#.#.##..##....##.#..#.#..#..#..#.#..
+###.#.....#.##.#..#...###.###..##..##...##..#.#.####.#.###.##.#.###..##..#.##.#.#.#..#####..#.#.#..#
+###.#....#.#...######.##..#.####..##.....#.###.....###...##....###.#######..#......#....####.#..#..#
+..#...#...#.##.#....###.#######....###..###.#####.###.#..#.....#.#.###.#...#.###..##.#.#.##.##.##...
+##...#.....##.#.##.##..#..#...#........##....#.#.#....#..##..####..#....#####.##.##..###.###.####.##
+.#.###.....#...##...#..#..###..#.##..#.##..##.#.##.#.##.#.###...####.#.#...##...####.#....#.#....#.#
+########.#.#.#.....##.##..###.#..#.#####.##.##.##.##.#..#..#.#.###.##########..##...#..###..#.##..#.
+......##.##..##.###.####...###.#..##.#.##.####.####...#######..#..#.###..##...###.###.#.#.#.######.#
+.###.####.#####.#.#.#...##.#.##....#..##.#####.####....#.....##.#.#..##....##..#.#.####...#.##...#.#
+##....######...#..##..#.#####.##.#####..#......#.#.#..#######.#...##.##..##..#..#.###.#.#......##.#.
+.##......#..#...#..##..#.#.###..##.#..###.###.##.##.#...#.#.##.#.###....#####....##...##...####.###.
+####.###....###..###.###......####.#..#####.#......##....#...##..#####....#.#######.##...##.##.##.##
+#....##.####....#####...##......####.#.#.#.##....#.###.#...##.##...#.#.##.#....#..#.##.#.#..#.#..##.
+#.##.#.##..##.#.##...#####.###.#..##.....###...#.##.###....#.###..###.####....###..##.###.#..######.
+..#...##...#...#...#..###..#..#.#......##.#...#...#..#.#..#..#.##.#####...#..##..###...#.###..#....#
+.##...#.#.....#.###...###....#####...##.#.###..##..###.#...######.#####.#..####.#....###.####..#...#
+#.##.##.#.#.#..#.#####.###.###.#.###..#.#.##..####.#.######.#.###.#.##...#..#..#..#.#.#..#.#.#..##..
+#####.####.##.#..##.......#....#...#.#.....#..#.#...#.......##.#######.#.##....#.....##...##...###.#
+##.#...#.#..####.##.###.####..###..###..#...#.######.##.##.#.#.#..###.#.##.#.#.#..#####..###.##....#
+.#.##.#.#......#......###.#.####..#.#..###....#####..###..#.######....##..##.##.##....#..#........#.
+.##.##..#####.....#.###.....#.##....#.....#.#.#..#..#######..#####.....##.###.###.##..##..###...##.#
+#..#.#.#.####..###.#.##.......#.#.#.#.##.#.#.#.#..##.##.##.......#.#.#..#..###...#.##.#.#..#....###.
+.#####.#.##.#..#.#...####...###.####.#.#.....####..#...#.###...#....#.#..####.####...#....#.##.###..
+.....##..#.##.#######....###...##...#.#.##.#..###....#.##..###....##..##.#.###.##..#####........#.##
+##.#.#.#########..##....#..#.##.#...#..#....##..#.###.#.#.#.###.#.....#......##.##....#.....#.#...##
+..##..#..#.##...#.....##.##....##.####....#...###..##...##.#......#...#.....#....##...###.###....#..
+##.#.##.....#.#.##..#......#...####....#.##.#.##..####.##.#.###.#...#..#..##..###..#.###.####.####.#
+.#.#..####.##.#.###..##.#.###..##.##..#...##..#..#.##..####..####..#...###.######....###.#..#####..#
+#.##..##.##...#....##...###..#.##...##....#.....#..##.#.###....#......##.##..###.#..######....##.#..
+#.####.....##.###.##...###.###.#....#.....####.#####......#.#......#..##...##.#....###.##.#....#..#.
+...###..###.#.#.###.#.#.##.####.#.######.#.##..#...#..##.#.#.#.#.............#..#.#.###.....##.###..
+#...###.#.##.####..##...###.##...####.##....######.....######.##.##.#..#.##.##.#......#.###.#.#...##
+####.#.########.##...##.############...###.##...#...######....##.########.##.##..#...##..#.#...##.##
+###.#..#..##.##....#..#..#..##.#.##.##.......##..#...#.###.#.#....##.#.#.##.#####.##.......#.#.#..##
+..#######.####.##...#####.#.####.#...#...#..#..##.###.#########....#..###.##..#.##..##.....###.#..#.
+###.#.#..#.#..###.#.#..#.##...##....#.#..#.......#.###.#.#.#.#####...#...######.##.#....##.#..#.#.#.
+.##....#.#.###...#.#...####..###.#.#.#..##.##.#..##...#...####..#......#####..####..##.##.##...##..#
+...##.##..#.#.....##...#..##.#.#.####..##.........##..##.....#.###.##...##.##..#..#...#..#......####
+......#..#####.....#....##..#####...#.#.##......##....####...#...####.###.#.#.##..#..#...##...###...
+...###....###.####.#....###......#.#...#.##.#..#######..#....#####.##.#####..###....##.##..##....#.#
+##...###.####..#...#.##....#..#.#.#..#.#....#.#...#.##..#..######.....##..#.#.######.#.#....##.#.#.#
+#..##...#..#.##.....####.##.##.#.#.##.#..##..##..#...#####.###.###........#.#.#..#.#.##.#...##..#.#.
+#####..##....#.#..##.#.##..#.###..##..#.#.###.####.#.#..#.....#..##.####..#.####.###..#.....##....##
+.##..###.#.#.#.#.####.#.##...###..#####.####.###.##.###.##.#....#.#.#..#.#.##.#..####...###.####.##.
+#.#.#......#.###.#...###..###...#...#.#..######.###.##.#.####.....#...##.#..##..##.#..##.#.#....#.##
+#...##...##.#...##....######.########....#..#######.#.####....#..##..##.##.#.###.####.####..###.####
+#.##..##...#.####.#.#..####.#.##.#.#...####...####.#.#....####..##...#......#........##........####.
+..##.#..######...#####.#.##.###.##.......#..###..###...#....#..####..#..#..#...##.#.##.####.#.##.#..
+#..#...###..#..#.#...###.#..#.#...#.....##..#.#...#####...##....##.......####.##..####..##.#..######
+.##.####..###..##.#.####.###.##...##..###.#.#.##...##.....#..#..#.####..###...##...#######.....##.#.
+.####.#.#.##...##...###.....####.##..####....##....#...##.##...##.####.###.##...#####..#...#.#...#..
+....#.#...#..#.#.#....####.##..#.#....#........#...####..###..###.###...#..###.#..#.##.#..#...#.####
+#..#..##..##.#...#####...#.......#..##..###.#.#.####..###.#...##......##.##.#..#.#.##.#..##.#.#...#.
+.#####...#.##.###.#.##..###.##.#.#...##..#.#...###.....##.#.##.#..#..####...#.######....#..#.##..#..
+#.#...#.....#.....######.##.##.##.##.#.#..#..#.#.####..#...#####.##.####..###.##.#.#.#.#..#.#...####
+##.##.#.#...##.#.###.#####.#...##.........#......#.##.....#.......##....#.#.##..#.#..#.#..##..#.###.
+....#.#.##.###.##..##.#..#.##.#..#.######.###.##..#..#.#...###.#........###.###.##..####.#...###..#.
+#####..####.#.###..#####...#.......#.##.#.....#.###.####.......##.#.#.##.#...#....#....#....##...##.
+.##.#..####...##...##.....##..#.####.#...#..##..#....####.#..#..#.#..#...#.#.#.##.####..######..#.#.
+#.#.##.##.#.....#...#..#...#.#.#..#.#.#####..#.##..#.##.#......##.#..#.#.#...#...####.#.#.#.#....#..
+.##..###.##..##...#..##...#..#......#.#####.####.####.#.......##.#.#..#..#.#.##.#..#..###.#.#..##..#
+#..##...#........##..#...###########.#.###...##.##...##.#.###...####..########..#...##..####..###...
+.#.#..###.#.##.#.#..#######......####.#....#####...##...#.###.##....#####.#...#######.######..######
+.#.###..###.##...#...###.########...#.#.#.#..#...#..#.#.....####..#...####......#.#...##.#.###..##.#
+#.###.###...#..#####.###.#...###..#..#..###.#..#..###.#..##.####..#####..#....#....##.##.#..#.####.#
+..#.###.#.#.#.#...####.#.##.#...#.##...#.###.##.#.#######.#####.##..####....###.###.##.#.##....##.##
+#..#.....#..#.##.#....#.####..#.##..####.#..#.#.###..##..#..#..##.####........#..#....#.#.#.###.##..
+#.##.#.#..##.#####...##.#...#..#...#.#.##.#..##.....##.##.#.#.#.###......#.###.###..###.###..#######
+##.###.###...#..##.....#######..##.#.##..#.#.....###.#....####.####.#..##.#..#..#..##.....#..###..##
+#....#..#.#.#..#.#....#.##.#.#.#.###.###.###.##..##.####..####.#.#....#.#######..###.#.....####.#..#
+###.....#.#####..###.#.#....#.....#.###....##..###.#..#.#.#...###.##....#....#..#......#..#....#..#.
+.#.#.#.#####........#.#######...#.####...#...#.###..#....#.#.###.##.....##.#.##..#.#.....#.#..##..##
+...###..#....#.###.#.#.#..##.##.....##.##...#.#........#.#.#####.#...####.#...##..##......#####.###.
+##.###..#.#...#......#######.#..##....###.#.##.#..###.#..###.#...#..######..........##.#.#.#..#..##.
+#..###.#...##..#######..#..#.###..#.###.##.######.##.###.##..#######.#..###.##.##...###....##..#.#.#
+#.#....#..#.###.#.##...#####.##....#...#.##.#..#.##..#...#...##.#..#..#.#.#..#####..##.###....#.#.##
+###...#.#.#..####.....##.#.##.##..#.####...###....###.#.##.########..#####.##.##.#..#....###..###.##
+##.###...#.#.#.#.##...##.#.##.#.#..#.#.#.###.##.#.##.##....########.#..#####..##.#.#.#..#####.#..###
+##..##.##.###.#######.##.......#.#.##.###..##...#...##...#####.#....#.#.#...#.#..#.#.#..####.###.#.#
+###..#.#..#..#..####.#.#.####..#....######...####..######.##.##..#####....####...##########..#####.#
+...#####.#.##....##.##....#...##...##.#.#.#.#.......#.##.#...####.##..####.....#...##..##.#...##...#
+#####.#.###..#..###.#..#..##..##.#.#.#.#..#...###...#.###.###.###..#.#.##.#####...#.#.##.#....#####.
+###.#..###.#.####.#.#..#.##.##.#.#.##......##.####..#...#....##..#....#.#..#..##...###...##.##.#.#..
+..#.#..#...##.#....###.##...#...##.##..###..#.#.#.......##.#.#..#.##.#......#.#..#..#...#...#.#.#.##
+#.#.#.#..###.##.#.#####.###.#.#..###....###...###....#.#..#.......##.#.###..##..#...###.#.##....#..#
+.#..##......#.#.....##.#...##....####....##.####..#....#...##.######.#..#.#.#....#.#######.....####.
+..#..###....##.##..##..#.#..####..##...#.####..........##.#.#.#..##..#..#.##....###.####.....#..##.#
+....#.#.....#.#..#....#..#.###.####..#..##.####....##....#.#..#.#.####.##.......##.##.###.#.##..#.#.
+..###.##....#.##......####..###..#..##.########.###.##...###.#.....#...###.#..#..#.#....#..#.######.
+.##.#.........#..#.#..#.#.##.####.#..##...#.###....#..#...##..##.#..#..####.#...#...####.....##...##
+##..#.#.##.##.#...######..##.##.#.#.#.###..#.#.#....###......##...#.#....#...##.########.##..####.##
+.#......##.###...##..##..###.####.#....##.#.#.#....##.#....##...######.....##..##....#.###..#..#.##.
+#...#...#.......#.#.#####.#..###..#..#...###...###..#.#.......###.#..##.#####...##.#####...#.#.####.
diff --git a/2021/day20/main.rs b/2021/day20/main.rs
@@ -0,0 +1,142 @@
+use std::collections::{HashMap, HashSet, VecDeque};
+
+#[derive(Debug, Clone, Copy, Eq, PartialEq)]
+enum Pixel {
+ Dark,
+ Light,
+}
+
+impl Pixel {
+ fn new(c: char) -> Self {
+ match c {
+ '.' => Self::Dark,
+ '#' => Self::Light,
+ _ => unreachable!(),
+ }
+ }
+
+ fn to_digit(&self) -> usize {
+ match self {
+ Self::Dark => 0,
+ Self::Light => 1,
+ }
+ }
+}
+
+#[derive(Debug, Clone)]
+struct Image {
+ pixels: HashMap<(i32, i32), Pixel>,
+ fill: Pixel,
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.to_string())
+ .collect::<Vec<String>>();
+ let algo = input[0].chars().map(Pixel::new).collect::<Vec<_>>();
+ let image = {
+ let mut pixels = HashMap::new();
+ for y in 0..(input.len() - 2) {
+ for (x, c) in input[y + 2].chars().enumerate() {
+ pixels.insert((x as i32, y as i32), Pixel::new(c));
+ }
+ }
+ Image {
+ pixels,
+ fill: Pixel::Dark,
+ }
+ };
+ // 5065
+ println!("Part 1: {}", part_1(&algo, &image, 2));
+ // 14790
+ println!("Part 2: {}", part_1(&algo, &image, 50));
+}
+
+const DARK_KEY: usize = 0b000000000;
+const LIGHT_KEY: usize = 0b111111111;
+
+fn enhance(algo: &Vec<Pixel>, image: &Image) -> Image {
+ let enhanced_fill = match image.fill {
+ Pixel::Dark => algo[DARK_KEY],
+ Pixel::Light => algo[LIGHT_KEY],
+ };
+ let mut enhanced_pixels = HashMap::new();
+ let mut enhance_queue = image
+ .pixels
+ .keys()
+ .map(|&px| px)
+ .collect::<VecDeque<(i32, i32)>>();
+ loop {
+ let mut next_batch = HashSet::new();
+ // println!("{:?}", &enhance_queue);
+ while let Some((x, y)) = enhance_queue.pop_front() {
+ let mut boundary = Vec::new();
+ let mut key = 0;
+ for &(a, b) in [
+ (x - 1, y - 1),
+ (x, y - 1),
+ (x + 1, y - 1),
+ (x - 1, y),
+ (x, y),
+ (x + 1, y),
+ (x - 1, y + 1),
+ (x, y + 1),
+ (x + 1, y + 1),
+ ]
+ .iter()
+ {
+ key <<= 1;
+ key += if let Some(c) = image.pixels.get(&(a, b)) {
+ c.to_digit()
+ } else {
+ // track boundary as they may change
+ boundary.push((a, b));
+ image.fill.to_digit()
+ }
+ }
+ // only track if not a fill pixel
+ if key
+ != match image.fill {
+ Pixel::Dark => DARK_KEY,
+ Pixel::Light => LIGHT_KEY,
+ }
+ {
+ enhanced_pixels.insert((x, y), algo[key]);
+ for px in boundary.into_iter() {
+ next_batch.insert(px);
+ }
+ }
+ }
+ for px in next_batch.into_iter() {
+ if !enhanced_pixels.contains_key(&px) {
+ enhance_queue.push_back(px);
+ }
+ }
+ if enhance_queue.is_empty() {
+ break;
+ }
+ }
+ Image {
+ pixels: enhanced_pixels,
+ fill: enhanced_fill,
+ }
+}
+
+fn part_1(algo: &Vec<Pixel>, image: &Image, enhance_times: usize) -> usize {
+ let mut enhanced_image = image.clone();
+ for _ in 0..enhance_times {
+ enhanced_image = enhance(algo, &enhanced_image);
+ }
+
+ if let Pixel::Light = enhanced_image.fill {
+ panic!("There are infinitely many light pixels!");
+ }
+ enhanced_image
+ .pixels
+ .values()
+ .filter(|&&x| x == Pixel::Light)
+ .count()
+}