part1 (5117B)
1--- Day 20: Trench Map --- 2 3With the scanners fully deployed, you turn their attention to mapping the floor of the ocean trench. 4 5When you get back the image from the scanners, it seems to just be random noise. Perhaps you can 6combine an image enhancement algorithm and the input image (your puzzle input) to clean it up a 7little. 8 9For example: 10 11..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..## 12#..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.### 13.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#. 14.#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#..... 15.#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.. 16...####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#..... 17..##..####..#...#.#.#...##..#.#..###..#####........#..####......#..# 18 19#..#. 20#.... 21##..# 22..#.. 23..### 24 25The first section is the [1m[97mimage enhancement algorithm[0m. It is normally given on a single line, but it 26has been wrapped to multiple lines in this example for legibility. The second section is the 27[1m[97minput image[0m, a two-dimensional grid of [1m[97mlight pixels[0m (#) and [1m[97mdark pixels[0m (.). 28 29The image enhancement algorithm describes how to enhance an image by [1m[97msimultaneously[0m converting all 30pixels in the input image into an output image. Each pixel of the output image is determined by 31looking at a 3x3 square of pixels centered on the corresponding input image pixel. So, to determine 32the value of the pixel at (5,10) in the output image, nine pixels from the input image need to be 33considered: (4,9), (4,10), (4,11), (5,9), (5,10), (5,11), (6,9), (6,10), and (6,11). These nine 34input pixels are combined into a single binary number that is used as an index in the [1m[97mimage 35enhancement algorithm[0m string. 36 37For example, to determine the output pixel that corresponds to the very middle pixel of the input 38image, the nine pixels marked by [...] would need to be considered: 39 40# . . # . 41#[. . .]. 42#[# . .]# 43.[. # .]. 44. . # # # 45 46Starting from the top-left and reading across each row, these pixels are ..., then #.., then .#.; 47combining these forms ...#...#.. By turning dark pixels (.) into 0 and light pixels (#) into 1, the 48binary number 000100010 can be formed, which is 34 in decimal. 49 50The image enhancement algorithm string is exactly 512 characters long, enough to match every 51possible 9-bit binary number. The first few characters of the string (numbered starting from zero) 52are as follows: 53 540 10 20 30 [1m[97m34[0m 40 50 60 70 55| | | | [1m[97m|[0m | | | | 56..#.#..#####.#.#.#.###.##.....###.[1m[97m#[0m#.#..###.####..#####..#....#..#..##..## 57 58In the middle of this first group of characters, the character at index 34 can be found: #. So, the 59output pixel in the center of the output image should be #, a [1m[97mlight pixel[0m. 60 61This process can then be repeated to calculate every pixel of the output image. 62 63Through advances in imaging technology, the images being operated on here are [1m[97minfinite[0m in size. 64[1m[97mEvery[0m pixel of the infinite output image needs to be calculated exactly based on the relevant pixels 65of the input image. The small input image you have is only a small region of the actual infinite 66input image; the rest of the input image consists of dark pixels (.). For the purposes of the 67example, to save on space, only a portion of the infinite-sized input and output images will be 68shown. 69 70The starting input image, therefore, looks something like this, with more dark pixels (.) extending 71forever in every direction not shown here: 72 73............... 74............... 75............... 76............... 77............... 78.....#..#...... 79.....#......... 80.....##..#..... 81.......#....... 82.......###..... 83............... 84............... 85............... 86............... 87............... 88 89By applying the image enhancement algorithm to every pixel simultaneously, the following output 90image can be obtained: 91 92............... 93............... 94............... 95............... 96.....##.##..... 97....#..#.#..... 98....##.#..#.... 99....####..#.... 100.....#..##..... 101......##..#.... 102.......#.#..... 103............... 104............... 105............... 106............... 107 108Through further advances in imaging technology, the above output image can also be used as an input 109image! This allows it to be enhanced [1m[97ma second time[0m: 110 111............... 112............... 113............... 114..........#.... 115....#..#.#..... 116...#.#...###... 117...#...##.#.... 118...#.....#.#... 119....#.#####.... 120.....#.#####... 121......##.##.... 122.......###..... 123............... 124............... 125............... 126 127Truly incredible - now the small details are really starting to come through. After enhancing the 128original input image twice, [1m[97m35[0m pixels are lit. 129 130Start with the original input image and apply the image enhancement algorithm twice, being careful 131to account for the infinite size of the images. [1m[97mHow many pixels are lit in the resulting image?[0m 132 133