Advent of Code: Day 13 - Transparent Origami

It seems I’ve celebrated early, and the cave story goes on still. Our submarine reached another volcanically active part of the cave! In order to progress, we need to use our onboard thermal camera, which, unfortunately, wasn’t activated ever since it was installed. To activate the camera we need to input a code, which can be found in the manual.

However, the code is protected from copying by being marked on transparent paper with dots. By folding this paper accordingly to the instructions, we will be able to decipher the code.

Our example puzzle input looks like this:

6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0

fold along y=7
fold along x=5

Let’s start by parsing it:

day12> (ns day13
         (:require [clojure.string :as str]
                   [aoc-commons :refer [parse-long]]))
nil
day13> (def example-input "
6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0

fold along y=7
fold along x=5")
#'day13/example-input
day13> (defn read-input []
         (let [lines (->> example-input
                          str/trim
                          str/split-lines)
               points (take-while seq lines)
               folds (rest (drop-while seq lines))]
           {:points (mapv #(mapv parse-long (str/split % #",")) points)
            :folds (mapv #(update (-> (str/replace % #"fold along\s+" "")
                                      (str/split #"="))
                                  1 parse-long) folds)}))
#'day13/read-input

Today the input parsing function is a bit more involved. We need to not only parse the points but the tasks as well. The resulting data structure simply holds the vector of points and a vector of actions:

day13> (read-input)
{:points
 [[6 10] [0 14] [9 10] [0 3]
  [10 4] [4 11] [6 0] [6 12]
  [4 1] [0 13] [10 12] [3 4]
  [3 0] [8 4] [1 10] [2 14]
  [8 10] [9 0]],
 :folds [["y" 7] ["x" 5]]}

Now, the task shows us that if we render these points to a grid, we’ll get something like this:

...#..#..#.
....#......
...........
#..........
...#....#.#
...........
...........
...........
...........
...........
.#....#.##.
....#......
......#...#
#..........
#.#........

Let’s write a render function, and see if that’s right. Luckily for us, we’ve already implemented this exact function several times before, in days 9 and 5, so we can reuse it with some small tweaks:

day13> (defn render [points]
         (let [x (inc (apply max (map first points)))
               y (inc (apply max (map second points)))
               field (into [] (repeat x (into [] (repeat y "."))))]
           (->> points
                (reduce (fn [field p] (assoc-in field p "#")) field)
                (apply map vector)
                (map str/join)
                (map (partial str ";; "))
                (str/join "\n")
                println)))
#'day13/render
day13> (render (:points (read-input)))
;; ...#..#..#.
;; ....#......
;; ...........
;; #..........
;; ...#....#.#
;; ...........
;; ...........
;; ...........
;; ...........
;; ...........
;; .#....#.##.
;; ....#......
;; ......#...#
;; #..........
;; #.#........
nil

That seems about right! Now, the task suggests that we need to fold this transparent paper once, producing the following transformation:

...#..#..#.      #.##..#..#.
....#......      #...#......
...........      ......#...#
#..........  =>  #...#......
...#....#.#      .#.#..#.###
...........      ...........
...........      ...........
--8<---8<--
...........
...........  ^
.#....#.##.  |
....#......  |
......#...#
#..........
#.#........

So essentially all coordinated below the line are flipped exactly above it. This seems not hard to calculate - we just need to subtract the point’s respecting coordinate from the fold coordinate, only if it is greater than the fold coordinate. Otherwise we return the same coordinate:

day13> (defn fold [point along coord]
         (case along
           "x" (let [[x y] point]
                 (if (> x coord)
                   [(- coord (- x coord)) y]
                   [x y]))
           "y" (let [[x y] point]
                 (if (> y coord)
                   [x (- coord (- y coord))]
                   [x y]))))
#'day13/fold
day13> (render (mapv #(fold % "y" 7) (:points (read-input))))
;; #.##..#..#.
;; #...#......
;; ......#...#
;; #...#......
;; .#.#..#.###
nil

Looks like in the example, so hopefully, we got everything right. The final transformation looks like this:

#.##.|#..#.       #####
#...#|.....       #...#
.....|#...#       #...#
#...#|.....  =>   #...#
.#.#.|#.###       #####
.....|.....       .....
.....|.....       .....
      <---

Let’s try folding it this way:

day13> (render (mapv #(fold % "x" 5) (mapv #(fold % "y" 7) (:points (read-input)))))
;; #####
;; #...#
;; #...#
;; #...#
;; #####
nil

Great! This shows that our algorithm behaves at least the same way as the one from the example.

The task for the first part is to only do the first fold, and count amount of unique points. Seems easy:

day13> (count (distinct (mapv #(fold % "y" 7) (:points (read-input)))))
17

For the example input, the correct answer is indeed 17. Let’s run this against the real input, but actually automate getting the first fold coordinate and axis:

day13> (defn part-1 [input]
         (let [{:keys [points folds]} input
               [along coord] (first folds)]
           (->> points
                (mapv #(fold % along coord))
                distinct
                count)))
#'day13/part-1
day13> (part-1 (read-input))
631

This is the correct answer! Let’s see what’s in the second part.

Part two

We’re asked to finish the rest of the folding, and the code should be represented as eight capital letters. But wait, there are no letters, in this transparent paper! I wonder if we’re required to render it?!

day13> (defn part-2 [input]
         (let [{:keys [points folds]} input]
           (->> folds
                (reduce (fn [paper [along coord]]
                          (mapv #(fold % along coord) paper)) points)
                render)))
#'day13/part-2
day13> (part-2 (read-input))
;; ####.####.#....####...##..##..###..####
;; #....#....#....#.......#.#..#.#..#.#...
;; ###..###..#....###.....#.#....#..#.###.
;; #....#....#....#.......#.#.##.###..#...
;; #....#....#....#....#..#.#..#.#.#..#...
;; ####.#....####.#.....##...###.#..#.#...
nil

No way! Are you kidding me!¹ So the code is EFLFJGRF!

Entering the code from above grants us the second gold star for this day. Thankfully, we’re no longer required to figure out how to properly display things on the seven-segment display!

Day 13 thoughts

This task wasn’t hard, but I found it quite fun still! Finally our rendering paid off and proven to be useful.

Funnily enough, I can easily imagine such kind of protection from a device. This was a huge pain in my childhood - my parents often bought games for Dendy a Nintendo Entertainment System clone that was (as everybody thought) the original game console. I’m not sure if this was exactly on Dendy, but I remember that we had black and white displays, and some games required to enter a code to play them, and the code was encrypted via some colorful pallet, and you we’re supposed to enter the code. And some games were bought without manuals, or boxes, which contained the code, thus becoming unplayable. So today’s puzzle brought back some warm memories about my childhood, which is really great! And hey, the half of the event is already over, and I wonder what’s coming next!

Hope this was interesting, and until tomorrow!

Obviously, I’m overreacting here - it was kinda obvious after seeing how points formed a rectangle. ↩︎