Advent of Code: Day 20 - Trench Map

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)}))
#'day20/read-input

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
day20> (solve 2 (read-input))
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
day20> (solve 2 (read-input))
5619
day20> (defn read-input []
         (let [[enh img] (-> "inputs/day20-example"
                             slurp
                             (str/split #"\n\n"))]
           {:enhance (mapv #(if (= % \#) 1 0) enh)
            :image (img->coords img)}))
#'day20/read-input
day20> (def example-input (read-input))
#'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
day20> (solve 50 (read-input))
20122

And I’ve tested this on several inputs - it works, and I don’t understand why, honestly.

Day 20 thoughts

While working on this puzzle on the first development iteration I wrote an algorithm that always used zeroes as extended values. It worked on the example input, and on the real input but only for part one! And when I’ve tested it on different inputs it didn’t work, so I mean, this task is extremely finicky. Especially since I got the right answer for part one with the wrong code on one input non-example, but it didn’t work for another.

Five days to go.