After struggling unsuccessfully with day 18 and skipping day 19 entirely, I was happy to get a win on today’s puzzle. (I’ll come back to 18 and 19 in the coming days.)

(ns aoc.2021.day.20
  (:require [clojure.string :as str]
            [hyperfiddle.rcf :as rcf]))

(rcf/enable!)

Day 20 involves grids. We’re given a binary “photo”, the bottom grid below, and an “enhancement algorithm”, the initial long binary string.

The image below is actually infinite; we assume that the infinite grid of surrounding pixels are all dark, i.e. ..

We repeatedly “enhance” our image pixel-by-pixel by first taking the 3-by-3 grid of pixels centered on our target pixel, concatenating these 3 rows, converting that into a binary number, and then using that number to index into our “enhancement algorithm”, which is just an array.

(The puzzle does a better job of explaining.)

(def t-input "..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##
#..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###
.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#.
.#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#.....
.#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#..
...####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.....
..##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#

#..#.
#....
##..#
..#..
..###")

(def input "#..###.##....#.#.#...#.#.#...##...####......##.##..###...#.####..#..#..#####..#.##.....#..#.###.##...#.#.....#...##.##.##...#####.#.#.#.##.###.#.##..#.##.##.#..#...####.#.#.....#..#.....###.#..#.#.#.#...#.###..#.###..##.#..#...##...####.#.........###..#.##.#..#.#...##.#.#.##.####.###....#####..###...##..#####..###..##..#.#.#..###.##.###..#.#######.####..#....###.##...#.####..#.#######...###...##.##.###...##..#.....#.###....#..#.#..###.#...#######.#...##..#.#..##.#...##.#..##.##..#...#.#.##.####........#..#.\n\n#.###...#..#...###..#..#.#....#####.#...#..#####...#.##...#....#.#.#..#.#.........#..##..#..#.#..#..\n###.#..##.#.##.#......#.###.##..###.#..#.###..####.#...#.....#...#.#.#..#######..#.#.##.#.#####..###\n.....##...#..#.#..#....###.##..######.#..#.###.###.###.#.#.##.####.#..#.#....##..#.##.#.........#.#.\n.#####...##...###..####.##.##.#..###.#.#..##..###...##.#..#...###.###.#.##.#.#....##.#.##.#.#..##.#.\n..#.....#####.#.###.###..#..##.##...#######.#...#...#.##.#.###....#.....####..#.....##.#####.###..##\n.###.#####.#..#...#.#....####.#..###.##...##..#..##..#........###..#..###....###.#.#..##..#...#.#..#\n##.##.#.##.#...###.###.###....#...##.#.#..#.##...#..#.#.#..####.#.###....#.##.#.##.#..#.#.....###.#.\n..#..#.###..##..#####.##.#.#..#..##...##..#..##..##....###..#.###..##..#.#..#..#..#.##.#..##.##.....\n###.#.#.#...#.#...#.###..#.###....##..#.##.###.....###.#..#..#####.##.#.##..#..##..###.###..###....#\n###......##.##..#.......####...##.#......#.#.....#..#.#.###........##.#.####.#.#.##...#..###.#.#....\n.##.##...#.#..#...#####.#####..#.......##..##.#.....####.###.#..#...##.#.###.#..##.##..####..#..##.#\n.#...#.#.#.#....###......##.....#...##...###...##....#..##.#..##.#.##.#...##.#.#.......##.#....#.#.#\n#..#....####...#.#.#.####...###.###.######..#.#...##.#...#.##......#.#...#.#.###.#.#.#..####..#.#...\n..#..##....##.##...###..###.#...#.#...#.##..#..#.#.####..#...#..#.#.##....#....#.##..#.#..#.#....#.#\n.#.#.########.##.#....##.#..###....#.#.###.#...##....###......##########.#..#.#.####...#..##...#..##\n#..##..#..#.#.#####..#####...#.###..####..##.#.#.####.#..#.#..####......#..#..##....##...#..###.#.##\n..###.#.#.##.##.#.#...###.#..#....####..###.##..##.#..##....###.#####.#..#...###.#.#..##...#...#####\n#.##.##.#..##.###.#.#.##..#...#...###..#..##.#..##....#####...#.#.#.##...####.##....#.#.##.#.##.#...\n##...##.#.###.####.##......##...#..#..#.....##..##..#.###.#..##.#.##.##..#..####.#########...##..#..\n.###..#.#..##..##..#..#...#.#..###.....#.#####..##.####...#.#...######.........####...........#..#.#\n#..#...##.#.##...##..##..........#..#...#..#..#.#..#.........######..####.#.##...##.##.##.....##..##\n#..##.#.###..##..####.#..######....#....####...##.#.#.#.#..#.##..#..#..###..#.#.#.#.#....#..##.#.#..\n.....##.......#.#.##.......##.##.#..###...###....##.###....##.#.####.###.##..##.#..##...###........#\n##..##....#.###..###.##.....##.#...##....##..#....#....###...#..#...###..#.####....#.......##.....##\n#..#..#.#..#...##.#.##.##...#.#.##..##..#.##..#.#...#...#.###.####..#....#####...#.###.##.####..#.##\n..##..##....####..#...###.############.##.#.##.####.#..#.##.#..##....#####..#.#####...###.#..#.##...\n...#.##.#.###.....###.#.#...##.#.#.##.##.#..##.#.##.#.##.#..#.###...#####.#..#.#..##...#.####..##..#\n#.#.###.####..#.#.###...##...###..#......#..##.....###.....#.##...##.#..#.#.####.#..#.#.#.##.####.##\n.###...####..##..#..###.#.#.#.##..##.##.#..#..##.##.#..#....#.#.###...#...#....##..##.#.##.######.##\n###.##....##.#.####..#########.....#.###...######.#.#....#...##...####.##.#.#.#####.....##....#.#.##\n######.#..#......#......###.##.#.###.#####..#.###.......####.#.###.#.#.##.##.....####...#..#.#.#####\n....##.#.#.#.##..##.###..#.###.##.##..###..#..#####.#####........#..##.#..##........#.##..#..#..#...\n.###..###.##.###.#.##.####.##.#.#...####.#..#.######.#.#####.#......#####.##..##.#.#.#.##.#..###.#.#\n#.##....###...#.....#..##.##.##.#..#.#..#.#.#...##..####.#..#.......####.###.#.####..#.#..##..##.#..\n##.#########..#....#....##...##.###..##.......####...####.#..#...###..##..##.#.#####..##.#....#..###\n..#..#####..####.####...#..#.#...####...#..###..#...#...########..#.#.#..###....####.....###.##...#.\n##.###.##..###.#.#..#..#.####...#.#...###..##...#.###.....##.#.#.#.##.#.#...###..###.###..#.#..#.#.#\n#.##..#.##..##.##...#.##.....##.#..#..###.##..##.#.##..#####..#####.###.##..###...#.#.#.##.##...###.\n..#.##.###.##.###.##.##.##......###..#.##.#..#...##.##.###..#..###.#......#.#..##..#.#..#####.......\n..##.#.###.###.###.##..####.#..####.#.##.#..#.######.#..##.#.#.#...#######.##..###..####.##..#..###.\n.####.##...#.#..#...##..#.#....#.#.##.##.#.#.#..##.#.#......####....###.####..#######.##.#....#.#.#.\n###.#.##.......#...###...##.#.##.##...#..#.#..###.####.#.###.#.#.##.#.#.###....#....#.#....#..#.#..#\n.#......#...#.#...#.##.#.###...#...##...#.###.#..#..#...#.#.#.###.##...###..##..###..#.#.##.#...####\n##.##...##..##...##..#...###...###..##.##.#......#..###.....##..#.#.#####...#######.#.####.#........\n#..#.....##..##.#.##..#.####......###..#...#.###.######..#.###..#.##..#.#....###..#..########..#.#..\n##.#..#......###.#.##....#.#...##...##.#..##......###..####.###.###.#.....#...##....#####.###..##..#\n###.......#.#.##....##..#.#..####.#.#..#.#..#...###.#.#.###.#####...####.#..#.##..#.....#.#.....#...\n.##.#..###....#.#####..###...##.#...####.###...#.######.#..###...#...#######.#.##.#....##.#.##...###\n#....#..#.#.#####..###.##..#.####..##.#.#....#.#.##.....##...#..#.###.#...#....#..#....###.#..#.###.\n#..#.#######.##..#.#..#.##..#######..####....#.#.###..###......###.####.#.....##..#.##.#.....###..##\n.###.#..##.......###..#.##....#......#.##..#.##..##.####.....###.#...#.#..##....#.#.###.###.#.#.##.#\n...#####.#.###....#..#.....###.#.....#..#..#..###...###.###..#....#####.#.###..#.....#..######....#.\n#..####...#...##..##.####..###.....##.###..#.###.#.#.##..#..#####...##.#...##.#..##.##.##.#....#....\n#...#.####......#.##..##.#.##.#.#####..#######.##.##.#.#.......#.#.#...##.####.###..#..#....#####.##\n..##...###...##.#..##..#...##.#.......#..#...#.#....#.###..##.#.###..##.#..####.######..#..#.##.#..#\n.##.....#.##..#..##......###.###.#......####..####.#.#.#...#..#..#..###..#..#...#.####.#.##..###.###\n........###.####...#...##..##..#.###..##..##.#...#..##.##....###.##.#.#..###.#.####....##..#.####.##\n.#..#...###.##.#....#.#.##...#..##..#.##...#...#.######.##.##.#####....##.###..####.....#.#..#...#.#\n#.#....##....#.######.##..#...##.##.#..#..#.#...#.##..##....###.#.#.#.#.#.######...##..###.#.##...#.\n..#....####.#.#############.####...#####......####.##.##.##..#..##.#....####..####.#..####.#.#..#.##\n#.##.#..#..####...#######....#...####.#..####....#####..##..#######..#.#....##.......#.#..#..####.#.\n#.#..#.#.#...####..#.....####.#...###...###.#.##.##.#.##.#........#.##..##.###.##.......#.###.....##\n..#.#.###.#.###.#.....###.#...##...#..#.....###.#..#..#..#...##..#..#.##..#..#.#.##..##.....#...##..\n..##.###.##.##..##.##.####..##..#.#.##.##.#...##...##....###..##...#..###.##.##.....###.#.##.##.#.##\n#.####...##.###..####...#.##.#####.#....#.#..#.....#......##..##.######...#....####...#..#.#..#..#.#\n.###..#.#.##.#.....###.#..#..#..#...####.#.####.#...###.##....###..##.##..#.##.#...#.#.#...####..##.\n##..##..####.####.#.##.#.#..####..##.######.###...##.##..#.#####.###..##...#.....##.##..#..###..####\n#..##.####.#.#.#####.....##.####..##..###...##...##...##....#.#.#...######...#...........##..###.##.\n...###.##...#.#.##...####...#..#.######.####.##.##.#....#.#.###..#.##...###.#...##.....##...###..##.\n.....#.###.##.....##.###.#.#..###..##..#..#.#.###..####......#.#####..##.####..###..##.#######.##.##\n#...#..#...##..#...####.##...#.#..##.......#.#...#.##.####.....#########...##....####.......#.###.##\n.#.....#.....####...#####..###.#.........##..##.##.#...#.#..#.#.#.#.#.###.#####..####..#......##.#.#\n#..#..###.#..#######.#..###.##..#..##.#..#..#.##.###.#..###.###..........#.###.#####.#.##.#.#...##..\n.##..###.#.#####.##.####.#.#..#..###....##.#.#..###.#.##..#.#..###..##.#.##.....#.#.#.#.#.####.#.##.\n..##.###...#....##.##.#####.##....#..##.######....###..#.#.##.###.#.......######.#..#..#..###.##....\n#.#..#.##.###...#..#####.##.#.###.#.###.......#######....#.####...####.##..#.#.###.##..#..#..###..#.\n#......#.##.##....##.#..#.#....##..#.###.....#.##...#.#..#...##.####......##..#.#.#...#...#.....#.##\n#....##.#.##.#.......#.##.#.###..#...###.#.###.##......#..#####..##.#..#....######.##.#..#...##..##.\n######.#.....#.#..##.##.....##.#..####.###..#.#.###....#..###..#..##.#..#.###..#.##...####....#.#...\n#.#..###..#####..#....#.#...##....###..##....#.##.#......#.#.###.....#.#.#..#.#..###.#....####......\n#..#.###.###.#.#.#..#.##..#.#.###.#...........#.#...#.##..#....##..#.#.##..##.#...##..#.##.##.#..#.#\n#.....#..#.#..##.##.######.#######....###.###...#####..#.....#..##.#.##.#.###...#..##.....###...#...\n#####.#.#..#.#.##..#.####.#...###.##.#....##.##.####.#...####.##.#...####..#..#.####.###....###.....\n#...#.......##.#...#..####...#.#..#.##.###..#.#.#.##...#.###......##....########..##.####.##.####.##\n#..#...##.###....##.##.#.##.##..#.#.#...###..#.#........###########.##..###.###.#..#....#.###....##.\n.#.#..##..##.##.#....##....###.##..###..#.###.#.###.#.###..######..###...####.....#.#...#.#.#..##.#.\n##...#..######.#.#...#.##....#...#..#..#.##.######.#..#..#.#...##..#..#...###..###.#.#......#....#.#\n.#.......#...#..#####.#####.#########..#......#..#.#.##.#.#.##.#.#.........####.##.#.###...#.##..#..\n..###.#.....###..#..#.#..#.#..####..###.....#.####.##...#.#..#.#.#.#.#.#..###..#......#..#####.#.#..\n#...#....###..####...#.##.#......###.#.##.###.#..###..##....##....#..#.....#...###.##.#......#..####\n#.####....######.####.#.####..#.#..#..#...####..#.#####..#..##.##..#.##...###...###.#.#..###.#.##.#.\n.####.###.#.##...###........#...##.#.#.######..#...##.###.##..#.#.######.#####..###....##...##.##...\n#.###.#.###..#.#.##..####.##..#...###...####..#..####.#.######.#####..#.##.##.##.##..#.#.##..#.##...\n.#.......#....##..#.#.##.#.#.##..###..#..##.....####.#...###....##.##......#....#.......#...##.##...\n.####.###..####.#.##..#.#.#..#...#..#.##.###..######.##.##.#.####.##.##.#..#..##..######.####..#..##\n#.###.##..#.#......##.#...#..#..#.##.#....##.....#......#..#...#..##....#.#####..####.#.#..#..##.##.\n#.#....#.#.#....#.#####.......#..#..#..#.##...#.#########..##..##...####.##..##.##.##..#.##...#.#.##\n.####....#..#.####.###.#.##########.###.#...#..##.##.#.####.##.###.##.#..#..#.##.##....###.#...##.#.\n...####.#.......#......#.######.#.##...###....####.##...##...##.#..#.##..##......#...####.#..##...##\n.#####...#....#....##.#.####....###..#.##...#.##..##..###.#.##.##.##...#.###..###.###...###...##.#..\n")

Some lift-and-shifted grid code:

(defn rows [grid] (count grid))
(defn cols [grid] (count (first grid)))

(defn coords [grid]
  (for [r (range (rows grid))
        c (range (cols grid))]
    [r c]))

(defn local-coords [coord]
  (let [ds (range -1 2)]
    (for [rd ds
          cd ds]
      (mapv + coord [rd cd]))))

Our enhancement algo will just be a vector of characters. For the grid, we’ll use a map indexed by [row column] coords; this will prove easier to deal with since the grid size expands every time we enhance the image.

We also return the dimension of our grid for convenience – we’ll need to make assumptions about the pixels beyond our grid later.

(defn parse-enhanceable-image [input]
  (let [[algo-s _ grid-s] (->> (str/split-lines input)
                               (partition-by #{""}))
        algo (->> algo-s
                  (reduce str)
                  (vec))
        grid (mapv vec grid-s)
        image (into {} (for [c (coords grid)]
                         [c (get-in grid c)]))
        dimension (count grid)]
    [algo image dimension]))

Our enhance-once algo takes all this info and an offset, which indicates how many pixels up/left we’ve gone (since we start with an image that begins at [0, 0] and then expand in all directions).

The key interesting part here, which I missed for a long time but was very satisfied to finally figure out, is that we can’t always assume that our infinite image is dark at the perimeter. It starts out dark, but it may be that our enhancement algorithm maps a grid of all-dark pixels to a light pixel, meaning that the perimeter of our image will flash entirely to light. It may also map a grid of all-light pixels to a dark pixel, in which case successive enhancements of the image will “flash” at the perimeters. (Of course this is the case for the actual input, but not for the example input.)

(defn enhance-once [algo image dimension offset]
  (let [top-ex (+ dimension offset)
        coords (for [r (range offset top-ex)
                     c (range offset top-ex)]
                 [r c])
        even-iteration (zero? (mod offset 2))
        dark-goes-to (first algo)
        light-goes-to (last algo)
        ; 🤢
        default (if even-iteration
                  dark-goes-to
                  (if (#{\#} dark-goes-to)
                    light-goes-to
                    \.))
        new-pixel (fn [coord]
                    (let [bit-str (->> (local-coords coord)
                                       (map (fn [coord]
                                              (or (get image coord)
                                                  default)))
                                       (map {\. 0 \# 1})
                                       (apply str))
                          idx (Integer/parseInt bit-str 2)]
                      (get algo idx)))
        enhanced (reduce (fn [acc coord]
                           (assoc acc coord (new-pixel coord)))
                         {}
                         coords)]
    enhanced))

A helper function for displaying our grid for debugging purposes:

(defn display-image [image dimension offset]
  (let [grid (vec (repeat dimension (vec (repeat dimension \.))))
        image (map (fn [[r c]]
                     [(- r offset) (- c offset)])
                   image)]
    (reduce (fn [grid coord]
              (assoc-in grid coord \#))
            grid
            image)))

Our infinitely-enhanced image (making janky use of reductions):

(defn enhance [algo image dimension]
  (let [offset 0]
    (->> (range)
         (reductions (fn [[image dimension offset] _]
                       (let [dimension (+ 2 dimension)
                             offset (dec offset)
                             image (enhance-once algo image dimension offset)]
                         [image dimension offset]))
                     [image dimension offset]))))

Now to solve:

(defn num-lit-after [input steps]
  (let [[algo image dimension] (parse-enhanceable-image input)
        enhanced-seq (enhance algo image dimension)
        [image _ _] (nth enhanced-seq steps)]
    (->> image
         (filter (comp #{\#} second))
         (count))))

(defn part-1 [input]
  (num-lit-after input 2))

(defn part-2 [input]
  (num-lit-after input 50))

(rcf/tests
  (part-1 t-input) := 35
  (part-1 input) := 5301
  (part-2 t-input) := 3351
  (time (part-2 input)) := 19492)  ; => 6727.967834 ms

⭐️⭐️