Advent of Code - 2021
This is a solution to Day 20 of Advent of Code 2021.
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 image enhancement algorithm. 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 input image, a two-dimensional grid of light pixels (
#) and dark pixels (.).The image enhancement algorithm describes how to enhance an image by simultaneously 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 image enhancement algorithm 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 (.) into0and light pixels (#) into1, the binary number000100010can be formed, which is34in 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 34 40 50 60 70 | | | | | | | | | ..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##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 light pixel.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 infinite in size. Every 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 a second time:
............... ............... ............... ..........#.... ....#..#.#..... ...#.#...###... ...#...##.#.... ...#.....#.#... ....#.#####.... .....#.#####... ......##.##.... .......###..... ............... ............... ...............Truly incredible - now the small details are really starting to come through. After enhancing the original input image twice, 35 pixels are lit.
Read input
We have another multisection input on our hands today. The first line, the algorithm is just a string so its transformer function can be str.
For the image though, we want to read it into an image dictionary where keys are (x, y) coordinates and values are # or . (the original input).
from utils import read_multisection_input
def transform_image(section):
lines = section.split('\n')
image = {}
for y in range(len(lines)):
width = len(lines[y])
for x in range(width):
image[(x,y)] = lines[y][x]
return image
VALUES = {
'#': 1,
'.': 0
}
algorithm, image = read_multisection_input(20, [str, transform_image])
Let's also create a debugging function for printing out our images.
Since I'm using a dictionary with points as keys (and since we'll expand beyond our starter image later), we can't assume the grid starts at (0, 0) (it'll actually start at (-enhance_count, -enhance_count) but we'll get to that later).
def print_image(image):
xs = [x for x, y in image]
ys = [y for x, y in image]
min_x, max_x = min(xs), max(xs)
min_y, max_y = min(ys), max(ys)
for y in range(min_x, max_y+1):
for x in range(min_y, max_x+1):
print(image.get((x,y), '.'), end="")
print()
Part 1
After the swarm of challenges from last week, this week was a really nice one for a change of pace. By this point, I'm very comfortable dealing with 2D coordinate systems.
Roughly half of my time spent on this puzzle went to accidentally copy-pasting the example input's algorithm string incorrectly and getting wrong results and trying to debug the code and not checking the algorithm string itself. Frustrating problem but at least my code was good and sound from the first try onwards.
We'll start by creating some helper functions to split up the code.
First, a very familiar looking function from previous days. Previously we've gotten all neighbors (diagonal and adjacent) and only adjacent neigbors but this time we want all the neighbors and the point itself. What a twist!
def get_points(point):
x,y = point
return [
(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)
]
A new value is calculated as the decimal value of binary number created by the point in question and the 8 values surrounding it.
For a simple 3x3 grid
.#.
#..
..#this would mean taking all the rows and concatenating them together to create a .#.#....# string that converts to binary as 010100001 which in decimal is 161.
Now, because we're dealing with infinite grids, every point outside our image will always be either . (starting value) or the result of the algorithm ran on the infinite values.
This means on the first time we've run the algorithm, we have a . in each of these spots. This means the binary value is 000000000 and translates to index 0 and turns all the infite spots into whatever is in algorithm[0] (so on step 1, we check for that).
After step 1, they are turned into whatever is in the algorithm[0] and since we only have max 2 values, we end up switching between these two.
def get_infinite(step, algorithm):
if step == 0:
return '.'
elif step % 2 == 0:
return algorithm[VALUES[algorithm[0]]]
else:
return algorithm[0]
def get_new_value(point, image, algorithm, step):
points = get_points(point)
binary = ''
for point in points:
binary += str(VALUES[image.get(point, get_infinite(step, algorithm))])
new_point = algorithm[int(binary, 2)]
return new_point
If your image was a fixed size image, we could just loop over every point in the image and calculate the new value, using '.' (or 0) for the bits that are outside the grid.
However, here we need to deal with infinite sized grids.
My solution is to always extend the image 1 to each direction (left, right, top, bottom) and calculate the new value.
def enhance(img, algorithm, step):
new_image = {}
max_x, max_y = max(x for x, y in img), max(y for x, y in img)
min_x, min_y = min(x for x, y in img), min(y for x,y in img)
for y in range(min_x-1, max_y+2):
for x in range(min_y-1, max_x+2):
new_image[(x,y)] = get_new_value((x,y), img, algorithm, step)
return new_image
To finally count the amount of pixels lit, I take all the values of the dictionary and count how many # there are.
def count_light_pixels(image):
return list(image.values()).count('#')
Start with the original input image and apply the image enhancement algorithm twice, being careful to account for the infinite size of the images. How many pixels are lit in the resulting image?
from copy import deepcopy
img = deepcopy(image)
img = enhance(image, algorithm, step=0)
img = enhance(img, algorithm, step=1)
result = count_light_pixels(img)
print(f'Solution: {result}')
assert(result) == 5203
Solution: 5203
Part 2
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 50 times, 3351 pixels are lit in the final output image.
Start again with the original input image and apply the image enhancement algorithm 50 times. How many pixels are lit in the resulting image?
Here we do the same but instead of twice, we run it 50 times.
from copy import deepcopy
img = deepcopy(image)
for step in range(50):
img = enhance(img, algorithm, step)
result = count_light_pixels(img)
print(f'Solution: {result}')
assert result == 18806
Solution: 18806