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 (.) 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 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.
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?
# Python imports
from itertools import combinations
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Optional, Set, Tuple
import numpy as np
# Paths to data
testpath = Path("day20_test.txt")
datapath = Path("day20_data.txt")
We parse the algorithm instructions into a dictionary, keyed by the value of the window in decimal, having values that are the output of the algorithm as 0 and 1 instead of . and # (this makes things easier to deal with, later).
The image data is parsed into a numpy array of 1 and 0 ints, rather than . and #, for the same reason.
def parse_imgdata(imgdata: List[str]) -> np.array:
"""Returns array of lit/unlit locations in image
:param imgdata: list of strings representing image data
"""
# Convert ./# to 0/1
newimg = []
for row in imgdata:
newimg.append([0 if _ == "." else 1 for _ in row])
return np.array(newimg)
def parse_algo(algostr: str) -> Dict[int,int]:
"""Returns dictionary of image enhancement algorithm
:param algostr: string defining image enhancement algorithm
"""
return {idx: 0 if output == "." else 1 for idx, output in enumerate(list(algostr))}
def load_input(fpath: Path) -> Tuple[Dict[int,int], np.array]:
"""Return the enhancement algorithm and start image
:param fpath: Path to data file
"""
with fpath.open("r") as ifh:
data = [_.strip() for _ in ifh.readlines()]
# Convert image enhancement algorithm string to dictionary
algodict = parse_algo(data[0])
# Convert initial image to set of lit locations
imgdata = parse_imgdata(data[2:])
return algodict, imgdata
Image update has a complication: the infinite field. If the algorithm sends windows of value 0 to 0 (as in the test example), then the infinite field remains 0. However, if the algorithm sends windows of value 0 to 1 (as the real example does!) then the infinite field flips from 0 to 1 each time the image is updated - which is presumably why we're given even numbers of updates to try.
To accommodate this, in a single update we pad the image array with the current value of the infinite field (inferred from the iteration number in update_image_n(). One row and column in each direction beyond the current image can be affected by the pixels in the current image, so we pad three rows and columns with the current value of the infinite field, update pixels for the area at least two pixels in from each edge, then trim the rows/columns corresponding to the infinite field.
def update_image(imgdata: np.array, algodict: Dict[int,int], fieldval: int=0) -> np.array:
"""Update the image with the algorithm
NOTE: the update is made, given an infinite field
with passed value. The image itself is padded with
3 rows/columns, before updating, and then the image
has two rows/columns unpadded after the update.
"""
# Pad image
padded = np.pad(imgdata, (3,3), "constant", constant_values=(fieldval,fieldval))
# Update image
updated = np.copy(padded)
rows, cols = updated.shape
for row in range(2, rows-2):
for col in range(2, cols-2):
window = padded[row-1:row+2, col-1:col+2].flatten()
val = int("".join([str(_) for _ in window]), 2)
enhanced = algodict[val]
updated[row, col] = enhanced
# Unpad image and return
unpadded = updated[2:-2, 2:-2]
return (unpadded)
For multiple updates, we keep track of the update number, and pass the appropriate infinite field value (0 for "even", 1 for "odd" iterations).
def update_image_n(imgdata: np.array, algodict: Dict[int,int], iterations: int=1) -> np.array:
"""Returns result of updating the image with the algorithm"""
updated = np.copy(imgdata)
for itern in range(iterations):
fieldval = 0 # default infinite field is zero
if itern % 2 and algodict[0] == 1:
# If the algorithm sends 0 -> 1, then on the "odd"
# itern values, the infinite field has value 1
fieldval = 1
updated = update_image(updated, algodict, fieldval)
return updated
Now we can try this on the test data:
algodict, imgdata = load_input(testpath)
updated = update_image_n(imgdata, algodict, 2)
# print(f"{algodict=}\n{updated=}")
print(f"{updated.sum()=}")
updated.sum()=35
And the puzzle data:
algodict, imgdata = load_input(datapath)
updated = update_image_n(imgdata, algodict, 2)
# print(f"{algodict=}\n{updated=}")
print(f"{updated.sum()=}")
updated.sum()=5225
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?
Our solution might be a bit slow over 50 iterations, but we can try it on the test data:
algodict, imgdata = load_input(testpath)
updated = update_image_n(imgdata, algodict, 50)
# print(f"{algodict=}\n{updated=}")
print(f"{updated.sum()=}")
updated.sum()=3351
And the puzzle data:
algodict, imgdata = load_input(datapath)
updated = update_image_n(imgdata, algodict, 50)
# print(f"{algodict=}\n{updated=}")
print(f"{updated.sum()=}")
updated.sum()=18131