main.rs (3796B)
1 use std::collections::{HashMap, HashSet, VecDeque};
2
3 #[derive(Debug, Clone, Copy, Eq, PartialEq)]
4 enum Pixel {
5 Dark,
6 Light,
7 }
8
9 impl Pixel {
10 fn new(c: char) -> Self {
11 match c {
12 '.' => Self::Dark,
13 '#' => Self::Light,
14 _ => unreachable!(),
15 }
16 }
17
18 fn to_digit(&self) -> usize {
19 match self {
20 Self::Dark => 0,
21 Self::Light => 1,
22 }
23 }
24 }
25
26 #[derive(Debug, Clone)]
27 struct Image {
28 pixels: HashMap<(i32, i32), Pixel>,
29 fill: Pixel,
30 }
31
32 fn main() {
33 let input = std::fs::read_to_string("input.txt")
34 .unwrap()
35 .trim()
36 .split('\n')
37 .map(|s| s.to_string())
38 .collect::<Vec<String>>();
39 let algo = input[0].chars().map(Pixel::new).collect::<Vec<_>>();
40 let image = {
41 let mut pixels = HashMap::new();
42 for y in 0..(input.len() - 2) {
43 for (x, c) in input[y + 2].chars().enumerate() {
44 pixels.insert((x as i32, y as i32), Pixel::new(c));
45 }
46 }
47 Image {
48 pixels,
49 fill: Pixel::Dark,
50 }
51 };
52 // 5065
53 println!("Part 1: {}", part_1(&algo, &image, 2));
54 // 14790
55 println!("Part 2: {}", part_1(&algo, &image, 50));
56 }
57
58 const DARK_KEY: usize = 0b000000000;
59 const LIGHT_KEY: usize = 0b111111111;
60
61 fn enhance(algo: &Vec<Pixel>, image: &Image) -> Image {
62 let enhanced_fill = match image.fill {
63 Pixel::Dark => algo[DARK_KEY],
64 Pixel::Light => algo[LIGHT_KEY],
65 };
66 let mut enhanced_pixels = HashMap::new();
67 let mut enhance_queue = image
68 .pixels
69 .keys()
70 .map(|&px| px)
71 .collect::<VecDeque<(i32, i32)>>();
72 loop {
73 let mut next_batch = HashSet::new();
74 // println!("{:?}", &enhance_queue);
75 while let Some((x, y)) = enhance_queue.pop_front() {
76 let mut boundary = Vec::new();
77 let mut key = 0;
78 for &(a, b) in [
79 (x - 1, y - 1),
80 (x, y - 1),
81 (x + 1, y - 1),
82 (x - 1, y),
83 (x, y),
84 (x + 1, y),
85 (x - 1, y + 1),
86 (x, y + 1),
87 (x + 1, y + 1),
88 ]
89 .iter()
90 {
91 key <<= 1;
92 key += if let Some(c) = image.pixels.get(&(a, b)) {
93 c.to_digit()
94 } else {
95 // track boundary as they may change
96 boundary.push((a, b));
97 image.fill.to_digit()
98 }
99 }
100 // only track if not a fill pixel
101 if key
102 != match image.fill {
103 Pixel::Dark => DARK_KEY,
104 Pixel::Light => LIGHT_KEY,
105 }
106 {
107 enhanced_pixels.insert((x, y), algo[key]);
108 for px in boundary.into_iter() {
109 next_batch.insert(px);
110 }
111 }
112 }
113 for px in next_batch.into_iter() {
114 if !enhanced_pixels.contains_key(&px) {
115 enhance_queue.push_back(px);
116 }
117 }
118 if enhance_queue.is_empty() {
119 break;
120 }
121 }
122 Image {
123 pixels: enhanced_pixels,
124 fill: enhanced_fill,
125 }
126 }
127
128 fn part_1(algo: &Vec<Pixel>, image: &Image, enhance_times: usize) -> usize {
129 let mut enhanced_image = image.clone();
130 for _ in 0..enhance_times {
131 enhanced_image = enhance(algo, &enhanced_image);
132 }
133
134 if let Pixel::Light = enhanced_image.fill {
135 panic!("There are infinitely many light pixels!");
136 }
137 enhanced_image
138 .pixels
139 .values()
140 .filter(|&&x| x == Pixel::Light)
141 .count()
142 }