# Advent of Code: Day 20 - Trench Map

@aoc2021 @programming clojure ~5 minutes read

With the scanners fully deployed (totally, yeah, totally), we now can compute the map of the trench. But when we get the image from the scanners, it looks like a random noise (I wonder why, perhaps because of the extremely convoluted positioning in the previous task?). So we need to enhance the image with a certain algorithm.

The algorithm consists of the string, that specifies how to enhance a particular image pixel. The example input consists of such string and an image:

``````..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#

#..#.
#....
##..#
..#..
..###
``````

To determine the value of the pixel we need to look at all pixels around this pixel and construct a binary number. For simplicity let’s replace `#` with `1` and `.` with `0`, and mark pixels that surround the middle one:

``````1  0  0  1  0
1 [0  0  0] 0
1 [1  0  0] 1
0 [0  1  0] 0
0  0  1  1  1
``````

This forms a binary number `000100010`, which is `34` in decimal. So, to enhance the current pixel, we need to take value from the enhancement string at this position, which happens to be `#` or `1`. We then repeat this for each pixel on the image. However, the image is actually infinite, and we need to process it as a whole.

This task looks like a cellular automaton once again, as the image basically grows between iterations, as some previously dark pixels will become light or dark, depending on the surroundings. Let’s start by reading the input. First, I’d like to transform the image itself to a table of coordinates as keys, and brightness as values:

``````user> (ns day20
(:require [clojure.string :as str]))
nil
day20> (defn img->coords [img]
(reduce-kv (fn [img y line]
(reduce-kv (fn [img x c]
(assoc img [x y] (if (= c \#) 1 0)))
img (vec line)))
(sorted-map)
(str/split img #"\n")))
#'day20/img->coords
day20> (img->coords "#..\n.#.\n..#")
{[0 0] 1,
[0 1] 0,
[0 2] 0,
[1 0] 0,
[1 1] 1,
[1 2] 0,
[2 0] 0,
[2 1] 0,
[2 2] 1}
``````

We’ll also parse the enhancement string as a vector of zeroes and ones:

``````day20> (defn read-input []
(let [[enh img] (-> "inputs/day20"
slurp
(str/split #"\n\n"))]
{:enhance (mapv #(if (= % \#) 1 0) enh)
:image (img->coords img)}))
``````

Now, when we have our image and enhancement string parsed, we can write a function that will enhance a given image. First, we need to write a function, that reads the pixel’s value and values of all surrounding pixels. It then computing an index in the enhancement string, and gets the enhancement value from that string:

``````day20> (defn enhancement [{:keys [image enhance]} [x y] default]
(nth enhance
(-> (for [y [(dec y) y (inc y)]
x [(dec x) x (inc x)]]
(get image [x y] default))
str/join
(Long/parseLong 2))))
#'day20/enhancement
``````

Note that I’m using an explicit default value, but let’s forget about it for now.

Our image is infinite, and we only have a portion of it, so we need to extend the image somehow. To do that we’ll just decrease the minimum image coordinate by `1` and increase the maximum by `1`. We’ll do it during the enhancement process, so the new image will become larger automatically:

``````day20> (defn enhance [{:keys [enhance image] :as img} step]
(let [points (keys image)
[min-x min-y] (first points)
[max-x max-y] (last points)
default (cond (zero? step) 0
(even? step) (peek enhance)
:else (first enhance))]
{:image (into
(sorted-map)
(for [x (range (dec min-x) (+ max-x 2))
y (range (dec min-y) (+ max-y 2))]
[[x y] (enhancement img [x y] default)]))
:enhance enhance}))
#'day20/enhance
``````

This `default` value is the bane of my existence. I’ve spent hours trying to understand why it is needed, and why at the first step it must be `0`. So I assume, that it is zero (or `.` in case of the task) on the first step is because we start with an empty image. Then we need to check what step we’re on and enhance using the first or the last value in the string. This is because when we expand the image new pixels are always zeroes, and thus will be converted to ones.

The final thing needed to do is to find all light pixels and count them - easy:

``````day20> (defn solve [n input]
(->> (reduce #(enhance %1 %2) input (range n))
:image
vals
(reduce +)))
#'day20/solve
5619
``````

Now, the craziest thing is that this solution will work the real input even without the `(zero? step)` case, but will not work for example one! Here:

``````day20> (defn enhance [{:keys [enhance image] :as img} step]
(let [points (keys image)
[min-x min-y] (first points)
[max-x max-y] (last points)
default (cond #_#_(zero? step) 0
(even? step) (peek enhance)
:else (first enhance))]
{:image (into
(sorted-map)
(for [x (range (dec min-x) (+ max-x 2))
y (range (dec min-y) (+ max-y 2))]
[[x y] (enhancement img [x y] default)]))
:enhance enhance}))
#'day20/enhance
5619
(let [[enh img] (-> "inputs/day20-example"
slurp
(str/split #"\n\n"))]
{:enhance (mapv #(if (= % \#) 1 0) enh)
:image (img->coords img)}))
#'day20/example-input
day20> (solve 2 example-input)
34
``````

It yields `34` instead of expected `35` but works for real input regardless. Part two is just the same as part one, just with `50` steps instead of two:

``````day20> (solve 50 example-input)
5209
day20> (solve 50 (read-input)) ; using the original function
20122
``````

Keep in mind that this is without the `(zero? step)`, so `5209` is the wrong answer for example input. But `20122` is the correct value for the real input. Consider the same but with original `enhance` function:

``````day20> (solve 2 example-input)
35
day20> (solve 50 example-input)
3351