commit fa6cebf49b96da9abe265cd82edad874eb56c846
parent c0f55021a0fe9386bd827813a9181935c2293e63
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 15 Apr 2023 22:44:49 -0400
Add day 20 solution
Diffstat:
6 files changed, 365 insertions(+), 0 deletions(-)
diff --git a/src/20/Cargo.toml b/src/20/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day20"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/20/input b/src/20/input
@@ -0,0 +1,103 @@
+##...#####.###...##.##..###.#..####..#.####......#.#.##..#.###.##.#..#...##.#.##..######..##.#.##..#..##.......#.#.#.######......#.##...##.#.#...###...#.##.###.##.#.##.#..#.####.#.#.####.#..#.#.##.....#####.#..##......####...#..####..#.##.#.#...#.#.#.#...#..##.###..#..##.#...#.##.###..#######.#.###.###.###.#.#.###.#####...#.#.###.##...#..##.#.#..#...#####.....##..###.###..#.#.#.#...####.#...#.####.#.##.#.##...###.####.#.#.###..#...#.##.##.##..#...##.#....#####..#..#..#...#..#.#.#.#..####....#.#....#..###.#.
+
+.####..####.#.##..##..###...#.##.......##.##..####....##.##.#..##......####..#.#....###....#.....##.
+.##.###...###.#.#..#..#...###......##..####...#.###..##.###..##....#####.##..##..#####.#.#.....##.##
+...#.#.##...#.....#..##.#.##...#####..#.##.#.##...###.###......#...##...#.###...####..###..#.#####.#
+###.#.###.......#.#..##.#..##.##.###..#....#.#...#.#..##.#...##.#.#..#.####..###...####.#..#.#..#...
+##..##..####...######.####.####...#...##.......#...##..#####..#..#....###.#..#.#..#.##.#.##.##.#....
+#..######.#.....#...#...#...#.#.##.#..##.##.##.#.........##.###.##.#..###..#......#.#.#..#.##...#.#.
+#..#.######.####.###.#.##.####.#.#...####.#.###.######.##....#.#.....###..###.#.###.#...#######.###.
+#.###.#..........#..###..#.####.#.##.##.####.#...##.#####.#...##...#.###...#..#.##.##..#####.##..#.#
+.##..####.#..##..###...###.###.##.##...##...##...##.#......###.#..#.##.##...........#.#...##.##.#...
+...###....##.#....#...###...##.##.#...###..####...#.#...#.....###.#.##.####.##.#..#....#..#.####..#.
+.####.##.#..##..#..###.####..#####.#..##.####.#.####...##.##..##.#.###.###.#...##..##.#.##..#.##..#.
+..#..##..##...##..#.#.#.#.#####.#.##.#....#.######.##.....#.....##..#..##.##....##..#....######.#.##
+#.######.###.####.#####..#.#...###..###.###.#.##.#.##########........####...#.##......#..#...#.###..
+######...##..#.###.###.##.....#.###.##..#..##......#..#..#..#..##..#...#.#..#####..#....#.####..##..
+.#.......#.#.##..#.##.#...####.##.##..##.##.#.######.##..###.##.###....#.#.#.##.#...#.####.#.#.#.##.
+...#.#.#.###....###.#.#..###.#..#..#..#....##..##.#..##..#..#...#..#...#...####.#.#.#.###..#.#...#.#
+##.#..#..####.#..#...#.#.##...#.#..#...###..####.#.......##.######.##....##...#.#...##.#.##.#...#..#
+....##..#..##.....#.#.######.##.#.#.#.####.##.###.###.##.#.....#.##..###.##.##.#.#..#..##..##..#.#.#
+#.##.#.#.#..#.####.#####...#.##.#.##.###..###.#.##.....####.#..##.###....#...###.#.#.#.#.##.#.#..###
+###......###..####..###....#.#######.#.###.##.##..######..#.#..#####..####.....#.##...#..##..#.....#
+####..#..#...####..##..#####..###.##.#...#.##..#..###.#......#...####.#.#..##..#.##.##..####..#..#.#
+..##..###..#.##..###..#....##.#.....#.#.##.#..##...##.#.#.....#..##.......##..#...#.##.#.#.....#.#..
+#.#.#..##.##...##.###.#.##...###..##..###...#...#.#.#.#..##.#.#..#..#.#...###.#.#....#.#....###.####
+##..####...##..#.#..#....####.##...##.#..#..##.#.###.##..#..#..#...##.#.....##.###..#.##.###..#.#..#
+##..#.......##.#.#.##.######.#..##.###.###..##...##.#.#.#.###..###.##.##..#.#..#..##.#.##.##.....###
+##...#.##......##....#..#..#####...##.###.####.#.#.#.#...##..#####.....#...##.#.###..##.###...##...#
+#..##.#..#.##...##.#..#.###..#..##...#...#..#.##.#...####..##........##.....#.#####.#.##.###.#...##.
+.#.##....####.##..##.##..##.###.#..#.##..##..#.#...#.#.....#.#..####.###.##.####...#.#####.#....#...
+.#..#####.#..##..##..#..#..####.#.....#.#..##..##.#.#...##..##.#..#.##.#.##...##.#.#.#...#.#.#..##..
+#..........##..#..#...#.#.##.#...##..###..#...#.#...#.####.#.#..#..#.###.#.##...######..#..#..###..#
+..#.##.###.####...####..##...#..####.#.#.####.##.###.......#.#.#.##....#.##.##...##.#.#....##..#...#
+.##..#.###.#.#.#.#..#####..#..#.....####..#####.#######.......#.####.#.#...##..#..#...#........###..
+.#.#.#..#.#.###..##.##....#..#...#.#####.#.####...#.#...#.##...#.##....#..##.##.##..#.##..#.#..#..#.
+..##...##..###.....#.#......###.##.#.###.#.#.#......#..#..##..##..#...##.......####.#.#.#.#.#..#..##
+..#.#..#.#.##.##.##.....#..#####.#..####.##...#..##..#..###..##...###.#......#..##.#.......###.##.##
+.#...##....#....####.##.###.##.#.##..#..###.##...##..##..##..###.#..#....##...#####...####...#.#..##
+....####...#..#.#.#.###.##..#..#######.#..#..#.##..####.#...#..##..#.##.###.##.###...#...#...#######
+..####.##....###...#.....##.##...##......####..#.###...####....#.###...#.#.#######....##.##.#####...
+........#.########.#.#.###...#..##.#..##.###.##...#...#.###.##.#.....#...#.#.#.#####.###....####.#..
+...#....#...#.##.#....##.###..##.#.#...#.##..#...#..##........####.#.###.#...####.##..##...#.####...
+#.#.#..##.#.#...........#.#.#.##..#.#...####.#########...#.##.###.#.#####..###.#.#..#...#####.####..
+..##.####...##.##.#.###..##...#...####.##....#.##..####.#.##.#...#....#...#.##..##.##....#.#.....##.
+#.#.##.#.#####.###.##......###..#..#####.#...#####..###.###.#####.#..#####.#.##.#.#.#.....##.#.##..#
+#...#..###..#...#.#.###...#.###.##.#.###.###..##...##.#...##.#.###....##..#...##....#.....###..#.#.#
+...##.##.#.###.###......#.##.####.#...##.##.#.#..####..####.###.##....#..#...##....#..#.####.##..#.#
+##...#...##..#######.#.#..##.#..#...#.#.##.##.#.##...####...######.#######.#..###..#.#.##.#####..##.
+####..#####.####.#####..#..###..###...#.#..#..##.#..#.###.#.####..###..#....##....#####..###.#....#.
+.###..#.##...######..#######.##..#....#######...##.#..#.##.#.###..#.####....#...##..#...####....#.#.
+##....#.##.#.##.##.##.#.##..###.#.#...##..#..##..#.#######......#.###.#.#.#...#..##..##....#...##...
+.#.#.#..##.....########..###.##..#....#..#####.##...#...####.####.##..###..#....#.######.##.#..####.
+#.##.#.#...##.###.#.#.#.#.##....#...####..##...##....###.#....#...##.##..##...#.#.##....#.##..#..###
+.##.#...###.....#.#.#.##..#.#.......#....##.#.#.#..##.####.##..##.#.##.##.########.....#....###.##.#
+##..#..#.#.####.###.###...##...#...####.####..#...#....#..###...##.#.#...##...###.#.##.###.##.##.##.
+.#..####.##..#.#...##..####.#..##.#....##.####..#.#.#.#..#####....###..##.#..#.#..#..#.###.#....#.##
+##..####.#....##.###.#....#.....#..##..#.......#...##.###...#...####.#.###.#.####...###.#####.#..#.#
+###...#.##.###...###..#....#.#...#..##..##...###....#.##....#.#...##.##..##.#..#.#.##.#.........####
+##..#.#######.##..#..###.###..#.#.####...##..####....########.#.###.#....#####.....#.#....##..##...#
+##.####.....###...##.....##.#..######..##..##.##..##..#..##.##.#......##.#.##....#...#.....##...#...
+#.#.##.##.#.####...#.#..#.#...###.#####.#...##.##..#.##.#.#.#####.##..#.##..##.#..##..#.###.#...#.##
+#.###.#..###.#.##...#.....####.##.##..##..#....##.##......#.#.#..#####...##....#...#.####.#.##.##.##
+##..####....#####.##..##.#.#####.##.###.##..#.#####...#....#.###....##.#..#....#.##...#.#.##..#....#
+#..##.###.#.##..###.#...####..##.########.#.#......#.###.##...#.#.#..##....#.##....##..#.##..#.#.#.#
+#.#..#..#.####.#.##.#####.#..#.....#####..#..#..##.####.#.#..#..##.#.#.#..#.#....#.########.##......
+#...#.##.####..###.#....#.#...#..##.##.##..#...#...###.#########..##..#########..##.##########..##..
+#..##..#.#.##..........#....#.#..####.#.##.###.#.#####..##....#.......#..#..#.#.##.#.####.####.##..#
+##.#####...##.#######.#..#.###.###..####.#..##.###.#..##.##.##...###..###..##.#..###.###......####..
+###.#.#####.###..####...##..#.###.##...#####.#####..######...####.#..####.#..##.##.#.#.#.##.###.##.#
+.#..##.##....#..#..##.##.#.#.###..#.#.#.....####..###.#..#.#.#.##...#.#.##.#...##.#.##..####.#####..
+....###..##.#.###.#..#.##...##.##.#..###..#.#...#....##...########..####.###.#.##.#..##...#....#.###
+#.####..##..######.####....#.#.....#.#.#.....#....##.#......####..######..#..#..###..#..#.....##..#.
+.#..#..#...#.#...###.#..#####......#....#.#...#.####.....#..#..#.#.#...###.#.###.###.#######.#..#.#.
+###.#...#.##.#..##...#..#....##.##.#..###..#..#.###.#.....##..##..#.#####.#.#....#.#.#.#...#########
+##..#...#######.###.#.##.#.###.#..##.###...#.#..##.####....#####..######..##..#.#####.####.....#....
+#..##..##.#...#.#..#.#....##..#..#.##.#.....#.#...#.#.#####.....#...#.##..#.....#.###..#####...##.#.
+##...####.###.#.##.#....##.##....##..##.##....#....#.....##..##.###.##.##....#..#...###..##..#.#####
+##.#.##.##..#..#....#.#..#.######.#.###.#.##.#..#....##.#.#.##....#####.#...#.#####...#.#....###....
+###...#..##..##.#....##.##..#..#..####..#.##.#..####..####...#.#.###.#....###..##.#.##...####.###..#
+...#..##.#.##..###.##....#..#########...##.#####.#..##.#####.##.##..###.#.#.##.####.#....##.#.##.#.#
+..##..#.###.##.#....#.####....#.#......#####..######..##...#...#.##.##.##.#......#..#..#.###..#.##..
+#.#.....###.##.###.#.##.#.#..#...#..#.#.#.######.##..#.##.##.#.#.##..#.#.#.#....######....#.####.##.
+#.......###..######.....#..##.##...#####.#.##..#..##..##...##.#....#....####..#..##.#..###.#..##.#..
+..#.###.##.#.#.#.#..###...#.###.#.#.##....#..##..#...##...#.##...##.#..###.........###...#.#....#..#
+#.#..#..#.....###..#.##..#...#.....###..##..#..#..#..#.#.##.#.##..####..#....##..##.##.#.#.#.....###
+.##.#####..#.####....########.#.##.##.#..###..####..###.###.#...###.##.##.#########.###....#..#...##
+.###.#..#....#.#######.#....##.#.#..##.##.#####.##..#####..##.#.######.#..##....#...#....#...#####.#
+.##.#..##.#.##..###.##..##...#.#..####.##.###....##..##.#...#..#..#....########.###.##.#.#.##.#.###.
+.#..####..#.#####...#####..##...####..####......#..##.##.##.#..#.....##..#........##.##.#...##.#....
+###.#...#.....######..##.#..#....##.###..#...###.##.#..#...###.###...####.#..#......##.##.#..###..##
+..##.##.###...#..##..####.##..#.#.#..#..#####...#.#.#..##.#..#.#.###..##.###.#..##.##.##..##.##..###
+###..#....#.#.....##.##..####........##.###.#..#####....###..##.###.##.##..###...#.##.#.####.####.#.
+#.....#..#.###.#######.###.#..#.##.#.##.###.###.##.##.###....######.#...#...#....##.#..###..###.#..#
+.#.#.###.#.#..##...#.#.#..#...#.##..##.....###.###....##.#...#.#....#...###.#..#.##...#.#.#...##..##
+...#..###....###.###.#.#.#..#.#.###.#.###...#......#..#..#..#.#.#..#.####...##.......###.#..########
+#.###..#..###..#.#.#.####.#..##..#.####...#.##...###...#..#.##...#..##.#######...#.#.#.##..##.#.....
+#.#.#..#...#..#..#....##..###.##.##..#.##.#.###..##.#.##.##..#..........#..##..##..###..#......#.#..
+.##########.#.#.##.#.####.###.#.#...##..#..#.######.#...##.####..#..##...#.....##..###..##...#.#...#
+#..##.##.##.##.####..#.##...##..###.#.##.#.#..#.##..###..#..#...#.#.####.....#.##..#...##....##..##.
+.##.#....##..#.##...##.#.##.##....###.#.#####..##.....#.##..#.###.#....###.##...###.###.#....#..##.#
+..####..#..####.#...#.#.#..####.#...######.####.###.##....#.###.#.######.##.#..###..####......#..#..
+.###..##.###....###...##.##..####...##..##....#....#.#.##.#..###.#....##.##.#....##..#.#..#...#.####
+
diff --git a/src/20/part1 b/src/20/part1
@@ -0,0 +1,133 @@
+--- Day 20: Trench Map ---
+
+With the scanners fully deployed, you turn their attention to mapping the floor of the ocean trench.
+
+When you get back the image from the scanners, it seems to just be random noise. Perhaps you can
+combine an image enhancement algorithm and the input image (your puzzle input) to clean it up a
+little.
+
+For example:
+
+..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##
+#..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###
+.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#.
+.#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#.....
+.#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#..
+...####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.....
+..##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###
+
+The first section is the [1m[97mimage enhancement algorithm[0m. It is normally given on a single line, but it
+has been wrapped to multiple lines in this example for legibility. The second section is the
+[1m[97minput image[0m, a two-dimensional grid of [1m[97mlight pixels[0m (#) and [1m[97mdark pixels[0m (.).
+
+The image enhancement algorithm describes how to enhance an image by [1m[97msimultaneously[0m converting all
+pixels in the input image into an output image. Each pixel of the output image is determined by
+looking at a 3x3 square of pixels centered on the corresponding input image pixel. So, to determine
+the value of the pixel at (5,10) in the output image, nine pixels from the input image need to be
+considered: (4,9), (4,10), (4,11), (5,9), (5,10), (5,11), (6,9), (6,10), and (6,11). These nine
+input pixels are combined into a single binary number that is used as an index in the [1m[97mimage
+enhancement algorithm[0m string.
+
+For example, to determine the output pixel that corresponds to the very middle pixel of the input
+image, the nine pixels marked by [...] would need to be considered:
+
+# . . # .
+#[. . .].
+#[# . .]#
+.[. # .].
+. . # # #
+
+Starting from the top-left and reading across each row, these pixels are ..., then #.., then .#.;
+combining these forms ...#...#.. By turning dark pixels (.) into 0 and light pixels (#) into 1, the
+binary number 000100010 can be formed, which is 34 in decimal.
+
+The image enhancement algorithm string is exactly 512 characters long, enough to match every
+possible 9-bit binary number. The first few characters of the string (numbered starting from zero)
+are as follows:
+
+0 10 20 30 [1m[97m34[0m 40 50 60 70
+| | | | [1m[97m|[0m | | | |
+..#.#..#####.#.#.#.###.##.....###.[1m[97m#[0m#.#..###.####..#####..#....#..#..##..##
+
+In the middle of this first group of characters, the character at index 34 can be found: #. So, the
+output pixel in the center of the output image should be #, a [1m[97mlight pixel[0m.
+
+This process can then be repeated to calculate every pixel of the output image.
+
+Through advances in imaging technology, the images being operated on here are [1m[97minfinite[0m in size.
+[1m[97mEvery[0m pixel of the infinite output image needs to be calculated exactly based on the relevant pixels
+of the input image. The small input image you have is only a small region of the actual infinite
+input image; the rest of the input image consists of dark pixels (.). For the purposes of the
+example, to save on space, only a portion of the infinite-sized input and output images will be
+shown.
+
+The starting input image, therefore, looks something like this, with more dark pixels (.) extending
+forever in every direction not shown here:
+
+...............
+...............
+...............
+...............
+...............
+.....#..#......
+.....#.........
+.....##..#.....
+.......#.......
+.......###.....
+...............
+...............
+...............
+...............
+...............
+
+By applying the image enhancement algorithm to every pixel simultaneously, the following output
+image can be obtained:
+
+...............
+...............
+...............
+...............
+.....##.##.....
+....#..#.#.....
+....##.#..#....
+....####..#....
+.....#..##.....
+......##..#....
+.......#.#.....
+...............
+...............
+...............
+...............
+
+Through further advances in imaging technology, the above output image can also be used as an input
+image! This allows it to be enhanced [1m[97ma second time[0m:
+
+...............
+...............
+...............
+..........#....
+....#..#.#.....
+...#.#...###...
+...#...##.#....
+...#.....#.#...
+....#.#####....
+.....#.#####...
+......##.##....
+.......###.....
+...............
+...............
+...............
+
+Truly incredible - now the small details are really starting to come through. After enhancing the
+original input image twice, [1m[97m35[0m pixels are lit.
+
+Start with the original input image and apply the image enhancement algorithm twice, being careful
+to account for the infinite size of the images. [1m[97mHow many pixels are lit in the resulting image?[0m
+
+
diff --git a/src/20/part2 b/src/20/part2
@@ -0,0 +1,11 @@
+--- Part Two ---
+
+You still can't quite make out the details in the image. Maybe you just didn't enhance it enough.
+
+If you enhance the starting input image in the above example a total of [1m[97m50[0m times, [1m[97m3351[0m pixels are
+lit in the final output image.
+
+Start again with the original input image and apply the image enhancement algorithm 50 times.
+[1m[97mHow many pixels are lit in the resulting image?[0m
+
+
diff --git a/src/20/src/main.rs b/src/20/src/main.rs
@@ -0,0 +1,103 @@
+use std::collections::HashMap;
+
+#[derive(PartialEq,Eq,Hash)]
+struct Pos {
+ x: isize,
+ y: isize
+}
+
+fn parse_input(input: &str) -> (HashMap<Pos,bool>,Vec<bool>){
+ let mut lines = input.lines();
+ let lut: Vec<bool> = lines.next().unwrap().chars().map(|c| c == '#').collect();
+
+ let mut map: HashMap<Pos,bool> = HashMap::new();
+ let mut y: usize = 0;
+ for l in lines {
+ if l.is_empty() { continue; }
+ for (x,c) in l.chars().enumerate() {
+ map.insert(Pos { x: x as isize, y: y as isize }, c == '#');
+ }
+ y += 1;
+ }
+
+ return (map, lut);
+}
+
+fn bounds(map: &HashMap<Pos, bool>) -> (isize, isize, isize, isize) {
+ let mut minx: Option<isize> = None;
+ let mut maxx: Option<isize> = None;
+ let mut miny: Option<isize> = None;
+ let mut maxy: Option<isize> = None;
+
+ for (p,_) in map.iter() {
+ if minx.is_none() || p.x < minx.unwrap() { minx = Some(p.x); }
+ if maxx.is_none() || p.x > maxx.unwrap() { maxx = Some(p.x); }
+ if miny.is_none() || p.y < miny.unwrap() { miny = Some(p.y); }
+ if maxy.is_none() || p.y > maxy.unwrap() { maxy = Some(p.y); }
+ }
+
+ return (minx.unwrap(), maxx.unwrap(), miny.unwrap(), maxy.unwrap());
+}
+
+fn enhance(map: &HashMap<Pos,bool>, lut: &Vec<bool>,
+ default: bool) -> HashMap<Pos,bool> {
+ let mut nmap: HashMap<Pos, bool> = HashMap::new();
+
+ let (minx, maxx, miny, maxy) = bounds(map);
+
+ for y in miny-1..maxy+2 {
+ for x in minx-1..maxx+2 {
+ let mut idx: usize = 0;
+ for dy in -1..2 {
+ for dx in -1..2 {
+ let dp = Pos { x: x + dx, y: y + dy };
+ let res = map.get(&dp);
+ let bit: bool;
+ if res.is_some() {
+ bit = *res.unwrap();
+ } else {
+ bit = default;
+ }
+ idx = (idx << 1) | (bit as usize);
+ }
+ }
+ nmap.insert(Pos { x, y }, lut[idx]);
+ }
+ }
+
+ return nmap;
+}
+
+fn enhance_n(map_in: HashMap<Pos,bool>, lut: &Vec<bool>,
+ n: usize) -> HashMap<Pos,bool> {
+ let mut map = map_in;
+ let mut default = false;
+ for _ in 0..n {
+ map = enhance(&map, lut, default);
+ default = if default { lut[511] } else { lut[0] };
+ }
+ return map;
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let (map, lut) = parse_input(&aoc.input);
+ let map = enhance_n(map, &lut, 2);
+
+ let answer = map.iter().filter(|(_,&v)| v).count();
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("5617");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let (map, lut) = parse_input(&aoc.input);
+ let map = enhance_n(map, &lut, 50);
+
+ let answer = map.iter().filter(|(_,&v)| v).count();
+ aoc.answer = Some(format!("{}", answer));
+ // aoc.solution = "
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/20/test1 b/src/20/test1
@@ -0,0 +1,8 @@
+..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###
+
